Open Collections

How to verify a quantum computation

Banff International Research Station for Mathematical Innovation and Discovery

We give a new interactive protocol for 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 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, 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) suffice. We also present a new soundness analysis, based on a reduction to an entanglement-based protocol. Reference: http://arxiv.org/abs/1509.09180

Mathematics; Quantum theory; Information and communication, circuits; Theoretical computer science

video/mp4

Author affiliation: University of Ottawa

2016-10-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/59539

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/