- Quantum proof systems for iterated exponential time, and beyond
We show that any language in nondeterministic time exp(exp(⋯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 polynomial-time verifier and a constant number of quantum entangled provers, with completeness 1 and soundness 1−exp(−Cexp(⋯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 time-constructible 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 (unpublished) on the uncomputability of the entangled value of multiprover games. 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.
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen
Manuscript, arXiv:1805.12166.
- Certifiable Randomness from a Single Quantum Device
We give a protocol for producing certifiable randomness from a single untrusted quantum device that is polynomial-time 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 post-quantum secure trapdoor claw-free 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.
Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, Thomas Vidick
To appear in the proceedings of FOCS'18, arXiv:1804.00640.
- 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
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. To appear in the 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
Proceedings of CCC'18, 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
Submitted, 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. Submitted, 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.