Abstract
Joe Fitzsimons (Centre for Quantum Technologies, Singapore/U.C.D.)
Universal blind quantum computation
In this talk I will provide a brief introduction to the notion of interactive proofs, and discuss how this relates to verification of quantum computers. In particular, I will focus on the problem of whether or not the results of a quantum computer can be classically verified. For problems contained within NP the answer is clearly that they can be verified. There do exist problems, however, inside BQP which are not believed to be contained within NP, and it is unclear how such results can be verified. I will introduce the notion of 'blind quantum computation', and how it can be exploited in the context of verification and interactive proof systems. Blind quantum computation refers to the problem of allowing Alice to have Bob carry out a quantum computation for her such that Bob learns nothing about the computation that he performs. I will introduce a protocol for performing secure blind computation and show that it allows any quantum computation to be verified by a classical verifier given to non-communicating quantum provers, or by a semi-classical verifier using only a single quantum prover. The existence of such a protocol has consequences for the study of complexity theory, as it allows quantum verifiers in multiple-prover interactive proofs to be replaced with classical verifiers.