Interactive proofs for BQP via self-tested graph states

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. In this regard we introduce two important improvements over previous work. Specifically, we derive new error bounds which scale polynomially with the size of the graph compared with exponential dependence on the size of the graph in previous work. We also extend the self-testing error bounds on measurements to a very general set which includes the adaptive measurements used for measurement-based quantum computation as a special case.

53 pages

References in corpus (7)

• Device-independent security of quantum cryptography against collective attacks
• Device-independent quantum key distribution secure against collective attacks
• Robust Self Testing of the Singlet
• Interactive Proofs For Quantum Computations
• Optimal robust quantum self-testing by binary nonlocal XOR games
• A classical leash for a quantum system: Command of quantum systems via rigidity of CHSH games
• Quantum Information Processing with Adversarial Devices

Cited by in corpus (52)

• Self-testing of quantum systems: a review
• Verification of quantum computation: An overview of existing approaches
• A quantum network stack and protocols for reliable entanglement-based networks
• Theory of quantum system certification: a tutorial
• Self-testing multipartite entangled states through projections onto two systems
• Post hoc verification with a single prover
• Post hoc verification of quantum computation
• Scalable Bell inequalities for qubit graph states and robust self-testing
• Rigidity of quantum steering and one-sided device-independent verifiable quantum computation
• Certifying the building blocks of quantum computers from Bell's theorem
• Verified measurement-based quantum computing with hypergraph states
• Self-guaranteed measurement-based quantum computation
• Resource-efficient verification of quantum computing using Serfling's bound
• Quantum networks self-test all entangled states
• Quantum NETwork: from theory to practice
• Self-testing in parallel
• Non-interactive classical verification of quantum computation
• Device-Independent Verifiable Blind Quantum Computation
• Optimised resource construction for verifiable quantum computation
• Device-independent characterization of quantum instruments
• Accrediting outputs of noisy intermediate-scale quantum computing devices
• Device-independent detection of genuine multipartite entanglement for all pure states
• Measurement-only verifiable blind quantum computing with quantum input verification
• Flow Ambiguity: A Path Towards Classically Driven Blind Quantum Computation
• A generalization of the CHSH inequality self-testing maximally entangled states of any local dimension
• Robust Self-Testing of Multiparticle Entanglement
• Self-testing with finite statistics enabling the certification of a quantum network link
• Reducing resources for verification of quantum computations
• Client-friendly continuous-variable blind and verifiable quantum computing
• Contextuality in multipartite pseudo-telepathy graph games
• Parallel Self-Testing of the GHZ State with a Proof by Diagrams
• Unifying Quantum Verification and Error-Detection: Theory and Tools for Optimisations
• Classical verification of quantum circuits containing few basis changes
• Measurement-based universal blind quantum computation with minor resources
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Cross-verification of independent quantum devices
• On optimising quantum communication in verifiable quantum computing
• All Real Projective Measurements Can be Self-tested
• An Operational Environment for Quantum Self-Testing
• Constant-Soundness Interactive Proofs for Local Hamiltonians
• Finding resource states of measurement-based quantum computing is harder than quantum computing
• Multi-server Blind Quantum Computation Protocol With Limited Classical Communication Among Servers
• Sumcheck-based delegation of quantum computing to rational server
• Multi-agent blind quantum computation without universal cluster states
• Practical parallel self-testing of Bell states via magic rectangles
• Interactive proofs for BQP via self-tested graph states (extended abstract)
• Parallel remote state preparation for fully device-independent verifiable blind quantum computation
• Accreditation Against Limited Adversarial Noise
• Unifying communication paradigms in measurement-based delegated quantum computing
• Self-Testing Graph States Permitting Bounded Classical Communication
• Certifying the absence of quantum nonlocality
• Equivalence of Single-server and Multiple-servers Blind Quantum Computation Protocols