# How to Verify a Quantum Computation

Anne Broadbent Department of Mathematics and Statistics, University of Ottawa,
Ontario, Canada. Email<EMAIL_ADDRESS>
###### 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 $\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; 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.

##  1 Introduction

Feynman [Fey82] was the first to point out that quantum computers, if built,
would be able to perform quantum simulations (_i.e._ to compute the
predictions of quantum mechanics; which is widely believed to be classically
intractable). But this immediately begs the question: if the output of a
quantum computation cannot be predicted, how do we know that it is correct?
Conventional wisdom would tell us that we can rely on testing _parts_ (or
scaled-down versions) of a quantum computer—conclusive results would then
extrapolate to the larger system. But this is somewhat unsatisfactory, since
we may not rule out the hypothesis that, at a large scale, quantum computers
behave unexpectedly. A different approach to the verification of a quantum
computation would be to construct a number of quantum computers based on
different technologies (_e.g._ with ionic, photonic, superconducting and/or
solid state systems), and to accept the computed predictions if the
experimental results agree. Again, this is still somewhat unsatisfactory, as a
positive outcome does not confirm the correctness of the output, but instead
confirms that the various large-scale devices behave similarly on the given
instances.

This problem, though theoretical in nature [AV14], is already appearing as a
major experimental challenge. One of the outstanding applications for the
verification of quantum systems is in quantum chemistry, where the current
state-of-the-art is that the inability to verify quantum simulations is much
more the norm than the exception [GH05]. Any theoretical advance in this area
could have dramatic consequences on applications of quantum chemistry
simulations, including the potential to revolutionize drug discovery. Another
case where experimental techniques are reaching the limits of classical
verifiability is in the Boson Sampling problem [AA11], where the process of
verification has been raised as a fundamental objection to the viability of
experiments [GKAE13] (fortunately, these claims are refuted [AA14], and
progress was made in the experimental verification [SVB+14]).

As mere classical probabilistic polynomial-time111 _i.e._ assuming humans can
flip coins and execute classical computations that take time polynomial in $n$
to solve on inputs of size $n$. individuals, we appear to be in an impasse:
how can we validate the output of a quantum computation?222Assuming the
widely-held belief that $\BQP\neq\BPP$, _i.e._ that quantum computers are
indeed more powerful than classical computers. For some problems of interest
in quantum computing (such as factoring and search), a claimed solution can be
efficiently verified by a classical computer. However, current techniques do
not give us such an efficient verification procedure for the _hardest_
problems that can be solved by quantum computers (such problems are known as
$\BQP$-complete, and include the problem of approximating the Jones
polynomial[AJL06]). Here, we propose a solution based on _interaction_ ,
viewing an experiment not in the traditional, static, predict-and-verify
framework, but as an interaction between an experimentalist and a quantum
device. In the context of theoretical computer science, it has been
established for quite some time that interaction between a probabilistic
polynomial-time _verifier_ and a computationally unbounded _prover_ allows the
verification of a class of problems _much_ wider than what static proofs
allow333This is the famous $\IP=\PSPACE$ result[LFKN92, Sha92]..

Interactive proof systems traditionally model the prover as being all-powerful
(_i.e._ computationally unbounded)444Notable exceptions include [CL92,
GKR08].. For our purposes, we restrict the prover to being a “realistic”
quantum device, _i.e._ we model the prover as a quantum polynomial-time
machine. Our approach equates the verifier with a classical polynomial-time
machine, augmented with _extremely_ rudimentary quantum operations, namely of
being able to prepare random single pure-state qubits (chosen among a specific
set, see Section 3). Our verifier does not require any quantum memory or
quantum processing power. Without loss of generality, the random quantum bits
can be sent in the first round, the balance of the interaction and verifier’s
computation being classical. Formally, we present our results in terms of an
_interactive proof system_ , showing that in our model, it is possible to
devise a _quantum prover interactive proof system_ for all problems solvable
(with bounded error) in quantum polynomial time.

###  1.1 Related Work

The complexity class $\mathsf{QPIP}$, corresponding to quantum prover
interactive proof systems, was originally defined by Aharonov, Ben-Or and Eban
[ABE10], who, using techniques from [BOCG+06], showed that
$\BQP=\mathsf{QPIP}$ for a verifier with the capacity to perform quantum
computations on a constant-sized quantum register (together with polynomial-
time classical computation). The main idea of [ABE10] is to encode the input
into a _quantum authentication code_ [BCG+02], and to use interactive
techniques for _quantum computing on authenticated data_ in order to enable
verification of a quantum computation. This result was revisited in light of
foundations of physics in [AV14], and the protocol was also shown secure in a
scenario of _composition_ [BGS13].

In a different line of research, Kashefi and Fitzsimons [FK12] consider a
measurement-based approach to the problem, giving a scheme that requires the
verifier to prepare only random single qubits: the main idea is to encode the
computation into a larger one which includes a verification mechanism, and to
execute the resulting computation using blind quantum computing [BFK09]. Thus,
success of the encoded computation can be used to deduce the correctness of
actual computation. A small-scale version of this protocol was implemented in
quantum optics [BFKW13]. Further work by Kapourniotis, Dunjko and Kashefi
[KDK15] shows how to combine the [ABE10] and [FK12] protocols in order to
reduce the quantum communication overhead; Kashefi and Wallden [KW15] also
show how to reduce the overhead of [FK12].

To the best of our knowledge, the proof techniques in these prior works appear
as sketches only, or are cumbersome. In particular, the approach that uses
quantum authentication codes [ABE10] is based on [BOCG+06]. However, the full
proof of security for [BOCG+06] never appeared. Although [ABE10] makes
significant progress towards closing this gap, it provides only a sketch of
how the soundness is established in the interactive case. A full proof of
soundness for [ABE10] follows from [BGS13], however the proof is very
elaborate and phrased in terms of a rather different cryptographic task
(called “quantum one-time programs”). In terms of the measurement-based
approach, note that a proposed protocol for verification in [BFK09] was deemed
incomplete [FK12], but any gaps were addressed in [FK12]. In this case,
however, the protocol (and proof) are very elaborate, and to the best of our
knowledge, remain unpublished.

In sharp contrast to these approaches, Reichardt, Unger and Vazirani [RUV13]
show that it is possible to make the verifier _completely_ classical, as long
as we postulate _two_ non-communicating entangled provers (this could be
enforced, for instance, by space-like separation such that communication
between the provers would be forbidden by the limit on the speed of light).
The main technique used is a _rigidity theorem_ which, provided that the
provers pass a certain number of tests, gives the verifier a tight classical
control on the quantum provers.

###  1.2 Contributions

Our main contributions are a new, simple quantum prover interactive proof
system for $\BQP$, with a verifier whose quantum power is limited to the
random preparation of single-qubit pure states, together with a new proof
technique:

##### New protocol.

All prior approaches to the verification of quantum computations required some
type of encoding (either of the input or of the computation). In contrast, our
protocol achieves soundness via the verifier’s random choice of different
types of runs. This is a typical construction in interactive proofs, and in
some sense it is surprising that it is used here for the first time in the
context of verifying quantum computations. According to the new protocol, the
overhead required for verification can be reduced to repetition of a very
simple protocol (with overhead at most linear compared to performing the
original computation), and thus may lead to implementations sooner than
expected (in general, it is much easier to repeat an experiment using
different initial settings, than to run a single, more complex experiment!).

##### New proof technique.

In order to prove soundness, we use the proof technique of a reduction to an
“entanglement-based” protocol. This proof technique originates from Shor and
Preskill [SP00] and has been used in a number of quantum cryptographic
scenarios, _e.g._ [DFSS05, DFPR14, FBS+14]. This is the first time that this
technique is used in the context of the verification of quantum computations;
we show how the technique provides a much-needed succinct and convincing
method to prove soundness. In particular, it allows us to reduce the analysis
of an interactive protocol to the analysis of a non-interactive one, and to
formally delay the verifier’s choice of run until _after_ the interaction with
the prover.

Furthermore, this work unifies the two distinct approaches given above, (one
based on quantum authentication codes and the other on measurement-based
quantum computing). Indeed, one can view our protocol as performing a very
basic type of quantum computing on authenticated data [BGS13]; with hidden
gates being executed via a computation-by-teleportation process [GC99] that is
reminiscent of measurement-based quantum computation, and thus of blind
quantum computation [BFK09].

On the conceptual front, this work focuses on the _simplest possible_ way to
achieve a quantum prover interactive proof system. Via this process, we have
further emphasized links between various concepts:

  1. 1.

A link between input privacy and verification. Prior results [ABE10, BFK09,
BGS13, FK12] all happened to provide both _privacy_ of a quantum computation
and its _verification_ (one notable exception being the recent [FH15]). Here,
we make this link explicit, essentially starting from input privacy and
constructing a verifiable scheme (this was also done, to a certain extent in
[BFK09, FK12]).

  2. 2.

A link between fault-tolerant quantum computation and cryptography. Prior
results [BOCG+06, ABE10, BGS13] used constructions inspired by fault-tolerant
quantum computation. Here, we make the link even more explicit by using
single-qubit gate gadgets that are adaptations of the gate gadgets used in
fault-tolerant quantum computation. Furthermore, our results also emphasize
how the ubiquitous technique of “tracking the Pauli frame” from fault-tolerant
quantum computation can be re-phrased in terms of keeping track of an
encryption key.

  3. 3.

A link between entanglement and parallelization. It is known that entanglement
can reduce the number of rounds in quantum interactive proof systems [KKMV08];
a consequence of our entanglement-based protocol is that we can parallelize
our interactive proof system to a single round, as long as we are willing to
allow the prover to share entanglement with the verifier, and to perform
adaptive measurements.

###  1.3 Overview of Techniques

The main idea for our quantum prover interactive proof system is that the
verifier chooses randomly to interact with the prover in one of three runs.
Among these runs, one is the _computation_ run, while the two others are
_test_ runs. In an honest interaction, the output of the computation run is
the result (a single bit) of evaluating the given quantum circuit. The test
runs are used to detect a deviating prover; there are two types of test runs:
an _${\sf X}$ -test_ and a _${\sf Z}$ -test_. Intuitively (and formally proved
in Section 7.1), we see that the prover cannot distinguish between all three
runs. Thus, his strategy must be invariant over the different runs. It should
be clear now how this work links _input privacy_ with verification: by varying
the input to the computation, the verifier differentiates between test and
computation runs; by input privacy, however, the prover cannot identify the
type of run and thus any deviation from the prescribed protocol has a chance
of being detected.

In more details, the runs have the following properties (from the point of
view of the verifier)

  * •

Computation run. In a computation run, the prover executes the target circuit
on input ${\left|{0}\right\rangle}^{\otimes n}$.

  * •

${\sf X}$-test run. In an ${\sf X}$-test run, the prover executes the identity
circuit on input ${\left|{0}\right\rangle}^{\otimes n}$. At the end of the
computation, the verifier verifies that the result is $0$. This test also
contains internal checks for cheating within the protocol.

  * •

${\sf Z}$-test run. In a ${\sf Z}$-test run, the prover executes the identity
circuit on input ${\left|{+}\right\rangle}^{\otimes n}$. This test run is used
only as an internal check for cheating within the protocol.

In order for the prover to execute the above computations without being able
to distinguish between the runs, we use a technique inspired by _quantum
computing on encrypted data (QCED)_ [FBS+14, Bro15]: the input qubits are
encrypted with a random Pauli, as are auxiliary qubits that are used to drive
the computation.

Viewing the target computation as a sequence of gates in the universal gateset
$\\{{\sf X},{\sf Z},{\sf H},{\sf CNOT},{\sf T}\\}$ (see Section 2.1 for
notation), the task we face is, in the computation run, to perform these
logical gates on encrypted quantum data. Furthermore, the ${\sf X}$\- and
${\sf Z}$-test runs should (up to an encryption key), leave the quantum wires
in the ${\left|{0}\right\rangle}^{\otimes n}$ or
${\left|{+}\right\rangle}^{\otimes n}$ state, respectively. Performing Pauli
gates in this fashion is straightforward, as this can be done by adjusting the
encryption key (in the computation run only). As we show in Section 4.2, the
${\sf CNOT}$ gate can be executed directly (since it does not have any effect
on the wires for the test runs). The ${\sf T}$-gate (Section 4.3) is performed
using a construction (“gate gadget”) inspired both by QCED and fault-tolerant
quantum computation [BMP+00] (see also [BJ15]); the ${\sf T}$-gate gadget
involves the use of an auxiliary qubit and classical interaction. The ${\sf
H}$ is performed thanks to an identity involving the ${\sf H}$ and ${\sf P}$
(Section 4.4). Note that ${\sf P}$ can be accomplished as ${\sf T}^{2}$.

In order to prove soundness, we consider any general deviation of the prover,
and show that such deviation can be mapped to an attack on the measured wires
only, corresponding to an honest run of the protocol (without loss of
generality, we can also delay all measurements until the end of the protocol).
Furthermore, because the computation is performed on encrypted data, by the
_Pauli twirl_ [DCEL09], this attack can be described as a convex combination
of Pauli attacks on the measured qubits. Since all measurements are performed
in the computational basis, ${\sf Z}$ attacks are obliterated, and thus the
only family of attacks of concern consists in ${\sf X}$\- and ${\sf Y}$-gates
applied to various measured qubits; these act as bit flips on the
corresponding classical output. We show that the combined effect of test runs
is to detect _all_ such attacks; this allows us to bound the probability that
the verifier accepts a _no_ -instance. Since only ${\sf X}$ and ${\sf Y}$
attacks require detection, one may wonder why we use also a ${\sf Z}$-test
run. The answer to this question lies in the implementation of the ${\sf
H}$-gate: while its net effect is to apply the identity in the test runs, its
internal workings temporality _swap_ the roles of the ${\sf X}$\- and ${\sf
Z}$-test runs: thus the ${\sf Z}$-test runs are also is used to detect ${\sf
X}$ and ${\sf Y}$ errors.

Finally, some words on showing indistinguishability between the test and
computation runs. This is done by showing that the verifier can delay her
choice of run (computation, ${\sf X}$\- or ${\sf Z}$-test) until _after_ the
interaction with the prover is complete. This is accomplished via an
entanglement-based protocol, where the verifier’s messages to the prover
consist in only half-EPR pairs, as well as classical random bits. These
messages are identical in both the test and computation runs; as the verifier
decides on the type of run only _after_ having the interacted with the prover.
Depending on this choice, the verifier performs measurements on the system
returned by the prover, resulting in the desired effect.

###  1.4 Open Problems

The main outstanding open problem is the verifiability of a quantum
computation with a _single_ , classical verifier, interacting with a quantum
polynomial-time prover. In this context, we mention a few observations:

  * •

If the prover is unbounded, there exists a quantum interactive proof system
for $\BQP$, since $\QIP=\PSPACE$ [JJUW10].

  * •

If $\P=\BQP$, there is a trivial quantum interactive proof system.

  * •

One possible approach would be to relax the definition to require only
_computational_ soundness (following the lines of Brassard, Chaum and Crépeau
[BCC88], this would lead to a quantum interactive _argument_). This approach
seems promising, especially if we consider a computational assumption that is
_post-quantum_ secure. If, via its interaction with the prover, a classical
verifier accepts, then we can conclude that either the verifier performed the
correct computation _or_ the prover has broken the computational assumption.

###  1.5 Organization

The remainder of this paper is organized as follows. Section 2 presents some
preliminary notation and background. Section 3 defines quantum prover
interactive proofs and states our main theorem. Section 4 describes the
interactive proof system, for which we show completeness (Section 6), and
soundness (Section 7).

##  2 Preliminaries

###  2.1 Notation

We assume the reader is familiar with the basics of quantum information
[NC00]. We use the following well-known qubit gates ${\sf
X}:{\left|{j}\right\rangle}\mapsto{\left|{j\oplus 1}\right\rangle}$, ${\sf
Z}:{\left|{j}\right\rangle}\mapsto(-1)^{j}{\left|{j}\right\rangle}$, Hadamard
${\sf
H}:{\left|{j}\right\rangle}\mapsto\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}+(-1)^{j}{\left|{1}\right\rangle})$,
phase gate ${\sf P}:{\left|{j}\right\rangle}\mapsto
i^{j}{\left|{j}\right\rangle}$ and $\pi/8$ rotation ${\sf
T}:{\left|{j}\right\rangle}\mapsto e^{(i\pi/4)^{j}}{\left|{j}\right\rangle})$
and the two-qubit controlled-not ${\sf
CNOT}:{\left|{j}\right\rangle}{\left|{k}\right\rangle}\mapsto{\left|{j}\right\rangle}{\left|{j\oplus
k}\right\rangle}$. Let ${\sf Y}=i{\sf X}{\sf Z}$. We denote by
$\mathbb{P}_{n}$ the $n$-qubit Pauli group, where a $P\in\mathbb{P}_{n}$ is
given by $P=P_{1}\otimes P_{2}\otimes\cdots\otimes P_{n}$ where
$P_{i}\in\\{I,{\sf X},{\sf Y},{\sf Z}\\}$.

###  2.2 Quantum Encryption and the Pauli Twirl

The quantum one-time pad encryption maps a single-qubit system $\rho$ to
$\frac{1}{4}\sum_{a,b\in\\{0,1\\}}{\sf X}^{a}{\sf Z}^{b}\rho{\sf Z}^{b}{\sf
X}^{a}=\frac{I}{2}$ ; its generalization to $n$-qubit systems is
straightforward [AMTW00]. Here, we take $(a,b)$ to be the classical private
_encryption key_. Clearly, this scheme provides information-theoretic
security, while allowing decryption, given knowledge of the key. A useful
observation is that if we have an _a priori_ knowledge of the quantum operator
$\rho$, then it may not be necessary to encrypt it with a full quantum one-
time pad (_e.g._ if the state corresponds to a pure state of the form
$\frac{1}{\sqrt{2}}({\left|{0}\right\rangle}+e^{i\theta}{\left|{1}\right\rangle})$,
it can be encrypted with a random ${\sf Z}$), although there is no loss of
generality in encrypting it with the full random Pauli. We use the two
interpretations interchangeably.

Consider for a moment the classical one-time pad (that encrypts a plaintext
message by XORing it with a random bit-string of the same length). It is
intuitively clear that if an adversary (who does not know the encryption key)
has access to the ciphertext only, and is allowed to modify it, then the
effect of any adversarial attack (after decryption) is to probabilistically
introduce bit flips in target locations. The quantum analogue of this is given
by the _Pauli twirl_ [DCEL09]:

######  Lemma 1.

(Pauli Twirl) Let $P,P^{\prime}$ be $n$-qubit Pauli operators. Then:

$\frac{1}{\lvert\mathbb{P}_{n}\rvert}\sum_{Q\in\mathbb{P}_{n}}Q^{*}PQ\rho
Q^{*}P^{\prime*}Q=\begin{cases}0,\text{ }P\neq P^{\prime}\\\ P\rho
P^{*},\text{otherwise}\,.\end{cases}$

##  3 Definitions and Statement of Results

Interactive proof systems were introduced by Babai [Babai85] and Goldwasser,
Micali, and Rackoff [GMR89]. An interactive proof system consists of an
interaction between a computationally unbounded prover and a computationally
bounded probabilistic verifier. For a language $L$ and a string $x$, the
prover attempts to convince the verifier that $x\in L$, while the verifier
tries to determine the validity of this “proof”. Thus, a language $L$ is said
to have an interactive proof system if there exists a polynomial-time verifier
$V$ such that:

  * •

(Completeness) if $x\in L$, there exists a prover (called an honest prover)
such that the verifier accepts with probability $p\geq{2}/{3}$;

  * •

(Soundness) if $x\not\in L$, no prover can convince $V$ to accept with
probability $p\geq 1/3$.

The class of languages having interactive proof systems is denoted $\IP$.

Watrous [Wat03] defined $\QIP$ as the quantum analogue of $\IP$, _i.e._ as the
class of languages having a _quantum_ interactive proof system, which consists
in a quantum interaction between a computationally unbounded quantum prover
and a computationally bounded quantum verifier, with the analogous
completeness and soundness conditions as given above.

For our results, we are interested in the scenario of a polynomial-time prover
(in the honest case), as well as an _almost-classical_ verifier; that is, a
verifier with the power to generate random qubits as specified by a parameter
$\mathcal{S}$ (Definition 1). Furthermore, as a technicality, instead of
considering languages, we consider promise problems: a promise problem
$\Pi=(\Pi_{Y},\Pi_{N})$, is a pair of disjoint sets of strings, corresponding
to YES and NO instances, respectively. For a formal treatment of the model
(which we specialize here to our scenario), see [Wat03].

######  Definition 1.

Let $\mathcal{S}=\\{\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell}\\}$ where
$\mathcal{S}_{i}=\\{\rho_{1},\ldots,\rho_{\ell_{i}}\\}$ $(i=1,\ldots,\ell)$ is
a set of density operators. A $\mathcal{S}$-_Quantum Prover Interactive Proof
System for a promise problem $\Pi=(\Pi_{Y},\Pi_{N})$_ is an interactive proof
system with a verifier $V$ that runs in classical probabilistic polynomial
time, augmented with the capacity to randomly generate states in each of
$\mathcal{S}_{1},\ldots,\mathcal{S}_{\ell}$ (upon generation, these states are
immediately sent to the prover, with its index $i\in\\{1,\ldots,\ell\\}$ known
to the verifier). The verifier $V$ interacts with a prover $P$ such that:

  * •

(Completeness) if $x\in\Pi_{Y}$, there exists a quantum polynomial-time prover
(called an honest prover) such that the verifier accepts with probability
$p\geq{2}/{3}$;

  * •

(Soundness) if $x\in\Pi_{N}$, no prover (even unbounded) can convince $V$ to
accept with probability $p\geq 1/3$.

The class of promise problems having an $\mathcal{S}$-quantum interactive
proof systems is denoted $\mathsf{QPIP}_{\mathcal{S}}$. Note that by standard
amplification, the class $\mathsf{QPIP}_{\mathcal{S}}$ is unchanged if we
replace the completeness parameter $c$ and soundness parameter $s$ by any
values, as long as $c-s>\frac{1}{\poly(n)}$.

Comparing our definition of $\mathsf{QPIP}_{\mathcal{S}}$ to the class of
quantum prover interactive proof systems ($\mathsf{QPIP}$) as given in
[ABE10], we note that we have made some modifications and clarifications,
namely that the verifier in $\mathsf{QPIP}_{\mathcal{S}}$ does not have any
quantum memory and does not perform any gates ($\mathsf{QPIP}$ allows a
verifier that stores and operates on a quantum register of a constant number,
$c$, of qubits), and that soundness holds against unbounded provers.

Finally, we use the same $\BQP$-complete promise problem as [ABE10]: (the
canonical $\BQP$-complete problem.)

######  Definition 2.

The promise problem Q-CIRCUIT consists of a quantum circuit made of a sequence
of gates, $U=U_{T},\ldots,U_{1}$ acting on $n$ input qubits (we take these
circuits to be given in the universal gateset $\\{{\sf X},{\sf Z},{\sf H},{\sf
CNOT},{\sf T}\\})$. Let
$p(U)=\left\lVert{\left|{0}\right\rangle}{\left\langle{0}\right|}\otimes\mathbb{I}_{n-1}U{\left|{0^{n}}\right\rangle}\right\rVert^{2}$
be the probability of observing “0” as a results of a computational basis
measurement of the $n^{\text{th}}$ output qubit, obtained by evaluating $U$ on
input ${\left|{0^{n}}\right\rangle}$.

Then define
Q-CIRCUIT$=\\{\mathsf{Q-CIRCUIT}_{\mathsf{YES}},\mathsf{Q-CIRCUIT}_{\mathsf{NO}}\\}$
with:

$\displaystyle\mathsf{Q-CIRCUIT}_{\mathsf{YES}}$ $\displaystyle:p(U)\geq 2/3$
(1) $\displaystyle\mathsf{Q-CIRCUIT}_{\mathsf{NO}}$ $\displaystyle:p(U)\leq
1/3$ (2)

We can now formally state our main theorem.

######  Theorem 1 (Main Theorem).

Let
$\mathcal{S}=\\{\\{{\left|{0}\right\rangle},{\left|{1}\right\rangle}\\},\\{{\left|{+}\right\rangle},{\left|{-}\right\rangle}\\},\\{{\sf
P}{\left|{+}\right\rangle},{\sf P}{\left|{-}\right\rangle}\\},\\{{\sf
T}{\left|{+}\right\rangle},{\sf T}{\left|{-}\right\rangle},{\sf P}{\sf
T}{\left|{+}\right\rangle},{\sf P}{\sf T}{\left|{-}\right\rangle}\\}\\}$. Then
$\BQP=\mathsf{QPIP}_{\mathcal{S}}$.

##  4 Quantum Prover Interactive Proof System

In order to prove Theorem 1, we give an interactive proof system (see
Interactive Proof System 1). This protocol uses the various gate gadgets as
described in Sections 4.1–4.4. Completeness is studied in Section 6 and
soundness is proved in Section 7.

Interactive Proof System 1 Verifiable quantum computation with trusted
auxiliary states

Let $\mathcal{C}$ be given as an $n$-qubit quantum circuit in the universal
gateset ${\sf X},{\sf Z},{\sf CNOT},{\sf H},{\sf T}$.

  1. 1.

The verifier randomly chooses to execute one of the following three runs (but
does not inform the prover of this choice).

    1. A.

Computation Run

      1. A.1.

The verifier encrypts input ${\left|{0}\right\rangle}^{\otimes n}$ and sends
the input to $P$.

      2. A.2.

The verifier sends auxiliary qubits required for the ${\sf T}$-gate gadgets
for the computation run as given in Sections 4.4 and 4.3.

      3. A.3.

For each gate $G$ in $\mathcal{C}$: ${\sf X},{\sf Z}$ and ${\sf CNOT}$ are
performed without any auxiliary qubits or interaction as given in Sections 4.1
and 4.2, while the ${\sf H}$\- and ${\sf T}$-gate gadgets are performed using
the auxiliary qubits from Step 1(A.)A.2. and the interaction as given in
Sections 4.4 and 4.3, respectively.

      4. A.4.

$P$ measures the output qubit and returns the result to $V$.

      5. A.5.

$V$ decrypts the answer; let the result be $c_{\text{comp}}$. $V$ accepts if
$c_{\text{comp}}=0$; otherwise reject.

    2. B.

${\sf X}$-test Run

      1. B.1.

The verifier encrypts input ${\left|{0}\right\rangle}^{\otimes n}$ and sends
the input to $P$.

      2. B.2.

The verifier sends auxiliary qubits required for the ${\sf T}$-gate gadgets
for the ${\sf X}$-test run as given in Sections 4.4 and 4.3.

      3. B.3.

For each gate $G$ in $\mathcal{C}$: ${\sf X},{\sf Z}$ and ${\sf CNOT}$ are
performed without any auxiliary qubits or interaction as given in Sections 4.1
and 4.2, while the ${\sf H}$\- and ${\sf T}$-gate gadgets are performed using
the auxiliary qubits from Step 1(B.)B.2. and the interaction as given in
Sections 4.4 and 4.3, respectively.

      4. B.4.

$P$ measures the output qubit and returns the result to $V$.

      5. B.5.

$V$ decrypts the answer; let the result be $c_{\text{test}}$. $V$ accepts if
no errors were detected in step 1(B.)B.3. _and_ if $c_{\text{test}}=0$;
otherwise reject.

    3. C.

${\sf Z}$-test Run

      1. C.1.

The verifier encrypts input ${\left|{+}\right\rangle}^{\otimes n}$ and sends
the input to $P$.

      2. C.2.

The verifier sends auxiliary qubits required for the ${\sf T}$-gate gadgets
for the ${\sf Z}$-test run as given in Sections 4.4 and 4.3.

      3. C.3.

For each gate $G$ in $\mathcal{C}$: ${\sf X},{\sf Z}$ and ${\sf CNOT}$ are
performed without any auxiliary qubits or interaction as given in Sections 4.1
and 4.2, while the ${\sf H}$\- and ${\sf T}$-gate gadgets are performed using
the auxiliary qubits from Step 1(C.)C.2. and the interaction as given in
Sections 4.4 and 4.3, respectively.

      4. C.4.

$P$ measures the output qubit and returns the result to $V$.

      5. C.5.

$V$ disregards the output. $V$ accepts if no errors were detected in step
1(C.)C.3.; otherwise reject.

###  4.1 ${\sf X}$\- and ${\sf Z}$-gate gadget

In order to apply an ${\sf X}$ on a qubit register $i$ encrypted with key
$(a_{i},b_{i})$, the verifier updates the key according to $a_{i}\leftarrow
a_{i}\oplus 1$ ($b_{i}$ is unchanged). In order to apply an ${\sf Z}$ on a
qubit register $i$ encrypted with key $(a_{i},b_{i})$, the verifier updates
the key according to $b_{i}\leftarrow b_{i}\oplus 1$ ($a_{i}$ is unchanged).
This operation is performed only in the computation run.

###  4.2 ${\sf CNOT}$-gate gadget

In order to apply a ${\sf CNOT}$ gate on the encrypted registers (say with
register $i$ being the control and register $j$ the target), the prover simply
applies the ${\sf CNOT}$ gate on the respective registers. The verifier
updates the encryption keys according to $a_{i}\leftarrow
a_{i};b_{i}\leftarrow b_{i}\oplus b_{j};a_{j}\leftarrow a_{i}\oplus
a_{j};\text{ and }b_{j}\leftarrow b_{j}.$ We mention that ${\sf
CNOT}({\left|{0}\right\rangle}{\left|{0}\right\rangle})={\left|{0}\right\rangle}{\left|{0}\right\rangle}$
and ${\sf
CNOT}({\left|{+}\right\rangle}{\left|{+}\right\rangle})={\left|{+}\right\rangle}{\left|{+}\right\rangle}$;
thus in the ${\sf X}$\- and ${\sf Z}$-test runs, the underlying data is
unchanged.

###  4.3 ${\sf T}$-gate gadget

Here, we show how the ${\sf T}$ is performed on encrypted data. This is
accomplished using an auxiliary qubits, as well as classical interaction. For
the computation run, we use a combination of a protocol inspired from [FBS+14,
Bro15], as well as fault-tolerant quantum computation [BMP+00] (see also
[BJ15]). This is given in Figure 1. In the case of an ${\sf X}$ and ${\sf Z}$
test runs, as usual, we want the identity map to be applied. This is done as
in Figures 2 and 3, respectively. Correctness of Figure 1 is proven in Section
5. Note that we show in Section 6.1 that the set of auxiliary quantum states
required by the verifier can be reduced via a simple re-labelling, in order to
match the resources requires in Theorem 1.

Also, note that in this work, we have slightly sacrificed efficiency for
clarity in the proof, namely that we could have defined a ${\sf P}$-gadget
using one simple auxiliary qubit instead of two auxiliary qubits that are used
by implementing the ${\sf P}$ as ${\sf T}^{2}$. Furthermore, we suspect that
the $P^{y}$ gate is unnecessary in Figure 1 and thus that we can simplify the
set $\mathcal{S}$ (however, the proof in this case appears to be more
elaborate, so once more we choose clarity of the proof over efficiency).

$\textstyle{{\sf X}^{a}{\sf Z}^{b}{\left|{\psi}\right\rangle}}$
$\textstyle{\bullet}$Prover$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\sf
P}^{x}}$$\textstyle{{\sf X}^{a\oplus c}{\sf Z}^{(a\oplus c)\cdot(d\oplus
y)\oplus a\oplus b\oplus c\oplus e\oplus y}{\sf
T}{\left|{\psi}\right\rangle}}$Verifier$\textstyle{x=a\oplus c\oplus
y}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{c}$$\textstyle{{\left|{+}\right\rangle}}$$\textstyle{{\sf
T}}$$\textstyle{{\sf P}^{y}}$$\textstyle{{\sf Z}^{e}}$$\textstyle{{\sf
X}^{d}}$($d,e,y\in_{R}\\{0,1\\}$){{

Figure 1:  ${\sf T}$-gate gadget for a computation run. Here, an auxiliary
qubit is prepared by the verifier in the state ${\sf X}^{d}{\sf Z}^{e}{\sf
P}^{y}{\sf T}{\left|{+}\right\rangle}$ and sent to the prover. The prover
performs a ${\sf CNOT}$ between the auxiliary register and the data register;
and then measures the data register. Given the measurement result, $c$, the
verifier sends a classical message, $x=a\oplus c\oplus y$ to the prover, who
applies the conditional gate ${\sf P}^{x}$ to the remaining register (which we
now re-label as the data register). The verifier’s key update rule is given in
the figure.

$\textstyle{{\sf X}^{a}{\left|{0}\right\rangle}}$
$\textstyle{\bullet}$Prover$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\sf
P}^{x}}$$\textstyle{{\sf
X}^{d}{\left|{0}\right\rangle}}$Verifier$\textstyle{x\in_{R}\\{0,1\\}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{c=a\oplus
d}$$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{{\sf
X}^{d}}$($d\in_{R}\\{0,1\\}$){{

Figure 2:  ${\sf T}$-gate gadget for an ${\sf X}$-gate test run. The goal here
is to mimic the interaction established in Figure 1, but to perform the
identity operation on the input state ${\left|{0}\right\rangle}$ (up to
encryptions). Here, we include an additional _verification_ that $c=a\oplus
d$.

$\textstyle{{\sf Z}^{b}{\left|{+}\right\rangle}}$
$\textstyle{\bullet}$Prover$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\sf
P}^{x}}$$\textstyle{{\sf X}^{c}{\sf Z}^{b\oplus d\oplus
y}{\left|{+}\right\rangle}}$Verifier$\textstyle{x=y}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{c}$$\textstyle{{\left|{+}\right\rangle}}$$\textstyle{{\sf
P}^{y}}$$\textstyle{{\sf Z}^{d}}$($d,y\in_{R}\\{0,1\\}$){{

Figure 3:  ${\sf T}$-gate gadget for a ${\sf Z}$-gate test run. The goal here
is to mimic the interaction established in Figure 1, but to perform the
identity operation on the input state ${\left|{+}\right\rangle}$ (up to
encryptions)

###  4.4 ${\sf H}$-gate gadget

Performing a ${\sf H}$ gate has the effect of swapping between the ${\sf X}$\-
and ${\sf Z}$-test runs (as well as swapping the role of the ${\sf X}$ and
${\sf Z}$ encryption keys in the computation run). While this is alright if
done in isolation, it does not work if the ${\sf H}$-gate is performed as part
of a larger computation (for instance, a ${\sf CNOT}$-gate could no longer be
performed as given above as the inputs would not, in general, be of the form
${\left|{0}\right\rangle}{\left|{0}\right\rangle}$ (for the ${\sf X}$-test
run) or ${\left|{+}\right\rangle}{\left|{+}\right\rangle}$ (for the ${\sf
Z}$-test run). Our solution is to use the following two identities:

$\displaystyle{\sf H}{\sf P}{\sf H}{\sf P}{\sf H}{\sf P}{\sf H}={\sf H}$ (3)
$\displaystyle{\sf H}{\sf H}{\sf H}{\sf H}=\mathbb{I}\,.$ (4)

Thus we build the gadget so that the prover starts by applying an ${\sf H}$ at
the start. By doing this, we swap the roles of the ${\sf X}$\- and ${\sf
Z}$-tests. For the following ${\sf P}$, we apply twice the gadgets from
Section 4.3 (taking in to account the swapped role for the test runs). The
result is that a ${\sf P}$ is applied in the computation run, while the
identity is applied in the test runs. Now an ${\sf H}$ is applied, which
reverts the roles of the ${\sf X}$\- and ${\sf Z}$-tests. We apply the ${\sf
P}$ again. Continuing in this fashion, the effect is:

  1. 1.

In the computation run (using twice the gadget of Figure 1 for each ${\sf
P}$-gate), the effect is to apply ${\sf H}$ on the input qubit (by Equation
3).

  2. 2.

In the ${\sf X}$-test run (using (twice each time) the gadgets of Figures 3,
2, 3 for the first, second and third ${\sf P}$-gate), the effect is to apply
the identity.

  3. 3.

In the ${\sf Z}$-test run (using (twice each time) gadgets of Figure 2, 3, 2
for the first, second and third ${\sf P}$-gate), the effect is to apply the
identity.

##  5 Correctness of the ${\sf T}$-gate protocol

We give below a step-by-step proof of the correctness of the ${\sf T}$-gate
protocol as given in Figure 1 (Section 4.3). The basic building block is the
circuit identity for an X-teleportation from [ZDC00]. Also of relevance to
this work are the techniques developed by Childs, Leung, and Nielsen [CLN05]
to manipulate circuits that produce an output that is correct _up to known
Pauli corrections_.

We will make use of the following identities which all hold up to an
irrelevant global phase: ${\sf X}{\sf Z}={\sf Z}{\sf X}$, ${\sf P}{\sf Z}={\sf
Z}{\sf P}$, ${\sf P}{\sf X}={\sf X}{\sf Z}{\sf P}$, ${\sf T}{\sf Z}={\sf
Z}{\sf T}$, ${\sf T}{\sf X}={\sf X}{\sf Z}{\sf P}{\sf T}$, ${\sf P}^{2}={\sf
Z}$ and ${\sf P}^{a\oplus b}={\sf Z}^{a\cdot b}{\sf P}^{a+b}$ (for
$a,b\in\\{0,1\\}$).

  1. 1.

We start with the “X-teleportation” of [ZDC00], which is easy to verify
(Figure 4).

$\textstyle{{\left|{\psi}\right\rangle}}$
$\textstyle{c}$$\textstyle{{\left|{+}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\sf
X}^{c}{\left|{\psi}\right\rangle}}$

Figure 4: Circuit identity: “${\sf X}$-teleportation”.

  2. 2.

Then we substitute the input ${\sf X}^{a}{\sf
Z}^{b}{\left|{\psi}\right\rangle}$ for the top wire. We add the gate sequence
${\sf T},{\sf P}^{y},{\sf Z}^{e},{\sf X}^{d},{\sf P}^{a\oplus c\oplus y}$ to
the output (Figure 5). By Figure 4, the outcome is given by ${\sf P}^{a\oplus
c\oplus y}{\sf X}^{d}{\sf Z}^{e}{\sf P}^{y}{\sf T}{\sf X}^{a\oplus c}{\sf
Z}^{b}{\left|{\psi}\right\rangle}$. We apply the identities given above to
simplify this to a Pauli correction (on ${\sf T}$) only:

$\displaystyle{\sf P}^{a\oplus c\oplus y}{\sf X}^{d}{\sf Z}^{e}{\sf P}^{y}{\sf
T}{\sf X}^{a\oplus c}{\sf Z}^{b}$ $\displaystyle={\sf P}^{a\oplus c\oplus
y}{\sf X}^{d}{\sf Z}^{e}{\sf P}^{y}{\sf X}^{a\oplus c}{\sf P}^{a\oplus c}{\sf
Z}^{b\oplus a\oplus c}{\sf T}$ (5) $\displaystyle={\sf P}^{a\oplus c\oplus
y}{\sf X}^{d}{\sf Z}^{e}{\sf P}^{y}{\sf P}^{a\oplus c}{\sf X}^{a\oplus c}{\sf
Z}^{b}{\sf T}$ (6) $\displaystyle={\sf P}^{a\oplus c\oplus y}{\sf P}^{y}{\sf
X}^{d}{\sf Z}^{d\cdot y\oplus e}{\sf P}^{a\oplus c}{\sf X}^{a\oplus c}{\sf
Z}^{b}{\sf T}$ (7) $\displaystyle={\sf P}^{a\oplus c\oplus y}{\sf P}^{y}{\sf
P}^{a\oplus c}{\sf X}^{d}{\sf Z}^{d\cdot(a\oplus c)}{\sf Z}^{d\cdot y\oplus
e}{\sf X}^{a\oplus c}{\sf Z}^{b}{\sf T}$ (8) $\displaystyle={\sf P}^{(a\oplus
c)\oplus y}{\sf P}^{y}{\sf P}^{a\oplus c}{\sf X}^{a\oplus c\oplus d}{\sf
Z}^{d(a\oplus c\oplus y)\oplus b\oplus e}{\sf T}$ (9) $\displaystyle={\sf
Z}^{y\cdot(a\oplus c)}{\sf P}^{a\oplus c}{\sf P}^{y}{\sf P}^{y}{\sf
P}^{a\oplus c}{\sf X}^{a\oplus c\oplus d}{\sf Z}^{d(a\oplus c\oplus y)\oplus
b\oplus e}{\sf T}$ (10) $\displaystyle={\sf X}^{a\oplus c\oplus d}{\sf
Z}^{(a\oplus c\oplus d)\cdot(d\oplus y)\oplus a\oplus b\oplus c\oplus d\oplus
e\oplus y}{\sf T}$ (11) $\displaystyle={\sf X}^{a\oplus c^{\prime}}{\sf
Z}^{(a\oplus c^{\prime})\cdot(d\oplus y)\oplus a\oplus b\oplus
c^{\prime}\oplus e\oplus y}{\sf T}$ (12)

Where above, we let $c^{\prime}\leftarrow c\oplus d$.

$\textstyle{{\sf X}^{a}{\sf Z}^{b}{\left|{\psi}\right\rangle}}$
$\textstyle{c;c^{\prime}\leftarrow c\oplus
d}$$\textstyle{{\left|{+}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\sf
T}}$$\textstyle{{\sf P}^{y}}$$\textstyle{{\sf Z}^{e}}$$\textstyle{{\sf
X}^{d}}$$\textstyle{{\sf P}^{a\oplus c\oplus y}}$$\textstyle{{\sf X}^{a\oplus
c^{\prime}}{\sf Z}^{(a\oplus c^{\prime})\cdot(d\oplus y)\oplus a\oplus b\oplus
c^{\prime}\oplus e\oplus y}{\sf T}{\left|{\psi}\right\rangle}}$

Figure 5: Circuit identity: adding gates to the “${\sf X}$-teleportation”. The
output is computed in Equations 5–12.

  3. 3.

Next, we note that, because diagonal gates commute with control, the circuit
of Figure 5 is equivalent to the one in Figure 6.

$\textstyle{{\sf X}^{a}{\sf Z}^{b}{\left|{\psi}\right\rangle}}$
$\textstyle{c;c^{\prime}\leftarrow c\oplus d}$$\textstyle{{\sf Z}^{e}{\sf
P}^{y}{\sf T}{\left|{+}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\sf
X}^{d}}$$\textstyle{{\sf P}^{a\oplus c\oplus y}}$$\textstyle{{\sf X}^{a\oplus
c^{\prime}}{\sf Z}^{(a\oplus c^{\prime})\cdot(d\oplus y)\oplus a\oplus b\oplus
c^{\prime}\oplus e\oplus y}{\sf T}{\left|{\psi}\right\rangle}}$

Figure 6: Circuit equivalent to Figure 5, since diagonal gates commute with
control.

  4. 4.

We note that the ${\sf X}^{d}$ on the bottom wire _after_ the ${\sf CNOT}$ can
be moved to the bottom wire _before_ the ${\sf CNOT}$, as long as we add an
${\sf X}^{d}$ to the top wire after the ${\sf CNOT}$. (Figure 7).

$\textstyle{{\sf X}^{a}{\sf Z}^{b}{\left|{\psi}\right\rangle}}$
$\textstyle{{\sf X}^{d}}$$\textstyle{c;c^{\prime}\leftarrow c\oplus
d}$$\textstyle{{\sf X}^{d}{\sf Z}^{e}{\sf P}^{y}{\sf
T}{\left|{+}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\sf P}^{a\oplus
c\oplus y}}$$\textstyle{{\sf X}^{a\oplus c^{\prime}}{\sf Z}^{(a\oplus
c^{\prime})\cdot(d\oplus y)\oplus a\oplus b\oplus c^{\prime}\oplus e\oplus
y}{\sf T}{\left|{\psi}\right\rangle}}$

Figure 7: We move the ${\sf X}^{d}$ to the input of the bottom wire.

  5. 5.

Finally, since $c^{\prime}=c\oplus d$, yet the measurement result $c$
undergoes an ${\sf X}^{d}$, these two operations cancel out, and we obtain the
final circuit as in Figure 8.

$\textstyle{{\sf X}^{a}{\sf Z}^{b}{\left|{\psi}\right\rangle}}$
$\textstyle{c}$$\textstyle{{\sf X}^{d}{\sf Z}^{e}{\sf P}^{y}{\sf
T}{\left|{+}\right\rangle}}$$\textstyle{\bullet}$$\textstyle{{\sf P}^{a\oplus
c\oplus y}}$$\textstyle{{\sf X}^{a\oplus c}{\sf Z}^{(a\oplus c)\cdot(d\oplus
y)\oplus a\oplus b\oplus c\oplus e\oplus y}{\sf
T}{\left|{\psi}\right\rangle}}$

Figure 8: We move the ${\sf X}^{d}$ to the input of the bottom wire.

We note that a more direct proof of correctness for Figure 8 is possible, but
that our intermediate Figure 7 is crucial in the proof of soundness.

##  6 Completeness

Suppose $\mathcal{C}$ is a yes-instance. Suppose $P$ follows the protocol
honestly. Then we have the following:

  1. 1.

In the case of a computation run, the output bit, $c_{\text{comp}}$ has the
same distribution as the output bit of $C({\left|{0^{n}}\right\rangle})$, thus
$V$ accepts with probability at least $2/3$.

  2. 2.

In the case of an ${\sf X}$-test run and in the case of a ${\sf Z}$-test run
(by the identities and observations from the previous sections), $V$ accepts
with probability $1$.

Given that each run happens with probability $\frac{1}{3}$, we get that $V$
accepts with probability at least
$\frac{2}{3}+\frac{1}{3}\cdot\frac{2}{3}=\frac{8}{9}$.

###  6.1 Auxiliary qubits for the ${\sf T}$-gate gadget

In the protocol for the ${\sf T}$-gate gadget (Figure 1), we assume the
verifier can produce auxiliary qubits of the form ${\sf X}^{d}{\sf Z}^{e}{\sf
P}^{y}{\sf T}{\left|{+}\right\rangle}$. We now show that this is equivalent to
requiring the prover to generate auxiliary qubits of the form ${\sf Z}^{e}{\sf
P}^{y}{\sf T}{\left|{+}\right\rangle}$, as claimed in Theorem 1. This is true
because, up to global phase:

${\sf X}^{d}{\sf Z}^{e}{\sf P}^{y}{\sf T}{\left|{+}\right\rangle}={\sf
Z}^{e\oplus d}{\sf P}^{y\oplus d}{\sf T}{\left|{+}\right\rangle}$ (13)

The above can be seen easily since, up to global phase, ${\sf X}{\sf
T}{\left|{+}\right\rangle}={\sf Z}{\sf P}{\sf T}{\left|{+}\right\rangle}$, and
${\sf X}{\sf P}={\sf Z}{\sf P}{\sf X}$, thus for the case $d=1$, we get:

$\displaystyle{\sf X}{\sf Z}^{e}{\sf P}^{y}{\sf T}{\left|{+}\right\rangle}$
$\displaystyle={\sf Z}^{e}{\sf X}{\sf P}^{y}{\sf T}{\left|{+}\right\rangle}$
(14) $\displaystyle={\sf Z}^{e}{\sf Z}^{y}{\sf P}^{y}{\sf X}{\sf
T}{\left|{+}\right\rangle}$ (15) $\displaystyle={\sf Z}^{e\oplus y}{\sf
P}^{y}{\sf Z}{\sf P}{\sf T}{\left|{+}\right\rangle}$ (16) $\displaystyle={\sf
Z}^{e\oplus y\oplus 1}{\sf P}^{y+1}{\sf T}{\left|{+}\right\rangle}$ (17)
$\displaystyle={\sf Z}^{e\oplus y\oplus 1}{\sf Z}^{y}{\sf P}^{y\oplus 1}{\sf
T}{\left|{+}\right\rangle}$ (18) $\displaystyle={\sf Z}^{e\oplus 1}{\sf
P}^{y\oplus 1}{\sf T}{\left|{+}\right\rangle}$ (19)

Thus, the verifier chooses a classical $x$ uniformly at random, and if $x=1$,
the verifier re-labels the auxiliary qubits according to Equation 13.

##  7 Soundness

As discussed in Section 1.3, the main idea to prove soundness is to analyze an
entanglement-based version of the Interactive Proof System 1. We present the
EPR-based version (Section 7.1), and show that, for any prover, the
interactive proof systems are indistinguishable (and thus the completeness and
soundness parameters are the same). Then, we analyze a general deviating
prover $P^{*}$ in the EPR-based version and show how to simplify an attack
(Section 7.2). We then analyze the case of a test run (Section 7.4) and of a
computation run (Sections 7.5). This completes the proof of our main theorem
(Theorem 1).

An interesting consequence of the analysis in this section is that it implies
that, if we are willing to have the prover and the verifier share
entanglement, then the protocol reduces to a single round (however, in this
case, the work of the verifier becomes more important; one can wonder if the
verifier is still “almost-classical”). Another interesting observation is that
sequential repetition is not required (parallel repetition suffices), due to
the fact that the analysis makes use of the Pauli twirl (see Section 7.2),
which would also be applicable to the scenario of parallel repetition.

###  7.1 EPR-based protocol

In this version of the quantum prover interactive proof system (Interactive
Proof System 2), _all_ quantum inputs sent by the verifier are half-EPR pairs,
and _all_ classical messages sent by the verifier are random bits. The actions
related to choosing between test and computation runs are done _after_ the
interaction with the server. For the ${\sf T}$-gate, this can be done as shown
in Figures 9, 10 and 11.

$\textstyle{{\sf X}^{a}{\sf Z}^{b}{\left|{\psi}\right\rangle}}$
$\textstyle{\bullet}$Prover$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\sf
P}^{x}}$$\textstyle{{\sf X}^{a\oplus c}{\sf Z}^{(a\oplus c)\cdot(d\oplus
y)\oplus a\oplus b\oplus c\oplus e\oplus y}{\sf
T}{\left|{\psi}\right\rangle}}$$\textstyle{x\in_{R}\\{0,1\\}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{c}$Verifier$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{{\sf
H}}$$\textstyle{\bullet}$($d\in_{R}\\{0,1\\},y=a\oplus c\oplus
x$)$\textstyle{{\left|{0}\right\rangle}}$ $\textstyle{{\sf
T}}$$\textstyle{{\sf P}^{y\oplus d}}$$\textstyle{{\sf Z}^{d}}$$\textstyle{{\sf
H}}$$\textstyle{e}${{

Figure 9: Entanglement-based protocol for a ${\sf T}$-gate (computation run).
This protocol performs the same computation as the protocol in Figure 1, as
can be seen via Equation LABEL:eqn:relabellin. The output is obtained from the
output of Figure 1 by using $y=a\oplus c\oplus x$. The circuit in the dashed
box prepares an EPR-pair.

---
$\textstyle{{\sf X}^{a}{\left|{0}\right\rangle}}$
$\textstyle{\bullet}$Prover$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\sf
P}^{x}}$$\textstyle{{\sf
X}^{d}{\left|{0}\right\rangle}}$$\textstyle{x\in_{R}\\{0,1\\}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{c=a\oplus
d}$Verifier$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{{\sf
H}}$$\textstyle{\bullet}$$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{d}${{

Figure 10: Entanglement-based protocol for an ${\sf T}$-gate (${\sf X}$-test
run). This protocol performs the same computation as the protocol in Figure 2.
The circuit in the dashed box prepares an EPR-pair. As in Figure 2, we include
an additional _verification_ that $c=a\oplus d$.

---
$\textstyle{{\sf Z}^{b}{\left|{+}\right\rangle}}$
$\textstyle{\bullet}$Prover$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{{\sf
P}^{x}}$$\textstyle{{\sf X}^{c}{\sf Z}^{b\oplus d\oplus
y}{\left|{+}\right\rangle}}$$\textstyle{x\in_{R}\\{0,1\\}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{c}$Verifier$\textstyle{{\left|{0}\right\rangle}}$$\textstyle{{\sf
H}}$$\textstyle{\bullet}$($y=x$)$\textstyle{{\left|{+}\right\rangle}}$
$\textstyle{{\sf P}^{y}}$$\textstyle{{\sf H}}$$\textstyle{d}${{

Figure 11: Entanglement-based protocol for an ${\sf T}$-gate (${\sf Z}$-test
run). This protocol performs the same computation as the protocol in Figures
3. The circuit in the dashed box prepares an EPR-pair.

We therefore define $V_{\text{EPR}}$ as a verifier that delays all choices
until after the Prover has returned all messages (_i.e._ as the verifier in
Interactive Proof System 2). Clearly, no prover $P^{*}$ can distinguish
between an interaction with $V$ or $V_{\text{EPR}}$. This is because we can
first fix $x$ to be random in the ${\sf T}$-gate gadget in Interactive Proof
System 1. This determines $y$, but the operation, ${\sf P}^{y}$, that is
conditionned on $y$ can be formally delayed until _after_ the interaction
without changing the prover’s view (via the EPR-picture).

Thus the soundness parameter is the same for both protocols. Furthermore,
clearly the completeness parameter is unchanged. From now on, we therefore
focus on establishing the soundness parameter for Interactive Proof System 2.

Interactive Proof System 2 Verifiable quantum computation with trusted
auxiliary states- EPR version

Let $\mathcal{C}$ be given as an $n$-qubit quantum circuit in the universal
gateset ${\sf X},{\sf Z},{\sf CNOT},{\sf H},{\sf T}$.

  1. 1.

The verifier prepares ${\left|{\Phi^{+}}\right\rangle}^{\otimes n}$ and sends
half of each pair to the prover. These registers are identified with the
_input_ registers.

  2. 2.

For each auxiliary qubit required in the ${\sf H}$\- and ${\sf T}$-gate
gadgets, the verifier prepares ${\left|{\Phi^{+}}\right\rangle}$ and sends
half of each pair to the prover.

  3. 3.

The prover executes the gate gadgets. The verifier records the classical
communication and responds with random classical bits (when required).

  4. 4.

The prover returns a single bit of output, $c$ to the verifier.

  5. 5.

The verifier randomly chooses to execute one of the following three runs (but
does not inform the prover of this choice).

    1. A.

Computation Run

      1. A.1.

Measure the remaining input register halves in the computational basis. Take
the initial ${\sf X}$-encryption key to be the measurement outcomes (set the
${\sf Z}$-key to 0).

      2. A.2.

For each gate $G$ in $\mathcal{C}$: perform the key updates for the ${\sf
X},{\sf Z}$ , ${\sf CNOT}$ and ${\sf H}$ gates. For the ${\sf T}$ gadget,
taking into account the classical message received and sent in Step 2, perform
the measurement and key update rules for the ${\sf T}$-gadget (Figure 9).

      3. A.3.

$V$ decrypts the output bit $c$; let the result be $c_{\text{comp}}$. $V$
accepts if $c_{\text{comp}}=0$; otherwise reject.

    2. B.

${\sf X}$-test Run

      1. B.1.

Measure the remaining input register halves in the computational basis. Take
the initial ${\sf X}$-encryption key to be the measurement outcomes (set the
${\sf Z}$-key to 0).

      2. B.2.

For each gate $G$ in $\mathcal{C}$: perform the key updates for the ${\sf
X},{\sf Z}$, ${\sf CNOT}$ and ${\sf H}$ gates. For the ${\sf T}$ gadget,
taking into account the classical message received and sent in Step 2, perform
the measurement, key update rules and tests for the ${\sf T}$-gadget (Figure
10).

      3. B.3.

$V$ decrypts the output bit $c$; let the result be $c_{\text{comp}}$. $V$
accepts if $c_{\text{comp}}=0$ _and_ if no errors were detected in step
5(B.)B.2.; otherwise reject.

    3. C.

${\sf Z}$-test Run

      1. C.1.

Measure the remaining input register halves in the Hadamard basis. Take the
initial ${\sf Z}$-encryption key to be the measurement outcomes (set the ${\sf
X}$-key to 0).

      2. C.2.

For each gate $G$ in $\mathcal{C}$: perform the key updates for the ${\sf
X},{\sf Z}$, ${\sf CNOT}$ and ${\sf H}$ gates. For the ${\sf T}$ gadget,
taking into account the classical message received and sent in Step 2, perform
the measurement, key update rules and tests for the ${\sf T}$-gadget (Figure
11)

      3. C.3.

$V$ accepts if no errors were detected in step 5(C.)C.2.; otherwise reject.

###  7.2 Simplifying a general attack

We now consider a general deviating prover $P^{*}$ interacting with
$V_{\text{EPR}}$. First, we make a simplifying assumption that $P^{*}$ does
not perform any measurements (and instead returns single qubits to $V$, who
then performs the measurement). Next, we show that, without loss of
generality, we can assume that the prover’s actions are the honest ones,
followed by a general attack (on the measured and traced-out qubits). In order
to see this, for a $k$-round protocol (involving $k$ rounds of classical
interaction), define $P$’s actions at round $i$ by $\Phi_{i}C_{i}$, where
$C_{i}$ acts on the qubits used in the computation, as well as the classical
bit received in round $i$, and is the honest application of the prover’s
circuit, while $\Phi_{i}$ is a general deviating map acting on the classical
bit received in round $i$, the output registers of $C_{i}$ as well as a
private memory register. (Recall that there are no measurements at this point
— V does the measurement).

Thus the actions of a general prover $P^{*}$ can be described as:

$\Phi_{r}C_{r}\ldots\Phi_{1}C_{1}\Phi_{0}C_{0}\,.$ (20)

Since $C_{0},\ldots,C_{r}$ are unitary, we can re-write Equation 20 as:

$\displaystyle\Phi_{r}C_{r}\ldots\Phi_{3}C_{3}\Phi_{2}C_{2}\Phi_{1}C_{1}\Phi_{0}C_{0}$
$\displaystyle=\Phi_{r}C_{r}\ldots\Phi_{3}C_{3}\Phi_{2}C_{2}(\Phi_{1}C_{1}\Phi_{0}{C_{1}}^{*})C_{1}C_{0}$
(21)
$\displaystyle=\Phi_{r}C_{r}\ldots\Phi_{3}C_{3}(\Phi_{2}C_{2}\Phi_{1}C_{1}\Phi_{0}{C_{1}}^{*}{C_{2}}^{*})C_{2}C_{1}C_{0}$
(22)
$\displaystyle=\Phi_{r}C_{r}\ldots(\Phi_{3}C_{3}\Phi_{2}C_{2}\Phi_{1}C_{1}\Phi_{0}{C_{1}}^{*}{C_{2}}^{*}C_{3}^{*})C_{3}C_{2}C_{1}C_{0}$
(23)
$\displaystyle=(\Phi_{r}C_{r}\ldots\Phi_{3}C_{3}\Phi_{2}C_{2}\Phi_{1}C_{1}\Phi_{0}{C_{1}}^{*}{C_{2}}^{*}C_{3}^{*}\ldots
C_{r}^{*})C_{r}\ldots C_{3}C_{2}C_{1}C_{0}$ (24)

Thus, by denoting a general attack by
$\Phi=\Phi_{r}C_{r}\ldots\Phi_{3}C_{3}\Phi_{2}C_{2}\Phi_{1}C_{1}\Phi_{0}{C_{1}}^{*}{C_{2}}^{*}C_{3}^{*}\ldots
C_{r}^{*}$, and the map corresponding to the honest prover as $C=C_{r}\ldots
C_{3}C_{2}C_{1}C_{0}$, we get that without loss of generality, we can assume
that the prover’s actions are the honest ones, followed by a general attack:

$\Phi C$ (25)

Taking $E_{k}$ to be Kraus terms associated with $\Phi$, and supposing a total
of $m$ qubit registers are involved, we get that the system after interaction
with $P^{*}$, where the initial state is
${\left|{\Phi^{+}}\right\rangle}{\left\langle{\Phi^{+}}\right|}^{\otimes
m}=\frac{1}{2^{m}}\sum_{i,j=0}^{2^{m}-1}{\left|{ii}\right\rangle}{\left\langle{jj}\right|}$
(here, we include the classical random bits, as they are uniformly random and
therefore we can represent them as maximally entangled states), and where the
verifier has not yet performed the gates and measurements, can be described
as:

$\frac{1}{2^{m}}\sum_{k}\sum_{i,j}(I\otimes
E_{k}C){\left|{ii}\right\rangle}{\left\langle{jj}\right|}(I\otimes
C^{*}E_{k}^{*})$ (26)

For a fixed $k$, we write $E_{k}$ and $E_{k}^{*}$ in the Pauli basis:
$E_{k}=\sum_{Q}\alpha_{Q}Q$ and
$E_{k}^{*}=\sum_{Q^{\prime}}\alpha_{Q^{\prime}}^{*}Q^{\prime}$ (to simplify
notation, we assume throughout that $Q$, $Q^{\prime}$ ranges over
$\mathbb{P}_{m}$). For such an $E_{k}$, we now consider the probability of
acceptance, depending on the type of run (the following analysis can be
applied to each operator in the Kraus decomposition).

###  7.3 Conventions and definitions

In addition to the convention of representing an attack as in Equation 26, in
the following Sections 7.4–7.5, we use the following conventions:

  1. 1.

The circuit $C$ that we consider is already “compiled” in terms of the ${\sf
H}$ gates as in Section 4.4 (the identity ${\sf H}={\sf H}{\sf P}{\sf H}{\sf
P}{\sf H}{\sf P}{\sf H}$ is already applied).

  2. 2.

The input prepared by the verifier (in step 5(A.)A.1., 5(B.)B.1. or 5(C.)C.1.
of Protocol 2) given as
$\sum_{P}P{\left|{\psi}\right\rangle}{\left\langle{\psi}\right|}P^{*}$ (an
encrypted version of ${\left|{\psi}\right\rangle}{\left\langle{\psi}\right|}$,
where ${\left|{\psi}\right\rangle}$ is either ${\left|{0}\right\rangle}$ or
${\left|{+}\right\rangle}$).

  3. 3.

The number of ${\sf T}$-gate gadgets is $t$ (each such gadget uses two
auxiliary qubits—one representing an auxiliary quantum bit, and one
representing a classical bit $x$), and the number of qubits in the computation
is $n$, thus we have $m=2t+n$.

  4. 4.

In the ${\sf T}$-gate gadget, the auxiliary wire is swapped with the measured
wire immediately before the measurement; this way, we may picture that only
auxiliary qubits are measured as part of the computation, and that the data
registers for the input ${\left|{\psi}\right\rangle}$ represent the
computation wires throughout.

  5. 5.

Given the system as in Equation 26, we suppose that the first ${\sf T}$-gate
gadget uses the first EPR pair as auxiliary quantum bit, and the second EPR
pair as a qubit representing the classical bit (and so on for the following
${\sf T}$-gadgets). The last $n$ EPR pairs are the data qubits, and we suppose
that at the end of the protocol, the last data qubit is the one that is
measured, representing the output.

  6. 6.

Normalization constants are omitted when they are clear from context.

Finally, we define _benign_ and _non-benign_ Pauli attacks, based on their
effect on the protocol: as we will see, benign attacks have no effect on the
acceptance probability (because all qubits are either traced-out or measured
in the computational basis). However, non-benign attacks may influence the
acceptance probability.

######  Definition 3.

For a fixed Pauli $P\in\mathbb{P}_{m}$, we call it _benign_ if $P\in B_{t,n}$,
where $B_{t,n}$ is the set of Paulis acting on $m=2t+n$ qubits, such that the
_measured_ qubits in the protocol are acted on only by a gate in $\\{I,{\sf
Z}\\}$. Using the above conventions, this means that $B_{t,n}=\\{\\{\\{I,{\sf
Z}\\}\mathbb{P}\\}^{t}\mathbb{P}_{n-1}\\{I,{\sf Z}\\}\\}$. A Pauli $P$ is
called _non-benign_ if at least one _measured_ qubit in the protocol is acted
on only by a gate in $\\{{\sf X},{\sf Y}\\}$. In analogy to the set of benign
Paulis, we denote the set of non-benign Paulis acting on $m=2t+n$ qubits as
$B^{\prime}_{t,n}$.

###  7.4 In the case of a test run

Based on the preliminaries of Sections 7.2 and 7.3, we now bound the
probability of acceptance of the test runs, by describing the effect of the
attack on the entire system, and considering which attacks are detected by the
test runs (essentially, we show in Lemma 2 that all non-benign attacks are
detected by one of the test runs).

######  Lemma 2.

Consider the Interactive Proof System 2 for a circuit $C$ on $n$ qubits and
with $t$ ${\sf T}$-gate gadgets, with attack $E_{k}=\sum_{Q}\alpha_{Q}Q$. Let
$B^{\prime}_{t,n}$ be the set of non-benign attacks. Then with the following
probability, one of the test runs will reject:

$\sum_{Q\in B^{\prime}_{t,n}}\lvert\alpha_{Q}\rvert^{2},$ (27)

###### Proof.

In the case of a test run, the effect of $V_{EPR}$’s operations, (consisting
in gates and measurements) is to prepare an encrypted version of an input
state ${\left|{\phi}\right\rangle}{\left|{\psi}\right\rangle}$ which is
${\left|{\psi}\right\rangle}={\left|{0}\right\rangle}^{n}$ for the ${\sf
X}$-test run or ${\left|{\psi}\right\rangle}={\left|{+}\right\rangle}^{n}$ in
the ${\sf Z}$-test run, together with ${\left|{\phi}\right\rangle}$ consisting
in auxiliary qubits, which are a tensor product of systems
${\left|{0}\right\rangle}$ and ${\sf P}^{y}{\left|{+}\right\rangle}$ (the
choice of which state depending on the number of ${\sf H}$-gates that have
been applied so far, as per the ${\sf H}$-gate construction in Section 4.4).
Furthermore, we can assume that the classical random bits are obtained by a
computational basis measurement on $V_{EPR}$’s portion of the maximally
entangled states and included as encryptions of ${\left|{0}\right\rangle}$ in
${\left|{\phi}\right\rangle}$.

Thus $V$’s operations can be seen as the preparation of
${\left|{\phi}\right\rangle}{\left|{\psi}\right\rangle}$, up to some uniformly
distributed random Pauli operator $P$ on the entire space of
${\left|{\phi}\right\rangle}{\left|{\psi}\right\rangle}$. Representing $C$ as
the honest prover’s operations, the system is thus described as:

$\sum_{P}E_{k}CP({\left|{\phi}\right\rangle}{\left\langle{\phi}\right|}\otimes{\left|{\psi}\right\rangle}{\left\langle{\psi}\right|})P^{*}C^{*}E_{k}^{*}\,,$
(28)

where $P$ ranges over all Pauli operators $P\in\mathbb{P}_{m}$. Recall that we
have assumed that the verifier performs the measurement in place of the
prover; we can further delay this measurement until _after_ the verifier has
applied the decryption operation. In this case, the decryption key $\tilde{P}$
is computed such that $CP=\tilde{P}C$. Thus after decryption, the system is:

$\sum_{P}\tilde{P}^{*}E_{k}CP({\left|{\phi}\right\rangle}{\left\langle{\phi}\right|}\otimes{\left|{\psi}\right\rangle}{\left\langle{\psi}\right|})P^{*}C^{*}E_{k}^{*}\tilde{P}=\sum_{P}\tilde{P}^{*}E_{k}\tilde{P}C({\left|{\phi}\right\rangle}{\left\langle{\phi}\right|}\otimes{\left|{\psi}\right\rangle}{\left\langle{\psi}\right|})C^{*}\tilde{P}^{*}E_{k}^{*}\tilde{P}\,.$
(29)

The map $P\mapsto\tilde{P}$ is a bijection, hence we can rewrite Equation 29
as:

$\sum_{P}P^{*}E_{k}PC({\left|{\phi}\right\rangle}{\left\langle{\phi}\right|}\otimes{\left|{\psi}\right\rangle}{\left\langle{\psi}\right|})C^{*}P^{*}E_{k}^{*}P\,.$
(30)

Using the Pauli decomposition for $E_{k}$, we can write this as:

$\sum_{Q,Q^{\prime}}\sum_{P}\alpha_{Q}\alpha_{Q^{\prime}}^{*}P^{*}QPC({\left|{\phi}\right\rangle}{\left\langle{\phi}\right|}\otimes{\left|{\psi}\right\rangle}{\left\langle{\psi}\right|})C^{*}P^{*}{Q^{\prime}}P\,.$
(31)

By Lemma 1 (Pauli twirl), Equation 31 simplifies to:

$\sum_{Q}|\alpha_{Q}|^{2}QC({\left|{\phi}\right\rangle}{\left\langle{\phi}\right|}\otimes{\left|{\psi}\right\rangle}{\left\langle{\psi}\right|})C^{*}Q^{*}\,.$
(32)

Let $Q\in B^{\prime}_{t,n}$. Then we claim that at least one of the test runs
(an ${\sf X}$\- or ${\sf Z}$-test run) rejects. This is clear because each
time a qubit is measured, it will be in the state ${\left|{0}\right\rangle}$
in exactly one of the ${\sf X}$\- or ${\sf Z}$-test runs (recall, we have
stripped away the encryption; also, according to the honest prover’s actions
$C$, if an even number of ${\sf H}$ gates are applied, the ${\sf X}$-test run
will have auxiliary qubit ${\left|{0}\right\rangle}$; if an odd number of
${\sf H}$ gates are applied, then the ${\sf Z}$-test run will have auxiliary
qubit ${\left|{0}\right\rangle}$). Thus, the verifier always detects a non-
benign attack in one of the test runs. Thus with probability $\sum_{Q\in
B^{\prime}_{t,n}}\lvert\alpha_{Q}\rvert^{2}$, one of the test runs rejects. ∎

###  7.5 In the case of a computation run

Still using the notation of Sections 7.2 and 7.3, we now analyze soundness in
the case of a computation run. First, we determine the effect of a bit flip on
the measured qubit in the ${\sf T}$-gate gadget (Section 7.5.1), then we do
the analysis for the case that the computation run consists in a single ${\sf
T}$-gadget (Section 7.5.2); this is extended to full generality in Section
7.5.3.

####  7.5.1 Effect of a bit flip on a measured qubit

In Lemma 3, we establish the effect of a bit flip on the measured qubit in the
${\sf T}$-gate gadget.

######  Lemma 3.

The error induced by an ${\sf X}$-gate on the measured qubit in the ${\sf
T}$-gate gadget in Figure 9 to introduce an extra ${\sf Z}^{a\oplus c\oplus
d\oplus x}{\sf P}$ on the output.

###### Proof.

We determine below the effect of an ${\sf X}$-gate on the measured qubit in
Figure 1 to be the application of an extra ${\sf Z}^{d\oplus y}{\sf P}$ on the
output. Since $y=a\oplus c\oplus x$ in Figure 9, this yields the effect of
applying ${\sf Z}^{a\oplus c\oplus d\oplus x}{\sf P}$ on the output.

An ${\sf X}$-gate on the measured qubit in Figure 1 will cause the bottom wire
to receive the correction ${\sf P}^{a\oplus c\oplus y\oplus 1}$ (instead of
${\sf P}^{a\oplus c\oplus y}$). Since ${\sf P}^{a\oplus c\oplus y\oplus
1}={\sf P}{\sf Z}^{a\oplus c\oplus y}{\sf P}^{a\oplus c\oplus y}$, we use and
revise the calculation from Equations 5–12, as follows:

$\displaystyle{\sf P}^{a\oplus c\oplus y\oplus 1}{\sf X}^{d}{\sf Z}^{e}{\sf
P}^{y}{\sf T}{\sf X}^{a\oplus c}{\sf Z}^{b}$ $\displaystyle={\sf P}{\sf
Z}^{a\oplus c\oplus y}{\sf P}^{a\oplus c\oplus y}{\sf X}^{d}{\sf Z}^{e}{\sf
P}^{y}{\sf T}{\sf X}^{a\oplus c}{\sf Z}^{b}$ (33) $\displaystyle={\sf P}{\sf
Z}^{a\oplus c\oplus y}{\sf X}^{a\oplus c\oplus d}{\sf Z}^{(a\oplus c\oplus
d)\cdot(d\oplus y)\oplus a\oplus b\oplus c\oplus d\oplus e\oplus y}{\sf T}$
(34) $\displaystyle={\sf X}^{a\oplus c\oplus d}{\sf Z}^{(a\oplus c\oplus
d)\cdot(d\oplus y)\oplus a\oplus b\oplus c\oplus d\oplus e\oplus y}{\sf
Z}^{a\oplus c\oplus y}{\sf Z}^{a\oplus c\oplus d}{\sf P}{\sf T}$ (35)
$\displaystyle={\sf X}^{a\oplus c\oplus d}{\sf Z}^{(a\oplus c\oplus
d)\cdot(d\oplus y)\oplus a\oplus b\oplus c\oplus d\oplus e\oplus y}({\sf
Z}^{d\oplus y}{\sf P}){\sf T}\qed$ (36)

####  7.5.2 The ${\sf T}$-gate protocol under attack

Here, we study the effect of an attack $E_{k}=\sum_{Q}\alpha_{Q}Q$,
$E_{k}^{*}=\sum_{Q^{\prime}}\alpha_{Q^{\prime}}^{*}Q^{\prime}$, considering
the case of a single-qubit input and of a single ${\sf T}$ protocol; the
general case (Section 7.5.3) follows this analysis closely.

Consider an attack on the protocol as given in Figure 9, and suppose the
verifier applies the corrections conditional on $c$ coherently, as well as the
decryption coherently (without performing a measurement), but otherwise the
verifier performs the measurements on the half-EPR pairs (so that $a,b,d,e,x$
are all classical, uniformly random bits). According to Figure 7, we can see
the attacks as being applied before the measurement and decryption on the top
wire(this allows the application of the Pauli twirl).

Given that we are analyzing a single ${\sf T}$-gate gadget, we note that each
Pauli $Q,Q^{\prime}$ in the attack consists in three single-qubits Paulis:
$Q=Q_{1}\otimes Q_{2}\otimes
Q_{3},Q^{\prime}={Q^{\prime}}_{1}\otimes{Q^{\prime}}_{2}\otimes{Q^{\prime}}_{3}$.
According to our convention, the Paulis $Q_{1}$ and ${Q^{\prime}}_{1}$ act on
the measured qubit in Figure 9, the Paulis $Q_{2}$ and ${Q^{\prime}}_{2}$ acts
on the traced-out qubit that represents the classical bit $x$ (which we
represent as ${\sf X}^{x}{\left|{0}\right\rangle}$) and the Paulis $Q_{3}$ and
${Q^{\prime}}_{3}$ act on the output qubit (also eventually measured).

Let $E$ be the error on the output induced by an ${\sf X}$ on the top wire in
Figure 9; by Lemma 3, $E={\sf Z}^{a\oplus c\oplus d\oplus x}{\sf P}$. For a
Pauli $Q\in\mathbb{P}_{1}$, let $\delta_{Q}=0$ if $Q\in\\{I,{\sf Z}\\}$ and
$\delta_{Q}=1$ otherwise. Ignoring the normalization, for a fixed $k$, the
system becomes:

$\sum_{Q,Q^{\prime}}\alpha_{Q}\alpha_{{Q^{\prime}}^{*}}\sum_{a,b,c,d,e,x\in\\{0,1\\}}{\sf
X}^{d}Q_{1}{\sf X}^{d}{\left|{c}\right\rangle}{\left\langle{c}\right|}{\sf
X}^{d}{{Q^{\prime}}_{1}}{\sf X}^{d}\otimes Q_{2}{\sf
X}^{x}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x}{{Q^{\prime}}_{2}}\otimes\\\ {\sf X}^{a\oplus c}{\sf Z}^{(a\oplus
c)\cdot(d\oplus y)\oplus a\oplus b\oplus c\oplus e\oplus y}Q_{3}{\sf
X}^{a\oplus c}{\sf Z}^{(a\oplus c)\cdot(d\oplus y)\oplus a\oplus b\oplus
c\oplus e\oplus y}E^{\delta_{Q_{1}}}{\sf T}{\left|{0}\right\rangle}\\\
{\left\langle{0}\right|}{\sf T}E^{\delta_{Q^{\prime}_{1}}}{\sf X}^{a\oplus
c}{\sf Z}^{(a\oplus c)\cdot(d\oplus y)\oplus a\oplus b\oplus c\oplus e\oplus
y}({Q^{\prime}}_{3}){\sf X}^{a\oplus c}{\sf Z}^{(a\oplus c)\cdot(d\oplus
y)\oplus a\oplus b\oplus c\oplus e\oplus y}$ (37)

Since $a$ and $b$ appear only on the last register, we can re-write the above
as:

$\sum_{Q,Q^{\prime}}\alpha_{Q}\alpha_{{Q^{\prime}}^{*}}\sum_{c,d,e,x\in\\{0,1\\}}{\sf
X}^{d}Q_{1}{\sf X}^{d}{\left|{c}\right\rangle}{\left\langle{c}\right|}{\sf
X}^{d}{{Q^{\prime}}_{1}}{\sf X}^{d}\otimes Q_{2}{\sf
X}^{x}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x}{{Q^{\prime}}_{2}}\otimes\\\ \sum_{a,b}{\sf X}^{a}{\sf Z}^{b}{\sf
X}^{f(a,b,c,d,x)}{\sf Z}^{g(a,b,c,d,x)}Q_{3}{\sf X}^{f(a,b,c,d,x)}{\sf
Z}^{g(a,b,c,d,x)}{\sf X}^{a}{\sf Z}^{b}E^{\delta_{Q_{1}}}{\sf
T}{\left|{0}\right\rangle}\\\ {\left\langle{0}\right|}{\sf
T}E^{\delta_{Q^{\prime}_{1}}}{\sf X}^{a}{\sf Z}^{b}{\sf X}^{f(a,b,c,d,x)}{\sf
Z}^{g(a,b,c,d,x)}({Q^{\prime}}_{3}){\sf X}^{f(a,b,c,d,x)}{\sf
Z}^{g(a,b,c,d,x)}{\sf X}^{a}{\sf Z}^{b},$ (38)

Where $f$ and $g$ are functions of $a,b,c,d,x$ that can be derived from the
previous equation. We apply the Pauli twirl (Lemma 1) to the last register.
The cross-terms cancel out, and the decryption is applied. Letting
$\alpha_{Q}=\alpha_{Q_{1}}\alpha_{Q_{2}}\alpha_{Q_{3}}$ (and similarly for
$\alpha_{Q}^{\prime}$), we get:

$\sum_{Q_{1},Q_{1}^{\prime},Q_{2},Q_{2}^{\prime},Q_{3}}\alpha_{Q_{1}}\alpha_{Q_{2}}\alpha_{{Q^{\prime}}_{1}^{*}}\alpha_{{Q^{\prime}}_{2}^{*}}\lvert\alpha_{Q_{3}}\rvert^{2}\sum_{c,d,x\in\\{0,1\\}}{\sf
X}^{d}Q_{1}{\sf X}^{d}{\left|{c}\right\rangle}{\left\langle{c}\right|}{\sf
X}^{d}{{Q^{\prime}}_{1}}{\sf X}^{d}\otimes Q_{2}{\sf
X}^{x}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x}{{Q^{\prime}}_{2}}\otimes\\\ Q_{3}E^{\delta_{Q_{1}}}{\sf
T}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
T}E^{\delta_{Q^{\prime}_{1}}}Q_{3}$ (39)

Since the second register is traced out, we can assume it is decrypted before
the trace-out; we can also move the quantifier over $x$ to the second
register:

$\sum_{Q_{1},Q_{1}^{\prime},Q_{2},Q_{2}^{\prime},Q_{3}}\alpha_{Q_{1}}\alpha_{Q_{2}}\alpha_{{Q^{\prime}}_{1}^{*}}\alpha_{{Q^{\prime}}_{2}^{*}}\lvert\alpha_{Q_{3}}\rvert^{2}\sum_{c,d\in\\{0,1\\}}{\sf
X}^{d}Q_{1}{\sf X}^{d}{\left|{c}\right\rangle}{\left\langle{c}\right|}{\sf
X}^{d}{{Q^{\prime}}_{1}}{\sf X}^{d}\otimes\\\ \sum_{x\in\\{0,1\\}}{\sf
X}^{x}Q_{2}{\sf X}^{x}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x}{{Q^{\prime}}_{2}}{\sf X}^{x}\otimes Q_{3}E^{\delta_{Q_{1}}}{\sf
T}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
T}E^{\delta_{Q^{\prime}_{1}}}Q_{3}$ (40)

Next, we apply the Pauli twirl to the first and second registers to get:

$\sum_{Q_{1},Q_{2},Q_{3}}\lvert\alpha_{Q_{1}}\rvert^{2}\lvert\alpha_{Q_{2}}\rvert^{2}\lvert\alpha_{Q_{3}}\rvert^{2}\sum_{c\in\\{0,1\\}}Q_{1}{\left|{c}\right\rangle}{\left\langle{c}\right|}Q_{1}\otimes
Q_{2}{\left|{0}\right\rangle}{\left\langle{0}\right|}{Q_{2}}\otimes
Q_{3}E^{\delta_{Q_{1}}}{\sf
T}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
T}E^{\delta_{Q_{1}}}{Q_{3}}$ (41)

From the above, it is clear that the outcome after measuring the first and
last register (and tracing out the second register) is the correct computation
(_i.e._ a computational basis measurement on ${\sf
T}{\left|{0}\right\rangle}$) if $Q=Q_{1}\otimes Q_{2}\otimes Q_{3}$ is benign.
Thus the outcome is correct with probability at least $\sum_{Q\in
B_{1,1}}\lvert\alpha_{Q}\rvert^{2}$.

####  7.5.3 General analysis for a computation run

We now bound the acceptance probability in the case of a computation run. In
analogy to the case of the test runs, we show that an attack $E_{k}$ can be
broken down into a convex combination of Pauli attacks; this is possible
essentially because, from the provers’s point of view, the system is
encrypted. More formally, we follow the lines of the case analyzed in Section
7.5.2, and write down an expression for the system after the verifier’s
coherent operations. Thanks to the Pauli twirl, we can simplify this
expression considerably. Then, we show how to bound the acceptance probability
of benign attacks (no such bound is possible for non-benign attacks), which
gives us the desired result.

######  Lemma 4.

Consider the Interactive proof system 2 for a circuit $C$ on $n$ qubits and
with $t$ ${\sf T}$-gate gadgets, with attack $E_{k}=\sum_{Q}\alpha_{Q}Q$. Let
$B_{t,n}$ be the set of benign attacks, and $B^{\prime}_{t,n}$ be the set of
non-benign attacks. Then the probability of acceptance for a computation run
is at most:

$p\sum_{Q\in B_{t,n}}\lvert\alpha_{Q}\rvert^{2}+\sum_{Q\in
B^{\prime}_{t,n}}\lvert\alpha_{Q}\rvert^{2}$ (42)

Where
$p=\left\lVert({\left|{0}\right\rangle}{\left\langle{0}\right|}\otimes\mathbb{I}_{n-1})C{\left|{0^{n}}\right\rangle}\right\rVert^{2}$
is the probability that we observe “0” as a results of a computational basis
measurement of the $n^{\text{th}}$ output qubit, obtained by evaluating $C$ on
input ${\left|{0^{n}}\right\rangle}$.

###### Proof.

The proof is a generalization of the techniques developed in Section 7.5.2.
Following the conventions of Section 7.3, we ignore normalization constants.
Let $E$ be the error on the output induced by an ${\sf X}$ on the top wire in
Figure 9; by Lemma 3, $E={\sf Z}^{a\oplus c\oplus d\oplus x}{\sf P}$. For a
Pauli $Q\in\mathbb{P}_{1}$, let $\delta_{Q}=0$ if $Q\in\\{I,{\sf Z}\\}$ and
$\delta_{Q}=1$ otherwise. We let $Q=P_{1}\otimes Q_{1}\otimes P_{2}\otimes
Q_{2}\otimes\ldots\otimes\P_{t}\otimes Q_{t}\otimes R$, with
$P_{i},Q_{i}\in\mathbb{P}_{1}$ and $R\in\mathbb{P}_{n}$, and we decompose the
target circuit $C$ as $C=C_{t}{\sf T}\ldots{\sf T}C_{1}{\sf T}C_{0}$, where
each $C_{i}$ is a Clifford group circuit.

As Section 7.5.2, we use the identity from Figure 7. For a fixed $k$, the
system after the attack, and the verifier’s coherent corrections is thus:

$\sum_{Q,Q^{\prime}}\alpha_{Q}\alpha_{{Q^{\prime}}^{*}}\biggl{(}\sum_{c_{1},d_{1},e_{1},x_{1}\in\\{0,1\\}}{\sf
X}^{d_{1}}P_{1}{\sf
X}^{d_{1}}{\left|{c_{1}}\right\rangle}{\left\langle{c_{1}}\right|}{\sf
X}^{d_{1}}{{P^{\prime}}_{1}}{\sf X}^{d_{1}}\otimes Q_{1}{\sf
X}^{x_{1}}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x_{1}}{Q^{\prime}}_{1}\otimes\ldots\otimes\\\
\sum_{c_{t},d_{t},e_{t},x_{t}\in\\{0,1\\}}{\sf X}^{d_{t}}P_{t}{\sf
X}^{d_{t}}{\left|{c_{t}}\right\rangle}{\left\langle{c_{t}}\right|}{\sf
X}^{d_{t}}{{P^{\prime}}_{t}}{\sf X}^{d_{t}}\otimes Q_{t}{\sf
X}^{x_{t}}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x_{t}}{Q^{\prime}}_{t}\otimes\\\ \sum_{P\in\mathbb{P}_{n}}{\sf
Z}^{g(P,c_{i},d_{i},x_{i})}{\sf X}^{f(P,c_{i},d_{i},x_{i})}PRP{\sf
X}^{f(P,c_{i},d_{i},x_{i})}{\sf
Z}^{g(P,c_{i},d_{i},x_{i})}C_{t}E^{\delta_{t}}{\sf T}_{t}\ldots
E^{\delta_{Q_{2}}}{\sf T}_{2}C_{1}E^{\delta_{Q_{1}}}{\sf
T}_{1}C_{0}{\left|{0^{n}}\right\rangle}\\\
{\left\langle{0^{n}}\right|}{C_{0}}^{*}{\sf
T}^{*}_{1}E^{\delta_{Q^{\prime}_{1}}}{C_{1}}^{*}{\sf
T}^{*}_{2}E^{\delta_{Q^{\prime}_{2}}}\ldots{\sf
T}^{*}_{t}E^{\delta_{Q^{\prime}_{1}}}{C_{t}}^{*}{\sf
Z}^{g(P,c_{i},d_{i},x_{i})}{\sf X}^{f(P,c_{i},d_{i},x_{i})}PR^{\prime}P{\sf
X}^{f(P,c_{i},d_{i},x_{i})}{\sf Z}^{g(P,c_{i},d_{i},x_{i})}\biggr{)},$ (43)

Where $f(P,c_{i},d_{i},x_{i}),g(P,c_{i},d_{i},x_{i})$ are functions that
depend on $P\in\mathbb{P}_{n}$, as well as $c_{1},c_{2},\ldots c_{t}$,
$d_{1},d_{2},\ldots d_{t}$ and $x_{1},x_{2},\ldots x_{t}$, as given by the key
update rules in Sections 4.1–4.4. We note that by these key update rules, it
is a property of the protocol that the $P$’s appear uniformly at random for
any choice of computation $C$.

We thus apply the same techniques as in Section 7.5.2 in order to simplify the
above equation. First, note that we can use the Pauli twirl (Lemma 1) on the
last $n$-qubit register; this yields:

$\sum_{P_{1},Q_{1},{Q_{1}}^{\prime},{P_{1}}^{\prime},\ldots
P_{t},Q_{t},{Q_{t}}^{\prime},{P_{t}}^{\prime},R}\alpha_{P_{1}}\alpha_{Q_{1}}\alpha_{{{P_{1}}^{\prime}}^{*}}\alpha_{{{Q_{1}}^{\prime}}^{*}}\ldots\alpha_{P_{t}}\alpha_{Q_{t}}\alpha_{{{P_{t}}^{\prime}}^{*}}\alpha_{{{Q_{t}}^{\prime}}^{*}}\lvert\alpha_{R}\rvert^{2}\\\
\biggl{(}\sum_{c_{1},d_{1},e_{1},x_{1}\in\\{0,1\\}}{\sf X}^{d_{1}}P_{1}{\sf
X}^{d_{1}}{\left|{c_{1}}\right\rangle}{\left\langle{c_{1}}\right|}{\sf
X}^{d_{1}}{{P^{\prime}}_{1}}{\sf X}^{d_{1}}\otimes Q_{1}{\sf
X}^{x_{1}}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x_{1}}{Q^{\prime}}_{1}\otimes\ldots\otimes\\\
\sum_{c_{t},d_{t},e_{t},x_{t}\in\\{0,1\\}}{\sf X}^{d_{t}}P_{t}{\sf
X}^{d_{t}}{\left|{c_{t}}\right\rangle}{\left\langle{c_{t}}\right|}{\sf
X}^{d_{t}}{{P^{\prime}}_{t}}{\sf X}^{d_{t}}\otimes Q_{t}{\sf
X}^{x_{t}}{\left|{0}\right\rangle}{\left\langle{0}\right|}{\sf
X}^{x_{t}}{Q^{\prime}}_{t}\otimes\\\ RC_{t}E^{\delta_{t}}{\sf T}_{t}\ldots
E^{\delta_{Q_{2}}}{\sf T}_{2}C_{1}E^{\delta_{Q_{1}}}{\sf
T}_{1}C_{0}{\left|{0^{n}}\right\rangle}{\left\langle{0^{n}}\right|}{C_{0}}^{*}{\sf
T}^{*}_{1}E^{\delta_{Q^{\prime}_{1}}}{C_{1}}^{*}{\sf
T}^{*}_{2}E^{\delta_{Q^{\prime}_{2}}}\ldots{\sf
T}^{*}_{t}E^{\delta_{Q^{\prime}_{1}}}{C_{t}}^{*}R\biggr{)},$ (44)

Next, we apply the Pauli twirl on the first $2t$ registers (assuming that the
traced-out registers are decrypted); the result is

$\sum_{P_{1},Q_{1},\ldots
P_{t},Q_{t},R}\lvert\alpha_{P_{1}}\rvert^{2}\lvert\alpha_{Q_{1}}\rvert^{2}\ldots\lvert\alpha_{P_{t}}\rvert^{2}\lvert\alpha_{Q_{t}}\rvert^{2}\lvert\alpha_{R}\rvert^{2}\\\
\biggl{(}\sum_{c_{1},d_{1},e_{1},x_{1}\in\\{0,1\\}}P_{1}{\left|{c_{1}}\right\rangle}{\left\langle{c_{1}}\right|}{{P}_{1}}\otimes
Q_{1}{\left|{0}\right\rangle}{\left\langle{0}\right|}{Q}_{1}\otimes\ldots\otimes\sum_{c_{t},d_{t},e_{t},x_{t}\in\\{0,1\\}}P_{t}{\left|{c_{t}}\right\rangle}{\left\langle{c_{t}}\right|}{{P}_{t}}\otimes
Q_{t}{\left|{0}\right\rangle}{\left\langle{0}\right|}{Q}_{t}\otimes\\\
RC_{t}E^{\delta_{t}}{\sf T}_{t}\ldots E^{\delta_{Q_{2}}}{\sf
T}_{2}C_{1}E^{\delta_{Q_{1}}}{\sf
T}_{1}C_{0}{\left|{0^{n}}\right\rangle}{\left\langle{0^{n}}\right|}{C_{0}}^{*}{\sf
T}^{*}_{1}E^{\delta_{Q^{\prime}_{1}}}{C_{1}}^{*}{\sf
T}^{*}_{2}E^{\delta_{Q^{\prime}_{2}}}\ldots{\sf
T}^{*}_{t}E^{\delta_{Q^{\prime}_{1}}}{C_{t}}^{*}R\biggr{)},$ (45)

From the above, it is clear that benign attacks ($Q\in B_{t,n}$) lead to an
acceptance probability of at most $p$, since in the case that $Q$ is benign,
each of the $\delta$’s are 0, and so the correct computation, $C=C_{t}{\sf
T}\ldots{\sf T}C_{1}{\sf T}C_{0}$ is applied before the output qubit is
measured (and furthermore, since $Q$ is benign this output qubit is affected
by either $I$ or ${\sf Z}$). However, for non-benign attacks, we bound their
acceptance probability by the trivial bound of 1. This completes the proof. ∎

###  7.6 Proof of Soundness

In order to complete the proof of soundness, we consider each possible fixed
Pauli attack (the attacks are broken up into the same convex combination of
Pauli attacks in all types of runs). Suppose that the input corresponds to a
no instance. Consider the following cases.

  1. 1.

$P$ is benign. Then by Lemma 2, $V$ accepts both test runs. In the computation
run, by Lemma 4, $V$ accepts with probability $\leq 1/3$ (as this is the
probability that the honest computation outputs $0$). The acceptance
probability is thus at most $\frac{2}{3}+\frac{1}{9}=\frac{7}{9}$.

  2. 2.

$P$ is not benign. Then by Lemma 2, at least one of the ${\sf X}$ or ${\sf Z}$
test run rejects. The acceptance probability is thus at most $\frac{2}{3}$.

This completes the proof of Theorem 1. It is interesting to note that an
optimal strategy to increase the acceptance probability is to behave honestly!

## Acknowledgements

I am grateful to Urmila Mahadev for suggesting the relabelling described in
Section 6.1, which simplifies the proof of soundness, and also for related
discussions. It is a pleasure to thank Gus Gutoski for many deep
conversations, from which this work originated, and Thomas Vidick for many
related discussions. Furthermore, it is a pleasure to thank Jacob Krich for
supplying background material on quantum simulations. I am also grateful to
Harry Buhrman and Evelyn Wainewright for feedback on an earlier version of
this work. A. B. is supported by Canada’s NSERC and the University of Ottawa’s
Research Chairs program.

## References

  * [AA11] S. Aaronson and A. Arkhipov.  The computational complexity of linear optics.  In Proceedings of the 43rd annual ACM symposium on Theory of computing, pages 333–342. ACM, 2011.
  * [AA14] S. Aaronson and A. Arkhipov.  Bosonsampling is far from uniform.  Quantum Information & Computation, 14:1383–1423, 2014.
  * [ABE10] D. Aharonov, M. Ben-Or, and E. Eban.  Interactive proofs for quantum computations.  In Proceeding of Innovations in Computer Science 2010 (ICS 2010), pages 453–469, 2010.
  * [AJL06] D. Aharonov, V. Jones, and Z. Landau.  A polynomial quantum algorithm for approximating the Jones polynomial.  In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC ’06, pages 427–436, 2006.
  * [AMTW00] A. Ambainis, M. Mosca, A. Tapp, and R. De Wolf.  Private quantum channels.  In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pages 547–553, 2000.
  * [AV14] D. Aharonov and U. Vazirani.  Is quantum mechanics falsifiable? A computational perspective on the foundations of quantum mechanics.  In Computability: Turing, Godel, Church and Beyond. MIT press, 2014\.
  * [BCC88] G. Brassard, D. Chaum, and C. Crépeau.  Minimum disclosure proofs of knowledge.  J. Comput. Syst. Sci., 37(2):156–189, October 1988.  Preliminary version by Brassard and Crépeau in 27th FOCS, 1986.
  * [BCG+02] H. Barnum, C. Crépeau, D. Gottesman, A. Smith, and A. Tapp.  Authentication of quantum messages.  In Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science (FOCS ’02), pages 449–458, 2002.
  * [BFK09] A. Broadbent, J. Fitzsimons, and E. Kashefi.  Universal blind quantum computation.  In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pages 517–526, 2009.
  * [BFKW13] S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther.  Experimental verification of quantum computation.  Nature Physics, 9:727–731, 2013.
  * [BGS13] A. Broadbent, G. Gutoski, and D. Stebila.  Quantum one-time programs.  In Advances in Cryptology CRYPTO 2013, pages 344–360, 2013.
  * [BJ15] Anne Broadbent and Stacey Jeffery.  Quantum homomorphic encryption for circuits of low $T$-gate complexity.  In Advances in Cryptology–CRYPTO 2015, pages 609–629, 2015.
  * [BMP+00] P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan.  On universal and fault-tolerant quantum computing.  Information Processing Letters, 75:101–107, 2000.
  * [BOCG+06] M. Ben-Or, C. Crépeau, D. Gottesman, A. Hassidim, and A. Smith.  Secure multiparty quantum computation with (only) a strict honest majority.  In Proc. 47th IEEE Symposium on the Foundations of Computer Science (FOCS 2006), pages 249–260, 2006.
  * [Bro15] A. Broadbent.  Delegating private quantum computations.  Canadian Journal of Physics, 93(9):941–946, 2015.
  * [CL92] A. Condon and R. Ladner.  Interactive proof systems with polynomially bounded strategies.  In Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual, pages 282–294, Jun 1992.
  * [CLN05] A. M. Childs, D. W. Leung, and M. A. Nielsen.  Unified derivations of measurement-based schemes for quantum computation.  Phys. Rev. A, 71:032318, 2005.
  * [DCEL09] C. Dankert, R. Cleve, J. Emerson, and E. Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Physical Review A, 80:012304, 2009.
  * [DFPR14] V. Dunjko, J .F. Fitzsimons, C. Portmann, and R. Renner.  Composable security of delegated quantum computation.  In Advances in Cryptology ASIACRYPT 2014, volume 8874 of Lecture Notes in Computer Science, pages 406–425, 2014.
  * [DFSS05] I. B. Damgård, S. Fehr, L. Salvail, and C. Schaffner.  Cryptography in the bounded quantum-storage model.  In Proc. 46th Annual IEEE Aymposium on the Foundations of Computer Science (FOCS 2005), pages 449–458, 2005.
  * [FBS+14] K. Fisher, A. Broadbent, L. K. Shalm, Z. Yan, J. Lavoie, R. Prevedel, T. Jennewein, and K. J. Resch.  Quantum computing on encrypted data.  Nature Communications 5, 3074 (2014). arXiv:1309.2586 [quant-ph], 5:3074, 2014.
  * [Fey82] R. Feynman.  Simulating physics with computers.  International Journal of Theoretical Physics, 21:467–488, 1982\.
  * [FH15] Joseph F. Fitzsimons and Michal Hajdu ek.  Post hoc verification of quantum computation.  Available as: arXiv:1512.04375, 2015.
  * [FK12] J. F. Fitzsimons and E. Kashefi.  Unconditionally verifiable blind computation.  Available as: arXiv:1203.5217v3, 2012.
  * [GC99] D. Gottesman and I. L. Chuang.  Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.  Nature, 402:390–393, 1999.
  * [GH05] Zhengting Gan and R.J. Harrison.  Calibrating quantum chemistry: A multi-teraflop, parallel-vector, full-configuration interaction program for the Cray-X1.  In Supercomputing, 2005. Proceedings of the ACM/IEEE SC 2005 Conference, pages 22–22, Nov 2005.
  * [GKAE13] C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert.  Boson-sampling in the light of sample complexity.  Available as: arXiv:1306.3995, 2013.
  * [GKR08] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum.  Delegating computation: Interactive proofs for muggles.  In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages 113–122, New York, NY, USA, 2008. ACM.
  * [JJUW10] R. Jain, Z. Ji, S. Upadhyay, and J. Watrous.  $\QIP=\PSPACE$.  Communications of the ACM, 53(12):102–109, 2010.
  * [KDK15] T. Kapourniotis, V. Dunjko, and E. Kashefi.  On optimising quantum communication in verifiable quantum computing.  In Proceedings of the Asian Quantum Information Science Conference 2015 (AQIS 2015), pages 23–25, 2015.
  * [KKMV08] J. Kempe, H. Kobayashi, K. Matsumoto, and T. Vidick.  Using entanglement in quantum multi-prover interactive proofs.  In Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, CCC ’08, pages 211–222, Washington, DC, USA, 2008\. IEEE Computer Society.
  * [KW15] E. Kashefi and P. Wallden.  Optimised resource construction for verifiable quantum computation.  Available as: arXiv:1510.07408, 2015.
  * [LFKN92] C. Lund, L. Fortnow, H. Karloff, and N. Nisan.  Algebraic methods for interactive proof systems.  J. ACM, 39(4):859–868, October 1992.
  * [NC00] M .A. Nielsen and I .L. Chuang.  Quantum computation and quantum information.  Cambridge University Press, 2000.
  * [RUV13] B. W. Reichardt, F. Unger, and U. Vazirani.  Classical command of quantum systems.  Nature, 496:456–460, 2013.
  * [Sha92] A. Shamir.  IP = PSPACE.  J. ACM, 39(4):869–877, October 1992.
  * [SP00] P. W. Shor and J. Preskill.  Simple proof of security of the BB84 quantum key distribution protocol.  Physical Review Letters, 85:441–444, 2000.
  * [SVB+14] N. Spagnolo, C. Vitelli, M. Bentivegna, D. J. Brod, A. Crespi, F. Flamini, S. Giacomini, G. Milani, R. Ramponi, P. Mataloni, R. Osellame, E. F. Galvão, and F. Sciarrino.  Experimental validation of photonic boson sampling.  Nature Photonics, 8(8):615–620, 2014.
  * [Wat03] J. Watrous.  PSPACE has constant-round quantum interactive proof systems.  Theoretical Computer Science, 292(3):575 – 588, 2003.  Algorithms in Quantum Information Prcoessing.
  * [ZDC00] X. Zhou, D. Leung, and I. L. Chuang.  Methodology for quantum logic gate construction.  Phys. Rev. A, 62:052316, 2000.