2013/11/06 by Matthew McKague, McKague, Matthew · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Logic, programming, and type systems #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1311.1534
13 pages. arXiv admin note: substantial text overlap with arXiv:1309.5675
arxiv created 2013/11/06 · openalex publication_date 2013/11/06 · arxiv updated 2013/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.