[quantum-info] PIQuDos seminars on Wednesday 4pm in Time room

[Josh Combes]

*How to verify a quantum computation*

Anne Broadbent (University of Ottawa)

*4pm in Time room*

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 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")
suffice. As a proof technique, we use a reduction to an entanglement-based
protocol; this enables a relatively simple analysis for a situation that
has previously remained ambiguous in the literature.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.uwaterloo.ca/pipermail/quantum-info/attachments/20160329/c3f17ef3/attachment.html>