- Computationally-secure and composable remote state preparation
We introduce a protocol between a classical polynomial-time verifier and a quantum polynomial-time prover that allows the verifier to securely delegate to the prover the preparation of certain single-qubit quantum states. The protocol realizes the following functionality, with computational security: the verifier chooses one of the observables Z, X, Y, (X+Y)/sqrt(2), (X−Y)/sqrt(2); the prover receives a uniformly random eigenstate of the observable chosen by the verifier; the verifier receives a classical description of that state. 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 single-qubit 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 an verifiable DQC were shown to be possible, under computational assumptions, with a classical polynomial-time client (Mahadev 2017, Mahadev 2018). Compared to the work of Mahadev, our protocol is more modular, applies to the measurement-based model of computation (instead of the Hamiltonian model) and is composable. Our proof of security builds on ideas introduced in (Brakerski et al. 2018).
Alexandru Gheorghiu, Thomas Vidick
Submitted, arXiv:1904.06320.
- Classical zero-knowledge arguments for quantum computations
We show that every language in BQP admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical (and quantum) polynomial-time verifiers. The protocol builds upon two recent results: a computational zero-knowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in BQP, with a classical verifier, introduced by Mahadev (FOCS 2018).
Thomas Vidick, Tina Zhang
Presented at TQC'19. Manuscript, arXiv:1902.05217.
- Bounds on Dimension Reduction in the Nuclear Norm
Oded Regev, Thomas Vidick
GAFA seminar notes, arXiv:1901.09480.
- Trading locality for time: certifiable randomness from low-depth circuits
The generation of certifiable randomness is the most fundamental information-theoretic 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 contains a polynomial number of certified random bits under the sole physical assumption that the device used to generate the output operated using a (classical or quantum) circuit of sub-logarithmic 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. Our procedure is inspired by recent work of Bravyi et al. (arXiv:1704.00690), who designed a relation problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic depth. We expand the discovery of Bravyi et al. into a framework for robust randomness expansion. Furthermore, to demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our proposal can thus be interpreted as a proposal for demonstrated quantum advantage that is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory. Our separation does not require any conjectures, but assumes that the adversarial device implements a circuit of sub-logarithmic depth.
Matthew Coudron, Jalex Stark, Thomas Vidick
Presented at QIP'19. Manuscript, arXiv:1810.04233.
- 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
Presented at QIP'19. Proceedings of STOC'19, 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
Proceedings of FOCS'18. Presented at QIP'19, 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. 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.