How to Verify a Quantum Computation

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 $\mathsf{BQP}$ 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.

Published in Theory of Computing, Volume 14 (2018), Article 11; Received: October 3, 2016, Revised: October 27, 2017, Published: June 11, 2018

References in corpus (8)

• Verifiable measurement-only blind quantum computing with stabilizer testing
• Quantum homomorphic encryption for circuits of low $T$-gate complexity
• Interactive Proofs For Quantum Computations
• Self-guaranteed measurement-based quantum computation
• Optimised resource construction for verifiable quantum computation
• Classical command of quantum systems via rigidity of CHSH games
• On optimising quantum communication in verifiable quantum computing
• Cryptography in the Bounded-Quantum-Storage Model

Cited by in corpus (26)

• Advances in Quantum Cryptography
• Verification of quantum computation: An overview of existing approaches
• A Deductive Verification Framework for Circuit-building Quantum Programs
• Verifiable blind quantum computing with trapped ions and single photons
• Non-interactive classical verification of quantum computation
• Accrediting outputs of noisy intermediate-scale quantum computing devices
• Experimental accreditation of outputs of noisy quantum computers
• Reducing resources for verification of quantum computations
• A Hybrid and Universal Blind Quantum Computation
• Quantum cryptography beyond key distribution: theory and experiment
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Unifying Quantum Verification and Error-Detection: Theory and Tools for Optimisations
• Client-friendly continuous-variable blind and verifiable quantum computing
• The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation
• 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
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation
• In situ characterization of linear-optical networks in randomized boson sampling
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Efficient classical verification of quantum computations
• A quantum homomorphic encryption scheme for polynomial-sized circuits
• Multi-agent blind quantum computation without universal cluster states
• Parallel remote state preparation for fully device-independent verifiable blind quantum computation
• Unifying communication paradigms in measurement-based delegated quantum computing
• Accreditation Against Limited Adversarial Noise
• Gate Teleportation-based Universal Blind Quantum Computation