Publications
2024

Expansion of higherdimensional cubical complexes with application to quantum locally testable codes(2024) arXiv.org. Abstract
We introduce a higherdimensional "cubical" chain complex and apply it to the design of quantum locally testable codes. Our cubical chain complex can be constructed for any dimension t, and in a precise sense generalizes the SipserSpielman construction of expander codes (case t=1) and the constructions by Dinur et. al and Panteleev and Kalachev of a square complex (case t=2), which have been applied to the design of classical locally testable and quantum lowdensity parity check codes respectively. For t=4 our construction gives a family of quantum locally testable codes conditional on a conjecture about robustness of fourtuples of random linear maps. These codes have linear dimension, inverse polylogarithmic relative distance and soundness, and polylogarithmicsize parity checks.Our complex can be built in a modular way from two ingredients. Firstly, the geometry (edges, faces, cubes, etc.) is provided by a set G of size N, together with pairwise commuting sets of actions A1,…,At on it. Secondly, the chain complex itself is obtained by associating local coefficient spaces based on codes, with each geometric object, and introducing local maps on those coefficient spaces.We bound the cycle and cocycle expansion of the chain complex. The assumptions we need are twofold: firstly, each Cayley graph Cay(G,Aj) needs to be a good (spectral) expander, and secondly, the families of codes and their duals both need to satisfy a form of robustness (that generalizes the condition of agreement testability for pairs of codes). While the first assumption is easy to satisfy, it is currently not known if the second can be achieved

(2024) Physical Review A. 109, 1, 012610. Abstract
A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits nonclassical behavior, under certain cryptographic assumptions. Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification or noninteractive challenges with inefficient (exponential time) verification. In this paper, we execute an efficient noninteractive test of quantumness on an iontrap quantum computer. Our results significantly exceed the bound for a classical device's success.
2023

(2023) STOC 2023  Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha B. & Servedio R. A.(eds.). p. 905918 Abstract
We construct a new explicit family of good quantum lowdensity paritycheck codes which additionally have linear time decoders. Our codes are based on a threeterm chain (2m× m)V →0 (2m)E →1 2F where V (Xchecks) are the vertices, E (qubits) are the edges, and F (Zchecks) are the squares of a leftright Cayley complex, and where the maps are defined based on a pair of constantsize random codes CA,CB:2m→2"where Δis the regularity of the underlying Cayley graphs. One of the main ingredients in the analysis is a proof of an essentiallyoptimal robustness property for the tensor product of two random codes.

(2023) Advances in Cryptology – CRYPTO 2023  43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings. Lysyanskaya A. & Handschuh H.(eds.). p. 162191 Abstract
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as [KCVY21, KLVY22], can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a buildingblock that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation. Certifying qubits was previously only known to be possible based on families of postquantum trapdoor clawfree functions (TCF) with an advanced “adaptive hardcore bit” property, which have only been constructed based on the hardness of the Learning with Errors problem [BCM+21] and recently isogenybased group actions [AMR23]. Our framework allows certification of qubits based only on the existence of postquantum TCF, without the adaptive hardcore bit property, or on quantum fully homomorphic encryption. These can be instantiated, for example, from Ring Learning with Errors. This has the potential to improve the efficiency of qubit certification and derived functionalities. On the technical side, we show that the quantum soundness of any such protocol can be reduced to proving a bound on a simple algorithmic task: informally, answering “two challenges simultaneously” in the protocol. Our reduction formalizes the intuition that these protocols demonstrate quantumness by leveraging the impossibility of rewinding a general quantum prover. This allows us to prove tight bounds on the quantum soundness of [KCVY21] and [KLVY22], showing that no quantum polynomialtime prover can succeed with probability larger than cos2π8≈0.853. Previously, only an upper bound on the success probability of classical provers, and a lower bound on the success probability of quantum provers, were known. We then extend this proof of quantum soundness to show that provers that approach the quantum soundness bound must perform almost anticommuting measurements. This certifies that the prover holds a qubit.

(2023) Nature Physics. Abstract
The ability to perform measurements in the middle of a quantum circuit is a powerful resource. It underlies a wide range of applications, from remote state preparation to quantum error correction. Here we apply midcircuit measurements for a particular task: demonstrating quantum computational advantage. The goal of such a demonstration is for a quantum device to perform a computational task that is infeasible for a classical device with comparable resources. In contrast to existing demonstrations, the distinguishing feature of our approach is that the classical verification process is efficient, both in asymptotic complexity and in practice. Furthermore, the classical hardness of performing the task is based upon wellestablished cryptographic assumptions. Protocols with these features are known as cryptographic proofs of quantumness. Using a trappedion quantum computer, we perform midcircuit measurements by spatially isolating portions of the ion chain via shuttling. This enables us to implement two interactive cryptographic proofs of quantumness, which when suitably scaled to larger systems, promise the efficient verification of quantum computational advantage. Our methods can be applied to a range of interactive quantum protocols.
2022

(2022) Advances in Cryptology – CRYPTO 2022. p. 195211 Abstract
We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are polylogarithmic in the runtime of the BQP computation (and polynomial in the security parameter). Our protocol is secure assuming the postquantum security of indistinguishability obfuscation (iO) and Learning with Errors (LWE). This is the first succinct argument for quantum computation in the plain model; prior work (ChiaChungYamakawa, TCC ’20) requires both a long common reference string and nonblackbox use of a hash function modeled as a random oracle.
At a technical level, we revisit the framework for constructing classically verifiable quantum computation (Mahadev, FOCS ’18). We give a selfcontained, modular proof of security for Mahadev’s protocol, which we believe is of independent interest. Our proof readily generalizes to a setting in which the verifier’s first message (which consists of many public keys) is compressed. Next, we formalize this notion of compressed public keys; we view the object as a generalization of constrained/programmable PRFs and instantiate it based on indistinguishability obfuscation. Finally, we compile the above protocol into a fully succinct argument using a (sufficiently composable) succinct argument of knowledge for NP. Using our framework, we achieve several additional results, includingSuccinct arguments for QMA (given multiple copies of the witness),Succinct noninteractive arguments for BQP (or QMA) in the quantum random oracle model, andSuccinct batch arguments for BQP (or QMA) assuming postquantum LWE (without iO). 
Experimental Implementation of an Efficient Test of Quantumness(2022) arxiv.org. Abstract
A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits nonclassical behavior, under certain cryptographic assumptions. Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or noninteractive challenges with inefficient (exponential time) verification. In this paper, we execute an efficient noninteractive test of quantumness on an iontrap quantum computer. Our results significantly exceed the bound for a classical device's success.

(2022) Quantum. 6, p. 791 Abstract
We establish a strong monogamyofentanglement property for subspace coset states, which are uniform superpositions of vectors in a linear subspace of \(\mathbb{F}_2^n\) to which has been applied a quantum onetime pad. This property was conjectured recently by [Coladangelo, Liu, Liu, and Zhandry, Crypto'21] and shown to have applications to unclonable decryption and copyprotection of pseudorandom functions. We present two proofs, one which directly follows the method of the original paper and the other which uses an observation from [Vidick and Zhang, Eurocrypt'20] to reduce the analysis to a simpler monogamy game based on BB'84 states. Both proofs ultimately rely on the same proof technique, introduced in [Tomamichel, Fehr, Kaniewski and Wehner, New Journal of Physics '13].

Interactive Protocols for ClassicallyVerifiable Quantum Advantage(2022) arxiv.org. Abstract
Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically simulating quantum mechanics; however, verifying the output is itself classically intractable. On the other hand, certain quantum algorithms (e.g. prime factorization via Shor's algorithm) are efficiently verifiable, but require more resources than what is available on nearterm devices. One way to bridge the gap between verifiability and implementation is to use "interactions" between a prover and a verifier. By leveraging cryptographic functions, such protocols enable the classical verifier to enforce consistency in a quantum prover's responses across multiple rounds of interaction. In this work, we demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer. We execute two complementary protocols  one based upon the learning with errors problem and another where the cryptographic construction implements a computational Bell test. To perform multiple rounds of interaction, we implement midcircuit measurements on a subset of trapped ion qubits, with subsequent coherent evolution. For both protocols, the performance exceeds the asymptotic bound for classical behavior; maintaining this fidelity at scale would conclusively demonstrate verifiable quantum advantage.

Efficient Certifiable Randomness from a Single Quantum Device(2022) arxiv.org. Abstract
Brakerski et. al [BCM+18] introduced the model of cryptographic testing of a single untrusted quantum device and gave a protocol for certifiable randomness generation. We use the leakage resilience properties of the Learning With Errors problem to address a key issue left open in previous work  the rate of generation of randomness. Our new protocol can certify Ω(n) fresh bits of randomness in constant rounds, where n is a parameter of the protocol and the total communication is O(n), thus achieving a nearly optimal rate. The proof that the output is statistically random is conceptually simple and technically elementary.

(2022) SIAM Journal on Computing. 51, 2, p. 214253 Abstract
We introduce a simple transformation on twoplayer nonlocal games, called “anchoring,” and prove an exponentialdecay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the FeigeKilian transformation [SIAM J. Comput., 30 (2000), pp. 324346], and has the property that if the quantum value of the original game G is v, then the quantum value of the anchored game G⊥ is 1−(1−α)2⋅(1−v), where α is a parameter of the transformation. In particular the anchored game has quantum value 1 if and only if the original game G has quantum value 1. This provides the first gap amplification technique for general twoplayer nonlocal games that achieves exponential decay of the quantum value.

(2022) 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). p. 586597 Abstract
A locally testable code is an errorcorrecting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of ReedMuller codes. The natural test for tensor codes, the axisparallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axisparallel line vs. point test as a twoprover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantumsoundness of the low individual degree test, which is an essential component of the MIP* = RE theorem. Our proof also generalizes to the infinitedimensional commutingoperator model of quantum provers.

(2022) Journal of Mathematical Physics. 63, 2, 022201. Abstract
The study of quantum correlation sets initiated by Tsirelson in the 1980s and originally motivated by questions in the foundations of quantum mechanics has more recently been tied to questions in quantum cryptography, complexity theory, operator space theory, group theory, and more. Synchronous correlation sets introduced by Paulsen et al. [J. Funct. Anal. 270, 21882222 (2016)] are a subclass of correlations that has proven particularly useful to study and arises naturally in applications. We show that any correlation that is almost synchronous, in a natural ℓ1 sense, arises from a state and measurement operators that are wellapproximated by a convex combination of projective measurements on a maximally entangled state. This extends a result of Paulsen et al. [J. Funct. Anal. 270, 21882222 (2016)] that applies to exactly synchronous correlations. Crucially, the quality of approximation is independent of the dimension of the Hilbert spaces or of the size of the correlation. Our result allows one to reduce the analysis of many classes of nonlocal games, including rigidity properties, to the case of strategies using maximally entangled states that are generally easier to manipulate.
2021

(2021) Communications of the ACM. 64, 11, p. 131138 Abstract
The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols.
In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomialtime verifier interacting with two allpowerful but noncommunicating provers sharing entanglement. The result resolves longstanding open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).

(2021) Journal of the ACM. 68, 5, p. 147 31. Abstract
We consider a new model for the testing of untrusted quantum devices, consisting of a single polynomial time bounded quantum device interacting with a classical polynomial time verifier. In this model, we propose solutions to two tasksa protocol for efficient classical verification that the untrusted device is "truly quantum" and a protocol for producing certifiable randomness from a single untrusted quantum device. Our solution relies on the existence of a new cryptographic primitive for constraining the power of an untrusted quantum device: postquantum secure trapdoor clawfree functions that must satisfy an adaptive hardcore bit property. We show how to construct this primitive based on the hardness of the learning with errors (LWE) problem.

(2021) Quantum. 5, 5, 544. Abstract
Selftesting is a method to characterise an arbitrary quantum system based only on its classical inputoutput correlations, and plays an important role in deviceindependent quantum information processing as well as quantum complexity theory. Prior works on selftesting require the assumption that the system's state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple noncommunicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed singlequbit measurements on it, up to a change of basis applied to both the device's state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break postquantum cryptography.


(2021) Communications in Mathematical Physics. 382, 1, p. 4986 Abstract
The generation of certifiable randomness is the most fundamental informationtheoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be verified classically in linear time, and is guaranteed to contain a polynomial number of certified random bits assuming that the device used to generate the output operated using a (classical or quantum) circuit of sublogarithmic depth. This assumption contrasts with the locality assumption used for randomness certification based on Bell inequality violation and more recent proposals for randomness certification based on computational assumptions. Furthermore, to demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our procedure is inspired by recent work of Bravyi et al. (Science 362(6412):308311, 2018), who introduced a relational problem that can be solved by a constantdepth quantum circuit, but provably cannot be solved by any classical circuit of sublogarithmic depth. We develop the discovery of Bravyi et al. into a framework for robust randomness expansion. Our results lead to a new proposal for a demonstrated quantum advantage that has some advantages compared to existing proposals. First, our proposal does not rest on any complexitytheoretic conjectures, but relies on the physical assumption that the adversarial device being tested implements a circuit of sublogarithmic depth. Second, success on our task can be easily verified in classical linear time. Finally, our task is more noisetolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we are able to allow a small constant additive error in total variation distance between the sampled and ideal distributions.

(2021) Advances in Cryptology – EUROCRYPT 2021  40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Canteaut A. & Standaert FX(eds.). p. 630660 Abstract
We define the notion of a proof of knowledge in the setting where the verifier is classical, but the prover is quantum, and where the witness that the prover holds is in general a quantum state. We establish simple properties of our definition, including that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an unbounded adversary, and that, under certain conditions on the parameters in our definition, a proof of knowledge protocol for a hardtoclone state can be used as a (destructive) quantum money verification protocol. In addition, we provide two examples of protocols (both inspired by privatekey classical verification protocols for quantum money schemes) which we can show to be proofs of quantum knowledge under our definition. In so doing, we introduce techniques for the analysis of such protocols which build on results from the literature on nonlocal games. Finally, we show that, under our definition, the verification protocol introduced by Mahadev (FOCS 2018) is a classical argument of quantum knowledge for QMA relations. In all cases, we construct an explicit quantum extractor that is able to produce a quantum witness given blackbox quantum (rewinding) access to the prover, the latter of which includes the ability to coherently execute the prover’s blackbox circuit controlled on a superposition of messages from the verifier.
2020

(2020) SIAM Journal on Computing. 49, 6, p. 14231427 Abstract
This note indicates an error in the proof of Theorem 3.1 in [T. Vidick, SIAM J. Comput., 45 (2016), pp. 10071063]. Due to an induction step in the soundness analysis not being carried out correctly, the analysis fails to prove the claimed result. The error invalidates the proofs of the main computational hardness results claimed in the paper. We discuss implications for subsequent works. In some cases results can be partially recovered by applying a weakened version of Theorem 3.1 shown in [Z. Ji et al., Quantum Soundness of the Classical Low Individual Degree Test, arXiv:2009.1298, 2020] subsequently to the discovery of the error. The validity of Theorem 3.1 as stated in the paper remains an open question.

(2020) Quantum. 4, p. 119 349. Abstract
We introduce a threeplayer nonlocal game, with a finite number of classical questions and answers, such that the optimal success probability of 1 in the game can only be achieved in the limit of strategies using arbitrarily highdimensional entangled states. Precisely, there exists a constant 0

Quantum soundness of the classical low individual degree test(2020) arxiv.org. Abstract
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as MIP=NEXP [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions of these tests which are sound against quantum provers have found increasing applications to the study of nonlocal games and the complexity class~MIP∗. The culmination of this line of work is the result MIP∗=RE [arXiv:2001.04383]. One of the key ingredients in the first reported proof of MIP∗=RE is a twoprover variant of the low degree test, initially shown to be sound against multiple quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently discovered in the latter result, invalidating the main result of [arXiv:1302.1242] as well as its use in subsequent works, including [arXiv:2001.04383]. We analyze a variant of the low degree test called the low individual degree test. Our main result is that the twoplayer version of this test is sound against quantum provers. This soundness result is sufficient to rederive several bounds on~MIP∗ that relied on [arXiv:1302.1242], including MIP∗=RE.

(2020) Advances in Cryptology – CRYPTO 2020. p. 799828 Abstract
A noninteractive zeroknowledge (NIZK) proof system for a language L∈NP allows a prover (who is provided with an instance x∈L, and a witness w for x) to compute a classical certificate π for the claim that x∈L such that π has the following properties: 1) π can be verified efficiently, and 2) π does not reveal any information about w, besides the fact that it exists (i.e. that x∈L). NIZK proof systems have recently been shown to exist for all languages in NP in the common reference string (CRS) model and under the learning with errors (LWE) assumption.
We initiate the study of NIZK arguments for languages in QMA. An argument system differs from a proof system in that the honest prover must be efficient, and that it is only sound against (quantum) polynomialtime provers. Our first main result is the following: if LWE is hard for quantum computers, then any language in QMA has an NIZK argument with preprocessing. The preprocessing in our argument system consists of (i) the generation of a CRS and (ii) a single (instanceindependent) quantum message from verifier to prover. The instancedependent phase of our argument system, meanwhile, involves only a single classical message from prover to verifier. Importantly, verification in our protocol is entirely classical, and the verifier needs not have quantum memory; its only quantum actions are in the preprocessing phase. NIZK proofs of (classical) knowledge are widely used in the construction of more advanced cryptographic protocols, and we expect the quantum analogue to likewise find a broad range of applications. In this respect, the fact that our protocol has an entirely classical verification phase is particularly appealing.
Our second contribution is to extend the notion of a classical proof of knowledge to the quantum setting. We introduce the notions of arguments and proofs of quantum knowledge (AoQK/PoQK), and we show that our noninteractive argument system satisfies the definition of an AoQK, which extends its domain of usefulness with respect to cryptographic applications. In particular, we explicitly construct an extractor which can recover a quantum witness from any prover who is successful in our protocol. We also show that any language in QMA has an (interactive) proof of quantum knowledge, again by exhibiting a particular proof system for all languages in QMA and constructing an extractor for it.

(2020) Geometric Aspects of Functional Analysis. p. 279299 Abstract
For all n >= 1, we give an explicit construction of m x m matrices A(1),...,A(n) with m = 2([n/2]) such that for any d and d x d matrices A(1)',..., A(n)' that satisfy
parallel to A(i)'  A(j)'parallel to(S1) = 2([n/2]1). This stands in contrast to the metric theory of commutative l(p) spaces, as it is known that for any p >= 1, any n points in l(p) embed exactly in l(p)(d) for d = n(n  1)/2.
Our proof is based on matrices derived from a representation of the Clifford algebra generated by n anticommuting Hermitian matrices that square to identity, and borrows ideas from the analysis of nonlocal games in quantum information theory. 
(2020) Quantum. 4, 266. Abstract
We show that every language in QMA admits a classicalverifier, quantumprover zeroknowledge argument system which is sound against quantum polynomialtime provers and zeroknowledge for classical (and quantum) polynomialtime verifiers. The protocol builds upon two recent results: a computational zeroknowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in QMA, with a classical verifier, introduced by Mahadev (FOCS 2018).

(2020) Bulletin (new series) of the American Mathematical Society. 57, 1, p. 3976 Abstract
Rapid technological advances point to a near future where engineered devices based on the laws of quantum mechanics are able to implement computations that can no longer be emulated on a classical computer. Once that stage is reached, will it be possible to verify the results of the quantum device?
Recently, Mahadev introduced a solution to the following problem: Is it possible to delegate a quantum computation to a quantum device in a way that the final outcome of the computation can be verified on a classical computer, given that the device may be faulty or adversarial and given only the ability to generate classical instructions and obtain classical readout information in return?
Mahadev's solution combines the framework of interactive proof systems from complexity theory with an ingenious use of classical cryptographic techniques to tie a "cryptographic leash" around the quantum device. In these notes I give a selfcontained introduction to her elegant solution, explaining the required concepts from complexity, quantum computing, and cryptography, and how they are brought together in Mahadev's protocol for classical verification of quantum computations.
2019

(2019) 2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019). p. 10241033 Abstract
We introduce a protocol between a classical polynomialtime verifier and a quantum polynomialtime prover that allows the verifier to securely delegate to the prover the preparation of certain singlequbit quantum states. The prover is unaware of which state he received and moreover, the verifier can check with high confidence whether the preparation was successful. The delegated preparation of singlequbit states is an elementary building block in many quantum cryptographic protocols. We expect our implementation of "random remote state preparation with verification", a functionality first defined in (Dunjko and Kashefi 2014), to be useful for removing the need for quantum communication in such protocols while keeping functionality. The main application that we detail is to a protocol for blind and verifiable delegated quantum computation (DQC) that builds on the work of (Fitzsimons and Kashefi 2018), who provided such a protocol with quantum communication. Recently, both blind and verifiable DQC were shown to be possible, under computational assumptions, with a classical polynomialtime client (Mahadev 2017, Mahadev 2018). Compared to the work of Mahadev, our protocol is more modular, applies to the measurementbased model of computation (instead of the Hamiltonian model) and is composable. Our proof of security builds on ideas introduced in (Brakerski et al. 2018).

(2019) Notices of the American Mathematical Society. 66, 10, p. 16181627 Abstract
Quantum mechanics and the theory of operator algebras have been intertwined since their origin. In the 1930s [20] vonNeumannlaidthefoundationsforthetheoryof(what are now known as) von Neumann algebras with the explicit goal of establishing Heisenberg’s matrix mechanics on a rigorous footing (quoting from the preface, in the translation by Beyer: “The object of this book is to present the new quantum mechanics in a unified representation which, so far as it is possible and useful, is mathematically rigorous”). Following the initial explorations of Murray and von Neumann, the new theory took on a life of its own, eventually leading to multiple applications unrelated to quantum mechanics, such as to free probability or noncommutative geometry.

(2019) PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19). p. 473480 Abstract
We show that any language solvable in nondeterministic time exp(exp(center dot center dot center dot exp(n))), where the number of iterated exponentials is an arbitrary function R(n), can be decided by a multiprover interactive proof system with a classical polynomialtime verifier and a constant number of quantum entangled provers, with completeness 1 and soundness 1  exp(C exp(center dot center dot center dot exp(n))), where the number of iterated exponentials is R(n)  1 and C > 0 is a universal constant. The result was previously known for R = 1 and R = 2; we obtain it for any timeconstructible function R.
The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC'17). As a separate consequence of this technique we obtain a different proof of Slofstra's recent result on the uncomputability of the entangled value of multiprover games (Forum of Mathematics, Pi 2019).
Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson's problem on the relation between the commuting operator and tensor product models for quantum correlations. 
(2019) SIAM Journal on Computing. 48, 1, p. 181225 Abstract
Deviceindependent security is the gold standard for quantum cryptography: not only is security based entirely on the laws of quantum mechanics, but it holds irrespective of any a priori assumptions on the quantum devices used in a protocol, making it particularly applicable in a quantumwary environment. While the existence of deviceindependent protocols for tasks such as randomness expansion and quantum key distribution has recently been established, the underlying proofs of security remain very challenging, yield rather poor key rates, and demand very high quality quantum devices, thus making them all but impossible to implement in practice. We introduce a technique for the analysis of deviceindependent cryptographic protocols. We provide a flexible protocol and give a security proof that provides quantitative bounds that are asymptotically tight, even in the presence of general quantum adversaries. At a high level our approach amounts to establishing a reduction to the scenario in which the untrusted device operates in an identical and independent way in each round of the protocol. This is achieved by leveraging the sequential nature of the protocol and makes use of a newly developed tool, the "entropy accumulation theorem" of Dupuis, Fawzi, and Renner [Entropy Accumulation, preprint, 2016]. As concrete applications we give simple and modular security proofs for deviceindependent quantum key distribution and randomness expansion protocols based on the CHSH inequality. For both tasks, we establish essentially optimal asymptotic key rates and noise tolerance. In view of recent experimental progress, which has culminated in loopholefree Bell tests, it is likely that these protocols can be practically implemented in the near future.

(2019) Advances in Cryptology – EUROCRYPT 2019  38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Rijmen V. & Ishai Y.(eds.). p. 247277 Abstract
The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two noncommunicating but entangled quantum provers. Our protocols have nearoptimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as O(glog g) for delegating a circuit of size g. This is in contrast to previous protocols, whose overhead in terms of resources employed, while polynomial, is far beyond what is feasible in practice. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit or its input. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem which allows a verifier to test that two entangled provers perform measurements specified by an arbitrary mqubit tensor product of singlequbit Clifford observables on their respective halves of m shared EPR pairs, with a robustness that is independent of m. Our twoprover classicalverifier delegation protocols are obtained by combining this rigidity theorem with a singleprover quantumverifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent.

(2019) Advances in Cryptology – EUROCRYPT 2019  38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Rijmen V. & Ishai Y.(eds.). p. 442469 Abstract
In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret X in order to establish a shared private key K by exchanging messages over an insecure communication channel. If the channel is authenticated the task can be solved in a single round of communication using a strong randomness extractor; choosing a quantumproof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, this simple solution is no longer secure. Nevertheless, Dodis and Wichs (STOC’09) showed that the problem can be solved in two rounds of communication using a nonmalleable extractor, a stronger pseudorandom construction than a strong extractor. We give the first construction of a nonmalleable extractor that is secure against quantum adversaries. The extractor is based on a construction by Li (FOCS’12), and is able to extract from source of minentropy rates larger than 1Â /Â 2. Combining this construction with a quantumproof variant of the reduction of Dodis and Wichs, due to Cohen and Vidick (unpublished) we obtain the first privacy amplification protocol secure against active quantum adversaries.
2018

(2018) 2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). p. 731742 Abstract
We show that given an explicit description of a multiplayer game, with a classical verifier and a constant number of players, it is QMAhard, under randomized reductions, to distinguish between the cases when the players have a strategy using entanglement that succeeds with probability 1 in the game, or when no such strategy succeeds with probability larger than 1/2. This proves the "games quantum PCP conjecture" of Fitzsimons and the second author (ITCS'15), albeit under randomized reductions.
The core component in our reduction is a construction of a family of twoplayer games for testing nqubit maximally entangled states. For any integer n >= 2, we give such a game in which questions from the verifier are O(log n) bits long, and answers are poly(log log n) bits long. We show that for any constant epsilon >= 0, any strategy that succeeds with probability at least 1  epsilon in the test must use a state that is within distance delta(epsilon) = O(epsilon(c)) from a state that is locally equivalent to a maximally entangled state on n qubits, for some universal constant c > 0. The construction is based on the classical planevspoint test for multivariate lowdegree polynomials of Raz and Safra (STOC'97). We extend the classical test to the quantum regime by executing independent copies of the test in the generalized Pauli X and Z bases over Fq, where q is a sufficiently large prime power, and combine the two through a test for the Pauli twisted commutation relations. Our main complexitytheoretic result is obtained by combining this family of games with techniques from the classical PCP literature. More specifically, we use constructions of PCPs of proximity introduced by BenSasson et al. (CCC'05), and crucially rely on a linear property of such PCPs. Another consequence of our results is a deterministic reduction from the games quantum PCP conjecture to a suitable formulation of the constraint satisfaction quantum PCP conjecture. 
(2018) Proceedings  59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. p. 320331 Abstract
We give a protocol for producing certifiable randomness from a single untrusted quantum device that is polynomialtime bounded. The randomness is certified to be statistically close to uniform from the point of view of any computationally unbounded quantum adversary, that may share entanglement with the quantum device. The protocol relies on the existence of postquantum secure trapdoor clawfree functions, and introduces a new primitive for constraining the power of an untrusted quantum device. We then show how to construct this primitive based on the hardness of the learning with errors (LWE) problem. The randomness protocol can also be used as the basis for an efficiently verifiable "quantum supremacy" proposal, thus answering an outstanding challenge in the field.

(2018) Quantum. 2, 92. Abstract
Bellinequality violations establish that two systems share some quantum entanglement. We give a simple test to certify that two systems share an asymptotically large amount of entanglement, n EPR states. The test is efficient: unlike earlier tests that play many games, in sequence or in parallel, our test requires only one or two CHSH games. One system is directed to play a CHSH game on a random specified qubit i, and the other is told to play games on qubits {i,j}, without knowing which index is i.
The test is robust: a success probability within delta of optimal guarantees distance O(n^{5/2} sqrt{delta}) from n EPR states. However, the test does not tolerate constant delta; it breaks down for delta = Omega~(1/sqrt{n}). We give an adversarial strategy that succeeds within delta of the optimum probability using only O~(delta^{2}) EPR states. 
(2018) Annales Henri Poincaré. 19, 10, p. 29793005 Abstract
We relate the amount of entanglement required to play linear system nonlocal games nearoptimally to the hyperlinear profile of finitely presented groups. By calculating the hyperlinear profile of a certain group, we give an example of a finite nonlocal game for which the amount of entanglement required to play optimally is at least O(1/ k), for some k > 0. Since this function approaches infinity as approaches zero, this provides a quantitative version of a theorem of the first author.

(2018) Quantum Information & Computation. 18, 78, p. 617631 Abstract
We characterize the amount of entanglement that is sufficient to play any XOR game nearoptimally. We show that for any XOR game G and epsilon > 0 there is an epsilonoptimal strategy for G using inverted right perpendicular epsilon(1)inverted right perpendicular ebits of entanglement, irrespective of the number of questions in the game. By considering the family of XOR games CHSH(n) introduced by Slofstra (Jour. Math. Phys. 2011), we show that this bound is nearly tight: for any epsilon > 0 there is an n = Theta(epsilon(1/5)) such that Omega(epsilon(1/5)) ebits are required for any strategy achieving bias that is at least a multiplicative factor (1  epsilon) from optimal in CHSH(n).
2017

(2017) Physical review. B. 96, 21, 214203. Abstract
The success of polynomialtime tensor network methods for computing ground states of certain quantum local Hamiltonians has recently been given a sound theoretical basis by Arad et al. [Math. Phys. 356, 65 (2017)]. The convergence proof, however, relies on "rigorous renormalization group" (RRG) techniques which differ fundamentally from existing algorithms. We introduce a practical adaptation of the RRG procedure which, while no longer theoretically guaranteed to converge, finds matrix product state ansatz approximations to the ground spaces and lowlying excited spectra of local Hamiltonians in realistic situations. In contrast to other schemes, RRG does not utilize variational methods on tensor networks. Rather, it operates on subsets of the system Hilbert space by constructing approximations to the global ground space in a treelike manner. We evaluate the algorithm numerically, finding similar performance to density matrix renormalization group (DMRG) in the case of a gapped nondegenerate Hamiltonian. Even in challenging situations of criticality, large groundstate degeneracy, or longrange entanglement, RRG remains able to identify candidate states having large overlap with ground and lowenergy eigenstates, outperforming DMRG in some cases.

(2017) Leibniz International Proceedings in Informatics, LIPIcs. Vol. 67. Abstract
In a recent work, Moshkovitz [FOCS '14] presented a transformation on twoplayer games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified twoplayer projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest. An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.

(2017) 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Vol. 67. Abstract
An ideal system of n qubits has 2^n dimensions. This exponential grants power, but also hinders characterizing the system's state and dynamics. We study a new problem: the qubits in a physical system might not be independent. They can "overlap," in the sense that an operation on one qubit slightly affects the others.
We show that allowing for slight overlaps, n qubits can fit in just polynomially many dimensions. (Defined in a natural way, all pairwise overlaps can be

(2017) Communications in Mathematical Physics. 356, 1, p. 65105 Abstract
One of the central challenges in the study of quantum manybody systems is the complexity of simulating them on a classical computer. A recent advance (Landau et al. in Nat Phys, 2015) gave a polynomial time algorithm to compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unsolved, including whether there exist efficient algorithms when the ground space is degenerate (and of polynomial dimension in the system size), or for the polynomially many lowest energy states, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm, based on a rigorously justified RG type transformation, for finding low energy states for 1D Hamiltonians acting on a chain of n particles. In the process we resolve some of the aforementioned open questions, including giving a polynomial time algorithm for poly(n) degenerate ground spaces and an n^{O(log}n) algorithm for the poly(n) lowest energy states (under a mild density condition). For these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustrationfree Hamiltonians the running time is O~ (nM(n) ) , where M(n) is the time required to multiply two n × n matrices.

(2017) Quantum. 1, Abstract
In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H. It was shown in [GS15] that this problem is QCMAcomplete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMAcomplete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.

(2017) STOC 2017  Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Hatami H., McKenzie P. & King V.(eds.). p. 10031015 Abstract
We introduce a simple twoplayer test which certifies that the players apply tensor products of Pauli σ_{X} and σ_{Z} observables on the tensor product of n EPR pairs. The test has constant robustness: any strategy achieving success probability within an additive ϵ of the optimal must be poly(ϵ)close, in the appropriate distance measure, to the honest nqubit strategy. The test involves 2nbit questions and 2bit answers. The key technical ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld. As applications of our result we give (i) the first robust selftest for n EPR pairs; (ii) a quantum multiprover interactive proof system for the local Hamiltonian problem with a constant number of provers and classical questions and answers, and a constant completenesssoundness gap independent of system size; (iii) a robust protocol for verifiable delegated quantum computation with a constant number of quantum polynomialtime provers sharing entanglement.

(2017) STOC 2017  Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Hatami H., McKenzie P. & King V.(eds.). p. 303316 Abstract
We study the parallel repetition of oneround games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate  in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored. We then introduce a simple transformation on games called anchoring, inspired in part by the FeigeKilian transformation, that turns any (multiplayer) game into an anchored game. Unlike the FeigeKilian transformation, our anchoring transformation is completeness preserving. We prove an exponentialdecay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture.

Parallel DIQKD from parallel repetition(2017) arxiv.org. Abstract
We give an arguably simpler and more direct proof of a recent result by Miller, Jain and Shi, who proved deviceindependent security of a protocol for quantum key distribution in which the devices can be used in parallel. Our proof combines existing results on immunization (Kempe et al., SICOMP 2011) and parallel repetition (Bavarian et al., STOC 2017) of entangled games.
2016

Privacy Amplification Against Active Quantum Adversaries(2016) arxiv.org. Abstract
Privacy amplification is the task by which two cooperating parties transform a shared weak secret, about which an eavesdropper may have side information, into a uniformly random string uncorrelated from the eavesdropper. Privacy amplification against passive adversaries, where it is assumed that the communication is over a public but authenticated channel, can be achieved in the presence of classical as well as quantum side information by a singlemessage protocol based on strong extractors.
In 2009 Dodis and Wichs devised a twomessage protocol to achieve privacy amplification against active adversaries, where the public communication channel is no longer assumed to be authenticated, through the use of a strengthening of strong extractors called nonmalleable extractors which they introduced. Dodis and Wichs only analyzed the case of classical side information.
We consider the task of privacy amplification against active adversaries with quantum side information. Our main result is showing that the DodisWichs protocol remains secure in this scenario provided its main building block, the nonmalleable extractor, satisfies a notion of quantumproof nonmalleability which we introduce. We show that an adaptation of a recent construction of nonmalleable extractors due to Chattopadhyay et al. is quantum proof, thereby providing the first protocol for privacy amplification that is secure against active quantum adversaries. Our protocol is quantitatively comparable to the nearoptimal protocols known in the classical setting. 
QuantumProof Extractors: Optimal up to Constant Factors(2016) arxiv.org. Abstract
We give the first construction of a family of quantumproof extractors that has optimal seed length dependence O(log(n/ε)) on the input length n and error ε. Our extractors support any minentropy k=Ω(logn+log1+α(1/ε)) and extract m=(1−α)k bits that are εclose to uniform, for any desired constant α>0. Previous constructions had a quadratically worse seed length or were restricted to very large input minentropy or very few output bits.
Our result is based on a generic reduction showing that any strong classical condenser is automatically quantumproof, with comparable parameters. The existence of such a reduction for extractors is a longstanding open question; here we give an affirmative answer for condensers. Once this reduction is established, to obtain our quantumproof extractors one only needs to consider high entropy sources. We construct quantumproof extractors with the desired parameters for such sources by extending a classical approach to extractor construction, based on the use of blocksources and sampling, to the quantum setting.
Our extractors can be used to obtain improved protocols for deviceindependent randomness expansion and for privacy amplification. 
(2016) Physical Review B. 93, 20, 205142. Abstract
The detectability lemma is a useful tool for probing the structure of gapped ground states of frustrationfree Hamiltonians of lattice spin models. The lemma provides an estimate on the error incurred by approximating the ground space projector with a product of local projectors. We provide a simpler proof for the detectability lemma which applies to an arbitrary ordering of the local projectors, and show that it is tight up to a constant factor. As an application, we show how the lemma can be combined with a strong converse by Gao to obtain local spectral gap amplification: We show that by coarse graining a local frustrationfree Hamiltonian with a spectral gap γ>0 to a length scale Oγ1/2, one gets a Hamiltonian with an Ω1 spectral gap.

(2016) Foundations and Trends in Theoretical Computer Science. 11, 12, p. 1215 Abstract
Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomialtime quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP^{∗} that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss noninteractive proofs and the complexity class QMA, singleprover quantum interactive proof systems and the complexity class QIP, statistical zeroknowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP^{∗}, and MIP^{∗}.

(2016) IEEE Transactions on Information Theory. 62, 3, p. 14401457 7377091. Abstract
In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game G with optimal winning probability 1  α and its repeated version G n (in which n games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this paper, the case of multiplayer nonsignaling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For completesupport games (games where all possible combinations of questions have nonzero probability to be asked) with any number of players, we prove a threshold theorem stating that the probability that nonsignaling players win more than a fraction 1α+β of the n games is exponentially small in nβ 2 for every 0 ≤ β ≤ α. For games with incomplete support, we derive a similar statement for a slightly modified form of repetition. The result is proved using a new technique based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.

(2016) Journal of Mathematical Physics. 57, 1, 015220. Abstract
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the applications of quantum mechanics to information theory, cryptography, and algorithms. Using the framework of nonlocal games, we relate measures of the nonlocality of quantum mechanics to certain norms in the Banach and operator space categories. We survey recent results that exploit this connection to derive large violations of Bell inequalities, study the complexity of the classical and quantum values of games and their relation to Grothendieck inequalities, and quantify the nonlocality of different classes of entangled states.

(2016) SIAM Journal on Computing. 45, 3, p. 10071063 Abstract
We show that for any ϵ >0 the problem of finding a factor (2ϵ) approximation to the entangled value of a threeplayer XOR game is NPhard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NPhard. These results are the first constantfactor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P≠NP. They can be thought of as an extension of Håstad's optimal hardness of approximation results for MAXE3LIN2 [J. ACM, 48 (2001), pp. 798859] to the entangledplayer setting. The key technical component of our work is a soundness analysis of a planevspoint lowdegree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick [Proceedings of the 53rd FOCS, IEEE, Piscataway, NJ, 2012, pp. 243252]. Our results demonstrate the possibility of efficient reductions between entangledplayer games and our techniques may lead to further hardness of approximation results.
2015

ConstantSoundness Interactive Proofs for Local Hamiltonians(2015) arxiv.org. Abstract
We give a quantum multiprover interactive proof system for the local Hamiltonian problem in which there is a constant number of provers, questions are classical of length polynomial in the number of qubits, and answers are of constant length. The main novelty of our protocol is that the gap between completeness and soundness is directly proportional to the promise gap on the (normalized) ground state energy of the Hamiltonian. This result can be interpreted as a concrete step towards a quantum PCP theorem giving entangledprover interactive proof systems for QMAcomplete problems.
The key ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld, where the function f:{0,1}n→{0,1} is replaced by a pair of functions X,Z:{0,1}n→Obsd(C), the set of ddimensional Hermitian matrices that square to identity. The test enforces that (i) each function is exactly linear, X(a)X(b)=X(a+b) and Z(a)Z(b)=Z(a+b), and (ii) the two functions are approximately complementary, X(a)Z(b)≈(−1)a⋅bZ(b)X(a). 
(2015) Quantum Information & Computation. 15, 1516, p. 13171332 Abstract
Quantum entanglement is known to provide a strong advantage in many twoparty distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple twoparty nonlocal game H, inspired by Lucien Hardy's paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1  O(dc) for some c ≥ 0:13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1  Ω (d2). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1  Ω (d2). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.

(2015) Nature Physics. 11, 7, p. 566569 Abstract
The density matrix renormalization group method has been extensively used to study the ground state of 1D manybody systems since its introduction two decades ago. In spite of its wide use, this heuristic method is known to fail in certain cases and no certifiably correct implementation is known, leaving researchers faced with an evergrowing toolbox of heuristics, none of which is guaranteed to succeed. Here we develop a polynomial time algorithm that provably finds the ground state of any 1D quantum system described by a gapped local Hamiltonian with constant groundstate energy. The algorithm is based on a framework that combines recently discovered structural features of gapped 1D systems with an efficient construction of a class of operators called approximate groundstate projections (AGSPs). The combination of these tools yields a method that is guaranteed to succeed in all 1D gapped systems. An AGSPcentric approach may help guide the search for algorithms for more general quantum systems, including for the central challenge of 2D systems, where even heuristic methods have had more limited success.

(2015) Computational Complexity. 24, 2, p. 201254 98. Abstract
We study the behavior of the entangled value of twoplayer oneround projection games under parallel repetition. We show that for any projection game G of entangled value (Formula presented.), the value of the kfold repetition of G goes to zero as (Formula presented.), for some universal constant (Formula presented.). If furthermore the constraint graph of G is expanding, we obtain the optimal c = 1. Previously exponential decay of the entangled value under parallel repetition was only known for the case of XOR and unique games. To prove the theorem, we extend an analytical framework introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call “vector quantum strategy” to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, the algorithm relies on a quantum analogue of Holenstein’s correlated sampling lemma which may be of independent interest. Our “quantum correlated sampling lemma” generalizes results of van Dam and Hayden on universal embezzlement to the following approximate scenario: two noncommunicating parties, given classical descriptions of bipartite states ψ⟩,φ⟩, respectively, such that ψ⟩≈φ⟩, are able to locally generate a joint entangled state Ψ⟩≈ψ⟩≈φ⟩ using an initial entangled state that is independent of their inputs.

(2015) Automata, Languages, and Programming  42nd International Colloquium, ICALP 2015, Proceedings. Speckmann B., Iwama K., Halldorsson M. M. & Kobayashi N.(eds.). p. 355366 Abstract
The class MIP∗ of promise problems that can be decided through an interactive proof system withmultiple entangled provers provides a complexitytheoretic framework for the exploration of the nonlocal properties of entanglement. Very little is known in terms of the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independently by Pironio et al. and Doherty et al. in 2006. This hierarchy converges to a value, the fieldtheoretic value, that is only known to coincide with the provers’ maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes’ embedding conjecture. No bounds on the rate of convergence are known. We introduce a rounding scheme for the hierarchy, establishing that any solution to its Nth level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by O(l^{2}/ √ N) in operator norm, where l is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of quantum multiprover interactive proof systems, called MIP∗ δ, in which the soundness property is required to hold against provers allowed to operate on the same Hilbert space as long as the commutator of operations performed by distinct provers has norm at most δ. Our rounding scheme implies the upper bound MIP∗ δ ⊆ DTIME(exp(exp(poly)/δ^{2})). In terms of lower bounds we establish that MIP*_{2−poly} contains NEXP with completeness 1 and soundness 1 − 2^{−poly}. We discuss connections with the mathematical literature on approximate commutation and applications to deviceindependent cryptography.

(2015) ITCS 2015  Proceedings of the 6th Innovations in Theoretical Computer Science. p. 103112 Abstract
We give a quantum interactive proof system for the local Hamiltonian problem on n qubits in which (i) the verifier has a single round of interaction with five entangled provers, (ii) the verifier sends a classical message on O(log n) bits to each prover, who replies with a constant number of qubits, and (iii) completeness and soundness are separated by an inverse polynomial in n. As the same class of proof systems, without entanglement between the provers, is included in QCMA, our result provides the first indication that quantum multiprover interactive proof systems with entangled provers may be strictly more powerful than unentangledprover interactive proof systems. A distinguishing feature of our protocol is that the completeness property requires honest provers to share a large entangled state, obtained as the encoding of the ground state of the local Hamiltonian via an errorcorrecting code. Our result can be interpreted as a first step towards a multiprover variant of the quantum PCP conjecture.
2014

(2014) Physical review letters. 113, 14, 140501. Abstract
Quantum cryptography promises levels of security that are impossible to replicate in a classical world. Can this security be guaranteed even when the quantum devices on which the protocol relies are untrusted? This central question dates back to the early 1990s when the challenge of achieving deviceindependent quantum key distribution was first formulated. We answer this challenge by rigorously proving the deviceindependent security of a slight variant of Ekert's original entanglementbased protocol against the most general (coherent) attacks. The resulting protocol is robust: While assuming only that the devices can be modeled by the laws of quantum mechanics and are spatially isolated from each other and from any adversary's laboratory, it achieves a linear key rate and tolerates a constant noise rate in the devices. In particular, the devices may have quantum memory and share arbitrary quantum correlations with the eavesdropper. The proof of security is based on a new quantitative understanding of the monogamous nature of quantum correlations in the context of a multiparty protocol.

(2014) Automata, Languages, and Programming  41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. p. 835846 Abstract
Quantum entanglement is known to provide a strong advantage in many twoparty distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple twoparty nonlocal game H, inspired by a paradox of Lucien Hardy. In our game each player has only two possible questions and can provide answers in a countable set. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1O(d^{c}) for some c ≥ 0.13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1  Ω(d^{2}). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1  Ω(d^{2}).

(2014) Proceedings of the 5th conference on innovations in theoretical computer science. p. 3536 Abstract
Quantum cryptography is based on the discovery that the laws of quantum mechanics allow levels of security that are impossible to replicate in a classical world [2, 8, 12]. Can such levels of security be guaranteed even when the quantum devices on which the protocol relies are untrusted? This fundamental question in quantum cryptography dates back to the early nineties when the challenge of achieving device independent quantum key distribution, or DIQKD, was first formulated [9]. We answer this challenge affirmatively by exhibiting a robust protocol for DIQKD and rigorously proving its security. The protocol achieves a linear key rate while tolerating a constant noise rate in the devices. The security proof assumes only that the devices can be modeled by the laws of quantum mechanics and are spatially isolated from each other and any adversary's laboratory. In particular, we emphasize that the devices may have quantum memory. All previous proofs of security relied either on the use of many independent pairs of devices [6, 4, 7], or on the absence of noise [10, 1].
To prove security for a DIQKD protocol it is necessary to establish at least that the generated key is truly random even in the presence of a quantum adversary. This is already a challenge, one that was recently resolved [14]. DIQKD is substantially harder, since now the protocol must also guarantee that the key is completely secret from the quantum adversary's point of view, and the entire protocol is robust against noise; this in spite of the substantial amounts of classical information leaked to the adversary throughout the protocol, as part of the error estimation and information reconciliation procedures.
Our proof of security builds upon a number of techniques, including randomness extractors that are secure against quantum storage [3] as well as ideas originating in the coding strategy used in the proof of the HolevoSchumacherWestmoreland theorem [5, 11] which we apply to bound correlations across multiple rounds in a way not unrelated to informationtheoretic proofs of the parallel repetition property for multiplayer games. Our main result can be understood as a new bound on monogamy [13] of entanglement in the type of complex scenario that arises in a key distribution protocol.
Precise statements of our results and detailed proofs can be found at arXiv:1210.1810. 
(2014) Proceedings of the 5th conference on innovations in theoretical computer science. p. 301302 Abstract
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMAcomplete, even for onedimensional Hamiltonians [1]. This means that we do not even expect that there is a subexponential size description of the ground state that allows efficient computation of local observables such as the energy. In sharp contrast, the heuristic density matrix renormalization group (DMRG) algorithm invented two decades ago [5] has been remarkably successful in practice on onedimensional problems. The situation is reminiscent of the unexplained success of the simplex algorithm before the advent of ellipsoid and interiorpoint methods. Is there a principled explanation for this, in the form of a large class of onedimensional Hamiltonians whose ground states can be provably efficiently approximated? Here we give such an algorithm for gapped onedimensional Hamiltonians: our algorithm outputs an (inversepolynomial) approximation to the ground state, expressed as a matrix product state (MPS) of polynomial bond dimension. The running time of the algorithm is polynomial in the number of qudits n and the approximation quality δ, for a fixed local dimension d and gap Δ > 0.
A key ingredient of our algorithm is a new construction of an operator called an approximate ground state projector (AGSP), a concept first introduced in [2] to derive an improved area law for gapped onedimensional systems [3]. For this purpose the AGSP has to be efficiently constructed; the particular AGSP we construct relies on matrixvalued Chernoff bounds [4]. Other ingredients of the algorithm include the use of convex programming, recently discovered structural features of gapped 1D quantum systems [2], and new techniques for manipulating and bounding the complexity of matrix product states. 
(2014) Journal of Operator Theory. 71, 2, p. 491506 Abstract
We provide alternative proofs of two recent Grothendieck theorems for jointly completely bounded bilinear forms, originally due to Pisier and Shlyakhtenko (Grothendieck's theorem for operator spaces, Invent. Math. 150(2002), 185217) and Haagerup and Musat (The EffrosRuan conjecture for bilinear forms on C*algebras, Invent. Math. 174(2008), 139163). Our proofs are elementary and are inspired by the socalled embezzlement states in quantum information theory. Moreover, our proofs lead to quantitative estimates.

(2014) Proceedings  IEEE 29th Conference on Computational Complexity, CCC 2014. p. 197208 Abstract
We study the behavior of the entangled value of twoplayer oneround projection games under parallel repetition. We show that for any projection game G of entangled value 1  epsilon = 1. Previously parallel repetition with an exponential decay in k was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call "vector quantum strategy" to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our "quantum correlated sampling lemma" generalizes results of van Dam and Hayden on universal embezzlement to the following approximate scenario: two isolated parties, given classical descriptions of arbitrary bipartite states vertical bar psi >, vertical bar phi > respectively such that vertical bar psi > approximate to vertical bar phi >, are able to locally generate a joint entangled state vertical bar Psi > approximate to vertical bar psi > approximate
2013

(2013) Communications in Mathematical Physics. 321, 1, p. 181207 Abstract
The study of quantummechanical violations of Bell inequalities is motivated by the investigation, and the eventual demonstration, of the nonlocal properties of entanglement. In recent years, Bell inequalities have found a fruitful reformulation using the language of multiplayer games originating from Computer Science. This paper studies the nonlocal properties of entanglement in the context of the simplest such games, called XOR games. When there are two players, it is well known that the maximum biasthe advantage over random playof players using entanglement can be at most a constant times greater than that of classical players. Recently, PérezGarcía et al. (Commun. Mathe. Phys. 279:455, 2008) showed that no such bound holds when there are three or more players: the use of entanglement can provide an unbounded advantage, and scale with the number of questions in the game. Their proof relies on nontrivial results from operator space theory, and gives a nonexplicit existence proof, leading to a game with a very large number of questions and only a loose control over the local dimension of the players' shared entanglement. We give a new, simple and explicit (though still probabilistic) construction of a family of threeplayer XOR games which achieve a large quantumclassical gap (QCgap). This QCgap is exponentially larger than the one given by PérezGarcía et. al. in terms of the size of the game, achieving a QCgap of order √N^{2} with N^{2} questions per player. In terms of the dimension of the entangled state required, we achieve the same (optimal) QCgap of √N^{2} for a state of local dimension N per player. Moreover, the optimal entangled strategy is very simple, involving observables defined by tensor products of the Pauli matrices.Additionally, we give the first upper bound on the maximal QCgap in terms of the number of questions per player, showing that our construction is only quadratically off in that respect. Our results rely on probabilistic estimates on the norm of random matrices and higherorder tensors which may be of independent interest.

(2013) SIGACT News. 44, 2, p. 4779 Abstract
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics and multipartite entanglement, topology and the socalled phenomenon of topological order, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theoryofCS audience.

Multipartite entanglement in XOR games(2013) Quantum Information and Computation. 13, 34, p. 334360 Abstract
We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of twoplayer XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pe ́rezGarci{dotless} ́a et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a threeplayer XOR game. We show that the multipartite entangled states that are most often seen in today's literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state localunitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the formPi for arbitrary amplitudes α_{i}. Our results have the following surprising consequence: classical threeplayer XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck's inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson's use of Grothendieck's inequality to bound the bias of twoplayer XOR games.

(2013) Approximation, Randomization, and Combinatorial Optimization. p. 468483 Abstract
A recent sequence of works, initially motivated by the study of the nonlocal properties of entanglement, demonstrate that a source of informationtheoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short random seed and the ability to ensure that two blackbox devices do not communicate (i.e. are nonsignaling). We call protocols achieving such certified amplification of a short random seed randomness amplifiers. We introduce a simple framework in which we initiate the systematic study of the possibilities and limitations of randomness amplifiers. Our main results include a new, improved analysis of a robust randomness amplifier with exponential expansion, as well as the first upper bounds on the maximum expansion achievable by a broad class of randomness amplifiers. In particular, we show that nonadaptive randomness amplifiers that are robust to noise cannot achieve more than doubly exponential expansion. Finally, we show that a wide class of protocols based on the use of the CHSH game can only lead to (singly) exponential expansion if adversarial devices are allowed the full power of nonsignaling strategies. Our upper bound results apply to all known nonadaptive randomness amplifier constructions to date.

(2013) Proceedings  2013 IEEE Conference on Computational Complexity, CCC 2013. p. 144155 Abstract
We introduce quantum XOR games, a model of twoplayer oneround games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck's inequality, we present an efficient algorithm that gives a constantfactor approximation to the best performance players can obtain in a given game, both in case they have no shared entanglement and in case they share unlimited entanglement. As a byproduct of the algorithm we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.

(2013) Theory of Quantum Computation, Communication, and Cryptography  7th Conference, TQC 2012, Revised Selected Papers. p. 4564 Abstract
We present an analysis of Wiesner's quantum money scheme, as well as some natural generalizations of it, based on semidefinite programming. For Wiesner's original scheme, it is determined that the optimal probability for a counterfeiter to create two copies of a bank note from one, where both copies pass the bank's test for validity, is (3/4)^{n} for n being the number of qubits used for each note. Generalizations in which other ensembles of states are substituted for the one considered by Wiesner are also discussed, including a scheme recently proposed by Pastawski, Yao, Jiang, Lukin, and Cirac, as well as schemes based on higher dimensional quantum systems. In addition, we introduce a variant of Wiesner's quantum money in which the verification protocol for bank notes involves only classical communication with the bank. We show that the optimal probability with which a counterfeiter can succeed in two independent verification attempts, given access to a single valid nqubit bank note, is (3/4+ √ 2/8)^{n}. We also analyze extensions of this variant to higherdimensional schemes.

(2013) STOC 2013  Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 7180 Abstract
The classical Grothendieck inequality has applications to the design of approximation algorithms for NPhard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constantfactor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.
2012

(2012) 2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). p. 243252 Abstract
We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multiprover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in nondeterministic exponential time. While Babai, Fortnow, and Lund (Computational Complexity 1991) proved the celebrated equality MIP = NEXP in the absence of entanglement, ever since the introduction of the class MIP* it was open whether shared entanglement between the provers could weaken or strengthen the computational power of multiprover interactive proofs. Our result shows that it does not weaken their computational power: MIP* contains MIP.
At the heart of our result is a proof that Babai, Fortnow, and Lund's multilinearity test is sound even in the presence of entanglement between the provers, and our analysis of this test could be of independent interest. As a byproduct we show that the correlations produced by any entangled strategy which succeeds in the multilinearity test with high probability can always be closely approximated using shared randomness alone. 
(2012) SIAM Journal on Computing. 41, 4, p. 915940 Abstract
Randomness extraction involves the processing of purely classical information and is therefore usually studied with in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the wellknown construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g., extract all the conditional (smooth) minentropy of the source using a seed of length polylogarithmic in the input, or only require the seed to be weakly random.

(2012) STOC '12  Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 6176 Abstract
We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n bits that are εclose in statistical distance from n uniformly distributed bits, starting from a seed of O(log n log 1/ε) uniform bits. The bits generated are certifiably random based only on a simple statistical test that can be performed by the user, and on the assumption that the devices do not communicate in the middle of each phase of the protocol. No other assumptions are placed on the devices' inner workings. A modified protocol uses a seed of O(log ^{3} n) uniformly random bits to generate n bits that are poly ^{1}(n)indistinguishable from uniform even from the point of view of a quantum adversary who may have had prior access to the devices, and may be entangled with them.

(2012) Journal of Functional Analysis. 262, 1, p. 19 Abstract
We prove that the Banach algebra formed by the space of compact operators on a Hilbert space endowed with the Schur product is a quotient of a uniform algebra (also known as a Qalgebra). Together with a similar result of PérezGarcía for the trace class, this completes the answer to a longstanding question of Varopoulos.
2011

Certifiable Quantum Dice  Or, testable exponential randomness expansion(2011) arxiv.org. Abstract
We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n bits of true randomness from a seed of O(log n) uniform bits. The bits generated are certifiably random based only on a simple statistical test that can be performed by the user, and on the assumption that the devices obey the nosignaling principle. No other assumptions are placed on the devices' inner workings. A modified protocol uses a seed of O(log^3 n) uniformly random bits to generate n bits of true randomness even conditioned on the state of a quantum adversary who may have had prior access to the devices, and may be entangled with them.

(2011) Physical review letters. 107, 3, 030402. Abstract
A central question in our understanding of the physical world is how our knowledge of the whole relates to our knowledge of the individual parts. One aspect of this question is the following: to what extent does ignorance about a whole preclude knowledge of at least one of its parts? Relying purely on classical intuition, one would certainly be inclined to conjecture that a strong ignorance of the whole cannot come without significant ignorance of at least one of its parts. Indeed, we show that this reasoning holds in any noncontextual (NC) hiddenvariable model (HV). Curiously, however, such a conjecture is false in quantum theory: we provide an explicit example where a large ignorance about the whole can coexist with an almost perfect knowledge of each of its parts. More specifically, we provide a simple informationtheoretic inequality satisfied in any NC HV, but which can be arbitrarily violated by quantum mechanics.

(2011) Physical Review A  Atomic, Molecular, and Optical Physics. 83, 5, 052310. Abstract
Recent numerical investigations suggest that the I3322 inequality, arguably the simplest extremal Bell inequality after the CHSH inequality, has a very rich structure in terms of the entangled states and measurements that maximally violate it. Here we show that for this inequality the maximally entangled state of any dimension achieves the same violation than just a single EPR pair. In contrast, stronger violations can be achieved using higher dimensional states which are less entangled. This shows that the maximally entangled state is not the most nonlocal resource, even when one restricts attention to the most simple extremal Bell inequalities.

(2011) SIAM Journal on Computing. 40, 3, p. 848877 Abstract
We establish the first hardness results for the problem of computing the value of oneround games played by a verifier and a team of provers who can share quantum entanglement. In particular, we show that it is NPhard to approximate within an inverse polynomial the value of a oneround game with (i) a quantum verifier and two entangled provers or (ii) a classical verifier and three entangled provers. Previously it was not even known if computing the value exactly is NPhard. We also describe a mathematical conjecture, which, if true, would imply hardness of approximation of entangledprover games to within a constant. Using our techniques we also show that every language in PSPACE has a twoprover oneround interactive proof system with perfect completeness and soundness 1  1/ poly even against entangled provers. We start our proof by describing two ways to modify classical multiprover games to make them resistant to entangled provers. We then show that a strategy for the modified game that uses entanglement can be "rounded" to one that does not. The results then follow from classical inapproximability bounds. Our work implies that, unless P = NP, the values of entangledprover games cannot be computed by semidefinite programs that are polynomial in the size of the verifier's system, a method that has been successful for more restricted quantum games.

(2011) Abstract
Entanglement is at the heart of quantum mechanics. The nonlocal correlations that can be obtained from spacetime separated measurements on an entangled state are a central feature which provably distinguish it from local theories. This dissertation studies entanglement through a computational viewpoint. We develop new insights into the complex nature of entanglement by studying its role in multiplayer games, in which cooperating, but noncommunicating, players interact with a referee in an attempt to win a prespecified game. On the one hand, the nonlocal correlations that entanglement allows may enable players using it to develop new colluding strategies, defeating previously secure protocols. On the other, the richness of this new resource may also be exploited in order to design new protocols, providing solutions to problems previously deemed impossible. We explore both aspects of this dual nature of entanglement, putting limits on its strength while at the same time showing how it can be put to profit to solve new computational problems. A major unresolved question on the computational complexity of multiplayer entangled games is the power of MIP*, the class of languages having entangled multiprover interactive proofs: how does it relate to its purely classical analogue MIP, which was completely characterized through the fundamental equation MIP=NEXP? Since the players may use entanglement to increase their odds at colluding against the verifier, MIP* could potentially be a much weaker class than MIP. Indeed, for a long time it has been an open question whether two entangled provers are more useful than a single prover. In this thesis we resolve this question by showing that the class of languages having multiprover interactive proofs with entangled provers is at least as large as its classical counterpart: NEXP is included in MIP*. At the heart of this result is an analysis of the multilinearity test of Babai, Fortnow, and Lund in the presence of entanglement. The fact that this test remains sound gives a systematic way for a verifier to impose strong limits on the ability of entangled provers to collude against the verifier. Gap amplification is a fundamental primitive in the study of classical multiplayer games. While sequential repetition of a game always decreases the prover's maximum success probability at an exponential rate, the fact that parallel repetition also achieves a gap amplification is a highly nontrivial fact. We show that gap amplification can be performed in parallel even in the presence of entanglement between the provers. We adapt a technique which was originally introduced by Feige and Kilian and results in a polynomial rate of amplification. The phenomenon of monogamy of entanglement states, in first approximation, that if two parties are maximally entangled then they cannot simultaneously be entangled with a third party. We use this phenomenon in two distinct results. In the first, we show that the bits generated in our randomnessexpansion protocol are certifiably random even from the point of view of a quantum adversary who may share prior entanglement with the provers. In addition, we prove the security against quantum adversaries of a randomnessefficient extractor construction originally due to Trevisan. This lets us transform the highentropy bits that are generated in our protocol into ones that are almost indistinguishable from uniform by any adversary. More generally, we show how the monogamy of entanglement can be exploited to design multiprover interactive proof systems that are partially entanglementresistant. Quantitative bounds on the monogamy of entanglement have generally been elusive, and the analysis of our protocol demonstrates such a bound in a new context. The nonlocal correlations that can be created by entangled players provide a statistical means of differentiating them from classical, unentangled players. This is the main idea behind Bell inequalities, the violation of which demonstrates the nonlocality of quantum mechanics. We show how this phenomenon may be exploited to design a protocol in which the bits produced by successful players necessarily contain a large quantity of fresh randomness. The presence of randomness is guaranteed irrespective of the provers' actual strategy, as long as the sole constraint of no signaling is respected. Hence a statistical certification for the presence of randomness, a feat easily seen to be impossible to achieve classically. In order to manipulate the random bits produced in our protocol, and make them useful in cryptography, we give the first proof of security of a polylogarithmic seed extractor secure against quantum adversaries. To achieve this we adapt the reconstruction paradigm originally introduced by Trevisan to the quantum setting. We study other ways in which entanglement may be used in interactive proof systems by also allowing a quantum interaction between the referee and the players. We show that, using entanglement, the class of QMIP* proof systems can be parallelized to only three rounds of interaction, and made publiccoin, a property that does not hold in the absence of entanglement between the provers.

(2011) STOC'11  Proceedings of the 43rd ACM Symposium on Theory of Computing. p. 353362 Abstract
We consider oneround games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz's celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. In the case where players share entanglement, the only previously known results are for special cases of games, and are based on techniques that seem inherently limited. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1. Our proof is inspired by a seminal result of Feige and Kilian in the context of classical twoprover oneround interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.