, arXiv:1804.00640.
</li>
A three-player coherent state embezzlement game
We introduce a three-player 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 high-dimensional entangled states. Precisely, there exists a constant 0<c<1 such that to succeed with probability 1−eps in the game it is necessary to use an entangled state of at least Omega(eps−c) qubits, and it is sufficient to use a state of at most O(eps−1) qubits. The game is based on the coherent state exchange game of Leung et al. (CJTCS 2013). In our game, the task of the quantum verifier is delegated to a third player by a classical referee. Our results complement those of Slofstra (arXiv:1703.08618) and Dykema et al. (arXiv:1709.05032), who obtained two-player games with similar (though quantitatively weaker) properties based on the representation theory of finitely presented groups and C*-algebras respectively.
Zhengfeng Ji, Debbie Leung, Thomas Vidick
Manuscript, arXiv:1802.04926.
Low-degree testing for quantum states
For any integer n≥2 we construct a one-round two-player game Gn, with communication that scales poly-logarithmically with n, having the following properties. First, there exists an entangled strategy that wins with probability 1 in Gn and in which the players' outcomes are determined by performing generalized Pauli measurements on their respective share of an n-qudit maximally entangled state, with qudits of local dimension q=polylog(n). Second, any strategy that succeeds with probability at least 1-eps in Gn must be within distance O((logn)1/d), for universal constants c,d≥1, of the perfect strategy, up to local isometries. This is an exponential improvement on the size of any previously known game certifying Ω(n) qudits of entanglement with comparable robustness guarantees. The construction of the game Gn is based on the classical test for low-degree polynomials of Raz and Safra, which we extend to the quantum regime. Combining this game with a variant of the sum-check protocol, we obtain the following consequences. First, we show that is QMA-hard, under randomized reductions, to approximate up to a constant factor the maximum acceptance probability of a multiround, multiplayer entangled game with polylog(n) bits of classical communication. Second, we give a quasipolynomial reduction from the multiplayer games quantum PCP conjecture to the constraint satisfaction quantum PCP conjecture. Third, we design a multiplayer protocol with polylogarithmic communication and constant completeness-soundness gap for deciding the minimal energy of a class of frustration-free nonlocal Hamiltonians up to inverse polynomial accuracy.
Anand Natarajan, Thomas Vidick
Presented at QIP'18. Proceedings of FOCS'18, arXiv:1801.03821.
Entanglement in non-local games and the hyperlinear profile of groups
We relate the amount of entanglement required to play linear-system non-local games near-optimally to the hyperlinear profile of finitely-presented groups. By calculating the hyperlinear profile of a certain group, we give an example of a finite non-local game for which the amount of entanglement required to play eps-optimally is at least Ω(1/eps^k), for some k>0. Since this function approaches infinity as eps approaches zero, this provides a quantitative version of a theorem of the first author.
William Slofstra, Thomas Vidick
Annales Henri Poincare (2018) (journal link). Presented at QIP'18, arXiv:1711.10676.
Practical device-independent quantum cryptography via entropy accumulation
Proving security of device-independent (DI) cryptographic protocols has been regarded to be a complex and tedious task. In this work we show that a newly developed tool, the entropy accumulation theorem of Dupuis et al., can be effectively applied to give fully general proofs of DI security. At a high level our technique 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 makes the proof much simpler and yields significantly better, essentially tight, quantitative results when considering general quantum adversaries, compared to what was known before. As concrete applications we give simple and modular security proofs for DI quantum key distribution and randomness expansion protocols based on the CHSH inequality. For both tasks we establish essentially optimal key rates and noise tolerance. As loophole-free Bell tests are finally being realised, our results considerably decrease the gap between theory and experiments, thereby marking an important step towards practical DI protocols and their implementations.
Rotem Arnon-Friedman, Frederic Dupuis, Omar Fawzi, Renato Renner, Thomas Vidick
Nature Communications 9:459(2018). Journal version of "Simple and tight device-independent security proofs", arXiv:1607.01797.
Two-player entangled games are NP-hard
We show that the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length is NP-hard to approximate to within constant factors. As a corollary, the inclusion of NEXP in MIP*, first shown in [IV12] with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test Raz and Safra (STOC'97) against two entangled provers.
Anand Natarajan, Thomas Vidick
This paper appeared in the proceedings of CCC'18. Due to a critical error in a paper on which the work relied, the result has been invalidated and the paper withdrawn. See Section 3 in this errata for details, arXiv:1710.03062.
A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries
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 quantum-proof extractor allows one to establish security against quantum adversaries. In the case that the channel is not authenticated, Dodis and Wichs (STOC'09) showed that the problem can be solved in two rounds of communication using a non-malleable extractor, a stronger pseudo-random construction than a strong extractor. We give the first construction of a non-malleable 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 min-entropy rates larger than 1/2. Combining this construction with a quantum-proof variant of the reduction of Dodis and Wichs, shown by Cohen and Vidick (unpublished), we obtain the first privacy amplification protocol secure against active quantum adversaries.
Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, Thomas Vidick
Proceedings of EUROCRYPT'19, arXiv:1710.00557.
Verifier-on-a-Leash new schemes for verifiable delegated quantum computation with quasilinear resources
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 non-communicating but entangled quantum provers. Our protocols have near-optimal 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(glogg) for delegating a circuit of size g. This is in contrast to previous protocols, which all require a prohibitively large polynomial overhead. 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 being delegated. 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 m-qubit tensor product of single-qubit Clifford observables on their respective halves of m shared EPR pairs, with a robustness that is independent of m. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent.
Andrea Coladangelo, Alex Grilo, Stacey Jeffery, Thomas Vidick
Presented at QIP'18. Proceedings of EUROCRYPT'19, arXiv:1708.07359.
Parallel DIQKD from parallel repetition
We give an arguably simpler and more direct proof of a recent result by Miller, Jain and Shi, who proved device-independent 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.
Thomas Vidick
Manuscript, arXiv:1703.08508.
Rigorous renormalization group method for ground space and low-energy states of local Hamiltonians
The practical success of polynomial-time tensor network methods for computing ground states of certain quantum local Hamiltonians has recently been given a sound theoretical basis by Arad, Landau, Vazirani, and Vidick. The convergence proof, however, relies on rigorous renormalization group (RRG) techniques which differ fundamentally from existing algorithms. We introduce an efficient implementation of the theoretical RRG procedure which finds MPS ansatz approximations to the ground spaces and low-lying excited spectra of local Hamiltonians in situations of practical interest. 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 tree-like manner. We evaluate the algorithm numerically, finding similar performance to DMRG in the case of a gapped nondegenerate Hamiltonian. Even in challenging situations of criticality, or large ground-state degeneracy, or long-range entanglement, RRG remains able to identify candidate states having large overlap with ground and low-energy eigenstates, outperforming DMRG in some cases.
Brenden Roberts, Olexei I. Motrunich, Thomas Vidick
Phys. Rev. B 96, 214203 (2017), arXiv:1703.01994.
Overlapping Qubits
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 <=eps in n^O(1/eps^2) dimensions.) Thus, even before considering issues like noise, a real system of n qubits might inherently lack any potential for exponential power. On the other hand, we also provide an efficient test to certify exponential dimensionality. Unfortunately, the test is sensitive to noise. It is important to devise more robust tests on the arrangements of qubits in quantum devices.
Rui Chao, Ben Reichardt, Chris Sutherland, Thomas Vidick
Proceedings of ITCS'17, arXiv:1701.01062.
Focus on device independent quantum information
Stefano Pironio, Valerio Scarani, Thomas Vidick
Closing editorial for New Journal of Physics special issue on device independence..
Robust self-testing of many-qubit states
We introduce a simple two-player 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 eps of the optimal must be poly(eps)-close, in the appropriate distance measure, to the honest n-qubit strategy. The test involves 2n-bit questions and 2-bit 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 self-test 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 completeness-soundness gap independent of system size; (iii) a robust protocol for delegated quantum computation.
Anand Natarajan, Thomas Vidick
Proceedings of STOC'17, arXiv:1610.03574.
QCMA hardness of ground space connectivity for commuting Hamiltonians
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 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H. It was shown in [Gharibian and Sikora, ICALP'15] that this problem is QCMA-complete 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 QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.
David Gosset, Jenish Mehta, Thomas Vidick
Quantum 1, 16 (2017), arXiv:1610.03582.
Quantum Proofs
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 polynomial-time 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 non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.
Thomas Vidick, John Watrous
NOW Foundations and Trends in Theoretical Computer Science, Vol. 11, No. 1-2 (2015) 1-215 (journal link), arXiv:1610.01664.
Test for a large amount of entanglement, using few measurements
Bell-inequality 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.
Rui Chao, Ben Reichardt, Chris Sutherland, Thomas Vidick
Quantum, arXiv:1610.00771.
Entanglement of approximate quantum strategies in XOR games
Dimiter Ostrev, Thomas Vidick
QIC Vol.18 No.7&8, pp. 0617-0631 (2018), arXiv:1609.01652.
A simple proof of Renner's exponential de Finetti theorem
We give a simple proof of the exponential de Finetti theorem due to Renner. Like Renner's proof, ours combines the post-selection de Finetti theorem, the Gentle Measurement lemma, and the Chernoff bound, but avoids virtually all calculations, including any use of the theory of types.
Thomas Vidick, Henry Yuen
Manuscript, arXiv:1608.04814.
Simple and Tight Device-Independent Security Proofs
Device-independent 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 quantum-wary environment. While the existence of device-independent 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 device-independent 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 device-independent 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 loophole-free Bell tests, it is likely that these protocols can be practically implemented in the near future.
Rotem Arnon-Friedman, Renato Renner, Thomas Vidick
SICOMP 48(1), 181–225 (link), arXiv:1607.01797.
A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem
We prove a moment majorization principle for matrix-valued functions with domain {-1,1}^m. The principle is an inequality between higher-order moments of a non-commutative multilinear polynomial with different random matrix ensemble inputs, where each variable has small influence and the variables are instantiated independently. This technical result can be interpreted as a noncommutative generalization of one of the two inequalities of the seminal invariance principle of Mossel, O'Donnell and Oleszkiewicz. Our main application is sharp Unique Games hardness for two versions of the noncommutative Grothendieck inequality. This generalizes a result of Raghavendra and Steurer who established hardness of approximation for the commutative Grothendieck inequality. A similar application was proven recently by Briet, Regev and Saket using different techniques.
Steven Heilman, Thomas Vidick
Submitted, arXiv:1603.0562.
Parallel repetition via fortification analytic view and the quantum case
In a recent work, Moshkovitz (FOCS '14) presented a transformation on two-player games called fortification, and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player 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.
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Proceedings of ITCS'17, arXiv:1603.05349.
Rigorous RG algorithms and area laws for low energy eigenstates in 1D
One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance of Landau et al. gave a polynomial time algorithm to actually compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unresolved, including whether there exist rigorous efficient algorithms when the ground space is degenerate (and poly(n) dimensional), or for the poly(n) lowest energy states for 1D systems, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm for finding low energy states for 1D systems, based on a rigorously justified RG type transformation. 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(logn) algorithm for the poly(n) lowest energy states for 1D systems (under a mild density condition). We note that 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 frustration-free Hamiltonians the running time is O(nM(n)), where M(n) is the time required to multiply two n×n matrices.
Itai Arad, Zeph Landau, Umesh Vazirani, Thomas Vidick
Communications in Mathematical Physics, 2017. Also appeared in the proceedings of ITCS'17, arXiv:1602.08828.
(video)
A simple proof of the detectability lemma and spectral gap amplification
The detectability lemma is a useful tool for probing the structure of gapped ground states of frustration-free 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 new, 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 frustration-free Hamiltonian with a spectral gap g>0 to a length scale O(g^{−1/2}), one gets an Hamiltonian with a constant spectral gap.
Anurag Anshu, Itai Arad, Thomas Vidick
Phys. Rev. B 93, 205142, arXiv:1602.01210.
Constant-Soundness Interactive Proofs for Local Hamiltonians
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 entangled-prover interactive proof systems for QMA-complete 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->Obs_d(C), the set of d-dimensional 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)^{ab}Z(b)X(a).
Anand Natarajan, Thomas Vidick
Manuscript, arXiv:1512.02090.
Survey on nonlocal games and operator space theory
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.
Carlos Palazuelos, Thomas Vidick
, arXiv:1512.00419.
Anchoring games for parallel repetition
Two major open problems regarding the parallel repetition of games are whether an analogue of Raz's parallel-repetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on both problems: we introduce a class of games we call anchored, and prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled-player settings. We introduce a simple transformation on games called anchoring and show that this transformation turns any game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness-amplification technique in both the classical multiplayer and quantum settings.
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Proceedings of STOC'17. Also presented at QIP'16, arXiv:1509.07466.
Interactive proofs with approximately commuting provers
The class MIP* of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic 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 field-theoretic 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 N-th 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^(1/2))$ 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*(delta), 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 delta. Our rounding scheme implies an upper bound of DTIME(exp(exp(poly)/delta^2)) on MIP*(delta). In terms of lower bounds we establish that MIP*(exp(-poly)) contains NEXP with completeness 1 and soundness 1-exp(-poly). We discuss connections with the mathematical literature on approximate commutation and applications to device-independent cryptography.
Matthew Coudron, Thomas Vidick
Presented at QIP'16. Proceedings of ICALP'15, arXiv:1510.00102.
Non-signalling parallel repetition using de Finetti reductions
In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game G with optimal winning probability 1-a 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 work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction 1-a+b of the n games is exponentially small in nb^2, for every 0<=b<=a. 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.
Rotem Arnon-Friedman, Renato Renner, Thomas Vidick
IEEE Transactions on Information Theory, 2014, arXiv:1411.1582.
A multiprover interactive proof system for the local Hamiltonian problem
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 reply 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 unentangled-prover 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 error-correcting code. Our result can be interpreted as a first step towards a multiprover variant of the quantum PCP conjecture.
Joseph Fitzsimons, Thomas Vidick
Proceedings of ITCS'15, arXiv:1409.026.
Unbounded entanglement can be needed to achieve the optimal success probability
Quantum entanglement is known to provide a strong advantage in many two-party 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 two-party nonlocal game H, inspired by 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(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).
Laura Mancinska, Thomas Vidick
Proceedings of ICALP'14. Journal version to appear in QIC., arXiv:1402.4145.
A parallel repetition theorem for entangled projection games
We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game G of entangled value 1-eps < 1, the value of the k-fold repetition of G goes to zero as O(poly(1-eps)), for some universal constant c > 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.
Irit Dinur, David Steurer, Thomas Vidick
Presented at QIP'14. Proceedings of CCC'14, arXiv:1310.4113.
The Quantum PCP Conjecture
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, the global nature of entanglement and its topological properties, 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 theory-of-CS audience.
Dorit Aharonov, Itai Arad, Thomas Vidick
A version of the survey appeared in the complexity column of SIGACT News. See also a related blog post, arXiv:1309.7495.
A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.
Zeph Landau, Umesh Vazirani, Thomas Vidick
Proceedings of ITCS'14. Journal version in Nature Physics 11, 566-569 (2015), arXiv:1307.5143.
(video)
Robust Randomness Amplifiers, Upper and Lower Bounds
A recent sequence of works, initially motivated by the study of the nonlocal properties of entanglement, demonstrate that a source of information-theoretically 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 black-box devices do not communicate (i.e. are non-signaling). 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 non-adaptive 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 non-signaling strategies. Our upper bound results apply to all known non-adaptive randomness amplifier constructions to date.
Matthew Coudron, Thomas Vidick, Henry Yuen
Proceedings of RANDOM'13, arXiv:1305.6626.
Three-player entangled XOR games are NP-hard to approximate
We show that for any eps>0 the problem of finding a factor (2-eps) approximation to the entangled value of a three-player XOR game is NP-hard. Equivalently, the problem of approximating the largest possible quantum violation of a tripartite Bell correlation inequality to within any multiplicative constant is NP-hard. These results are the first constant-factor hardness of approximation results for entangled games or quantum violations of Bell inequalities shown under the sole assumption that P
eq NP. They can be thought of as an extension of Hastad's optimal hardness of approximation results for MAX-E3-LIN2 (JACM'01) to the entangled-player setting. The key technical component of our work is a soundness analysis of a point-vs-plane low-degree test against entangled players. This extends and simplifies the analysis of the multilinearity test by Ito and Vidick (FOCS'12). Our results demonstrate the possibility for efficient reductions between entangled-player games and our techniques may lead to further hardness of approximation results.
Thomas Vidick
This paper appeared in the proceedings of FOCS'13 and in SICOMP. Due to a mistake in the proof of the main result, the paper has been withdrawn. See the erratum for details.
Efficient rounding for the noncommutative Grothendieck inequality
The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard 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 constant-factor 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.
Assaf Naor, Oded Regev, Thomas Vidick
Proceedings of STOC'13., arXiv:1210.7656.
Fully device independent quantum key distribution
The laws of quantum mechanics allow unconditionally secure key distribution protocols. Nevertheless, security proofs of traditional quantum key distribution (QKD) protocols rely on a crucial assumption, the trustworthiness of the quantum devices used in the protocol. In device-independent QKD, even this last assumption is relaxed: the devices used in the protocol may have been adversarially prepared, and there is no a priori guarantee that they perform according to specification. Proving security in this setting had been a central open problem in quantum cryptography. We give the first device-independent proof of security of a protocol for quantum key distribution that guarantees the extraction of a linear amount of key even when the devices are subject to a constant rate of noise. Our only assumptions are that the laboratories in which each party holds his or her own device are spatially isolated, and that both devices, as well as the eavesdropper, are bound by the laws of quantum mechanics. All previous proofs of security relied either on the use of many independent pairs of devices, or on the absence of noise.
Umesh Vazirani, Thomas Vidick
Plenary talk at QIP'13. Proceedings of ITCS'14. Journal version in Phys. Rev. Lett. 113, 140501 (2014). See the erratum, arXiv:1210.181.
(video)
Quantum XOR games
We introduce quantum XOR games, a model of two-player one-round 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 constant-factor 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.
Oded Regev, Thomas Vidick
Presented at QIP'13. Proceedings of CCC'13, arXiv:1207.4939.
A multi-prover interactive proof for NEXP sound against entangled provers
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 multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic 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 multi-prover 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.
Tsuyoshi Ito, Thomas Vidick
Appeared in FOCS'12, co-winner of the FOCS 2012 Best Paper Award. Invited for a plenary talk at QIP'13., arXiv:1207.055.
(video)
A concentration inequality for the overlap of a vector on a large set, with application to communication complexity
Given two sets A,B in Rn, a measure of their correlation is given by the expected squared inner product between a random x in A and a random y in B. We prove an inequality showing that no two sets of large enough Gaussian measure (at least e^{-delta n} for some constant delta >0) can have correlation substantially lower than would two random sets of the same size. Our proof is based on a concentration inequality for the overlap of a random Gaussian vector on a large set. As an application, we show how our result can be combined with the partition bound of Jain and Klauck to give a simpler proof of a recent linear lower bound on the randomized communication complexity of the Gap-Hamming-Distance problem due to Chakrabarti and Regev.
Thomas Vidick
Chicago Journal of Theoretical Computer Science, 2012 (link).
Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms
We provide alternative proofs of two recent Grothendieck theorems for jointly completely bounded bilinear forms, originally due to Pisier and Shlyakhtenko (Invent. Math. 2002) and Haagerup and Musat (Invent. Math. 2008). Our proofs are elementary and are inspired by the so-called embezzlement states in quantum information theory. Moreover, our proofs lead to quantitative estimates.
Oded Regev, Thomas Vidick
Journal of Operator Theory 71(2), pp.491-506, Spring 2014 (link)., arXiv:1206.4025.
Optimal counterfeiting attacks and generalizations for Wiesner's quantum money
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 n-qubit bank note, is (3/4+sqrt(2)/8)^n. We also analyze extensions of this variant to higher-dimensional schemes.
Abel Molina, Thomas Vidick, John Watrous
Proceedings of TQC'12, Lecture Notes in Computer Science Volume 7582 (2013)., arXiv:1202.401.
All Schatten spaces endowed with the Schur product are Q-algebras
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 Q-algebra). Together with a similar result of Pérez-García for the trace class, this completes the answer to a long-standing question of Varopoulos.
Jop Briet, Harry Buhrman, Troy Lee, Thomas Vidick
Journal of Functional Analysis, 262(1), 2012..
Parallel Repetition of Entangled Games
We consider one-round 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 two-prover one-round interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.
Julia Kempe, Thomas Vidick
Appeared in STOC'11 and as a featured talk at QIP'11, arXiv:1012.4728.
Certifiable quantum dice - Or, exponential randomness expansion
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 no-signaling 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.
Umesh Vazirani, Thomas Vidick
Appeared in STOC'12. Shorter version published in a special theme issue on The foundations of computation, physics and mentality the Turing legacy of Phil. Trans. R. Soc. A (2012) 370, 3432-3448, arXiv:1111.6054.
Explicit lower and upper bounds on the entangled value of multiplayer XOR games
XOR games are the simplest model in which the nonlocal properties of entanglement manifest themselves. When there are two players, it is well known that the bias --- the maximum advantage over random play --- of entangled players can be at most a constant times greater than that of classical players. Recently, Perez-Garcia et al. (Comm. Math. Phys. 279 (2), 2008) showed that no such bound holds when there are three or more players: the advantage of entangled players over classical players can become unbounded, and scale with the number of questions in the game. Their proof relies on non-trivial results from operator space theory, and gives a non-explicit 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 three-player XOR games which achieve a large quantum-classical gap (QC-gap). This QC-gap is exponentially larger than the one given by Perez-Garcia et. al. in terms of the size of the game, achieving a QC-gap of order N−−√ with N2 questions per player. In terms of the dimension of the entangled state required, we achieve the same (optimal) QC-gap of N−−√ 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 QC-gap 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 higher-order tensors which may be of independent interest.
Jop Briet, Thomas Vidick
Comm. Math. Phys. 321(1), 2013. Presented as a contributed talk at QIP'12., arXiv:1108.5647.
Does ignorance of the whole imply ignorance of the parts? - Large violations of non-contextuality in quantum theory
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 non-contextual hidden variable model (NC-HV). Curiously, however, such a conjecture is mph{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 information-theoretic inequality satisfied in any NC-HV, but which can be arbitrarily violated by quantum mechanics. Our inequality has interesting implications for quantum cryptography.
Thomas Vidick, Stephanie Wehner
Phys. Rev. Lett. 107, 030402 (2011)., arXiv:1011.6448.
More non-locality with less entanglement
We provide an explicit example of a Bell inequality with 3 settings and 2 outcomes per site for which the largest violation is not obtained by the maximally entangled state, even if its dimension is allowed to be arbitrarily large. This complements recent results by Junge and Palazuelos (arXiv:1007.3042) who show, employing tools from operator space theory, that such inequalities do exist. Our elementary example provides arguably the simplest setting in which it can be demonstrated that even an infinite supply of EPR pairs is not the strongest possible nonlocal resource.
Thomas Vidick, Stephanie Wehner
Phys. Rev. A 83, 052310 (2011), arXiv:1011.5206.
Trevisan's extractor in the presence of quantum side information
Randomness extraction involves the processing of purely classical information and is therefore usually studied 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 well known 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) min-entropy of the source using a seed of length poly-logarithmic in the input, or only require the seed to be weakly random.
Anindya De, Christopher Portmann, Renato Renner, Thomas Vidick
SIAM J. Comput 41(4), 2012, arXiv:912.5514.
Better Gap-Hamming Lower Bounds via Better Round Elimination
Gap Hamming Distance is a well-studied problem in communication complexity, in which Alice and Bob have to decide whether the Hamming distance between their respective n-bit inputs is less than n/2-sqrt(n) or greater than n/2+sqrt(n). We show that every k-round bounded-error communication protocol for this problem sends a message of at least Omega(n/(k*k*log k)) bits. This lower bound has an exponentially better dependence on the number of rounds than the previous best bound, due to Brody and Chakrabarti. Our communication lower bound implies strong space lower bounds on algorithms for a number of data stream computations, such as approximating the number of distinct elements in a stream. Subsequent to this result, the bound has been improved by some of us to the optimal Omega(n), independent of k, by using different techniques.
Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
Proceedings of RANDOM'10, arXiv:912.5276.
</ul>