## Robust verification of quantum computation

##### Abstract

Quantum computers promise to offer a considerable speed-up in solving certain
problems, compared to the best classical algorithms. In many instances, the gap
between quantum and classical running times is conjectured to be exponential.
While this is great news for those applications where quantum computers would
provide such an advantage, it also raises a significant challenge: how can classical
computers verify the correctness of quantum computations? In attempting to
answer this question, a number of protocols have been developed in which a
classical client (referred to as verifier) can interact with one or more quantum
servers (referred to as provers) in order to certify the correctness of a quantum
computation performed by the server(s). These protocols are of one of two types:
either there are multiple non-communicating provers, sharing entanglement, and
the verifier is completely classical; or, there is a single prover and the classical
verifier has a device for preparing or measuring quantum states. The latter type
of protocols are, arguably, more relevant to near term quantum computers, since
having multiple quantum computers that share a large amount of entanglement
is, from a technological standpoint, extremely challenging.
Before the realisation of practical single-prover protocols, a number of challenges
need to be addressed: how robust are these protocols to noise on the
verifier's device? Can the protocols be made fault-tolerant without significantly
increasing the requirements of the verifier? How do we know that the verifier's
device is operating correctly? Could this device be eliminated completely, thus
having a protocol with a fully classical verifier and a single quantum prover? Our
work attempts to provide answers to these questions.
First, we consider a single-prover verification protocol developed by Fitzsimons
and Kashefi and show that this protocol is indeed robust with respect to
deviations on the quantum state prepared by the verifier. We show that this
is true even if those deviations are the result of a correlation with the prover's
system. We then use this result to give a verification protocol which is device-
independent. The protocol consists of a verifier with a measurement device and
a single prover. Device-independence means that the verifier need not trust the
measurement device (nor the prover) which can be assumed to be fully malicious
(though not communicating with the prover). A key element in realising
this protocol is a robust technique of Reichardt, Unger and Vazirani for testing,
using non-local correlations, that two untrusted devices share a large number of
entangled states. This technique is referred to as rigidity of non-local correlations.
Our second result is to prove a rigidity result for a type of quantum correlations
known as steering correlations. To do this, we first show that steering correlations
can be used in order to certify maximally entangled states, in a setting in which
each test is independent of the previous one. We also show that the fidelity with
which we characterise the state, in this specific test, is optimal. We then improve
the previous result by removing the independence assumption. This then leads
to our desired rigidity result. We make use of it, in a similar fashion to the
device-independent case, in order to give a verification protocol that is one-sided
device-independent. The importance of this application is to show how different
trust assumptions affect the efficiency of the protocol.
Next, we describe a protocol for fault-tolerantly verifying quantum computations,
with minimal "quantum requirements" for the verifier. Specifically, the
verifier only requires a device for measuring single-qubit states. Both this device,
and the prover's operations are assumed to be prone to errors. We show that
under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of
principle, and to better illustrate the inner workings of the protocol, we describe
a toy implementation of the protocol in a quantum simulator, and present the
results we obtained, when running it for a small computation.
Finally, we explore the possibility of having a verification protocol, with a
classical verifier and a single prover, such that the prover is blind with respect
to the verifier's computation. We give evidence that this is not possible. In fact,
our result is only concerned with blind quantum computation with a classical
client, and uses complexity theoretic results to argue why it is improbable for
such a protocol to exist. We then use these complexity theoretic techniques to
show that a client, with the ability to prepare and send quantum states to a
quantum server, would not be able to delegate arbitrary NP problems to that
server. In other words, even a client with quantum capabilities cannot exploit
those capabilities to delegate the computation of NP problems, while keeping
the input, to that computation, private. This is again true, provided certain
complexity theoretic conjectures are true.