Abstract: We give a new theoretical solution to a leading-edge experimental challenge, namely to the verification of quantum computations in the regime of high computational complexity. Our results are given in the language of quantum interactive proof systems. Specifically, we show that any language in has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover. Here, soundness is unconditional--i.e., it holds even for computationally unbounded provers. Compared to prior work achieving similar results, our technique does not require the encoding of the input or of the computation; instead, we rely on encryption of the input (together with a method to perform computations on encrypted inputs), and show that the random choice between three types of input (defining a computational run, versus two types of test runs) suffices. Because the overhead is very low for each run (it is linear in the size of the circuit), this shows that verification could be achieved at minimal cost compared to performing the computation. As a proof technique, we use a reduction to an entanglement-based protocol; to the best of our knowledge, this is the first time this technique has been used in the context of verification of quantum computations, and it enables a relatively straightforward analysis.
Recommendations
- Verification of quantum computation: an overview of existing approaches
- Classical verification of quantum computations
- Succinct classical verification of quantum computation
- Verification of quantum computation and the price of trust
- Classical verification of quantum computations with efficient verifier
- Verification of quantum programs
- Non-interactive classical verification of quantum computation
- scientific article; zbMATH DE number 7699438
- Verifying quantum computations at scale: a cryptographic leash on quantum devices
- Classical verification of quantum proofs
Cites work
- A new universal and fault-tolerant quantum basis
- A polynomial quantum algorithm for approximating the Jones polynomial
- Algebraic methods for interactive proof systems
- Composable security of delegated quantum computation
- Cryptography in the Bounded-Quantum-Storage Model
- Delegating computation: interactive proofs for muggles
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- Interactive proof systems with polynomially bounded strategies
- Minimum disclosure proofs of knowledge
- Optimised resource construction for verifiable quantum computation
- PSPACE has constant-round quantum interactive proof systems
- Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
- The computational complexity of linear optics
- The Knowledge Complexity of Interactive Proof Systems
- Universal Blind Quantum Computation
- Using entanglement in quantum multi-prover interactive proofs
Cited in
(28)- Measurement-based universal blind quantum computation with minor resources
- Classical verification of quantum computations with efficient verifier
- Secure two-party computation based on blind quantum computation
- A hybrid universal blind quantum computation
- An automated deductive verification framework for circuit-building quantum programs
- Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources
- Verification of quantum computation: an overview of existing approaches
- Verification of quantum computation and the price of trust
- Blindness and verification of quantum computation with one pure qubit
- Optimised resource construction for verifiable quantum computation
- The road to quantum computational supremacy
- Information theoretically secure hypothesis test for temporally unstructured quantum computation (extended abstract)
- Testing quantum circuits and detecting insecure encryption
- Distinguishing short quantum computations
- A simple protocol for verifiable delegation of quantum computation in one round
- Classical verification of quantum computations
- Classical verification of quantum proofs
- Verifying quantum computations at scale: a cryptographic leash on quantum devices
- Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states
- scientific article; zbMATH DE number 7651035 (Why is no real title available?)
- Succinct classical verification of quantum computation
- Simple tests of quantumness also certify qubits
- Multi-agent blind quantum computation without universal cluster states
- Quantum interactive proofs using quantum energy teleportation
- Interactive oracle arguments in the QROM and applications to succinct verification of quantum computation
- Zero-knowledge proof systems for QMA
- Quantum delegation with an off-the-shelf device
- A verification scheme for universal quantum computers
This page was built for publication: How to Verify a Quantum Computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4568113)
