Plaintext
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37
www.theoryofcomputing.org
How to Verify a Quantum Computation
Anne Broadbent∗
Received October 3, 2016; Revised October 27, 2017; Published June 11, 2018
To my daughter Émily, on the occasion of her first birthday.
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; to the best of our knowledge, 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.
ACM Classification: F.1.3
AMS Classification: 68Q15, 81P68
Key words and phrases: complexity theory, cryptography, interactive proofs, quantum computing,
quantum interactive proofs, quantum cryptography
∗ This material is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-17-
1-0083, Canada’s NSERC, and the University of Ottawa’s Research Chairs program.
© 2018 Anne Broadbent
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2018.v014a011
A NNE B ROADBENT
1 Introduction
Feynman [24] 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 [6], 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 [29]. 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 [1], where the process of verification has been raised as a fundamental objection
to the viability of experiments [30] (fortunately, these claims are refuted [2], and progress was made in
the experimental verification [45]).
As mere classical probabilistic polynomial-time1 individuals, we appear to be in an impasse: how
can we validate the output of a quantum computation?2 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 [5]). 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 allow.3
Interactive proof systems traditionally model the prover as being all-powerful (i. e., computationally
unbounded).4 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
1 I. e., assuming humans can flip coins and execute classical computations that take time polynomial in n to solve on inputs of
size n.
2 Assuming the widely-held belief that BQP 6= BPP, i. e., that quantum computers are indeed more powerful than classical
computers.
3 This is the famous IP = PSPACE result [40, 43].
4 Notable exceptions include [20, 31].
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 2
H OW TO V ERIFY A Q UANTUM C OMPUTATION
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 QPIP, corresponding to quantum-prover interactive proof systems, was originally
defined by Aharonov, Ben-Or and Eban [3], who, using techniques from [11], showed that BQP = 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 [3] is to encode the input
into a quantum authentication code [9], 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 [6], and the protocol was also shown secure in a scenario of
composition [16].
In a different line of research, Kashefi and Fitzsimons [27] 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 [15]. 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 [10]. Further work by Kapourniotis, Dunjko and Kashefi [37] shows how
to combine the [3] and [27] protocols in order to reduce the quantum communication overhead; Kashefi
and Wallden [38] also show how to reduce the overhead of [27].
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 [3] is based
on [11]. However, the full proof of security for [11] never appeared. Although [3] makes significant
progress towards closing this gap, it provides only a sketch of how the soundness is established in the
interactive case (see, however, the very recent [4]). A full proof of soundness for [3] follows from [16],
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 [15] was deemed incomplete [27], but any gaps were addressed in [27]. In
this case, however, the protocol (and proof) are very elaborate, and to the best of our knowledge, remain
unpublished.5 Note, however that follow-up work has appeared in peer-reviewed form [37, 38], and that
these works consider the more general problem of verification for quantum inputs and outputs.
A related line of research also studies the problem of verification with a client that can perform only
single-qubit measurements [35]; the case of untrusted devices is also considered in [34]. In sharp contrast
to these approaches, Reichardt, Unger and Vazirani [42] show that it is possible to make the verifier
completely classical, as long as we postulate two non-communicating entangled provers. (This could be
5 This work has been published as [28] during the review period of the current paper.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 3
A NNE B ROADBENT
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. Very recently, Coladangelo, Grilo, Jeffery, and Vidick [19] have used the techniques
described here to achieve efficient schemes for verifying quantum computations in the model of a classical
verifier and two entangled 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), or otherwise had the verifier perform part 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 [44] and has been
used in a number of quantum cryptographic scenarios, e. g., [21,23,25]. To the best of our knowledge, 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 [16]; with
hidden gates being executed via a computation-by-teleportation process [33] that is reminiscent of
measurement-based quantum computation, and thus of blind quantum computation [15].
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. A link between input privacy and verification. Prior results [3, 15, 16, 27] all happened to
provide both privacy of a quantum computation and its verification (one notable exception being
the recent [26]). 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 [15, 27]).
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 4
H OW TO V ERIFY A Q UANTUM C OMPUTATION
2. A link between fault-tolerant quantum computation and cryptography. Prior results [3,11,16]
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. A link between entanglement and parallelization. It is known that entanglement can reduce the
number of rounds in quantum interactive proof systems [39]; 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 X-test and a 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 |0i⊗n .
• X-test run. In an X-test run, the prover executes the identity circuit on input |0i⊗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.
• Z-test run. In a Z-test run, the prover executes the identity circuit on input |+i⊗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) [14,25]: 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 set of gates {X, Z, H, CNOT, 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 X- and Z-test runs should (up to an encryption key), leave
the quantum wires in the |0i⊗n or |+i⊗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 CNOT gate can be executed directly (since it does not have any effect on
the wires for the test runs). The T-gate (Section 4.3) is performed using a construction (“gate gadget”)
inspired both by QCED and fault-tolerant quantum computation [12] (see also [17]); the T-gate gadget
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 5
A NNE B ROADBENT
involves the use of an auxiliary qubit and classical interaction. The H is performed thanks to an identity
involving the H and P (Section 4.4). Note that P can be accomplished as T2 .
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 [22], 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, Z attacks are obliterated, and thus the only family of attacks
of concern consists in X- and 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 X and Y attacks
require detection, one may wonder why we use also a Z-test run. The answer to this question lies in
the implementation of the H-gate: while its net effect is to apply the identity in the test runs, its internal
workings temporarily swap the roles of the X- and Z-test runs; thus the Z-test runs are also used to detect
X and 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, X- or 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 classical verifier,
interacting with a single quantum polynomial-time prover. In this context, we make a few observations.
• If the prover is unbounded, there exists a quantum interactive proof system for BQP, since
QIP(= PSPACE) = IP.6
• 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 [13], 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
6 QIP = PSPACE is due to [36].
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 6
H OW TO V ERIFY A Q UANTUM C OMPUTATION
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 [41]. We use the following
well-known qubit gates
X : | ji 7→ | j ⊕ 1i , (2.1)
j
Z : | ji 7→ (−1) | ji , (2.2)
1
Hadamard H : | ji 7→ √ (|0i + (−1) j |1i) , (2.3)
2
j
phase gate P : | ji 7→ i | ji , (2.4)
(iπ/4) j
π/8 rotation T : | ji 7→ e | ji) , and the (2.5)
two-qubit controlled-not CNOT : | ji|ki 7→ | ji| j ⊕ ki . (2.6)
Let Y = iXZ. We denote by Pn the set of n-qubit Pauli operators, where P ∈ Pn is given by P =
P1 ⊗ P2 ⊗ · · · ⊗ Pn where Pi ∈ {I, X, Y, Z}; we also denote an EPR pair
1
Φ+ = √ (|00i + |11i) . (2.7)
2
2.2 Quantum encryption and the Pauli twirl
The quantum one-time pad encryption maps a single-qubit system ρ to
1 I
∑ Xa Zb ρZb Xa = 2 ;
4 a,b∈{0,1}
(2.8)
its generalization to n-qubit systems is straightforward [7]. 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 ρ, 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 (1/ 2)(|0i + eiθ |1i), it can be encrypted with a random 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 [22].
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 7
A NNE B ROADBENT
Lemma 2.1 (Pauli Twirl). Let P, P0 ∈ Pn . Then
(
1 0, P 6= P0 ,
∑ Q∗ PQρQ∗ P0∗ Q =
|Pn | Q∈P PρP∗ , otherwise .
(2.9)
n
We also obtain the classical case for the single-qubit Pauli twirl, alluded to above, as the following.
Lemma 2.2 (Classical Pauli Twirl). Let c, i ∈ {0, 1} and P, P0 ∈ P1 . Then
(
1 0, P 6= P0 ,
∑ hi|Q∗ PQ|cihc|Q∗ P0 Q|ii =
2 Q∈{I,X} hi|P|cihc|P|ii, otherwise.
(2.10)
Proof. The proof is a simple application of Lemma 2.1, together with the observation that |0i, |1i are
eigenstates of Z:
1 1
∑ hi|Q∗ PQ|cihc|Q∗ P0 Q|ii = ∑ hi|Q∗ PQ|cihc|Q∗ P0 Q|ii (2.11)
2 Q∈{I,X} 4 Q∈{I,X,Y,Z}
(
0, P 6= P0 ,
= (2.12)
hi|P|cihc|P|ii, otherwise.
Working in the basis {|+i, |−i}, we also obtain the following.
Lemma 2.3. Let c, i ∈ {0, 1} and P, P0 ∈ P1 . Then
(
1 0, P 6= P0 ,
∑ hi|Q∗ HPHQ|cihc|Q∗ HP0 HQ|ii =
2 Q∈{I,X} hi|HPH|cihc|HPH|ii, otherwise.
(2.13)
3 Definitions and statement of results
Interactive proof systems were introduced by Babai [8] and Goldwasser, Micali, and Rackoff [32]. 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 ∈ 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 with the
following properties.
• (Completeness) if x ∈ L, there exists a prover (called an honest prover) such that the verifier accepts
with probability p ≥ 2/3;
• (Soundness) if x 6∈ L, no prover can convince V to accept with probability p ≥ 1/3.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 8
H OW TO V ERIFY A Q UANTUM C OMPUTATION
The class of languages having interactive proof systems is denoted IP.
Watrous [46] 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 computation-
ally 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 S (Definition 3.1). Furthermore, as a technicality, instead of considering languages,
we consider promise problems. A promise problem Π = (ΠY , Π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 [46].
Definition 3.1. Let S = {S1 , . . . , S` } where Si = {ρ1 , . . . , ρ`i } (i = 1, . . . , `) is a set of density operators.
A S-quantum-prover Interactive Proof System for a promise problem Π = (ΠY , Π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 S1 , . . . , S` (upon generation, these states are immediately sent to the
prover, with the index i ∈ {1, . . . , `} known to the verifier and prover, and the index j ∈ {1, . . . , `i } known
to the verifier only). The interaction of the verifier V and the prover P satisfies the following conditions.
• (Completeness) if x ∈ ΠY , there exists a quantum polynomial-time prover (called an honest prover)
such that the verifier accepts with probability p ≥ 2/3;
• (Soundness) if x ∈ ΠN , no prover (even unbounded) can convince V to accept with probability
p ≥ 1/3.
The class of promise problems having an S-quantum interactive proof systems is denoted QPIPS . Note
that by standard amplification, the class QPIPS is unchanged if we replace the completeness parameter c
and soundness parameter s by any values, as long as c − s > 1/poly(n).
Comparing our definition of QPIPS to the class of quantum-prover interactive proof systems (QPIP)
as given in [3], we note that we have made some modifications and clarifications, namely that the verifier
in QPIPS does not have any quantum memory and does not perform any gates (QPIP allows a verifier
that stores and operates on a quantum register of a constant number of qubits), and that soundness holds
against unbounded provers.
Finally, we use the canonical BQP-complete problem [3], defined as follows.
Definition 3.2. The input to the promise problem Q-CIRCUIT consists of a quantum circuit made of a
sequence of gates, U = UT , . . . ,U1 acting on n input qubits. (We take these circuits to be given in the
universal gateset {X, Z, H, CNOT, T}.) Let
p(U) = k|0ih0| ⊗ In−1U|0n ik2 (3.1)
be the probability of observing “0” as a result of a computational basis measurement of the nth output
qubit, obtained by evaluating U on input |0n i.
Then define Q-CIRCUIT= {Q − CIRCUITYES , Q − CIRCUITNO } with
Q − CIRCUITYES : p(U) ≥ 2/3 , (3.2)
Q − CIRCUITNO : p(U) ≤ 1/3 . (3.3)
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 9
A NNE B ROADBENT
We can now formally state our main theorem.
Theorem 3.3 (Main Theorem). Let
S = {|0i, |1i}, {|+i, |−i}, {P|+i, P|−i}, {T|+i, T|−i, PT|+i, PT|−i} .
(3.4)
Then BQP = QPIPS .
4 Quantum-prover interactive proof system
In order to prove Theorem 3.3, 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.
4.1 X- and Z-gate gadget
In order to apply an X on a qubit register i encrypted with key (ai , bi ), the verifier updates the key
according to ai ← ai ⊕ 1 (bi is unchanged). In order to apply an Z on a qubit register i encrypted with
key (ai , bi ), the verifier updates the key according to bi ← bi ⊕ 1 (ai is unchanged). This operation is
performed only in the computation run.
4.2 CNOT-gate gadget
In order to apply a CNOT gate on the encrypted registers (say with register i being the control and
register j the target), the prover simply applies the CNOT gate on the respective registers. The verifier
updates the encryption keys according to ai ← ai ; bi ← bi ⊕ b j ; a j ← ai ⊕ a j ; and b j ← b j . We mention
that CNOT(|0i|0i) = |0i|0i and CNOT(|+i|+i) = |+i|+i; thus in the X- and Z-test runs, the underlying
data is unchanged.
4.3 T-gate gadget
Here, we show how the T is performed on encrypted data. This is accomplished using an auxiliary qubit,
as well as classical interaction. For the computation run, we use a combination of a protocol inspired
from [14, 25], as well as fault-tolerant quantum computation [12] (see also [17]). This is given in Figure 1.
In the case of an X and 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 Figures 1–3 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-labeling, in order to match the resources required in Theorem 3.3.
Also, note that in this work, we have slightly sacrificed efficiency for clarity in the proof, namely that
we could have defined a P-gadget using one simple auxiliary qubit instead of two auxiliary qubits that are
used by implementing the P as T2 . Furthermore, we suspect that the Py gate is unnecessary in Figure 1
and thus that we can simplify the set S (however, the proof in this case appears to be more elaborate, so
once more we choose clarity of the proof over efficiency).
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 10
H OW TO V ERIFY A Q UANTUM C OMPUTATION
Interactive Proof System 1 Verifiable quantum computation with trusted auxiliary states
Let C be given as an n-qubit quantum circuit in the universal gateset X, Z, CNOT, H, T.
1. The verifier randomly chooses to execute one of the following three runs (but does not inform the
prover of this choice).
A. Computation Run
A.1. The verifier encrypts input |0i⊗n and sends the input to P.
A.2. The verifier sends auxiliary qubits required for the T-gate gadgets for the computation
run as given in Sections 4.4 and 4.3.
A.3. For each gate G in C: X, Z and CNOT are performed without any auxiliary qubits
or interaction as given in Sections 4.1 and 4.2, while the H- and T-gate gadgets are
performed using the auxiliary qubits from Step A.2 and the interaction as given in
Sections 4.4 and 4.3, respectively.
A.4. P measures the output qubit and returns the result to V .
A.5. V decrypts the answer; let the result be ccomp . V accepts if ccomp = 0; otherwise reject.
B. X-test Run
B.1. The verifier encrypts input |0i⊗n and sends the input to P.
B.2. The verifier sends auxiliary qubits required for the T-gate gadgets for the X-test run as
given in Sections 4.4 and 4.3.
B.3. For each gate G in C: X, Z and CNOT are performed without any auxiliary qubits
or interaction as given in Sections 4.1 and 4.2, while the H- and T-gate gadgets are
performed using the auxiliary qubits from Step B.2 and the interaction as given in
Sections 4.4 and 4.3, respectively.
B.4. P measures the output qubit and returns the result to V .
B.5. V decrypts the answer; let the result be ctest . V accepts if no errors were detected in
Step B.3 and if ctest = 0; otherwise reject.
C. Z-test Run
C.1. The verifier encrypts input |+i⊗n and sends the input to P.
C.2. The verifier sends auxiliary qubits required for the T-gate gadgets for the Z-test run as
given in Sections 4.4 and 4.3.
C.3. For each gate G in C: X, Z and CNOT are performed without any auxiliary qubits
or interaction as given in Sections 4.1 and 4.2, while the H- and T-gate gadgets are
performed using the auxiliary qubits from Step C.2 and the interaction as given in
Sections 4.4 and 4.3, respectively.
C.4. P measures the output qubit and returns the result to V .
C.5. V disregards the output. V accepts if no errors were detected in Step C.3; otherwise
reject.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 11
A NNE B ROADBENT
Xa Zb |ψi •
Prover • •
0 0
• Px Xa Zb T|ψi
x = a⊕c⊕y • • c
Verifier
|+i T Py Ze Xd (d, e, y ∈R {0, 1})
Figure 1: T-gate gadget for a computation run. Here, an auxiliary qubit is prepared by the verifier in the
state Xd Ze Py T|+i and sent to the prover. The prover performs a 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 ⊕ c ⊕ y to the prover, who applies the conditional gate Px to the remaining
register (which we now re-label as the data register). The verifier’s key update rule is given by a0 = a ⊕ c
and b0 = (a ⊕ c) · (d ⊕ y) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ y .
Xa |0i •
Prover • •
Xd |0i
• Px
x ∈R {0, 1} • • c = a⊕d
Verifier
|0i Xd (d ∈R {0, 1})
Figure 2: T-gate gadget for an 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 |0i (up to encryptions). Here, we include
an additional verification that c = a ⊕ d.
Zb |+i •
Prover • •
Xc Zb⊕d⊕y |+i
• Px
x=y • • c
Verifier
|+i Py Zd (d, y ∈R {0, 1})
Figure 3: T-gate gadget for a 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 |+i (up to encryptions).
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 12
H OW TO V ERIFY A Q UANTUM C OMPUTATION
4.4 H-gate gadget
Performing a H gate has the effect of locally swapping between the X- and Z-test runs (as well as swapping
the role of the X and Z encryption keys in the computation run). While this is alright if done in isolation,
it does not work if the H-gate is performed as part of a larger computation (for instance, a CNOT-gate
could no longer be performed as given above as the inputs would not, in general, be of the form |0i|0i
(for the X-test run) or |+i|+i (for the Z-test run)). Our solution is to use the following two identities.
HPHPHPH = H , (4.1)
HHHH = I . (4.2)
Thus we build the gadget so that the prover starts by applying an H at the start. By doing this, we locally
swap the roles of the X- and Z-tests we also cause a key update which swaps the role of the X- and
Z-encryption keys. For the following 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 P is applied in the computation run, while the
identity is applied in the test runs. Now an H is applied, which reverts the roles of the X- and Z-tests. We
apply the P again. Continuing in this fashion, we observe the following effect.
1. In the computation run (using twice the gadget of Figure 1 for each P-gate), the effect is to apply H
on the input qubit (by Equation (4.1)).
2. In the X-test run (using (twice each time) the gadgets of Figures 3, 2, 3 for the first, second and
third P-gate), the effect is to apply the identity.
3. In the Z-test run (using (twice each time) gadgets of Figures 2, 3, 2 for the first, second and third
P-gate), the effect is to apply the identity.
5 Correctness of the T-gate protocol
We give below a step-by-step proof of the correctness of the T-gate protocol as given in Figure 1
(Section 4.3). In Section 5.1, we show how similar techniques are used to show corrections of the T-gate
protocol for the test runs, as given in Figures 2 and 3. The basic building block is the circuit identity
for an X-teleportation from [47]. Also of relevance to this work are the techniques developed by Childs,
Leung, and Nielsen [18] 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: XZ = ZX,
PZ = ZP, PX = XZP, TZ = ZT, TX = XZPT, P2 = Z and Pa⊕b = Za·b Pa+b (for a, b ∈ {0, 1}).
1. We start with the “X-teleportation” of [47], which is easy to verify (Figure 4).
|ψi c
|+i • Xc |ψi
Figure 4: Circuit identity: “X-teleportation.”
2. Then we substitute the input Xa Zb |ψi for the top wire. We add the gate sequence T, Py , Ze , Xd ,
Pa⊕c⊕y to the output (Figure 5). By Figure 4, the outcome is given by Pa⊕c⊕y Xd Ze Py TXa⊕c Zb |ψi.
We apply the identities given above to simplify this to a Pauli correction (on T) as follows.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 13
A NNE B ROADBENT
Pa⊕c⊕y Xd Ze Py TXa⊕c Zb = Pa⊕c⊕y Xd Ze Py Xa⊕c Pa⊕c Zb⊕a⊕c T (5.1)
= Pa⊕c⊕y Xd Ze Py Pa⊕c Xa⊕c Zb T (5.2)
a⊕c⊕y y d d·y⊕e a⊕c a⊕c b
=P PX Z P X Z T (5.3)
= Pa⊕c⊕y Py Pa⊕c Xd Zd·(a⊕c) Zd·y⊕e Xa⊕c Zb T (5.4)
(a⊕c)⊕y y a⊕c a⊕c⊕d d(a⊕c⊕y)⊕b⊕e
=P PP X Z T (5.5)
y·(a⊕c) a⊕c y y a⊕c a⊕c⊕d d(a⊕c⊕y)⊕b⊕e
=Z P PPP X Z T (5.6)
= Xa⊕c⊕d Z(a⊕c⊕d)·(d⊕y)⊕a⊕b⊕c⊕d⊕e⊕y T (5.7)
a⊕c0 (a⊕c0 )·(d⊕y)⊕a⊕b⊕c0 ⊕e⊕y
=X Z T, (5.8)
where above we let c0 ← c ⊕ d.
Xa Zb |ψi c; c0 ← c ⊕ d
0 0 0
|+i • T Py Ze Xd Pa⊕c⊕y Xa⊕c Z(a⊕c )·(d⊕y)⊕a⊕b⊕c ⊕e⊕y T|ψi
Figure 5
3. Next, we note that, because diagonal gates commute with control, the circuit of Figure 5 is
equivalent to the one in Figure 6.
Xa Zb |ψi c; c0 ← c ⊕ d
0 0 0
Ze Py T|+i • Xd Pa⊕c⊕y Xa⊕c Z(a⊕c )·(d⊕y)⊕a⊕b⊕c ⊕e⊕y T|ψi
Figure 6
4. We note that the Xd on the bottom wire after the CNOT can be moved to the bottom wire before
the CNOT, as long as we add an Xd to the top wire after the CNOT. (Figure 7.)
Xa Zb |ψi Xd c; c0 ← c ⊕ d
0 0 0
Xd Ze Py T|+i • Pa⊕c⊕y Xa⊕c Z(a⊕c )·(d⊕y)⊕a⊕b⊕c ⊕e⊕y T|ψi
Figure 7
5. Finally, since c0 = c ⊕ d, yet the measurement result c undergoes an Xd , these two operations cancel
out, and we obtain the final circuit as in Figure 8.
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.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 14
H OW TO V ERIFY A Q UANTUM C OMPUTATION
Xa Zb |ψi c
Xd Ze Py T|+i • Pa⊕c⊕y Xa⊕c Z(a⊕c)·(d⊕y)⊕a⊕b⊕c⊕e⊕y T|ψi
Figure 8
5.1 Correctness of the T-gate gadget in the test runs
The correctness of the T-gate gadget in the X-test run of Figure 2 is straightforward: the CNOT flips the
bit in the top wire if and only if d = 1, while the Px has no effect on the computational basis states. The
correctness of Figure 3 is derived from the X-teleportation of Figure 4. Since the diagonal gates Z and P
commute with control, they can be seen as acting on the output qubit. Furthermore, using P2 = Z and the
fact that X has no effect on |+i, we get the final circuit in Figure 3.
6 Completeness
Suppose C is a yes-instance of Q-CIRCUIT. Suppose P follows the protocol honestly. Then we have the
following.
1. In the case of a computation run, the output bit, ccomp has the same distribution as the output bit of
C(|0n i), thus V accepts with probability at least 2/3.
2. In the case of an X-test run and in the case of a Z-test run (by the identities and observations from
the previous sections), V accepts with probability 1.
Given that each run happens with probability 1/3, we get that V accepts with probability at least
2/3 + (1/3) · (2/3) = 8/9.
6.1 Auxiliary qubits for the T-gate gadget
In the protocol for the T-gate gadget (Figure 1), we assume the verifier can produce auxiliary qubits of
the form Xd Ze Py T|+i. We now show that this is equivalent to requiring the verifier to generate auxiliary
qubits of the form Ze Py T|+i, as claimed in Theorem 3.3. This can be seen by the following equation,
which holds up to global phase.
Xd Ze Py T|+i = Ze⊕d Py⊕d T|+i . (6.1)
The above can be seen easily since, up to global phase, XT|+i = ZPT|+i, and XP = ZPX. The analysis
for the case d = 1, follows.
XZe Py T|+i = Ze XPy T|+i (6.2)
e y y
= Z Z P XT|+i (6.3)
e⊕y y
=Z P ZPT|+i (6.4)
e⊕y⊕1 y+1
=Z P T|+i (6.5)
e⊕y⊕1 y y⊕1
=Z ZP T|+i (6.6)
e⊕1 y⊕1
=Z P T|+i . (6.7)
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 15
A NNE B ROADBENT
Thus, the verifier chooses a classical x uniformly at random, and if x = 1, the verifier re-labels the
auxiliary qubits according to Equation (6.1).
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 argue why 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). In Section 7.6, we show how this
completes the proof of our main theorem (Theorem 3.3).
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 T-gate, this can be done as shown in Figures 9, 10 and 11.
Xa Zb |ψi •
Prover • •
0 0
• Px Xa Zb T|ψi
x ∈R {0, 1} • • c
Verifier |0i H • (d ∈R {0, 1}, y = a ⊕ c ⊕ x)
|0i T Py⊕d Zd H e
Figure 9: Entanglement-based protocol for a T-gate (computation run). This protocol performs the
same computation as the protocol in Figure 1. The output is obtained from the output of Figure 1
by using y = a ⊕ c ⊕ x. The circuit in the dashed box prepares an EPR-pair. Here, a0 = a ⊕ c and
b0 = (a ⊕ c) · (d ⊕ y) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ y .
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 16
H OW TO V ERIFY A Q UANTUM C OMPUTATION
Xa |0i •
Prover • •
Xd |0i
• Px
x ∈R {0, 1} • • c = a⊕d
Verifier |0i H •
|0i d
Figure 10: Entanglement-based protocol for a T-gate (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 ⊕ d.
Zb |+i •
Prover • •
Xc Zb⊕d⊕y |+i
• Px
x ∈R {0, 1} • • c
Verifier |0i H • (y = x)
|0i Py H d
Figure 11: Entanglement-based protocol for a T-gate (Z-test run). This protocol performs the same
computation as the protocol in Figure 3. The circuit in the dashed box prepares an EPR-pair.
We therefore define VEPR 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). That the soundness parameter is the same
for Interactive Proof Systems 1 and 2 follows from the following series of transformations, each of which
preserves the probability of accept/reject.
1. The quantum communication from the verifier to the prover in Interactive Proof System 1 can be
generated instead by preparing EPR pairs, sending half and then immediately measuring in the
appropriate basis to obtain the required qubit. Call this Interactive Proof System 1.1.
2. Starting from Interactive Proof System 1.1, by a change of variable, we can specify the classical
message x to be random in each of the T-gate gadgets. This determines y, and the operation Py ,
that is conditioned on y (for the computation and Z-test run) can be applied immediately before the
verifier’s measurement. Call this Interactive Proof System 1.2.
3. In Interactive Proof System 1.2, the prover and verifier operate on different subsystems. Their
operations therefore commute and we can specify that the Verifier delays his operations until after
the interaction with the Prover. The result of this transformation is Interactive Proof System 2.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 17
A NNE B ROADBENT
Since each transformation above preserves the soundness, and since the completeness parameter is
unchanged, from now on, we can focus on establishing the soundness parameter for Interactive Proof
System 2.
7.2 Simplifying a general attack
In this section, we derive a simplified expression for a general deviating prover for our Interactive Proof
System. We show that without loss of generality, we can rewrite the actions of any deviating prover as the
honest prover’s actions, followed by an arbitrary cheating map. But first, as a technicality, we consider
Interactive Proof System 3, which is closely related to Interactive Proof System 2, but where the prover is
unitary and show (Lemma 7.2) that a bound on the soundness of Interactive Proof System 3 implies a
bound on the soundness of Interactive Proof System 2.
Definition 7.1. We define Interactive Proof System 3 as Interactive Proof System 2, but with a unitary
prover. To be more precise, the prover (say, Pq ) in Interactive Proof System 3 performs the same
operations as the prover in Interactive Proof System 2, but does not perform any measurements: instead,
q
Pq sends qubits to the verifier, say VEPR , who immediately measures them in place of the prover, and then
continues according to the Interactive Proof System 2.
Lemma 7.2. Interactive Proof Systems 2 and 3 have the same completeness, and furthermore, an upper
bound on the soundness parameter for Interactive Proof System 3 is an upper bound on the soundness
parameter for Interactive Proof System 2.
Proof. It follows immediately by definition that Interactive Proof Systems 2 and 3 have the same
completeness parameter. For soundness, suppose that in Interactive Proof System 3, the probability that
q
VEPR accepts while interacting with any Pq∗ is at most s. Suppose for a contradiction that there is a P∗ for
Interactive Proof System 2, such that VEPR accepts with p > s.
Using polynomial overhead, we obtain P ∗ ∗ ∗
meas from P via purification (all actions of Pmeas are unitary,
] ]
except a one-qubit register is measured each time the protocol requires a classical message to be sent to
the verifier). The probability p of acceptance is unchanged.
Furthermore, starting with P∗ , we define P f∗ as a prover for Interactive Proof System 3, which
behaves like P ∗
meas , but instead of measuring messages to be sent to the verifier, it sends qubits, which
]
q
are immediately measured by VEPR , as per Interactive Proof System 3. The probability p that the verifier
in Interactive Proof System 3 accepts, when interacting with P f∗ is the same as the probability that the
verifier in Interactive Proof System 2 accepts, when interacting with P∗ . This contradicts p > s, and
proves the claim.
Next, we show that, in Interactive Proof System 3, without loss of generality, we can assume that
the prover’s actions are the honest unitary ones, followed by a general attack. In order to see this, for a
t-round protocol (involving t rounds of classical interaction), define a cheating prover’s actions at round i
by Φi Hi , where Hi 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 unitary circuit, while Φi is a general deviating map
acting on the classical bit received in round i, the output registers of Hi as well as a private memory
register. (Recall that there are no measurements at this point—V does the measurement.)
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 18
H OW TO V ERIFY A Q UANTUM C OMPUTATION
Interactive Proof System 2 Verifiable quantum computation with trusted auxiliary states- EPR version
Let C be given as an n-qubit quantum circuit in the universal set of gates X, Z, CNOT, H, T.
⊗n
1. The verifier prepares |Φ+ i and sends half of each pair to the prover. These registers are identified
with the input registers.
2. For each auxiliary qubit required in the H- and T-gate gadgets, the verifier prepares |Φ+ i and sends
half of each pair to the prover.
3. The prover executes the gate gadgets. The verifier records the classical communication and
responds with random classical bits (when required).
4. The prover returns a single bit of output, c to the verifier.
5. The verifier randomly chooses to execute one of the following three runs (but does not inform the
prover of this choice).
A. Computation Run
A.1. Measure the remaining input register halves in the computational basis. Take the initial
X-encryption key to be the measurement outcomes (set the Z-key to 0).
A.2. For each gate G in C: perform the key updates for the X, Z , CNOT and H gates. For the
T gadget, taking into account the classical messages received and sent in Step 3, perform
the measurement and key update rules for the T-gadget (Figure 9).
A.3. V decrypts the output bit c; let the result be ccomp . V accepts if ccomp = 0; otherwise
reject.
B. X-test Run
B.1. Measure the remaining input register halves in the computational basis. Take the initial
X-encryption key to be the measurement outcomes (set the Z-key to 0).
B.2. For each gate G in C: perform the key updates for the X, Z, CNOT and H gates. For the
T gadget, taking into account the classical messages received and sent in Step 3, perform
the measurement, key update rules and tests for the T-gadget (Figure 10).
B.3. V decrypts the output bit c; let the result be ccomp . V accepts if ccomp = 0 and if no errors
were detected in Step B.2; otherwise reject.
C. Z-test Run
C.1. Measure the remaining input register halves in the Hadamard basis. Take the initial
Z-encryption key to be the measurement outcomes (set the X-key to 0).
C.2. For each gate G in C: perform the key updates for the X, Z, CNOT and H gates. For the
T gadget, taking into account the classical messages received and sent in Step 3, perform
the measurement, key update rules and tests for the T-gadget (Figure 11)
C.3. V accepts if no errors were detected in Step C.2; otherwise reject.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 19
A NNE B ROADBENT
Thus the actions of a general prover P∗ are given as the follows.
Φt Ht . . . Φ1 H1 Φ0 H0 . (7.1)
Since H0 , . . . , Ht are unitary, we can rewrite Equation (7.1).
Φt Ht . . . Φ3 H3 Φ2 H2 Φ1 H1 Φ0 H0 = Φt Ht . . . Φ3 H3 Φ2 H2 (Φ1 H1 Φ0 H1 ∗ )H1 H0 (7.2)
∗ ∗
= Φt Ht . . . Φ3 H3 (Φ2 H2 Φ1 H1 Φ0 H1 H2 )H2 H1 H0 (7.3)
= Φt Ht . . . (Φ3 H3 Φ2 H2 Φ1 H1 Φ0 H1 H2 H3∗ )H3 H2 H1 H0
∗ ∗
(7.4)
∗ ∗ ∗ ∗
= (Φt Ht . . . Φ3 H3 Φ2 H2 Φ1 H1 Φ0 H1 H2 H3 . . . Ht )Ht . . . H3 H2 H1 H0 .
(7.5)
Thus, by denoting a general attack by
Φ = Φt Ht . . . Φ3 H3 Φ2 H2 Φ1 H1 Φ0 H1 ∗ H2 ∗ H3∗ . . . Ht∗ , (7.6)
and the map corresponding to the honest prover as H = Ht . . . H3 H2 H1 H0 , we get that without loss of
generality, we can assume that the prover’s actions are the honest ones, followed by a general attack:
ΦH . (7.7)
Taking {Ek } to be Kraus terms associated with Φ, and supposing a total of m qubit registers are
involved, we get that the system after interaction with P∗ , where the initial state is
m
⊗m 1 2 −1
Φ+ Φ+ = |iiih j j| (7.8)
2m i,∑
j=0
(here, we include the classical random bits, as they are uniformly random and therefore we can repre-
sent them as maximally entangled states), and where the verifier has not yet performed the gates and
measurements, can be described as
1
2m ∑ ∑(I ⊗ Ek H)|iiih j j|(I ⊗ H ∗ Ek∗ ) . (7.9)
k i, j
For a fixed k, we write Ek and Ek∗ in the Pauli basis:
Ek = ∑ αk,Q Q and Ek∗ = ∑ αk,Q
∗ 0
0Q . (7.10)
Q Q0
(To simplify notation, we assume throughout that Q, Q0 ranges over Pm .) By the completeness relation,
we have:
∑ ∑|αk,Q |2 = 1 . (7.11)
k Q
When it is clear from context, we drop the “k” subscript, thus denoting
Ek = ∑ αQ Q and Ek∗ = ∑ αQ∗ 0 Q0 . (7.12)
Q Q0
In the following sections, we analyze the probability of acceptance, as a function of the type of run
and of the prover’s attack. By Lemma 7.2, a bound on the acceptance probability gives a bound on the
acceptance probability in Interactive Proof System 2 (which is a bound on the acceptance probability of
Interactive Proof System 1).
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 20
H OW TO V ERIFY A Q UANTUM C OMPUTATION
7.3 Conventions and definitions
In addition to the convention of representing an attack as in Equation (7.9), in the following Sections 7.4–
7.5, we use the following conventions.
1. The circuit C that we consider is already “compiled” in terms of the H gates as in Section 4.4 (the
identity H = HPHPHPH is already applied).
2. The number of 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.
3. In the 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 represent the computation wires throughout.
4. Given the system as in Equation (7.9), we suppose that the first 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 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.
5. 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 7.3. For a fixed Pauli P ∈ Pm , we call it benign if P ∈ Bt,n , where Bt,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, Z}. Using the above conventions, this means that Bt,n = {{{I, Z} ⊗ P}⊗t ⊗ Pn−1 ⊗ {I, 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 {X, Y}. In
analogy to the set of benign Paulis, we denote the set of non-benign Paulis acting on m = 2t + n qubits
0 .
as Bt,n
7.4 In the case of a test run
Based on the preliminaries of Section 7.2 and Section 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 7.4 that all non-benign Pauli attacks are
detected by one of the test runs).
Lemma 7.4. Consider the Interactive Proof System 2 for a circuit C on n qubits and with t T-gate
0 be the
gadgets, with attack {Ek } (with each Ek = ∑Q αk,Q Q), and suppose a test run is applied. Let Bt,n
set of non-benign attacks. Then with the following probability, the verifier rejects
1
2∑ ∑0 |αk,Q |2 . (7.13)
k Q∈B t,n
Proof. As a first step towards proving Lemma 7.4, we derive an expression for the system after the
application of the honest circuit (and before any attack). Let hi ∈ {0, 1} (i = 1 . . .t) be a bit that indicates if
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 21
A NNE B ROADBENT
the auxiliary qubit i is an encrypted version of |0i (hi = 0) or |+i (hi = 1). We note that, by the properties
of the protocol, hi = 0 in an X-test run if and only if hi = 1 in a Z-test run.
In the case of an X-test, the system that we obtain after the verifier has performed measurements that
prepare the encrypted auxiliary qubits and the computation wire is
∑ Ph1 ·x1 Hh1 Xd1 |0ih0|Xd1 Hh1 P∗ h1 ·x1 ⊗ Xx1 |0ih0|Xx1 ⊗ · · ·
d1 ...dt ∈{0,1}
x1 ...xt ∈{0,1}
⊗ Pht ·xt Hht Xdt |0ih0|Xdt Hht P∗ ht ·xt ⊗ Xxt |0ih0|Xxt ⊗
∑ Xa1 |0ih0|Xa1 ⊗ · · · ⊗ Xan |0ih0|Xan
a1 ...an ∈{0,1}
⊗ |d1 . . . dt , x1 . . . xt , a1 . . . an ihd1 . . . dt , x1 . . . xt , a1 . . . an | . (7.14)
Note that we have appended a 2t + n qubit register, which is held by the verifier and that contains a
classical basis state representing the key.
In the case of a Z-test, the system that we start with is
∑ Ph1 ·x1 Hh1 Xd1 |0ih0|Xd1 Hh1 P∗ h1 ·x1 ⊗ Xx1 |0ih0|Xx1 ⊗ · · ·
d1 ...dt ∈{0,1}
x1 ...xt ∈{0,1}
⊗ Pht ·xt Hht Xdt |0ih0|Xdt Hht P∗ ht ·xt ⊗ Xxt |0ih0|Xxt ⊗
∑ Zb1 |+ih+|Zb1 ⊗ · · · ⊗ Zbn |+ih+|Zbn
b1 ...bn ∈{0,1}
⊗ |d1 . . . dt , x1 . . . xt , b1 . . . bn ihd1 . . . dt , x1 . . . xt , b1 . . . bn | . (7.15)
We claim that, replacing the P and P∗ gates with the identity in Equation (7.14) and Equation (7.15),
we obtain expressions for the system for each test run, respectively, at the end of the application of the
honest unitary. This essentially follows by construction; for completeness we review the case of each
gate gadget below.
CNOT-gate. As discussed in Section 4.2, in both the X-test and Z-test, a CNOT gate, when applied
to the computation registers (the last n registers), will have no effect (up to a relabelling of the Paulis,
as computed by the key update). Thus a simple change of variable reverts the system to an expression
identical to its prior state.
H-gate. As given in Section 4.4, the application of the H gate to the computation registers will, up to a
relabelling of the Paulis, cause |0i 7→ |+i and vice-versa. Since an even number of H gates are applied to
each computation wire, the starting input state will not be changed by these gates.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 22
H OW TO V ERIFY A Q UANTUM C OMPUTATION
T-gate as part of an X-test. Suppose a T-gate is applied in the X-test run, on qubit j, using an auxiliary
qubit i (i = 1 . . .t). Suppose furthermore that qubit j has undergone an even number of H gates, so that
hi = 0, and the system that the prover acts upon for the T-gate gadget, together with the relevant key
register is
∑ Xdi |0ih0|Xdi ⊗ Xxi |0ih0|Xxi ⊗ Xa j |0ih0| j Xa j ⊗ di , xi , a j di , xi , a j . (7.16)
di ,xi ,a j ∈{0,1}
Applying the Px and CNOT as in the honest computation has very little effect on the system; it only
causes a key update:
∑ Xdi |0ih0|Xdi ⊗ Xxi |0ih0|Xxi ⊗ Xa j ⊕di |0ih0| j Xa j ⊕di ⊗ di , xi , a j ⊕ di di , xi , a j ⊕ di . (7.17)
di ,xi ,a j ∈{0,1}
As per our convention, we swap the first and last registers, so that the data wire remains in its position:
∑ Xa j ⊕di |0ih0|Xa j ⊕di ⊗ Xxi |0ih0|Xxi ⊗ Xdi |0ih0| j Xdi ⊗ a j ⊕ di , xi , di a j ⊕ di , xi , di . (7.18)
di ,xi ,a j ∈{0,1}
Next, a change of variable shows that the expression is unchanged:
∑ Xdi |0ih0|Xdi ⊗ Xxi |0ih0|Xxi ⊗ Xa j |0ih0| j Xa j ⊗ di , xi , a j di , xi , a j . (7.19)
di ,xi ,a j ∈{0,1}
T-gate as part of a Z-test. Suppose a T-gate is applied in the Z test run, on qubit j, using an auxiliary
qubit i (i = 1 . . .t). Suppose furthermore that qubit j has undergone an even number of H gates, so that
hi = 1, and the system that the prover acts upon for the T-gate gadget, together with the relevant key
register is
∑ Pxi Zdi |+ih+|Zdi P∗ xi ⊗ Xxi |0ih0|Xxi ⊗ Zb j |+ih+| j Zb j ⊗ di , xi , b j di , xi , b j . (7.20)
di ,xi ,b j ∈{0,1}
Applying the Px and CNOT as in the honest computation changes the system by canceling out the Pxi and
causing a key update:
∑ Zb j ⊕di ⊕xi |+ih+|Zb j ⊕di ⊕xi ⊗ Xxi |0ih0|Xxi ⊗ Zb j |+ih+| j Zb j
di ,xi ,b j ∈{0,1}
⊗ b j ⊕ di ⊕ xi , xi , b j b j ⊕ di ⊕ xi , xi , b j . (7.21)
As per our convention, we swap the first and last registers, so that the data wire remains in the last
position:
∑ Zb j |+ih+|Zb j ⊗ Xxi |0ih0|Xxi ⊗ Zb j ⊕di ⊕xi |+ih+| j Zb j ⊕di ⊕xi
di ,xi ,b j ∈{0,1}
⊗ b j , xi , b j ⊕ di ⊕ xi b j , xi , b j ⊕ di ⊕ xi . (7.22)
Next, a change of variable shows that the expression is unchanged, except that the P and P∗ gates are
removed:
∑ Zdi |+ih+|Zdi ⊗ Xxi |0ih0|Xxi ⊗ Zb j |+ih+| j Zb j ⊗ di , xi , b j di , xi , b j . (7.23)
di ,xi ,b j ∈{0,1}
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 23
A NNE B ROADBENT
Final expression before an attack. In the case that an odd number of H gates have been applied to a
data wire, the protocol specifies that we should temporarily swap the roles of the X-test and Z-test runs for
the T-gates that immediately follow. In this case, the data qubits and computation will be exactly those
considered in the two cases above, but with the roles of the X-test and Z-test exchanged; the same analysis
thus applies. For both the X-test and Z-test, we iteratively apply the various cases above (depending on
the circuit). Since it is the case that all computation wires eventually have an even number of H-gates
applied, we can write down an expression for the outcome for the X-test run:
∑ Hh1 Xd1 |0ih0|Xd1 Hh1 ⊗ Xx1 |0ih0|Xx1 ⊗ · · ·
d1 ...dt ∈{0,1}
x1 ...xt ∈{0,1}
⊗ Hht Xdt |0ih0|Xdt Hht ⊗ Xxt |0ih0|Xxt ⊗
∑ Xa1 |0ih0|Xa1 ⊗ · · · ⊗ Xan |0ih0|Xan
a1 ...an ∈{0,1}
⊗ |d1 . . . dt , x1 . . . xt , a1 . . . an ihd1 . . . dt , x1 . . . xt , a1 . . . an | . (7.24)
In the case of a Z-test, an expression for the outcome is
∑ Hh1 Xd1 |0ih0|Xd1 Hh1 ⊗ Xx1 |0ih0|Xx1 ⊗ · · ·
d1 ...dt ∈{0,1}
x1 ...xt ∈{0,1}
⊗ Hht Xdt |0ih0|Xdt Hht ⊗ Xxt |0ih0|Xxt ⊗
∑ Zb1 |+ih+|Zb1 ⊗ · · · ⊗ Zbn |+ih+|Zbn
b1 ...bn ∈{0,1}
⊗ |d1 . . . dt , x1 . . . xt , b1 . . . bn ihd1 . . . dt , x1 . . . xt , b1 . . . bn | . (7.25)
Applying the attack, decryption and measurement. Next, we apply the attack for a fixed k, as given
by
Ek = ∑ αQ Q and Ek∗ = ∑ αQ∗ 0 Q0 , (7.26)
Q Q0
followed by the verifier’s decryption, trace and measurement. For the registers that are traced out, we
assume that they are decrypted and measured. Furthermore, since they are traced out, we can assume that
the quantum auxiliary registers with hi = 1 are measured in the diagonal basis. We let
Q = P1 ⊗ Q1 ⊗ P2 ⊗ Q2 ⊗ · · · ⊗ Pt ⊗ Qt ⊗ R1 ⊗ · · · ⊗ Rn , (7.27)
with Pi , Qi , R j ∈ P1 (i = 1 . . .t, j = 1 . . . n) and similarly, let
Q0 = P0 1 ⊗ Q0 1 ⊗ P0 2 ⊗ Q0 2 ⊗ · · · ⊗ P0t ⊗ Q0t ⊗ R0 1 . . . R0 n , (7.28)
with P0 i , Q0 i , R0 j ∈ P1 (i = 1 . . .t, j = 1 . . . n).
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 24
H OW TO V ERIFY A Q UANTUM C OMPUTATION
For the X-test run, conditioned on outcomes i` (where h` = 0), and k1 , . . . , kn the system becomes
∑ ∑ αQ αQ∗ 0 ∑
(h` =1∧ Q,Q0 d1 ...dt ∈{0,1}
i` ∈{0,1}), x1 ...xt ∈{0,1}
jm ∈{0,1}
hi1 |Xd1 Hh1 P1 Hh1 Xd1 |0ih0|Xd1 Hh1 P0 1 Hh1 Xd1 |i1 i ⊗ h j1 |Xx1 Q1 Xx1 |0ih0|Xx1 Q0 1 Xx1 | j1 i
⊗···⊗
hit |Xdt Hht Pt Hht Xdt |0ih0|Xdt Hht P0t Hht Xdt |it i ⊗ h jt |Xxt Qt Xxt |0ih0|Xxt Q0t Xxt | jt i ⊗
∑ hk1 |Xa1 R1 Xa1 |0ih0|Xa1 R0 1 Xa1 |k1 i ⊗ · · · ⊗ hkn |Xan Rn Xan |0ih0|Xan R0n Xan |kn i . (7.29)
a1 ...an ∈{0,1}
Applying the classical Pauli twirl (Lemmas 2.2 and 2.3), we obtain that the cross terms of the attack
vanish, leaving as expression
2 h1 h1 h1 h1
∑ ∑ Q 1 |α | hi |H P1 H |0ih0|H P1 H |i 1 i ⊗ h j |Q
1 1 |0ih0|Q |
1 1j i ⊗···
(h` =1∧ Q
i` ∈{0,1}),
jm ∈{0,1}
⊗ hit |Hht Pt Hht |0ih0|Xdt Hht Pt Hht |it i ⊗ h jt |Qt |0ih0|Qt | jt i ⊗
hk1 |R1 |0ih0|R1 |k1 i ⊗ · · · ⊗ hkn |Rn |0ih0|Rn |kn i . (7.30)
Recall that in an X-test run, the verifier rejects if a measurement result on an auxiliary qubit with
hi = 0 decrypts to the value 1, or if the output decrypts to the value 1. Thus, applying the above to all
terms in {Ek }, we get that the probability that the verifier rejects is given by
∑ ∑ |αk,Q |2 , (7.31)
k Q∈B1
where B1 is the set of 2t +n-qubit Paulis with Pi ∈ {X, Y} (i = 1 . . .t) whenever hi = 0, or with Rn ∈ {X, Y}.
A similar calculation shows that for the Z-test run, conditioned on outcomes i` (where h` = 1), and
k1 , . . . , kn the system becomes
2 h1 h1 h1 h1
∑ ∑ Q 1 |α | hi |H P1 H |0ih0|H P1 H |i 1 i ⊗ h j |Q
1 1 |0ih0|Q |
1 1j i ⊗···
(h` =0∧ Q
i` ∈{0,1}),
jm ∈{0,1}
⊗ hit |Hht Pt Hht |0ih0|Xdt Hht Pt Hht |it i ⊗ h jt |Qt |0ih0|Qt | jt i ⊗
hk1 |R1 |+ih+|R1 |k1 i ⊗ · · · ⊗ hkn |Rn |+ih+|Rn |kn i . (7.32)
Recall that in a Z-test run, the verifier rejects if a measurement result on an auxiliary qubit with hi = 0
decrypts to the value 1. Thus, applying the above to all terms in {Ek }, we get that the probability that the
verifier rejects is given by
∑ ∑ |αk,Q |2 , (7.33)
k Q∈B2
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 25
A NNE B ROADBENT
where B2 is the set of 2t + n-qubit Paulis with Pi ∈ {X, Y} (i = 1 . . .t) whenever hi = 0.
Since each test is executed with probability 1/2, and since hi = 0 in the X-test run if and only if hi = 1
in the Z-test run, we obtain that the probability that the verifier rejects is
1
2∑ ∑0 |αk,Q |2 . (7.34)
k Q∈B t,n
7.5 In the case of a computation run
Again using the preliminaries of Section 7.2 and Section 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 T-gate gadget
(Section 7.5.1), then we do an analysis for the case that the computation run consists in a single T-gate
gadget (Section 7.5.2). This is extended to full generality in Section 7.5.3, where we give a lower bound
(as a function of the attack and of the underlying computation) on the probability that the verifier rejects
in a computation run (see Lemma 7.8).
7.5.1 Effect of a bit flip on a measured qubit
In Lemma 7.5, we establish the effect of a bit flip on the measured qubit in the T-gate gadget.
Lemma 7.5. The error induced by an X-gate on the measured qubit in the T-gate gadget in Figure 9 is
to introduce an extra XZP on the output.
Proof. An X-gate on the measured qubit in Figure 1 will cause the bottom wire to receive the correction
Pa⊕c⊕y⊕1 (instead of Pa⊕c⊕y ). Since Pa⊕c⊕y⊕1 = PZa⊕c⊕y Pa⊕c⊕y , the following shows how we can use
we use and revise the calculation from Equation (5.1)–Equation (5.8).
Pa⊕c⊕y⊕1 Xd Ze Py TXa⊕c Zb = PZa⊕c⊕y Pa⊕c⊕y Xd Ze Py TXa⊕c Zb (7.35)
= PZa⊕c⊕y Xa⊕c⊕d Z(a⊕c⊕d)·(d⊕y)⊕a⊕b⊕c⊕d⊕e⊕y T (7.36)
a⊕c⊕d (a⊕c⊕d)·(d⊕y)⊕a⊕b⊕c⊕d⊕e⊕y a⊕c⊕y a⊕c⊕d
=X Z Z Z PT (7.37)
= Xa⊕c⊕d Z(a⊕c⊕d)·(d⊕y)⊕a⊕b⊕c⊕e PT . (7.38)
We note furthermore that the X-gate on the measured qubit causes the Pauli key to be updated as c ← c ⊕ 1.
Starting with the right-hand side of Equation (7.38), we thus obtain
Xa⊕c⊕d⊕1 Z(a⊕c⊕d⊕1)·(d⊕y)⊕a⊕b⊕c⊕e⊕1 PT = Xa⊕c⊕d Z(a⊕c⊕d)·(d⊕y)⊕a⊕b⊕c⊕d⊕e⊕y (XZP)T . (7.39)
Comparing with Equation (5.8), we thus see that the effect is to apply XZP.
7.5.2 The T-gate protocol under attack
In this section, we analyze the effect of an attack in a single T-gate gadget: we show that the effect of
the gadget on an encrypted qubit is to apply a T gate on the plaintext, while maintaining the encryp-
tion. Furthermore, if the auxiliary qubit undergoes an attack Q1 ∈ {X, Y}, then an error E = XZP (by
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 26
H OW TO V ERIFY A Q UANTUM C OMPUTATION
Lemma 7.5) will be applied to the computation wire. The Pauli twirl plays again an important part in
simplifying a general attack to a convex combination of Pauli attacks. This analysis (Lemma 7.6) is used
as the inductive step in the proof of the general case as analysed in Section 7.5.3 (see Lemma 7.7).
Lemma 7.6. In Interactive Proof System 2, consider a circuit consisting in a single T-gate, applied to a
data wire which is initially an encryption of ρ. Consider a term in the attack {Ek }, given by Q = P1 ⊗ Q1 ,
Q0 = P0 1 ⊗ Q0 1 , acting on the auxiliary qubits (P1 , Q1 , P0 1 , Q0 1 ∈ P1 ). Then in the case P1 ⊗ Q1 6= P10 ⊗ Q01 ,
this term simplifies to 0, whereas otherwise the effect is to apply E δP1 T on the data, while maintaining a
uniform encryption, with the key held by the verifier. (Here, Q ∈ P1 , and δQ = 0 if Q ∈ {I, Z} and δQ = 1
otherwise.)
Proof. Suppose the honest circuit of the prover is applied, followed by an attack and the coherent
correction of the verifier, which is then followed by a measurement of auxiliary qubits. We consider the
effect of a Pauli attack Q = P1 ⊗ Q1 , Q0 = P0 1 ⊗ Q0 1 , acting on the auxiliary qubits (P1 , Q1 , P0 1 , Q0 1 ∈ P1 ).
(Strictly speaking this is not a full attack, but instead, ignoring the coefficient, it corresponds to one term
in the expansion of the full attack as given by {Ek }.) When a bit flip occurs on the top wire (i. e., when
P1 ∈ {X, Y}) in Figure 9, then the outcome undergoes an error E = XZP as given by Lemma 7.5. The
above is summarized in Figure 12.
Xa Zb |ψi •
P1
Prover • Q1 •
0 0
• Px Xa Zb E δP1 T|ψi
x ∈R {0, 1} • • c
Verifier |0i H • (d ∈R {0, 1}, y = a ⊕ c ⊕ x)
|0i T Py⊕d Zd H e
Figure 12: An attack P1 ⊗ Q1 on a single T-gate gadget (computation run). Here, a0 = a ⊕ c and
b0 = (a ⊕ c) · (d ⊕ y) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ y .
In order to give a mathematical expression for Figure 12, we use the circuit identity in Figure 7
(according to which the measurement outcome c undergoes an encryption and decryption with d). First
we consider the case δP1 = δP10 . Applying y = a ⊕ c ⊕ x, and considering the trace of the auxiliary qubits,
we get the following expression
∑ ∑ hi|Xd P1 Xd |cihc|Xd P0 1 Xd |ii ⊗ h j|Xx Q1 Xx |0ih0|Xx Q0 1 Xx | ji⊗
i, j∈{0,1} a,b,c,d,e,x∈{0,1}
Xa⊕c Z(a⊕c)·(d⊕x)⊕a⊕b⊕c⊕e⊕x E δP1 TρT∗ E ∗ δP1 Z(a⊕c)·(d⊕x)⊕a⊕b⊕c⊕e⊕x Xa⊕c
⊗ |a ⊕ c, (a ⊕ c) · (d ⊕ x) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ xiha ⊕ c, (a ⊕ c) · (d ⊕ x) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ x| . (7.40)
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 27
A NNE B ROADBENT
Note that above, we have included a key register for the computation wire, and have considered that the
first register is traced out, thus since δP1 = δP10 , cross terms of the form
hi|Xd P1 Xd |ci c0 Xd P0 1 Xd |ii (7.41)
with c 6= c0 vanish and are therefore excluded. Furthermore, we consider without loss of generality that
the second register is decrypted with Xx before being traced out.
Since a, b, and e appear only on the data register, and by a change of variable, we can rewrite this as
∑ ∑ hi|Xd P1 Xd |cihc|Xd P0 1 Xd |ii ⊗ h j|Xx Q1 Xx |0ih0|Xx Q0 1 Xx | ji⊗
i, j∈{0,1} c,d,x∈{0,1}
∑ Xa Zb E δP1 TρT∗ E ∗ δP1 Zb Xa ⊗ |a, biha, b| . (7.42)
a,b∈{0,1}
Applying the classical Pauli twirl (Lemma 2.2), we get that for the case under consideration (δP1 = δP10 ),
the system is 0 if P1 ⊗ Q1 6= P10 ⊗ Q01 , and otherwise is
∑ Xa Zb E δP1 TρT∗ E ∗ δP1 Zb Xa ⊗ |a, biha, b| . (7.43)
a,b∈{0,1}
Next we consider the case δP1 6= δP10 . Again applying y = a ⊕ c ⊕ x, letting c0 = c ⊕ 1, and considering
the trace of the auxiliary qubits, we get the following expression
∑ ∑ hi|Xd P1 Xd |ci c0 Xd P0 1 Xd |ii ⊗ h j|Xx Q1 Xx |0ih0|Xx Q0 1 Xx | ji⊗
i, j∈{0,1} a,b,c,d,e,x∈{0,1}
δ 0 0 0 0
ξ Xa⊕c Z(a⊕c)·(d⊕x)⊕a⊕b⊕c⊕e⊕x E δP1 TρT∗ E ∗ P1 Z(a⊕c )·(d⊕x)⊕a⊕b⊕c ⊕e⊕x Xa⊕c
⊗ |a ⊕ c, (a ⊕ c) · (d ⊕ x) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ xi a ⊕ c0 , (a ⊕ c0 ) · (d ⊕ x) ⊕ a ⊕ b ⊕ c0 ⊕ e ⊕ x . (7.44)
Note that above, we have included a key register for the computation wire, and have considered that the
first register is traced out. Thus terms of the form hi|Xd P1 Xd |cihc|Xd P0 1 Xd |ii vanish and are therefore
excluded. We again consider without loss of generality that the second register is decrypted with Xx
before being traced out. Here, ξ represents a phase that depends on the key register and is due to the fact
that c 6= c0 .
Since δP1 = δP10 ⊕ 1, since a, b, and e appear only on the data register, and by the following change of
variable,
a ← a⊕c (7.45)
b ← (a ⊕ c) · (d ⊕ x) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ x (7.46)
0 0
e ← (a ⊕ c ) · (d ⊕ x) ⊕ a ⊕ b ⊕ c ⊕ e ⊕ x , (7.47)
we can rewrite this as
∑ ∑ hi|Xd P1 Xd |cihc|Xd (XP0 1 )Xd |ii ⊗ h j|Xx Q1 Xx |0ih0|Xx Q0 1 Xx | ji⊗
i, j∈{0,1} c,d,x∈{0,1}
∑ ξ Xa Zb E δP1 TρT∗ E ∗ δP1 Ze Xa⊕1 ⊗ |a, biha ⊕ 1, e| . (7.48)
a,b,e∈{0,1}
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 28
H OW TO V ERIFY A Q UANTUM C OMPUTATION
Next, we apply the Pauli twirl to the first register, which yields 0 unless P1 = XP10 , in which case we
also get 0, since hi|P1 |cihc|(XP1 )|ii = 0.
Thus, we conclude that the case P1 ⊗ Q1 6= P10 ⊗ Q01 evaluates to 0, whereas otherwise (by Equa-
tion (7.43)) the effect of the T-gate gadget is to apply E δP1 T on the data, while maintaining a uniform
encryption, with the key held by the verifier.
7.5.3 General analysis for a computation run
In this section, we bound the acceptance probability in the case of a computation run. This result is
presented in Lemma 7.8, the proof of which depends on the following Lemma
Lemma 7.7. Consider Interactive Proof System 2 for a circuit C on n qubits and with t T-gate gadgets,
with attack {Ek } (with each Ek = ∑Q αk,Q Q). Suppose the target circuit C is decomposed as
C = T`t Ct . . . T`2 C2 T`1 C1 , (7.49)
where each Ci is a Clifford group circuit and `i ∈ {1 . . . n} indicates that the ith T-gate acts on qubit `i
(i = 1 . . .t). Let
Q = P1 ⊗ Q1 ⊗ P2 ⊗ Q2 ⊗ · · · ⊗ Pt ⊗ Qt , (7.50)
with Pi , Qi ∈ P1 (i = 1 . . .t) and similarly, let
Q0 = P0 1 ⊗ Q0 1 ⊗ P0 2 ⊗ Q0 2 ⊗ · · · ⊗ P0t ⊗ Q0t , (7.51)
with P0 i , Q0 i ∈ P1 (i = 1 . . .t). Let E be the error on the output induced by an X on the top wire in Figure 9.
For a Pauli P ∈ P1 , let δP = 0 if P ∈ {I, Z} and δP = 1 otherwise. Then we claim that after the honest
computation, attack, the verifier’s conditional corrections and tracing out of the auxiliary system, the
term of the system corresponding to the attack (Q, Q0 ) is 0 if
P1 ⊗ Q1 ⊗ P2 ⊗ Q2 ⊗ · · · ⊗ Pt ⊗ Qt 6= P10 ⊗ Q01 ⊗ P20 ⊗ Q02 ⊗ · · · ⊗ Pt0 ⊗ Qt0 , (7.52)
and otherwise is
δ δP
∑ (Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn )E`tPt T`t Ct . . . E δP2 `2 T`2 C2 E`1 1 T`1 C1 |0n i
a1 ,b1 ,...an ,bn
∈{0,1}
δP δP
h0n |C1 ∗ T∗`1 E ∗ `1 1 C2 ∗ T∗`2 E ∗ `2 2 . . .Ct ∗ T∗`t E ∗ `tPt (Zb1 Xa1 ⊗ · · · Zbn Xan )
δ
⊗ |a1 , b1 , . . . , an , bn iha1 , b1 , . . . , an , bn | . (7.53)
Note that in the statement of Lemma 7.7 above, we have that Q and Q0 are applied only to auxiliary
qubits—we have thus omitted the “R” portion of the attack. Furthermore, we refer the reader to Figure 12
for the t = 1 case.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 29
A NNE B ROADBENT
Proof. Lemma 7.7 is proven by induction on t. The base case t = 0 is verified, since the initial system is
∑ Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn |0n ih0n |Zb1 Xa1 ⊗ · · · ⊗ Zbn Xan ⊗ |a1 , b1 , . . . , an , bn iha1 , b1 , . . . , an , bn | .
a1 ,b1 ,...,an ,bn
∈{0,1}
(7.54)
Next, suppose Equation (7.53) holds for t = k and consider t = k + 1. Now, because each Pauli acts
on a different subsystem, an attack
Q = P1 ⊗ Q1 ⊗ P2 ⊗ Q2 ⊗ · · · ⊗ Pk ⊗ Qk ⊗ Pk+1 ⊗ Qk+1 (7.55)
can be decomposed as an attack on the first 2k auxiliary qubits, followed by an attack of the last two
qubits (and similarly for Q0 ). Suppose Pi ⊗ Qi = Pi0 ⊗ Q0i (i = 1 . . . k). By the hypothesis, the outcome will
be the application of the computation corresponding to the gadgets for Ck+1 and T`k+1 , followed by attack
(Qk+1 ⊗ Pk+1 , Q0k+1 ⊗ Pk+1
0
), (7.56)
on an encrypted system ρ given by:
δP δP
ρ= ∑ (Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn )E`k k T`k Ck . . . E δP2 `2 T`2 C2 E`1 1 T`1 C1 |0n i
a1 ,b1 ,...an ,bn
∈{0,1}
δP δP
h0n |C1∗ T∗`1 E ∗ `1 1 C2∗ T∗`2 E ∗ `2 2 . . .Ck∗ T∗`k E ∗ `kPt (Zb1 Xa1 ⊗ · · · Zbn Xan ) ⊗
δ
|a1 , b1 , . . . , an , bn iha1 , b1 , . . . , an , bn | . (7.57)
First, the prover applies a Clifford circuit Ck+1 . After a key update as given in Section 4, a change of
variable will lead to ρ 0 :
δP δP
ρ0 = ∑ (Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn )Ck+1 E`k k T`k Ck . . . E δP2 `2 T`2 C2 E`1 1 T`1 C1 |0n i
a1 ,b1 ,...an ,bn
∈{0,1}
δP δP
h0n |C1 ∗ T∗`1 E ∗ `1 1 C2∗ T∗`2 E ∗ `2 2 . . .Ck∗ T∗`k E ∗ `kPt Ck+1
∗
δ
(Zb1 Xa1 ⊗ · · · Zbn Xan ) ⊗
|a1 , b1 , . . . , an , bn iha1 , b1 , . . . , an , bn | . (7.58)
Next, the auxiliary qubits for T`k+1 are used; we apply Lemma 7.6 (only a single qubit, `k+1 is affected
by this part of the computation). Thus, if
Qk+1 ⊗ Pk+1 6= Q0k+1 ⊗ Pk+1
0
, (7.59)
the term vanishes, and otherwise it becomes
δP δP δP
∑ (Xa1 Zb1 ⊗ · · · ⊗ Xan Zbn )E`k+1
k+1
T`k+1 Ck+1 E`k k T`k Ck . . . E δP2 `2 T`2 C2 E`1 1 T`1 C1 |0n i
a1 ,b1 ,...an ,bn
∈{0,1}
δP δP δP
h0n |C1∗ T∗`1 E ∗ `1 1 C2∗ T∗`2 E ∗ `2 2 . . .Ck∗ T∗`k E ∗ `kPt Ck+1
∗
T∗ `k+1 E ∗ `k+1
δ k+1
(Zb1 Xa1 ⊗ · · · Zbn Xan ) ⊗
|a1 , b1 , . . . , an , bn iha1 , b1 , . . . , an , bn | . (7.60)
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 30
H OW TO V ERIFY A Q UANTUM C OMPUTATION
By the hypothesis, the term also vanishes if
Pi ⊗ Qi 6= Pi0 ⊗ Q0i (i = 1 . . . k) . (7.61)
Thus, Lemma 7.7 holds for the case t = k + 1 and by induction, Lemma 7.7 holds in general.
We now state and prove the main result of this Section.
Lemma 7.8. Consider the Interactive Proof System 2 for a circuit C on n qubits and with t T-gate
gadgets, with attack {Ek } (with each Ek = ∑Q αk,Q Q). Let Bt,n be the set of benign attacks. Then the
probability that the verifier rejects for a computation run is at least:
(1 − p) ∑ ∑ |αk,Q |2 , (7.62)
k Q∈Bt,n
where
p = k(|0ih0| ⊗ In−1 )C|0n ik2 (7.63)
is the probability that we observe “0” as a results of a computational basis measurement of the nth output
qubit, obtained by evaluating C on input |0n i.
Proof. Let the notation be as in Lemma 7.7. We apply Lemma 7.7 to the case of the attack {Ek }. We
denote each
Ek = ∑ αk,Q⊗R Q ⊗ R , (7.64)
Q⊗R
where
Q = P1 ⊗ Q1 ⊗ P2 ⊗ Q2 ⊗ · · · ⊗ Pt ⊗ Qt (7.65)
(as before) and R ∈ Pn . By linearity, we obtain the following system after the honest computation, attack,
the verifier’s conditional corrections and tracing out of the auxiliary system
∗
∑ ∑ ∑ ∑ αk,Q⊗R αk,Q⊗R R(Xa Zb ⊗ · · · ⊗ Xa Zb )
0
1 1 n n
a1 ,b1 ,...an ,bn k R,R0 Q
∈{0,1}
δP δP δP
E`tPt T`t Ct . . . E δP2 `2 T`2 C2 E`1 1 T`1 C1 |0n ih0n |C1∗ T∗`1 E ∗ `1 1 C2∗ T∗`2 E ∗ `2 2 . . .
δ
. . .Ct∗ T∗`t E ∗ `tPt (Zb1 Xa1 ⊗ · · · Zbn Xan )R0 ⊗
δ
|a1 , b1 , . . . , an , bn iha1 , b1 , . . . , an , bn | . (7.66)
We can assume that the verifier then decrypts the system; by the Pauli twirl (Lemma 2.1), the terms with
R 6= R0 vanish, leaving as the computation registers
δP1 δP1 δP2
∑ ∑ |αk,Q⊗R |2 RE` T` Ct . . . E δ `2 T` C2 E` T` C1 |0n ih0n |C1∗ T∗` E ∗ ` C2∗ T∗` E ∗ ` . . .Ct∗ T∗` E ∗ ` R .
δPt P2 δPt
t t 2 1 1 1 1 2 2 t t
k Q,R
(7.67)
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 31
A NNE B ROADBENT
Denoting R = R1 ⊗ · · · ⊗ Rn (Ri ∈ P1 ), we see that each term with Q ⊗ R being benign leads to the output
bit having the same distribution as in the honest case (Because for all i, benign attacks have δPi = 0, and
also Rn ∈ {I, Z} will have no effect on the output qubit that is measured.) In the honest case, p is the
probability of observing “0” (which leads to the verifier accepting). In the case of the Pauli Q ⊗ R being
not benign, we have no bound on the acceptance probability. Thus, with probability at least
(1 − p) ∑ ∑ |αk,Q |2 , (7.68)
k Q∈Bt,n
the verifier rejects.
7.6 Proof of soundness
In order to complete the proof of soundness, we combine Lemma 7.4 and Lemma 7.8. Consider the
Interactive Proof System 2 for a circuit C on n qubits and with t T-gate gadgets, with attack {Ek }, where
Ek = ∑ αk,Q Q . (7.69)
Q
0 be the set of non-benign Pauli attacks, and let p be as
Let Bt,n be the set of benign Pauli attacks, and Bt,n
given in Lemma 7.8. Then since a test run occurs with probability 2/3 and a computation run occurs with
probability 1/3, the probability that the verifier rejects is at least
2 1 1
· ∑ ∑ |αk,Q |2 + (1 − p) ∑ ∑ |αk,Q |2 . (7.70)
3 2 k Q∈B0 3 k Q∈Bt,n
t,n
Suppose that the input corresponds to a no instance of Q-CIRCUIT. Hence, 1− p ≥ 2/3 and the probability
that the verifier rejects is at least 2/9 since
1 1− p
∑ ∑ |αk,Q |2 + ∑ |αk,Q |2 (7.71)
3 k Q∈B0 3 ∑ k Q∈Bt,n
t,n
1 2
≥ ∑ ∑ |αk,Q |2 + ∑ ∑ |αk,Q |2 (7.72)
3 k Q∈B0 9 k Q∈Bt,n
t,n
2 1
=
9∑ ∑ |αk,Q |2 + 9 ∑ ∑0 |αk,Q |2 (7.73)
k Q∈P2t+n k Q∈B t,n
2
≥ . (7.74)
9
In Section 6, we saw that, in the case that the prover is honest, the probability c of acceptance of a
yes-instance of Q-CIRCUIT satisfies c ≥ 8/9 (completeness). We have determined above that for every
prover, the probability s of acceptance of a no-instance satisfies s ≤ 1 − 2/9 = 7/9 (soundness). Thus we
have c − s ≥ 1/9, which, by standard amplification, completes the proof of Theorem 3.3.
One consequence of the proof in this section is to note that the identity attack (i. e., the prover’s honest
behaviour) yields
∑ ∑ |αk,Q |2 = 0
0
(7.75)
k Q∈Bt,n
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 32
H OW TO V ERIFY A Q UANTUM C OMPUTATION
and
1− p 1− p
∑ ∑ |αk,Q |2 = , (7.76)
3 k Q∈Bt,n 3
from which we conclude (Equation (7.71)) that the identity attack is an attack that minimizes the
probability of rejection of a no instance.
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, Evelyn Wainewright and to the anonymous referees
for feedback on an earlier version of this work.
References
[1] S COTT A ARONSON AND A LEX A RKHIPOV: The computational complexity of linear op-
tics. Theory of Computing, 9(4):143–252, 2013. Preliminary version in STOC’11.
[doi:10.4086/toc.2013.v009a004, arXiv:1011.3245] 2
[2] S COTT A ARONSON AND A LEX A RKHIPOV: BosonSampling is far from uniform. Quantum Inf.
Comput., 14(15-16):1383–1423, 2014. [arXiv:1309.7460, ECCC:TR13-135] 2
[3] D ORIT A HARONOV, M ICHAEL B EN -O R , AND E LAD E BAN: Interactive proofs for quantum
computations. In Proc. 1st Symp. Innovations in Computer Science (ICS’10), pp. 453–469, 2010.
[arXiv:1704.04487] 3, 4, 5, 9
[4] D ORIT A HARONOV, M ICHAEL B EN -O R , E LAD E BAN , AND U RMILA M AHADEV: Interactive
proofs for quantum computations, 2017. [arXiv:1704.04487] 3
[5] D ORIT A HARONOV, VAUGHAN J ONES , AND Z EPH L ANDAU: A polynomial quantum algorithm
for approximating the Jones polynomial. Algorithmica, 55(3):395–421, 2009. Preliminary version
in STOC’06. [doi:10.1007/s00453-008-9168-0, arXiv:quant-ph/0511096] 2
[6] D ORIT A HARONOV AND U MESH VAZIRANI: Is Quantum Mechanics falsifiable? A computational
perspective on the foundations of Quantum Mechanics. In Computability: Turing, Gödel, Church,
and Beyond, pp. 329–349. MIT Press, 2013. [arXiv:1206.3686] 2, 3
[7] A NDRIS A MBAINIS , M ICHELE M OSCA , A LAIN TAPP, AND RONALD DE W OLF: Pri-
vate quantum channels. In Proc. 41st FOCS, pp. 547–553. IEEE Comp. Soc. Press, 2000.
[doi:10.1109/SFCS.2000.892142, arXiv:quant-ph/0003101] 7
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 33
A NNE B ROADBENT
[8] L ÁSZLÓ BABAI: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM
Press, 1985. [doi:10.1145/22145.22192] 8
[9] H OWARD BARNUM , C LAUDE C RÉPEAU , DANIEL G OTTESMAN , A DAM S MITH , AND A LAIN
TAPP: Authentication of quantum messages. In Proc. 43rd FOCS, pp. 449–458. IEEE Comp. Soc.
Press, 2002. [doi:10.1109/SFCS.2002.1181969, arXiv:quant-ph/0205128] 3
[10] S TEFANIE BARZ , J OSEPH F. F ITZSIMONS , E LHAM K ASHEFI , AND P HILIP WALTHER:
Experimental verification of quantum computation. Nature Physics, 9(11):727–731, 2013.
[doi:10.1038/nphys2763, arXiv:1309.0005] 3
[11] M ICHAEL B EN -O R , C LAUDE C RÉPEAU , DANIEL G OTTESMAN , AVINATAN H ASSIDIM , AND
A DAM S MITH: Secure multiparty quantum computation with (only) a strict honest majority. In
Proc. 47th FOCS, pp. 249–260. IEEE Comp. Soc. Press, 2006. [doi:10.1109/FOCS.2006.68,
arXiv:0801.1544] 3, 5
[12] P. O SCAR B OYKIN , TAL M OR , M ATTHEW P ULVER , V WANI ROYCHOWDHURY, AND FARROKH
VATAN: A new universal and fault-tolerant quantum basis. Inform. Process. Lett., 75(3):101–107,
2000. [doi:10.1016/S0020-0190(00)00084-3, arXiv:quant-ph/9906054] 5, 10
[13] G ILLES B RASSARD , DAVID C HAUM , AND C LAUDE C RÉPEAU: Minimum disclosure proofs of
knowledge. J. Comput. System Sci., 37(2):156–189, 1988. [doi:10.1016/0022-0000(88)90005-0] 6
[14] A NNE B ROADBENT: Delegating private quantum computations. Canad. J. Physics, 93(9):941–946,
2015. [doi:10.1139/cjp-2015-0030, arXiv:1506.01328] 5, 10
[15] A NNE B ROADBENT, J OSEPH F. F ITZSIMONS , AND E LHAM K ASHEFI: Universal blind
quantum computation. In Proc. 50th FOCS, pp. 517–526. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/FOCS.2009.36, arXiv:0807.4154] 3, 4
[16] A NNE B ROADBENT, G US G UTOSKI , AND D OUGLAS S TEBILA: Quantum one-time programs. In
Proc. 33rd Ann. Intern. Cryptology Conf. (CRYPTO’13), pp. 344–360, 2013. [doi:10.1007/978-3-
642-40084-1_20, arXiv:1211.1080] 3, 4, 5
[17] A NNE B ROADBENT AND S TACEY J EFFERY: Quantum homomorphic encryption for circuits of low
T-gate complexity. In Proc. 35th Ann. Intern. Cryptology Conf. (CRYPTO’15), pp. 609–629, 2015.
[doi:10.1007/978-3-662-48000-7_30, arXiv:1412.8766] 5, 10
[18] A NDREW M. C HILDS , D EBBIE W. L EUNG , AND M ICHAEL A. N IELSEN: Unified derivations
of measurement-based schemes for quantum computation. Phys. Rev. A, 71(3):032318, 2005.
[doi:10.1103/PhysRevA.71.032318, arXiv:quant-ph/0404132] 13
[19] A NDREA C OLADANGELO , A LEX G RILO , S TACEY J EFFERY, AND T HOMAS V IDICK: Verifier-on-
a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources,
2017. [arXiv:1708.07359] 4
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 34
H OW TO V ERIFY A Q UANTUM C OMPUTATION
[20] A NNE C ONDON AND R ICHARD E. L ADNER: Interactive proof systems with polynomially
bounded strategies. J. Comput. System Sci., 50(3):506–518, 1995. Preliminary version in SCT’92.
[doi:10.1109/SCT.1992.215403] 2
[21] I VAN B. DAMGÅRD , S ERGE F EHR , L OUIS S ALVAIL , AND C HRISTIAN S CHAFFNER: Cryptogra-
phy in the bounded-quantum-storage model. SIAM J. Comput., 37(6):1865–1890, 2008. Preliminary
version in FOCS’05. [doi:10.1137/060651343, arXiv:quant-ph/0508222] 4
[22] C HRISTOPH DANKERT, R ICHARD C LEVE , J OSEPH E MERSON , AND E TERA L IVINE: Exact
and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A,
80(1):012304, 2009. [doi:10.1103/PhysRevA.80.012304, arXiv:quant-ph/0606161] 6, 7
[23] V EDRAN D UNJKO , J OSEPH F. F ITZSIMONS , C HRISTOPHER P ORTMANN , AND R ENATO R EN -
NER : Composable security of delegated quantum computation. In 20th Internat. Conf. on the
Theory and Appl. of Cryptology and Information Security (ASIACRYPT’14), pp. 406–425, 2014.
[doi:10.1007/978-3-662-45608-8_22, arXiv:1301.3662] 4
[24] R ICHARD P. F EYNMAN: Simulating physics with computers. Internat. J. Theoretical Physics,
21(6-7):467–488, 1982. [doi:10.1007/BF02650179] 2
[25] K ENT A. G. F ISHER , A NNE B ROADBENT, LYNDEN K. S HALM , Z HENNYA YAN , J ONATHAN
L AVOIE , ROBERT P REVEDEL , T HOMAS J ENNEWEIN , AND K EVIN J. R ESCH: Quantum com-
puting on encrypted data. Nature Communications, 5:3074, 2014. [doi:10.1038/ncomms4074,
arXiv:1309.2586] 4, 5, 10
[26] J OSEPH F. F ITZSIMONS AND M ICHAL H AJDUŠEK: Post hoc verification of quantum computation,
2015. [arXiv:1512.04375] 4
[27] J OSEPH F. F ITZSIMONS AND E LHAM K ASHEFI: Unconditionally verifiable blind computation,
2012. [arXiv:1203.5217] 3, 4
[28] J OSEPH F. F ITZSIMONS AND E LHAM K ASHEFI: Unconditionally verifiable blind quantum compu-
tation. Phys. Rev. A, 96(1):012303, 2017. [doi:10.1103/PhysRevA.96.012303] 3
[29] Z HENGTING G AN AND ROBERT J. H ARRISON: Calibrating quantum chemistry: A multi-teraflop,
parallel-vector, full-configuration interaction program for the Cray-X1. In 18th Ann. Conf. on
Supercomputing (SC’05), pp. 22–22, 2005. [doi:10.1109/SC.2005.17] 2
[30] C HRISTIAN G OGOLIN , M ARTIN K LIESCH , L EANDRO AOLITA , AND J ENS E ISERT: Boson-
Sampling in the light of sample complexity, 2013. [arXiv:1306.3995] 2
[31] S HAFI G OLDWASSER , YAEL TAUMAN K ALAI , AND G UY N. ROTHBLUM: Delegating compu-
tation: Interactive proofs for muggles. J. ACM, 62(4):27:1–27:64, 2015. Preliminary version in
STOC’08. [doi:10.1145/2699436, ECCC:TR17-108] 2
[32] S HAFI G OLDWASSER , S ILVIO M ICALI , AND C HARLES R ACKOFF: The knowledge complexity of
interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989. Preliminary version in STOC’85.
[doi:10.1137/0218012] 8
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 35
A NNE B ROADBENT
[33] DANIEL G OTTESMAN AND I SAAC L. C HUANG: Demonstrating the viability of universal quantum
computation using teleportation and single-qubit operations. Nature, 402(6760):390–393, 1999.
[doi:10.1038/46503, arXiv:quant-ph/9908010] 4
[34] M ASAHITO H AYASHI AND M ICHAL H AJDUŠEK: Self-guaranteed measurement-based quantum
computation, 2016. [arXiv:1603.02195] 3
[35] M ASAHITO H AYASHI AND T OMOYUKI M ORIMAE: Verifiable measurement-only blind
quantum computing with stabilizer testing. Phys. Rev. Lett., 115(22):220502, 2015.
[doi:10.1103/PhysRevLett.115.220502, arXiv:1505.07535] 3
[36] R AHUL JAIN , Z HENGFENG J I , S ARVAGYA U PADHYAY, AND J OHN WATROUS: QIP
= PSPACE. Comm. ACM, 53(12):102–109, 2010. Preliminary version in STOC’10.
[doi:10.1145/1859204.1859231, arXiv:0907.4737] 6
[37] T HEODOROS K APOURNIOTIS , V EDRAN D UNJKO , AND E LHAM K ASHEFI: On optimising quan-
tum communications in verifiable quantum computing. In Asian Quantum Info. Sci. Conf. (AQIS’15),
pp. 23–25, 2015. [arXiv:1506.06943] 3
[38] E LHAM K ASHEFI AND P ETROS WALLDEN: Optimised resource construction for verifiable
quantum computation. J. Physics A, 50(14):145306, 2017. [doi:10.1088/1751-8121/aa5dac,
arXiv:1510.07408] 3
[39] J ULIA K EMPE , H IROTADA KOBAYASHI , K EIJI M ATSUMOTO , AND T HOMAS V IDICK: Using
entanglement in quantum multi-prover interactive proofs. Comput. Complexity, 18(2):273–307,
2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0275-3, arXiv:0711.3715] 5
[40] C ARSTEN L UND , L ANCE F ORTNOW, H OWARD K ARLOFF , AND N OAM N ISAN: Algebraic meth-
ods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146605] 2
[41] M ICHAEL A. N IELSEN AND I SSAC L. C HUANG: Quantum Computation and Quantum Information.
Cambridge University Press, 2000. [doi:10.1017/CBO9780511976667] 7
[42] B EN W. R EICHARDT, FALK U NGER , AND U MESH VAZIRANI: Classical command of quantum sys-
tems. Nature, 496(7446):456–460, 2013. Preliminary version in ITCS’13. [doi:10.1038/nature12035,
arXiv:1209.0448, arXiv:1209.0449] 3
[43] A DI S HAMIR: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146609] 2
[44] P ETER W. S HOR AND J OHN P RESKILL: Simple proof of security of the BB84 quantum key
distribution protocol. Phys. Rev. Lett., 85(2):441–444, 2000. [doi:10.1103/physrevlett.85.441,
arXiv:quant-ph/0003004] 4
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 36
H OW TO V ERIFY A Q UANTUM C OMPUTATION
[45] N ICOLÒ S PAGNOLO , C HIARA V ITELLI , M ARCO B ENTIVEGNA , DANIEL J B ROD , A NDREA
C RESPI , F ULVIO F LAMINI , S ANDRO G IACOMINI , G IORGIO M ILANI , ROBERTA R AMPONI ,
PAOLO M ATALONI , ROBERTO O SELLAME , E RNESTO F. G ALVÃO , AND FABIO S CIARRINO:
Experimental validation of photonic boson sampling. Nature Photonics, 8(8):615–620, 2014.
[doi:10.1038/nphoton.2014.135, arXiv:1311.1622] 2
[46] J OHN WATROUS: PSPACE has constant-round quantum interactive proof systems. Theoret. Comput.
Sci., 292(3):575–588, 2003. Preliminary version in FOCS’99. [doi:10.1016/S0304-3975(01)00375-
9, arXiv:cs/9901015] 9
[47] X INLAN Z HOU , D EBBIE W. L EUNG , AND I SAAC L. C HUANG: Methodology for quantum
logic gate construction. Phys. Rev. A, 62(5):052316, 2000. [doi:10.1103/PhysRevA.62.052316,
arXiv:quant-ph/0002039] 13
AUTHOR
Anne Broadbent
Associate professor
University of Ottawa
Ottawa, ON, Canada
abroadbe uottawa ca
http://mysite.science.uottawa.ca/abroadbe/
ABOUT THE AUTHOR
A NNE B ROADBENT holds an undergraduate degree (2002) in Combinatorics and Optimiza-
tion from the University of Waterloo. Her Master’s (2004) and Ph. D. (2008) work
were supervised by Gilles Brassard and Alain Tapp at the Département d’informatique
et de recherche opérationnelle of Université de Montréal. In her spare time, she likes
researching quantum cryptography beyond quantum key distribution.
T HEORY OF C OMPUTING, Volume 14 (11), 2018, pp. 1–37 37