Interactive Proofs For Quantum Computations
arXiv:0810.5375
Abstract
The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to experimentally test that these systems perform as they should, if we cannot efficiently compute predictions for their behavior? Vazirani has asked: If predicting Quantum Mechanical systems requires exponential resources, is QM a falsifiable theory? In cryptographic settings, an untrusted future company wants to sell a quantum computer or perform a delegated quantum computation. Can the customer be convinced of correctness without the ability to compare results to predictions? To answer these questions, we define Quantum Prover Interactive Proofs (QPIP). Whereas in standard Interactive Proofs the prover is computationally unbounded, here our prover is in BQP, representing a quantum computer. The verifier models our current computational capabilities: it is a BPP machine, with access to few qubits. Our main theorem can be roughly stated as: "Any language in BQP has a QPIP, and moreover, a fault tolerant one". We provide two proofs. The simpler one uses a new (possibly of independent interest) quantum authentication scheme (QAS) based on random Clifford elements. This QPIP however, is not fault tolerant. Our second protocol uses polynomial codes QAS due to BCGHS, combined with quantum fault tolerance and multiparty quantum computation techniques. A slight modification of our constructions makes the protocol "blind": the quantum computation and input are unknown to the prover. After we have derived the results, we have learned that Broadbent at al. have independently derived "universal blind quantum computation" using completely different methods. Their construction implicitly implies similar implications.
24 pages; reorganization of paper, minor content changes
References in corpus (5)
Cited by in corpus (42)
- Experimental Demonstration of Blind Quantum Computing
- Security in Quantum Cryptography
- Unconditionally verifiable blind computation
- Verification of quantum computation: An overview of existing approaches
- Quantum computing on encrypted data
- Reliable quantum certification for photonic quantum technologies
- Quantum one-time programs
- How "Quantum" is the D-Wave Machine?
- Interactive proofs for BQP via self-tested graph states
- Symmetric quantum fully homomorphic encryption with perfect security
- Composable security of delegated quantum computation
- Rigidity of quantum steering and one-sided device-independent verifiable quantum computation
- How to Verify a Quantum Computation
- Device-Independent Verifiable Blind Quantum Computation
- Unforgeable Quantum Encryption
- Quantum authentication with key recycling
- Accrediting outputs of noisy intermediate-scale quantum computing devices
- QFactory: classically-instructed remote secret qubits preparation
- Cryptographic approach to Quantum Metrology
- Fault-tolerant Operations for Universal Blind Quantum Computation
- Blind quantum computation for a user who only performs single-qubit gates
- Classical command of quantum systems via rigidity of CHSH games
- Preparation and verification of tensor network states
- Nonadaptive fault-tolerant verification of quantum supremacy with noise
- Deploying hybrid quantum-secured infrastructure for applications: When quantum and post-quantum can work together
- Classical zero-knowledge arguments for quantum computations
- Client-friendly continuous-variable blind and verifiable quantum computing
- Blind Quantum Computation Using a Circuit-Based Quantum Computer
- Quantum homomorphic encryption for polynomial-sized circuits
- Local certification of programmable quantum devices of arbitrary high dimensionality
- Constant-Space Quantum Interactive Proofs Against Multiple Provers
- Verified Delegated Quantum Computing with One Pure Qubit
- Sumcheck-based delegation of quantum computing to rational server
- A quantum homomorphic encryption scheme for polynomial-sized circuits
- A Quantum inspired proof of
- Can you sign a quantum state?
- Towards a quantum-inspired proof for IP = PSPACE
- Quantum-enhanced Secure Delegated Classical Computing
- Secure Two-Party Quantum Computation Over Classical Channels
- Blind quantum computation with completely classical client and a trusted center
- A framework for quantum homomorphic encryption with experimental demonstration
- Teleportation-based quantum homomorphic encryption scheme with quasi-compactness and perfect security