Interactive proofs for BQP via self-tested graph states (extended abstract)
arXiv:1311.1534
Abstract
Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in BQP with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. Our techniques use self-tested graph states which allow us to test the provers for honesty, establishing that they hold onto a particular graph state and measure it in specified bases. In this extended abstract we give an overview of the construction and proofs.
arXiv comment13 pages. arXiv admin note: substantial text overlap with arXiv:1309.5675
References in corpus (14)
- Device-independent security of quantum cryptography against collective attacks
- Measurement-based quantum computation with cluster states
- Random Numbers Certified by Bell's Theorem
- Device-independent quantum key distribution secure against collective attacks
- Robust Self Testing of the Singlet
- Device independent state estimation based on Bell's inequalities
- Interactive proofs for BQP via self-tested graph states
- Quantum computing via measurements only
- A classical leash for a quantum system: Command of quantum systems via rigidity of CHSH games
- Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates
- Optimal robust quantum self-testing by binary nonlocal XOR games
- Graph States, Pivot Minor, and Universality of (X,Z)-measurements
- Quantum Information Processing with Adversarial Devices
- Interactive proofs with efficient quantum prover for recursive Fourier sampling