Authors Matthew McKague,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42
www.theoryofcomputing.org
Interactive Proofs for BQP
via Self-Tested Graph States
Matthew McKague∗
Received May 3, 2015; Revised June 1, 2016; Published June 18, 2016
Abstract: Using the measurement-based quantum computation model, we construct in-
teractive proofs with non-communicating quantum provers and a classical verifier. Our
construction gives interactive proofs for all languages in BQP with a polynomial number of
quantum provers, each of which, in the honest case, performs only a single measurement.
In this paper we introduce two main improvements over previous work in self-testing
for graph states. Specifically, we derive new error bounds which scale polynomially with
the size of the graph compared with exponential dependence on the size of the graph in
previous work. We also extend the self-testing error bounds on measurements to a very
general set which includes the adaptive measurements used for measurement-based quantum
computation as a special case. These improvements allow us to apply graph state self-testing
and measurement based quantum computation to build interactive proofs for all languages in
BQP.
ACM Classification: F.1.3
AMS Classification: 68Q15
Key words and phrases: complexity theory, quantum computing, interactive proofs, BQP
1 Introduction
We seek to find interactive proofs between quantum provers and classical verifiers, both limited to
polynomial-time calculations. That is to say, we would like to have a procedure where a classical
computer (the “verifier”), limited to a polynomial number of operations, can query a quantum computer
∗ Supported by the Dodd-Walls Centre for Photonic and Quantum Technologies, the University of Otago, and the Centre for
Quantum Technologies.
© 2016 Matthew McKague
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2016.v012a003
M ATTHEW M C K AGUE
(the “prover”), also limited to a polynomial number of operations, and tap into its resources in order to
perform some computation. Additionally, if the verifier unhappily interacts with a malicious quantum
computer it should be able to detect this and abort the calculation, even if the prover has unlimited
computational resources. To make the challenge less trivial, there should exist interactive proofs for
problems that are harder than the verifier could solve by itself and ideally there should exist interactive
proofs for any problem that the prover can solve by itself.
This problem is interesting for a variety of reasons. First, as a complexity theoretic question it has
obvious value in further developing the theory of how powerful quantum computers are. From a practical
computing point of view, it would be nice to know whether it would be possible to have cheap classical
computers interact with large (and presumably more expensive) quantum “servers,” paying for services
as required. Of course the users would like to know that they get their money’s worth, and interactive
computations can confirm this. As well, from an experimental point of view, interactive proofs can
be used to verify the operation of some experimental apparatus. This is of particular importance for
quantum experiments since it may well be that, for large experiments, it is impossible (in practical terms)
to classically compute what the predictions of the quantum model are, leading to questions about the
falsifiability of the quantum formalism [3].
Clearly the set of languages recognizable by a poly-time classical verifier and poly-time quantum
prover lies somewhere between P and BQP since on one hand the verifier can ignore the prover, and
on the other hand the verifier and honest prover together form a poly-time quantum machine. As well,
there do exist interactive proofs for all of BQP since BQP ⊆ PSPACE and PSPACE = IP [10, 27], but
the known constructions require the prover to solve PSPACE-complete problems. Constructions for
particular problems are known ([16] for example) and of course anything in NP has a trivial interactive
proof. A general construction, however, has not yet been found.
One approach to solving the problem is to devise a method of detecting dishonest provers. Current
techniques [1, 4, 11, 12, 13, 15, 18, 20, 22, 23, 26] for probing the behavior of adversarial quantum
systems all rely on entanglement and hence in order to make use of them we must introduce more provers.
Reichardt et al. [26] considered the case of two provers. Here we will consider the case of a polynomial
number of provers, but each limited to a single operation, and show that we can recognize all of BQP
with this model.
Thinking more broadly, we may look at different relaxations of the problem. One possibility is to
grant the verifier some limited quantum capability. This approach is taken by Broadbent et al. [5] and
Aharonov et al. [2].
Our construction uses two major components. One is self-testing and the other is measurement-based
quantum computation. Self-testing allows us to confirm that the provers hold on to a graph state and
perform certain measurements on this state when instructed to do so. Measurement-based quantum
computation allows us to use these verified resources to perform the desired calculation.
1.1 Previous work
Self-testing was introduced by Mayers and Yao [12, 13]. Their goal was to establish that a pair of devices
share a maximally entangled pair of qubits, and that the devices implement some specific measurements,
all while making a minimum of assumptions on the devices. Most importantly they make no assumptions
about the dimension of the Hilbert space associated with the devices. Meanwhile, van Dam et al. [28]
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 2
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
considered testing gates in the context of known Hilbert space dimension. Magniez et al. [11] combined
the two approaches, allowing testing of entire quantum circuits. Further refinements, including simpler
proof techniques and extension to complex measurements appear in [14] and [17]. Self-testing of graph
states, critical for our application, appears in [15]. Miller and Shi [20] also give a general construction for
self-testing states based on any XOR game.
These previous works all require additional assumptions. In particular, they assume that devices
can be used repeatedly in an independent and identical manner in order to gather necessary statistics.
As well, [11] assumes that certain states are in a product form. McKague and Magniez (in preparation)
remove these assumptions for quantum circuits using techniques similar to those used here.
Stemming from a different heritage, Broadbent et al. [5] considered a semi-quantum verifier who
only prepares single qubit states, and a fully quantum prover. They give a construction for an interactive
proof for any language in BQP. Additionally, they describe an extension using two quantum provers and
a classical verifier. Their construction uses measurement-based quantum computation. Improvements to
the protocol appear in [8], while a rigorous proof of correctness for the classical verifier case appears
in [8]. Aharonov et al. [2] also describe a semi-quantum protocol using a constant sized quantum verifier
and a polynomial-time quantum prover.
In the context of quantum cryptography, Acín et al. [1] introduced device independent quantum key
distribution. This model is very similar to that used here. However, rather than computation the goal is
to expand a private shared key. From a physics perspective, Bardyn et al. [4] and McKague et al. [18]
consider self-testing type entanglement tests from the perspective of Bell inequalities.
Most recently, Reichardt et al. [26] proved a very general result allowing two non-communicating
quantum provers1 along with a classical verifier to recognize all of BQP. The core of their result is a
self-test, using only two provers, for multiple EPR pairs and measurements. Using this tool they show
how to test individual gates and perform measurements via teleportation. Finally, they combine the results
to give an interactive proof for entire quantum circuits.
Measurement-based quantum computation, also known as one-way quantum computation or graph
state computation, was introduced by Raussendorf and Briegel [24, 25]. In this model of computation
we begin with a graph state and perform measurements on each vertex, with the sequence of vertices
and the measurement bases used determined by the calculation we wish to make. The outcome of the
calculation is then derived from the measurement outcomes. One important aspect of the measurements
is that they are adaptive—the measurement basis for a particular vertex can depend on the outcomes of
measurements on previous vertices. This allows us to perform any calculation in BQP. The particular
variety of graph-state computation that we use is due to Mhalla and Perdrix [19]. The advantage of this
model is that it requires measurements in the X-Z plane only.
1.2 Contributions
Our main contributions are in improving self-testing. First, we modify the proof for the graph state
self-test from [15], allowing a tighter error analysis. For graphs on n vertices the error in the state is upper
√
bounded by O( n)ε 1/4 (where ε bounds the noise in the experimental outcomes) rather than O(2n/2 )ε 1/2
as in [15]. This exponential improvement in the error scaling in n makes it possible to self-test with a
1 Recall that our honest provers are BQP-bounded.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 3
M ATTHEW M C K AGUE
polynomial number of trials to achieve a constant error. We also analyze the error in the case of adaptive
measurements, which are required for measurement-based quantum computing. Additionally we extend
the graph state test to X-Z plane measurements in order to achieve universal computation. Finally we
show how to use the self-test in order to test the provers for honesty in the interactive proof scenario.
Combining this test for honesty with measurement-based quantum computation we achieve the following
theorem:
Theorem 1.1. For every language L ∈ BQP there exists a polynomial time verifier V that on input x
interacts with a polynomial number of non-communicating quantum provers such that:
• If x ∈ L then there exists2 a set of honest quantum provers, each of which performs a single
operation, for which V accepts with probability at least c = 2/3.
• If x ∈
/ L then, for any set of provers, V accepts with probability no more than s = 1/3.
Along the way we also prove several results which may be of independent interest. In particular our
error analysis for triangular cluster states (see Definition 2.12) can be applied to general graph states and
stabilizer states enabling self-testing of these states with robust error bounds. As well, our error bounds
for adaptive measurements are quite general, applying to general quantum circuits which incorporate the
untrusted measurements performed by the provers.
While the Reichardt et al. [26] construction uses a constant number of provers, each of which runs in
polynomial time, we use a polynomial number of provers, each of which runs in constant time (indeed,
each prover only performs a single measurement). The advantage of our technique is that the provers are
very easy to implement, requiring only the ability to measure in four different bases (once an appropriate
graph state is prepared). Finally, there is a very nice conceptual advantage, which is that the measurement-
based calculation that is performed is exactly what would be done with trusted devices, whereas the
Reichardt et al. construction requires qubits to be teleported between the two provers at each gate.
1.3 Overview of construction
We can divide our interactive proof into two distinct units: the calculation and the test for honesty. The
calculation is exactly the same measurement-based quantum computation that would be performed for
trusted devices. The test for honesty is derived from self-testing.
We give some technical details of measurement-based quantum computation in Section 2.1. The
procedure can be summarized as:
Procedure 1.
1. Prepare a universal graph state.
2. Perform measurements to obtain a computation-specific graph state.
3. Measure vertices in sequence, adapting bases according to outcomes from previous measurements.
2 The honest provers and the verifier are, of course, members of a uniform set, i. e., a description of the verifier and provers
can be generated by a polynomial-time Turing machine.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 4
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
4. Calculate the final outcome.
In order to perform the computation we need the provers to share a graph state and be able to measure
vertices. The verifier performs all the classical computation, including deriving the measurement patterns,
the required graph state, and the final outcome.
Our main contributions lie in constructing a test for honesty. Here we must define some test such that
if the provers were to cheat on the calculation then they will fail the test. Our test for honesty is based on
the graph state self-test, originally presented in [15]. It allows the verifier to establish that the provers
have access to high quality copies of the desired graph state and X and Z Pauli measurements. We give
details for this test, including our improved proof in Section 3.1.
In addition, for the measurement-based quantum computation we also need measurements covering
the entire X-Z plane. This is a simple extension of the graph-state test, which we present in Section 3.2.
The graph-state test, with extensions, define a set of subtests, each of which the provers must pass. To
administer the entire test, the verifier just chooses one of these subtests at random. If the provers actually
hold the required graph state and perform the measurements faithfully then they will pass the test with
high probability, and if their behavior deviates too much from the honest provers then they will pass with
a lower probability. The gap is 1/ poly(n) for a constant error bound and is calculated in Section 3.4.
With all of this in place we obtain a simple statement: if the provers deviate from the honest behavior
by more than δ (see Section 2.5 for a definition), then they will pass the test with probability at most
ctest − ε, where ε is a function of δ and ctest is the probability of honest provers passing the test. Hence if
the provers attempt to cheat we will catch them. The details are given in Section 3.4.
Having shown how to test whether the provers are honest, and how to perform the desired calculation,
we must put these two components together to form the interactive proof. The structure is as follows:
randomly either check for honesty or perform the calculation. The critical observation is that the queries
to an individual prover look the same whether the verifier is testing or calculating. More specifically,
every query that appears as part of a calculation also appears as part of the test for honesty. Hence provers
who attempt to cheat on the calculation can be caught by the test for honesty.
The final technical piece of the puzzle is to determine with what probability to test for honesty. We
give the derivation in Section 4.
2 Technical introduction
In this section we present some notation and definitions used in the construction and proof.
2.1 Measurement-based quantum computation
Here we give a general overview of measurement-based quantum computation (MBQC). Our goal is to
provide sufficient background for readers to understand the major features of MBQC. For more detail we
refer the reader to [24, 25].
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 5
M ATTHEW M C K AGUE
Before we start, we define some standard quantum states operators. First, we have the states
1
|+i = √ (|0i + |1i) , (2.1)
2
1
|−i = √ (|0i − |1i) . (2.2)
2
The Pauli operators X, Y and Z are given by
X|xi = |x ⊕ 1i , (2.3)
x
Z|xi = (−1) |xi , (2.4)
Y |xi = iXZ|xi . (2.5)
We also have the Hadamard operator, H, given by
1
H|xi = √ (|0i + (−1)x |1i) (2.6)
2
and the controlled Pauli operators, given by
CTRL-X|xi|yi = |xiX x |yi = |xi|x ⊕ yi , (2.7)
x xy
CTRL-Z|xi|yi = |xiZ = (−1) |xi|yi , (2.8)
x
CTRL-Y |xi|yi = |xiY |yi . (2.9)
Note that HXH = Z and (I ⊗ H)CTRL-X(I ⊗ H) = CTRL-Z. Further details about these operators, and
quantum information in general, can be found in [21].
To understand how MBQC works, we will show how to turn a simple teleportation circuit into a
circuit that applies a gate encoded in a measurement angle. Let us start with a basic teleportation circuit
as in Figure 1. Rather than performing entanglement swapping with an EPR pair held in memory, as
in the usual case, we entangle the input and output qubits directly using a CTRL-X gate. The classical
result of the measurement in the X basis is used to control a Z gate, which applies a necessary correction.
Direct calculation shows that the input state appears in the output register after the circuit is applied. In
the second circuit in Figure 1, we convert the CTRL-X gate to a CTRL-Z gate and two Hadamard gates.
In the third circuit in Figure 1, the left Hadamard simply changes the initial state from |0i to |+i. We
move the right Hadamard past the Z correction, which then becomes an X correction gate.
Now suppose that we apply a unitary U to the qubit as in Figure 2. For this construction we suppose
that U(θ ) = exp(iθ Z/2) so that it commutes with the CTRL-Z as in the second circuit of Figure 2. Now
we can see U as a modification of the measurement basis as in the final circuit. Since we originally
measured in the X basis the new measurement basis will be in the X-Y plane of the Bloch sphere:
U † XU = R(θ ) = cos θ X + sin θ Y .
Next we consider how multiple teleportations work together. First we consider the case of two
cascaded teleportations as in Figure 3. Using measurement angles θ1 and θ2 , the overall unitary applied
by the circuit is HU(θ2 )HU(θ1 ). In the second circuit of Figure 3 we have moved the second CTRL-Z
gate, used to entangle the second and third qubits together, to the left past the X correction on the second
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 6
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
• X •
|0i Z
• X •
|0i H • H Z
• X •
|+i • X H
Figure 1: Three equivalent basic teleportation circuits. In the second circuit the CTRL-X gate is replaced
with a CTRL-Z gate sandwiched between two Hadamard gates. In the third circuit the left Hadamard
gate changes |0i to |+i and the right Hadamard gate moves past the Z correction, changing it to an X.
qubit. This induces a Z correction on the third qubit, controlled along with the X correction. Finally, in
the third circuit we incorporate the X correction into the measurement angle on the second qubit. Indeed,
since XR(θ )X = R(−θ ), the angle θ2 becomes −θ2 whenever an X correction is needed.
We have seen how to convert X corrections into changes in the measurement angle. Z corrections
are even easier to apply. Since ZR(θ )Z = −R(θ ), a Z correction corresponds to simply inverting the
output of a measurement. Figure 4 shows how X and Z corrections together modify the behavior of the
measurement.
So far our construction has the following features: we can apply a sequence of unitaries
HU(θn ) · · · HU(θ1 )
to a qubit by repeatedly teleporting the qubit and varying the measurement angle used in the teleportation.
The necessary corrections from the teleportation can be incorporated into subsequent measurement angles
and outcomes, and all the entangling CTRL-Z gates can be pushed to the start of the procedure. Hence we
can perform a single qubit circuit by first building a large entangled state using |+i states and CTRL-Z
gates, and then measuring the qubits in sequence, adapting measurement angles as we go. Note that the
gates HU(θ ) form a universal set.
In order to perform general circuits we need one more piece of the puzzle, which is two-qubit gates.
In this case we obtain universality by including CTRL-Z gates. These can be applied at any time during
the circuit and appear as additional CTRL-Z gates on target qubits when we translate into the teleportation
scheme. These can be treated similarly to the CTRL-Z gates which are used to entangle input and output
qubits for teleportation. In particular, we can push the CTRL-Z gates back to the beginning of the circuit,
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 7
M ATTHEW M C K AGUE
U(θ ) • X •
|+i • X H
• U(θ ) X •
|+i • X H
• R(θ ) •
|+i • X H
Figure 2: Three equivalent circuits combining a unitary with teleportation. In the second circuit the fact
that U(θ ) = exp(iθ Z/2) is diagonal means that it commutes with the CTRL-Z gate. In the third circuit
the U(θ ) gate has modified the measurement basis to R(θ ) = cos θ X + sin θ Y .
past X and Z corrections. This induces extra corrections which must be taken into account on subsequent
measurements.
Now we have the complete picture. A calculation begins by preparing many |+i states and entangling
them with CTRL-Z gates. Then they are measured one at a time, and measurements are adjusted to
incorporate X and Z corrections as required.
The initial state, prepared by applying CTRL-Z gates to qubits in the |+i state, is called a graph state
(see Section 2.4 for a precise definition) and will play an important role in our results here.
Our construction will use a slightly different model of measurement-based quantum computation.
Although the usual and most easily understood method utilizes measurements in the X-Y plane, we
will instead use a different model, due to Mahalla and Perdrix [19], which requires only X-Z plane
measurements. In particular they prove the following theorem:
Theorem 2.1 (Mahalla and Perdrix [19]). Triangular cluster states are universal resources for measurement-
based computation based on X-Z plane measurements.
Triangular cluster states are graph states where the underlying graph is a triangular lattice. As we
shall see, these particular graph states are particularly easy to self-test since every vertex is in a triangle.
The proof of the above theorem consists of two parts: showing that triangular cluster states can be
converted into other graph states using measurements alone, and showing that X-Z measurements suffice
for universal computation. The details of the proof are not important for our results here. What is
important is that the overhead introduced by the construction is small, so that a given quantum circuit
gets translated into a graph state with size polynomial in the size of the original circuit.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 8
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
• R(θ1 ) •
|+i • X • R(θ2 ) •
|+i • X
• R(θ1 ) •
|+i • • X R(θ2 ) •
|+i • Z X
• R(θ1 ) • •
|+i • • R(±θ2 ) •
|+i • Z X
Figure 3: Two cascaded teleportations. The first circuit teleports the first qubit to the third, applying
HU(θ2 )HU(θ1 ). In the second circuit we have moved the CTRL-Z to the left past the X correction,
inducing a Z correction on the third qubit, but allowing all the CTRL-Z gates to be applied before any
measurements are made. Finally, since XR(θ )X = R(−θ ) the X correction can be omitted in favor of a
change of measurement basis.
2.2 Operators, isometries, bit strings
We will frequently deal with a tensor product of operators over several subsystems. To make this easier
we use the following notation:
Definition 2.2. Given some collection of operators {M j : j = 1 . . . n} with M j operating on the j-th
subsystem, and a vector x ∈ {0, 1}n define
n
O x
Mx = Mj j. (2.10)
j=1
This notation is quite frequently used with Pauli operators, but here we do not assume that the M j
operators are all the same. Instead, we merely suppose that there is some common label “M,” which may
refer to different operators on different subsystems.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 9
M ATTHEW M C K AGUE
z •
x •
Z X R(θ ) m
z •
x •
R(xθ ) • mz
Figure 4: Incorporating X and Z corrections into measurements. We have X and Z corrections according
to some previous measurement results x, z ∈ {±1}. The X correction is incorporated into the measurement
as a change in the angle. The Z correction is incorporated by flipping the outcome of the measurement.
For an operator M we may also be interested in the controlled version
Definition 2.3. Let M be an operator on HA . Then the operator CTRL-M, which operators on H2 ⊗ HA
is given by
CTRL-M|xi|ψi = |xiM x |ψi (2.11)
where x ∈ {0, 1}.
Another set of objects that we will deal with frequently is isometries.
Definition 2.4. An isometry is a linear operator Φ : X → Y that preserves inner products.
Isometries are a natural generalization of unitaries where the image space of Φ is not necessarily
the same as X, and may in general have a larger dimension. As a concrete and pertinent example,
adding an ancilla prepared in a particular state and applying a unitary are both isometries, as is their
composition. Isometries are naturally extended to the dual space by Φ(hψ|) = Φ(|ψi)† and to operators
by Φ(|xihy|) = Φ(|xi)Φ(hy|), combined with linearity.
As we shall see, we will need to address the state spaces of provers individually, so we will need the
concept of a local isometry.
Definition 2.5. A local isometry on n subsystems is an isometry of the form
Φ = Φ1 ⊗ · · · ⊗ Φn (2.12)
where Φ j operates on the j-th subsystem only.
Here a tensor product of isometries is evaluated in a way analogous to how a tensor product of
unitaries is applied: decompose the state into a sum of product states and apply the operator to the
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 10
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
appropriate vector in the tensor product. That is to say,
!
Φ1 ⊗ Φ2 ∑ xj 1 yj 2 = ∑ Φ1 x j 1 ⊗ Φ2 y j 2 . (2.13)
j j
By convention, we take Φ1 to mean Φ1 ⊗ I2 when applied to a state in H1 ⊗ H2 , and analogously for
other product spaces.
From this it is easy to derive the following properties of local isometries.
Lemma 2.6. Let Φ = Φ1 ⊗ Φ2 be a local isometry, |ψi1,2 be a bipartite state, and M1 be a local operator
on the first subsystem. Then
Φ(M1 |ψ1,2 i) = Φ1 (M1 )Φ(|ψ1,2 i) . (2.14)
We make extensive use of bit strings. For an n-bit string t the j-th bit is t j . Inner products of bit
strings are given by
n
s · t = ∑ s jt j . (2.15)
j=1
We will, at times, consider the inner product as an integer, and at other times as a bit (i. e., over Z or Z2 ).
Where the difference is important we will specify. For example, t · t taken over Z gives the number of
ones in t but when taken over Z2 it is the parity of the number of ones.
Finally, we define the bit string 1v to have a 1 only in the v position and zeros elsewhere, i. e.,
(1v ) j = δv j .
2.3 Technical lemmas for estimation
We will need to make use of several easy technical results in our proofs. We collect them here for
convenience.
Lemma 2.7. Let |ψi and |φ i be normalized states. Suppose hψ|M|ψi ≥ 1 − α and hψ|N|ψi ≥ 1 − β
where M 2 = N 2 = I. Then
√
|||ψi − M|ψi|| ≤ 2α , (2.16)
√ √ p
|||ψi − MN|ψi|| ≤ 2 α+ β . (2.17)
Further, if M is unitary and |ψ1 i and |ψ2 i are normalized states, then
|hφ |M|ψ1 i − hφ |M|ψ2 i| ≤ |||ψ1 i − |ψ2 i|| . (2.18)
The first inequality is a straightforward applications of the definition of ||·||. The second inequality is
an application of the first, along with the triangle inequality. The last inequality is an application of the
inequality ||O|ψi|| ≤ ||O||∞ |||ψi||2 where we use the operator O = hφ |M.
Lemma 2.8. Let t be an n-bit string. Then
∑ (−1)s·t = 2n δt . (2.19)
s∈{0,1}n
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 11
M ATTHEW M C K AGUE
If t = 0 then the summand is always 1. If t 6= 0 then half the strings s have inner product 0 with t and
the other half have inner product 1, so we get a sum with half the summands 1 and the other half -1.
Lemma 2.9. Let u ∈ {0, 1}n be given and let A be the adjacency matrix for a graph G = (V, E). Then
1 u·u
∑ ns·u = 2 ,
2n s∈{0,1}
(2.20)
1 n
2n ∑ s·t = , (2.21)
2 s,t∈{0,1}n 4
1 |E|
∑ n t · At = 4 .
2n t∈{0,1}
(2.22)
For the first one, the average inner product of a vector with u is half the number of 1’s in u. The
second computes this for an average u, which has n/2 1’s. For the last one, t · At counts the number of
edges in the induced subgraph on St = {v ∈ V | tv = 1}.
Consider an edge (u, v). Then (u, v) appears in the induced subgraph on St whenever both ends are in
St , i. e., when tu = tv = 1. This happens for a quarter of all bit strings t. Hence each edge is counted 2n−2
times for a total of 2n−2 |E|.
Lemma 2.10. Let x ∈ {0, 1}n . Then
1
H ⊗n |xi = √ ∑ (−1)x·y |yi . (2.23)
n
2 y∈{0,1}n
This is a standard result in quantum computing, and can be shown using induction on n.
2.4 Graph states
We assume that the reader is familiar with the basics of graph theory. A good resource is [7]. We now
fix some notation for our convenience. Let G = (V, E) be a graph, n = |V | and u, v ∈ V . The adjacency
matrix A of G is a {0, 1} matrix with Au,v = 1 whenever (u, v) ∈ E and 0 elsewhere. Note that A1v is
a vector containing a 1 in position u for each (u, v) ∈ E, and is hence the characteristic vector of the
neighborhood of v. A subgraph of G is a graph with vertices V 0 ⊆ V and edges E 0 ⊆ E such that all edges
in E 0 go between vertices of V 0 . Finally, the induced subgraph on a subset S ⊆ V is the graph on vertices
S which has edges {(u, v) | u, v ∈ S, (u, v) ∈ E}. In other words, the induced subgraph is the maximal
subgraph of G on vertices in S. A triangle is a set of three vertices which are pairwise adjacent.
The graph state |Gi is an n-qubit state, with qubits labeled by vertices, which is stabilized3 by the
operators
Sv = Xv Z A1v . (2.24)
That is, Sv has X on vertex v and Z on each of its neighbors and
Sv |Gi = |Gi . (2.25)
3 See [9] for more information on the stabilizer formalism.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 12
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
Equivalently,
1 1
|Gi = √ ∑ (−1) 2 x·Ax |xi (2.26)
2n x∈{0,1}n
with the inner product over Z. To explain, let us write
x · Ax = ∑ 1u · A1v = ∑ Au,v . (2.27)
u,v u,v
xu =1=xv xu =1=xv
Now since Au,v = Av,u = 1 whenever (u, v) ∈ E, we are counting edges. The summation and A are
symmetric, so we are double counting and we always get an even number (hence the 1/2 appearing in the
exponent above). Let Tx = {v | xv = 1}, then we are summing over all the vertices in Tx , double counting
the edges in the induced subgraph on Tx .
For completeness we show that the above two definitions are equivalent by showing that |Gi is
stabilized by Sv :
1 1
Xv Z A1v |Gi = √ ∑(−1) 2 x·Ax (−1)x·A1v |x ⊕ 1v i (2.28)
n
2 x
1 1
= √ ∑(−1) 2 (x⊕1v )·A(x⊕1v )±(x⊕1v )·A1v |xi (2.29)
2n x
where we have re-indexed the summation by x → x ⊕ 1v . The ± in the exponent of the −1 represents the
fact that we only care about the parity of the exponent, so we can add or subtract as we please.
Now (1/2)(x ⊕ 1v ) · A(x ⊕ 1v ) is the number of edges in the induced subgraph on Tx⊕1v . Meanwhile
(x ⊕ 1v ) · A1v = x · A1v since 1v · A1v = 0 (no vertex is adjacent to itself) and x · A1v counts the neighbors
of v that are in Sx .
There are two cases. First, if v ∈ Tx then Tx⊕1v does not contain v. The subgraph on Tx is obtained
from the induced subgraph on Tx⊕1v by adding v and all the associated edges—x · A1v of them—and the
total number of edges in the induced subgraph on Tx is
1 1
(x ⊕ 1v ) · A(x ⊕ 1v ) + (x ⊕ 1v ) · A1v = x · Ax . (2.30)
2 2
In the other case v ∈
/ Tx , so we obtain Tx by removing v and all associated edges from Tx⊕1v , so
1 1
(x ⊕ 1v ) · A(x ⊕ 1v ) − (x ⊕ 1v ) · A1v = x · Ax . (2.31)
2 2
Hence
1 1
Xv Z A1v |Gi = √ ∑(−1) 2 (x⊕1v )·A(x⊕1v )±(x⊕1v )·A1v |xi (2.32)
2n x
1 1
= √ ∑(−1) 2 x·Ax |xi (2.33)
n
2 x
= |Gi . (2.34)
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 13
M ATTHEW M C K AGUE
We have shown that the operators Sv stabilize |Gi. It is also easy to see that the Sv operators are
independent: any one cannot be obtained by multiplying together others. They also commute with each
other. We then have n independent, commuting n-qubit Pauli operators which stabilize a 1-dimensional
space [9].
Operationally, graph states are constructed by beginning with the qubits in the state |+i⊗n and
applying CTRL-Z gates on vertices u, v whenever (u, v) ∈ E.
We can generalize the above argument as follows:
Lemma 2.11. Let A be an n × n adjacency matrix and x, y be n-dimensional {0, 1}-vectors. Then
1 1 1
(−1) 2 (x⊕y)·A(x⊕y)+(x⊕y)·Ay = (−1) 2 x·Ax+ 2 y·Ay . (2.35)
Proof. We first do everything over Z. By linearity
(x + y) · A(x + y) = x · Ax + y · Ay + x · Ay + y · Ax . (2.36)
Since A is symmetric x · Ay = y · Ax. Thus, dividing everything by two and rearranging, we obtain
1 1 1
(x + y) · A(x + y) − x · Ay = x · Ax + y · Ay . (2.37)
2 2 2
Note that both sides of the equation will always be integer. Now
1 1 1
(−1) 2 (x+y)·A(x+y)−x·Ay = (−1) 2 x·Ax+ 2 y·Ay . (2.38)
We only care about the parity of the exponents so we can make two small changes. First, the − becomes
a +. Second, we can add y · Ay since it is always even and won’t affect the parity. Thus,
1 1 1
(−1) 2 (x+y)·A(x+y)+(x+y)·Ay = (−1) 2 x·Ax+ 2 y·Ay . (2.39)
Finally, we can do the additions modulo 2 (+ becomes ⊕) since we only care about the parity. This gives
the desired result.
The graphs that we will mostly be concerned with are triangular lattice graphs.
Definition 2.12. An m × n triangular lattice graph has mn vertices, {v(a,b) | a = 1 . . . m, b = 1 . . . n} where
vertex v(a,b) is adjacent to vertices v(a+1,b) , v(a,b+1) , v(a+1,b+1) , v(a−1,b) , v(a,b−1) and v(a−1,b−1) when they
exist.
A small example is given in Figure 5.
2.5 Definition of “closeness”
We will need to establish that the state held by the provers is “close to” a given graph state and that the
measurements they perform are “close to” the ideal X-Z plane observables. However, there are many
transformations that the provers can apply to both states and measurements which are invisible to the
verifier. In particular, the provers may add an ancilla or apply a local change of basis (simultaneously to
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 14
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
Figure 5: Triangular lattice graph.
both the state and measurements). In fact, we will see that for the states and observables we use these are
the only undetectable transformations that they can apply.
We can account for such transformations by allowing an arbitrary isometry which undoes these
transformations and presents us with the required graph state plus some arbitrary ancilla state. We also
allow for some noise by comparing states in the usual vector norm.
Definition 2.13. We say that a multi-partite (i. e., with more than one subsystem) state |ψ 0 i and observ-
ables {M 0 } are ε-equivalent4 to |ψi and {M} if there exists a local isometry Φ and a state |junki such
that for every M
Φ(M 0 ψ 0 ) − |junkiM|ψi 2 ≤ ε . (2.40)
Here we are thinking of “M” as both the ideal operation on |ψi and as a label for the operation M 0 .
Evidently this definition guarantees that the two systems behave like each other since isometries
preserve inner products, and hence outcome probabilities. As we shall see, it is also a necessary condition
for states and measurements to behave close to the ideal graph states and X-Z plane measurements. Hence
any other definition we could choose is at most a different characterization of the errors and in the exact
case is equivalent. The error bound used here has an operational meaning since we can quickly bound the
error in outcome distributions from it.
There is one shortcoming of this definition, which is that it is impossible to test states or operators
which contain any imaginary component in the ideal case (this restriction does not apply to the states
and operators held by the provers, only to the ideal that we compare them to.) The simple reason is that
the provers may apply a complex conjugation to everything without changing the distribution of their
responses to the verifier. This transformation is not an isometry, and hence it is impossible to conclude
that any system satisfies the above definition based on classical interaction alone. It is, however, possible
to extend the definition to account for this case [17]. We do not need to use this extended definition here
since all ideal operators and states in the Mahalla and Perdrix construction are real.
4 It is easy to see that this relation is (in the exact case) transitive and reflexive, but it is also clearly not symmetric. Thus it is
not a true equivalence relation. However the terminology has stuck.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 15
M ATTHEW M C K AGUE
2.6 Modelling the provers
An important argument in our work is that we can model the provers, even in the dishonest case, by a
pure joint state held by the provers, and a collection of observables for each prover, one per possible
query to that prover.
First, it should be clear that it is not a restriction to consider pure states. Any mixed state can be
purified and the purification given to any one of the provers. This only increases the power of the provers
by giving them additional information held in the purification.
Next, since our provers will only receive one query and respond with one message, we can model their
actions by a measurement. Any pre-processing done before the measurement can be incorporated into the
choice of measurement as can any post-processing. Further, since we are not making any assumptions on
the dimension of the state held by the provers, their measurements can be taken to be projective and, since
the provers will always respond with ±1, the projectors can be combined into an observable without any
loss of information or generality.
It is important to consider the view of a single prover during the protocol. They will receive one of
four measurement settings, all of which appear in the test for honesty, but not all will necessarily appear
as part of the computation. For settings that appear only in the test, the prover may decide to act honestly,
but this will not affect the outcome of the computation. Let us say that setting 1 appears in both the test
and the computation. The prover has no other information to act on, and so must measure some operator
M1 . They may decide on M1 based on the different distribution of measurement settings for the test and
the computation, but they are still left with a fixed M1 to be measured when queried with setting 1. Thus
the verifier can be sure that the M1 measured during the test is the same as the M1 measured during the
computation. What we need to prove, then, is that a strategy (state and measurement operators for each
measurement setting) cannot both pass the test with high probability and bias the calculation.
3 Test for honesty
In order to develop a test for honesty we go through several steps. The first step is to develop a test for
graph states. This is the foundation on which we build the test for honesty. After showing how we can
verify that the provers hold onto a particular graph state we then show how to test measurements in the
X-Z plane. Adaptive measurements built on measurements in the X-Z plane are the next step. Finally,
we put all of the tests together into a single test and show how the probability of passing this test relates
to the amount of error in an adaptive measurement performed on the same state and using the same
measurements.
3.1 Self-test for triangular cluster states
In this section we develop a self-test for triangular cluster states. The techniques used are similar to
those in [15]. However, we make some modifications which allow for a tighter error analysis and clearer
notation. Although we give the construction for triangular cluster states only, the same techniques can be
extended to work with any stabilizer state, as in [15].
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 16
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
Theorem 3.1. Let G be a triangular lattice graph on n vertices with adjacency matrix A and let ε > 0.
Further, suppose that for an n-partite state |ψ 0 i with local measurements Xv0 and Zv0 we have for each
v∈V
ψ 0 Sv0 ψ 0 ≥ 1 − ε (3.1)
(where Sv0 = Xv0 Z 0A1v ) and for each triangle T ⊆ V with characteristic vector τ
− ψ 0 X 0τ Z 0Aτ ψ 0 ≥ 1 − ε (3.2)
then there exists a local isometry Φ and state |junki such that
√ √ 1
Φ X 0q Z 0p ψ 0 − |junkiX q Z p |Gi ≤ 2 p · p + 2 2n + |E| + n (2ε) 4
p
(3.3)
for all p, q ∈ {0, 1}n .
We may interpret Theorem 3.1 as follows: for each triangular cluster state there exists a set of
non-local correlations that uniquely identifies that graph state and X and Z measurements, up to local
unitaries and additional ancillas.
The proof can be divided into several sections. The final goal is to construct an isometry Φ and prove
that it takes the state |ψ 0 i close to the desired graph state. The construction for the isometry is given in
terms of the X 0 and Z 0 operators on each vertex. To bound the error we need to know how these operators
behave and in particular whether they approximately anti-commute. This is done in Lemma 3.2 and
Corollary 3.3. In the ideal case we can use the stabilizers to show Xv |Gi = Z A1v |Gi. In Lemma 3.4 we
show that this is approximately true for the X’s, which will allow us to convert X 0 s into Z 0 s. With these
estimations in place we then proceed with the proof of Theorem 3.1.
3.1.1 Preliminary technical estimations
Our graph G is a triangular lattice, so every vertex lies in a triangle. For self-testing this gives a nice
advantage, since it is particularly easy to show that X 0 and Z 0 anti-commute for vertices in a triangle.
Lemma 3.2. Let v ∈ V be a vertex in a triangle. Under the conditions of Theorem 3.1,
√
Xv0 Zv0 ψ 0 + Zv0 Xv0 ψ 0 ≤ 4 2ε . (3.4)
Proof. First, let T = {u, v, w} be a triangle containing v. The first part of Lemma 2.7, together with the
conditions of Theorem 3.1, tell us √
Sx0 ψ 0 − ψ 0 ≤ 2ε (3.5)
for x ∈ {u, v, w}, and from triangle τ
√
Xu0 Xv0 Xw0 Z 0A1u Z 0A1v Z 0A1w ψ 0 + ψ 0 ≤ 2ε . (3.6)
Applying the second part of Lemma 2.7 three times to combine these, we find
√
Su0 Sv0 Sw0 Xu0 Xv0 Xw0 Z 0A1u Z 0A1v Z 0A1w ψ 0 + ψ 0 ≤ 4 2ε . (3.7)
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 17
M ATTHEW M C K AGUE
The Z 0 s operating on vertices outside T all cancel since they appear in Sx0 and in Z 0A1x for some x ∈ {u, v, w}
and there are no X 0 operators outside the triangle. We are left with
√
(Xu0 Zv0 Zw0 )(Zu0 Xv0 Zw0 )(Zu0 Zv0 Xw0 )(Xu0 Xv0 Xw0 ) ψ 0 + ψ 0 ≤ 4 2ε . (3.8)
By commuting operators on different subsystems past each other, we can pair up and cancel the Xx0 and
Zx0 for x ∈ {u, w}, resulting in √
Xv0 Zv0 Xv0 Zv0 ψ 0 + ψ 0 ≤ 4 2ε . (3.9)
Rearranging by multiplying by Zv0 Xv0 , we obtain our result.
Note that it is sufficient to consider a set of triangles that covers the set of vertices and hence
Theorem 3.1 holds for all graphs in which each vertex is contained in a triangle. In fact, as in [15], it is
sufficient to consider one triangle or just one edge in a connected graph, but this will give a less robust
result. Lemma 2 in [15] shows that if Xv0 and Zv0 approximately anti-commute, then so do Xu0 and Zu0 for
some neighbor u of v. Using this one can induct along paths to all vertices in a connected component. For
our purposes this is unnecessary since all vertices lie in at least one triangle.
The above lemma can be generalized to products of operators, as in the following corollary.
Corollary 3.3. Let s,t ∈ {0, 1}n . Under the conditions of Theorem 3.1,
√
X 0t Z 0s ψ 0 − (−1)s·t Z 0s X 0t ψ 0 ≤ 4(s · t) 2ε , (3.10)
where s · t is taken over Z.
This can be seen by repeatedly applying Lemma 3.2, once for every v such that sv = 1 = tv , and using
the triangle inequality. If sx = 1 but tx = 0, or vice versa, for some x ∈ V , then the single operator on
vertex x commutes with all other operators.
Now we consider the physical analogue of the stabilizer generators which are defined by Sv0 = Xv0 Z 0A1v .
The conditions of Theorem 3.1 establish that they really are (close to) stabilizers of |ψ 0 i. Next we consider
products of these generators and show that they too almost stabilize |ψ 0 i.
Lemma 3.4. Let t ∈ {0, 1}n . Under the conditions of Theorem 3.1,
1 √
X 0t ψ 0 − (−1) 2 t·At Z 0At ψ 0 ≤ (2(t · At) + t · t) 2ε , (3.11)
where t · At and t · t are evaluated over Z.
Proof. First, by Lemma 2.7 we find
√
ψ 0 − ∏ Sv0 ψ 0 ≤ (t · t) 2ε . (3.12)
v∈V
tv =1
The right term in the norm can be expanded as
∏ Sv0 ψ 0 = ∏ X 0v Z 0A1 ψ 0 . v
(3.13)
v∈V v∈V
tv =1 tv =1
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 18
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
We fix an ordering < on V , and evaluate the product according to that ordering. Thus if tv = tu = 1 and
u < v then Su0 appears in the product to the left of Sv0 . Now suppose that Auv = 1. Then Zu0 in Sv0 appears to
the right of the only occurrence of Xu0 in Su0 . We may commute Zu0 to the right past all remaining operators
on the u system, so that Zu0 appears to the right of all X 0 operators. The opposite is true if v > u, in which
case we may commute Zu0 to the left, and it appears to the left of all X 0 operators. Thus we may write the
above as
0A 0A
∏ Sv0 ψ 0 = ∏ Zv v,u X 0t ∏ Zv v,u ψ 0 . (3.14)
v∈V tu =1 tu =1
tv =1 u>v v>u
Let AL be the lower triangular part of A (with 0s elsewhere) and AU the upper triangular part. Then we
may rewrite the above as
U L
∏ Sv0 ψ 0 = Z 0A t X 0t Z 0A t ψ 0 . (3.15)
v∈V
tv =1
U
Using Corollary 3.3 with s = ALt and multiplying on the left by the unitary Z 0A t we obtain
U L L U L √
Z 0A t X 0t Z 0A t ψ 0 − (−1)t·A t Z 0A t Z 0A t X 0t ψ 0 ≤ 4(t · ALt) 2ε . (3.16)
Noting that AU t + ALt = At and t · ALt = (1/2)(t · At) since A is symmetric, this becomes
1 √
∏ Sv0 ψ 0 − (−1) (t·At) Z 0At X 0t ψ 0
2 ≤ 4(t · ALt) 2ε . (3.17)
v∈V
tv =1
Finally we apply the triangle inequality along with (3.12) to find
1 √
ψ 0 − (−1) 2 (t·At) Z 0At X 0t ψ 0 ≤ (2(t · At) + t · t) 2ε (3.18)
1
which is transformed into the desired result by multiplying by (−1) 2 (t·At) Z 0At .
3.1.2 Proof of Theorem 3.1
We are now in a position to prove Theorem 3.1. This is done by giving a construction for Φ and using the
above lemmas to prove that it has the necessary properties.
We will use Φv as defined in Figure 6. The circuit is modified from that used in [15, 18] and earlier
works, differing in the state of the ancilla. Whereas we use an entangled pair of qubits |φ+ i, previous
works used |0i. We also add an initial CTRL-X gate which was not needed when the initial state was
|0i. When Xv0 and Zv0 are the Pauli X and Z gates the circuit is clearly a SWAP gate. The idea is to swap a
qubit embedded in the input wire with an explicit qubit in a new register.
As we shall see, the use of a maximally entangled pair of qubits in the ancilla wires allows for a
tighter robustness analysis than is possible with the earlier version of the circuit. The reason is that the
previous isometry used in [15] was very sensitive to error in the amplitude of |0 . . . 0i, but less so for other
amplitudes. This is because |junki is |ψ 0 i projected down to the subspace corresponding to |0 . . . 0i. In
the new isometry |junki is no longer projected down from |ψ 0 i, and the sensitivity to error is spread out
among all subspaces.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 19
M ATTHEW M C K AGUE
|φ+ i
• H • H •
|inputiv Xv0 Zv0 Xv0
Figure 6: Circuit for Φv .
Proof. The structure of the proof is a sequence of chained inequalities between states ψ j and ψ j+1
for j = 1 . . . 4 defined below. We then use the triangle inequality to find the total distance. |ψ1 i is the state
immediately after Φ is applied. |ψ2 i, |ψ3 i and |ψ4 i are the states after three successive applications of
Corollary 3.3. Finally, |ψ5 i is the state after an application of Lemma 3.4. |ψ5 i is then factored to give
|junki and the ideal state |Gi.
We define the states |ψ1 i through to |ψ5 i:
|ψ1 i := Φ X 0q Z 0p ψ 0
1
=√ ∑ (−1)t·(s⊕u) X 0u Z 0t X 0s⊕q Z 0p ψ 0 |sui ,
23n s,t,u
1
|ψ2 i := √ ∑ (−1)t·(s⊕u) (−1) p·(s⊕q) X 0u Z 0t⊕p X 0s⊕q ψ 0 |sui ,
23n s,t,u
1
|ψ3 i := √ ∑ (−1)t·(q⊕u) X 0u⊕s⊕q Z 0t⊕p ψ 0 |sui ,
3n
2 s,t,u
1
|ψ4 i := √ ∑ (−1)t·s (−1) p·(u⊕s⊕q) Z 0t⊕p X 0u⊕s⊕q ψ 0 |sui ,
3n
2 s,t,u
1 1
|ψ5 i := √ ∑ (−1)t·s (−1) p·u (−1) 2 (u⊕s)·A(u⊕s) Z 0t⊕A(u⊕s) ψ 0 |si|u ⊕ qi
3n
2 s,t,u
= |junkiX q Z p |Gi .
Step 1: First we derive |ψ1 i. Let Φ = v∈V Φv , and |ψ1 i = Φ (X 0q Z 0p |ψ 0 i) to be the state after the
N
isometry Φ is applied. Before the circuit is applied the state is
1
X 0q Z 0p ψ 0 |φ+ i⊗n = √ ∑ X 0q Z 0p ψ 0 |ssi . (3.19)
2n s
Applying the first CTRL-X 0 gate yields
1
√ ∑ X 0s X 0q Z 0p ψ 0 |ssi . (3.20)
2n s
Next we multiply by the Hadamard gates and apply Lemma 2.10 to obtain
1
√ ∑(−1)t·s X 0s⊕q Z 0p ψ 0 |sti . (3.21)
22n s,t
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 20
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
The CTRL-Z 0 gate produces
1
√ ∑(−1)t·s Z 0t X 0s⊕q Z 0p ψ 0 |sti (3.22)
22n s,t
then another round of Hadamard and CTRL-X 0 gates yields
1
|ψ1 i = √ ∑ (−1)t·(s⊕u) X 0u Z 0t X 0s⊕q Z 0p ψ 0 |sui (3.23)
3n
2 s,t,u
where s,t, u ∈ {0, 1}n .
Step 2: In the ideal case, |ψ2 i is obtained from |ψ1 i by anti-commuting Z 0p and X 0s⊕q . Here we will
estimate |||ψ1 i − |ψ2 i|| by using Corollary 3.3. From the definition of the 2-norm,
p
|||ψ1 i − |ψ2 i|| = |||ψ1 i|| + |||ψ2 i|| − 2Re hψ1 |ψ2 i . (3.24)
We know that |||ψ1 i|| = 1 because it was formed by Φ applied to a norm-1 state. For |||ψ2 i|| we have
hψ2 |ψ2 i =
1 0 0 0 0 0 0 0
3n ∑ (−1)t·(s⊕u) (−1)t ·(s ⊕u ) (−1) p·(s⊕s ) ψ 0 X 0s⊕q Z 0t⊕p X 0u X 0u Z 0t ⊕p X 0s ⊕q ψ 0 su|s0 u0 . (3.25)
2 s,s0
t,t 0
u,u0
The hsu|s0 u0 i factor implies that u0 = u and s0 = s for all non-zero terms so
1 0 0
hψ2 |ψ2 i = 3n ∑ (−1)(t⊕t )·(s⊕u) ψ 0 X 0s⊕q Z 0t⊕p X 0u X 0u Z 0t ⊕p X 0s⊕q ψ 0 . (3.26)
2 s,t,t 0 u
The X 0u operators square to the identity, and subsequently so do the Z 0p s.
1 0 0
∑0 (−1)(t⊕t )·(s⊕u) ψ 0 X 0s⊕q Z 0t⊕t X 0s⊕q ψ 0 .
23n s,t,t
(3.27)
u
We then make a change of variable t 0 7→ t 0 ⊕ t and break (−1)t·(s⊕u) into (−1)t·s (−1)t·u . The summand
no longer depends on t 0 so we can omit it from the summation, multiplying by 2n instead. We also bring
the summation over u inside, forming an inner sum
1
(−1)t·s
∑(−1) t·u
ψ 0 X 0s⊕q Z 0t X 0s⊕q ψ 0 . (3.28)
22n ∑
s,t u
Lemma 2.8 says that the inner sum is 0 except when t = 0, so we can drop the Z 0t s and the summation
over t. Also t · s = 0. Then the X 0s⊕q s then square to the identity. We are left with
1
|||ψ2 i|| = ψ 0 |ψ 0 = 1 . (3.29)
2n ∑
s
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 21
M ATTHEW M C K AGUE
Now we estimate hψ1 |ψ2 i:
hψ1 |ψ2 i =
1 0 0 0 0 0 0 0
3n ∑ (−1)t·(s⊕u) (−1)t ·(s ⊕u ) (−1) p·(s ⊕q) ψ 0 Z 0p X 0q⊕s Z 0t X 0u X 0u Z 0t ⊕p X 0s ⊕q ψ 0 su|s0 u0 . (3.30)
2 s,s0
t,t 0
u,u0
From the hsu|s0 u0 i term, we see that s = s0 and u = u0 in all non-zero terms. This allows us to cancel
0
X 0u X 0u and remove the u0 and s0 variables. We also pull the sum over u in as an inner sum:
hψ1 |ψ2 i =
1 (t⊕t 0 )·u 0 0
∑0 ∑(−1) (−1)(t⊕t )·s (−1) p·(s⊕q) ψ 0 Z 0p X 0q⊕s Z 0t⊕t Z 0p X 0s⊕q ψ 0 . (3.31)
23n s,t,t u
0
Next we use Lemma 2.8 to see that the inner sum is zero except when t ⊕ t 0 = 0. The terms (−1)(t⊕t )·s)
0
and Z 0t⊕t then become 1 and the identity, leaving the summand independent of t and t 0 . We remove them
from the sum, multiplying by 2n instead. Finally, we make the change of variable s 7→ s ⊕ q to get
1
hψ1 |ψ2 i = (−1) p·s ψ 0 Z 0p X 0s Z 0p X 0s ψ 0 . (3.32)
2n ∑
s
Next set ε p,s = (−1) p·s hψ 0 |Z 0p X 0s Z 0p X 0s |ψ 0 i − hψ 0 |Z 0p X 0s X 0s Z 0p |ψ 0 i, with the second term becoming just
hψ 0 |ψ 0 i = 1, so that the above becomes
1 1
hψ1 |ψ2 i =
(1 + ε p,s ) = 1 + n ∑ ε p,s . (3.33)
2n ∑ s 2 s
√
Corollary 3.3 and the third part of Lemma 2.7 give |ε p,s | ≤ 4(p · s) 2ε and the triangle inequality then
gives us
1 √
|hψ1 |ψ2 i − 1| ≤ n ∑ 4(p · s) 2ε . (3.34)
2 s
Lemma 2.9 tells us how to deal with the sum over s, and we write
√
|hψ1 |ψ2 i − 1| ≤ 2(p · p) 2ε (3.35)
and plugging this back into the definition of the 2-norm gives
q √
|||ψ1 i − |ψ2 i|| ≤ 4(p · p) 2ε . (3.36)
Step 3: Now let us look at |ψ2 i and |ψ3 i:
1
|ψ2 i := √ ∑ (−1)t·(s⊕u) (−1) p·(s⊕q) X 0u Z 0t⊕p X 0s⊕q ψ 0 |sui ,
23n s,t,u
1
|ψ3 i := √ ∑ (−1)t·(q⊕u) X 0u⊕s⊕q Z 0t⊕p ψ 0 |sui .
23n s,t,u
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 22
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
|ψ3 i is obtained from |ψ2 i by moving the Z 0 s to the right, picking up a phase from the operators that
anti-commute. Following a argument similar to Step 2, we find
√
q
|||ψ2 i − |ψ3 i|| ≤ 2n 2ε . (3.37)
Step 4: Here is |ψ4 i once again:
1
|ψ4 i = √ ∑ (−1)t·s (−1) p·(u⊕s⊕q) Z 0t⊕p X 0u⊕s⊕q ψ 0 |sui.
23n s,t,u
We can see that |ψ4 i can be had from |ψ3 i by moving Z 0 to the left past the X 0 s, again using an argument
similar to Step 2. We find
√
q
|||ψ3 i − |ψ4 i|| ≤ 2n 2ε . (3.38)
Step 5: Now we make two changes of variable, t 7→ t ⊕ p and u 7→ u ⊕ q and to find that
1
|ψ4 i = √ ∑ (−1)t·s (−1) p·u Z 0t X 0u⊕s ψ 0 |si|u ⊕ qi.
23n s,t,u
(3.39)
We will replace the X 0 s with Z 0 s using Lemma 3.4 to obtain |ψ5 i, which we recall to be
1 1
|ψ5 i = √ ∑ (−1)t·s (−1) p·u (−1) 2 (u⊕s)·A(u⊕s) Z 0t⊕A(u⊕s) ψ 0 |si|u ⊕ qi .
3n
2 s,t,u
Let us now calculate |||ψ4 i − |ψ5 i||. Again we proceed by way of the definition of ||·|| and the inner
product. First, we find |||ψ5 i|| = 1 following an argument similar to that for |||ψ2 i|| in Step 2. Next we
estimate hψ4 |ψ5 i:
hψ4 |ψ5 i =
1 0 0 0 1 0 0 0 0 0 0 0
3n ∑ (−1)t·s (−1)t ·s (−1) p·(u⊕u ) (−1) 2 (u ⊕s )·A(u ⊕s ) ψ 0 X 0u⊕s Z 0t Z 0t ⊕A(u ⊕s ) ψ 0 s, u ⊕ q|s0 , u0 ⊕ q .
2 s,s0
t,t 0
u,u0
(3.40)
For all non-zero terms we have s = s0 and u = u0 . Re-indexing by s 7→ s ⊕ u we find that the above is
equal to
1 (t⊕t 0 )·u 0 1 0
∑0 ∑ (−1) (−1)(t⊕t )·s (−1) 2 s·As ψ 0 X 0s Z 0t⊕t ⊕As ψ 0 (3.41)
23n s,t,t u
where we have pulled all the terms dependent on u into the inner sum. Lemma 2.8 says that this inner
sum is zero except where t ⊕ t 0 = 0 when it is 2n . Substituting these in, the above becomes
1 1
(−1) 2 s·As ψ 0 X 0s Z 0As ψ 0 . (3.42)
2n ∑
s
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 23
M ATTHEW M C K AGUE
Now let us bound the inner product:
1 1
|1 − hψ4 |ψ5 i| = 1 − n ∑(−1) 2 s·As ψ 0 X 0s Z 0As ψ 0 (3.43)
2 s
1 1
≤ 1 − (−1) 2 s·As ψ 0 X 0s Z 0As ψ 0 (3.44)
2n ∑ s
√
2ε
≤ n ∑ 2(s · As) + (s · s) (3.45)
2 s
|E| + n √
≤ 2ε . (3.46)
2
To obtain the second line above we have used the triangle inequality. The third line comes from taking
Lemma 3.4, multiplying on the left by hX 0s | and applying Lemma 2.7. We then use Lemma 2.9 to obtain
the last line. Finally we find q √
|||ψ4 i − |ψ5 i|| ≤ (|E| + n) 2ε . (3.47)
Adding all the bounds using the triangle inequality we obtain
√ √ p 1
|||ψ1 i − |ψ5 i|| ≤ 2 p · p + 2 2n + |E| + n (2ε) 4 . (3.48)
Step 6: We now have an estimate for the distance between |ψ1 i and |ψ5 i. The final step is to show that
|ψ5 i factors so that we can define |junki.
In |ψ5 i, changing variable t 7→ t ⊕ A(u ⊕ s) we get
1 1
|ψ5 i = √ ∑ (−1)t·s (−1) p·u (−1)s·A(u⊕s) (−1) 2 (u⊕s)·A(u⊕s) Z 0t ψ 0 |si|u ⊕ qi (3.49)
3n
2 s,t,u
and applying Lemma 2.11 cleans this up to
1 1 1
√ ∑ (−1)t·s (−1) p·u (−1) 2 s·As (−1) 2 u·Au Z 0t ψ 0 |si|u ⊕ qi (3.50)
3n
2 s,t,u
after which the state factors as follows:
1 1 1
|ψ5 i = √ ∑(−1)t·s (−1) 2 s·As ψ 0 |si ∑(−1) p·u (−1) 2 u·Au |u ⊕ qi
3n
2 s,t u
!
1 1
= (−1)t·s (−1) 2 s·As Z 0t ψ 0 |si X q Z p |Gi . (3.51)
2n ∑ s,t
Setting
1 1
|junki := n ∑ (−1)t·s (−1) 2 s·As Z 0t ψ 0 |si (3.52)
2 s,t
we can finally state
√ √ 1
Φ X 0q Z 0p ψ 0
p
− |junkiX q Z p |Gi ≤ 2 p · p + 2 2n + |E| + n (2ε) 4
(3.53)
which concludes the proof.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 24
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
3.2 Error bounds for non-Pauli measurements
In order to achieve universal computation we need to have measurements other than just X and Z. It
suffices to have X-Z plane measurements. Let us define
Rv (θ ) = cos θ Xv + sin θ Zv . (3.54)
We use the symbol R0u (θ ) to denote the ±1 eigenvalue observable that the prover uses when queried with
the angle θ . We do not make any prior assumption on how R0u (θ ) is related to Xu0 or Zu0 . Instead we will
derive said relationship via the graph-state test and further measurements.
Lemma 3.5. Under the conditions of Theorem 3.1, if we have measurements R0v (θ ) and an edge (u, v)
such that
ψ 0 R0v (θ ) cos θ Z 0A1v + sin θ Xu0 Z 0A1u ⊕1v ψ 0 ≥ 1 − ε (3.55)
then with Φ and |junki set to those in Theorem 3.1,
Φ(R0v (θ ) ψ 0 ) − |junkiRv (θ )|ψi ≤
p
2(ε + 2δ ) (3.56)
where δ is the bound in Theorem 3.1.
Proof. From Theorem 3.1 we obtain Φ and |junki so that
Φ(M 0 ψ 0 ) − |junkiM|ψi ≤ δ (3.57)
for M 0 ∈ {Z 0A1v , Xu0 Z 0A1u ⊕1v } in particular. From the stabilizer generators Su and Sv we find
Xu Z A1u ⊕1v |ψi = Zv |ψi and Z A1v |ψi = Xv |ψi ,
hence linearity of Φ and the triangle inequality give
Φ cos θ Z 0A1v + sin θ Xu0 Z 0A1u ⊕1v ψ 0 − |junki (cos θ Xv + sin θ Zv ) |ψi
≤ (cos θ + sin θ )δ . (3.58)
Using cos θ Xv + sin θ Zv = Rv (θ ) and cos θ + sin θ ≤ 2 this becomes
Φ cos θ Z 0A1v + sin θ Xu0 Z 0A1u ⊕1v ψ 0 − |junkiRv (θ )|ψi ≤ 2δ . (3.59)
Now since ||hψ 0 |Φ(R0v (θ ))||∞ = 1, we have
Φ ψ 0 R0v (θ ) Φ cos θ Z 0A1v + sin θ Xu0 Z 0A1u ⊕1v ψ 0 − Φ ψ 0 R0v (θ ) |junkiRv (θ )|ψi ≤ 2δ .
(3.60)
Φ preserves inner products, so this becomes
ψ 0 R0v (θ ) cos θ Z 0A1v + sin θ Xu0 Z 0A1u ⊕1v ψ 0 − Φ ψ 0 R0v (θ ) |junkiRv (θ )|ψi ≤ 2δ .
(3.61)
Using the triangle inequality and (3.55) we find
Φ( ψ 0 R0v (θ ))|junkiRv (θ )|ψi ≥ 1 − ε − 2δ . (3.62)
We now apply Lemma 2.7 to obtain the desired bound.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 25
M ATTHEW M C K AGUE
The lemma says that if we can estimate the expected value for a certain operator we can bound the
error on R0u (θ ). Later in Section 3.4 we will show how we can estimate said expected value.
3.3 Error bounds for measurement patterns
Our bounds in Section 3.1 show that we can bound the error when applying a measurement of the
form M1 ⊗ · · · ⊗ Mn , which gives a single bit of output. However, for graph state computation we need
something much more substantial since we will need to measure the subsystems in a sequence, with each
basis chosen as a function of the previous outcomes. In fact we will prove something even stronger than
this.
We will consider a more general situation where instead of trusted classical computation and classical
interaction, we have some trusted quantum computation and quantum interaction with the provers. The
provers allow the basis to be chosen quantumly and they similarly return the result coherently. We can
model this by specifying that, when queried with a quantum register, prover j applies
mj
V j0 = ∑ |kihk| ⊗ M 0j,k (3.63)
k=0
where M 0j,k corresponds to the observable that prover j uses when queried with input k ∈ {0 . . . m j }. The
prover then passes the control register back to the verifier and the result of the query is stored as a ±1
phase. We will require that the prover’s actions are all of this form, although they are free to choose the
M 0j,k as they like. As well, the ideal operator V j has this form, using observables M j,k .
Assuming5 M 0j,0 = I we can retrieve the outcome for measurement M 0j,k by preparing the state
1
√ (|0i + |ki)
2
and observing the relative phase change in the prover’s response. Hence this model includes the original
classical behavior as a particular case.
A general circuit for the verifier-prover interaction in this stronger model is given in Figure 7. The
verifier first applies some unitary U0 to prepare its initial state, and then performs the first query to prover
1, V10 . The verifier then applies some unitary U1 to its internal state and performs the second query to
prover 2, V20 , and so on. The combined operation is UnVn0 . . .U1V10U0 . We require that each V j0 is applied at
most once and for convenience we suppose that they are numbered in the order in which they are applied.
In this circuit we have always used the same the control wire, which is a q-dit with dimension equal to the
maximum m j + 1. This is not a limitation since we can always use the same control wire by incorporating
swaps into the U’s if necessary.
Let W00 = U0 , and W j0 = U jV j0W j−1
0 for j ≥ 1. That is, W j0 represents running the circuit until the point
after U j has been applied. Similarly, let W j = U jV jW j−1 be the ideal circuit where we substitute in the
ideal V j (constructed from the ideal M j,k ).
5 Our current self-test doesn’t test whether the identity is performed correctly, but this should always give the outcome 1 so
we can simulate this perfectly by just ignoring the prover and setting the outcome to 1. We could instead test whether the prover
actually returns 1 but this is unnecessary except in this imaginary case of quantum control.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 26
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
Trusted U0 U1 U2 ...
• • •
V10
V20
Untrusted
...
V30
..
.
Figure 7: Semi-trusted circuit incorporating untrusted measurements by the provers, V j0 .
Lemma 3.6. Let |ψi, |ψ 0 i, |junki, and Φ = Φ1 ⊗ · · · ⊗ Φn be given along with M 0j,k and M j,k (k = 0 . . . m
and M 0j,0 = I) such that
Φ M 0j,k ψ 0 − |junkiM j,k |ψi ≤ δ .
(3.64)
Further, let some |φ i and U j be given where |φ i contains a register of dimension at least m + 1 and U j
acts only on the |φ i registers, and let, V j , V j0 , W j and W j0 be defined as above. Then
Φ(Wn0 ψ 0 |φ i) − |junkiWn |ψi|φ i ≤ (2nm + 1)δ . (3.65)
The intuition is that each V j0 is the sum of operators |kihk| ⊗ M 0j,k , each of which is close to the
corresponding ideal operator. We can then use the triangle inequality to say that V j0 as a whole is close to
its ideal counterpart. Inducting over the depth of the circuit gives the desired result.
Proof. The proof proceeds by induction. For the case n = 0 we have not yet applied any untrusted gates
and the conclusion is true by taking inequality (3.64) with k = 0 and multiplying by the trusted gate U0 .
Now let us suppose that (3.65) holds for n − 1. We start by using the bound (3.64) with ( j, k) = (1, 0)
to get
Φ ψ 0 − |junki|ψi ≤ δ .
(3.66)
0 ) to obtain inequalities
For each k 6= 0 we multiply on both sides by Φn (Mn,k
0 0
Φn (Mn,k )|junki|ψi − Φn (Mn,k )Φ( ψ 0 ) ≤ δ . (3.67)
By Lemma 2.6, Φn (Mn,k 0 )Φ(|ψ 0 i) = Φ(M 0 |ψ 0 i), so the state on the right above is close to |junkiM |ψi
n,k n,k
by (3.64) with ( j, k) = (n, k). Using the triangle inequality we find
0
Φn (Mn,k )|junki|ψi − |junkiMn,k |ψi ≤ 2δ . (3.68)
We introduce the register |φ i and apply the ideal unitary Wn−1 to both sides in the above estimation
without increasing the distance. On the left, since Φn and Mn,k 0 only operate on the nth subsystem,
0
Φn (Mn,k ) operates only on the nth subsystem of |junki|ψi (i. e., on the nth subsystem of |junki together
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 27
M ATTHEW M C K AGUE
with the nth subsystem of |ψi). Then since Wn−1 operates only on the trusted system and the first n − 1
0 ) and M
subsystems of |ψi, it commutes with Φn (Mn,k n,k so
0
Φn (Mn,k )|junkiWn−1 |ψi|φ i − |junkiMn,kWn−1 |ψi|φ i ≤ 2δ . (3.69)
Now we apply the projection |kihk| (used in the expression for Vn0 ) to both sides, again without increasing
the distance. Hence
0
|kihk| ⊗ Φn (Mn,k )Wn−1 |junki|ψi − |junki|kihk| ⊗ Mn,kWn−1 |ψi ≤ 2δ . (3.70)
Summing over all k using triangle inequality, we apply the definitions of V j and V j0 to arrive at
Φ(Vn0 )|junkiWn−1 |ψi|φ i − |junkiVnWn−1 |ψi|φ i ≤ 2mδ . (3.71)
Note that it is 2mδ and not 2(m + 1)δ since the case k = 0 has no error by assumption. The state on
the right above is almost what we want. Now we invoke the induction hypothesis (3.65) with n − 1 and
multiply through by Φ(Vn0 ) to get
Φ(Vn0Wn−1
0
ψ 0 |φ i) − Φ(Vn0 )|junkiWn−1 |ψi|φ i ≤ 2m(n − 1)δ (3.72)
and applying the triangle inequality to the above two estimates we get
Φ(Vn0Wn−1
0
ψ 0 |φ i) − |junkiVnWn−1 |ψi|φ i ≤ 2mnδ . (3.73)
Multiplying by the trusted gate Un (which commutes with Φ) finishes the proof.
For our purposes we do not need the full strength of the lemma. We need only know that adaptive
measurements give correct outcomes, which we prove in the following corollary.
Corollary 3.7. Let |ψi, |ψ 0 i, |junki, and Φ = Φ1 ⊗· · ·⊗Φn be given along with M 0j,k and M j,k (k = 0 . . . m
and M 0j,0 = I) such that
Φ M 0j,k ψ 0 − |junkiM j,k |ψi ≤ δ .
(3.74)
Then for any adaptive measurement made using the M 0 s, the probability of a particular outcome differs
from the ideal case by at most 2(2nm + 1)δ .
Proof. We can represent an adaptive measurement as a circuit Wn as in Lemma 3.6. Hence
Φ(Wn0 ψ 0 |φ i) − |junkiWn |ψi|φ i ≤ (2nm + 1)δ . (3.75)
To obtain the classical outcome we perform some measurement on one of the trusted subsystems. Without
loss of generality this can be a projective measurement, so let Πx be the projector for outcome x, which
acts non-trivially only on the trusted subsystem. The probability of outcome x is then
ψ 0 hφ |Wn†0 ΠxWn0 ψ 0 |φ i . (3.76)
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 28
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
Now to estimate this probability we use (3.75) above in two different ways. First, multiplying on the
left by Φ(hψ 0 |hφ |Wn†0 )Πx we get
Φ( ψ 0 hφ |Wn†0 )Πx Φ(Wn0 ψ 0 |φ i) − Φ( ψ 0 hφ |Wn†0 )Πx |junkiWn |ψi|φ i ≤ (2nm + 1)δ . (3.77)
Second, multiplying (3.75) on the left by h junk|hψ|hφ |Wn† Πx and then taking the adjoint of the resulting
expression we obtain
Φ( ψ 0 hφ |Wn†0 )Πx |junkiWn |ψi|φ i − hψ|hφ |Wn† ΠxWn |ψi|φ i ≤ (2nm + 1)δ . (3.78)
Adding these together using the triangle inequality and invoking the fact that Φ preserves inner products
we find
ψ 0 hφ |Wn†0 ΠxWn0 ψ 0 |φ i − hψ|hφ |Wn† ΠxWn |ψi|φ i ≤ 2(2mn + 1)δ . (3.79)
In other words, the probability of finding outcome x differs from the ideal case by at most 2(2mn +
1)δ .
3.4 A one-shot test
As stated, the self-testing results are not terribly useful to us. They require knowledge of the expected
value of various operators in order to draw any conclusions. The obvious solution is to take some samples
and estimate, but this would require either some independence assumptions or additional work with, for
example, martingales as is done in [23]. Instead we will work with the contrapositive of the self-testing
results: if the state and/or some measurements are far away from the ideal, then some measurable expected
value will also be far away from the ideal. Although this is logically equivalent, instead of requiring lots
of information about the various measurements, we instead are told that we just have to look for one
measurement that is misbehaving.
As well, we are going to arrange our measurements in a particular way as a test for honesty. For
example, the stabilizer measurements will always return 1 for honest provers, so if we perform this
measurement and we get a 1 the provers pass the test. If result is -1 then they fail the test. As the expected
value gets close to 1, the provers will pass with probability close to 1. If the expected value is far away
from 1, the provers will fail the test with some probability.
Now with the R(θ ) measurements we do not have the same situation, but we do have something just
as useful. We can build a compound test so that the ideal honest provers pass with some probability,
and no other provers can pass with a higher probability. This is analogous to the CHSH test: the ideal
quantum strategy passes with probability ≈ 0.85, and no other strategy achieves any higher success rate.
As well, cheating provers will pass the test with a probability that is bounded away from the quantum
limit, and so we obtain a gap between the ideal and cheating strategies. The honest provers will fail the
test some of the time, but this is no problem: we will later do some repetition so that the ideal provers
will pass with an overall probability that can be made arbitrarily close to 1.
Now we give the construction for our one-shot test. Fix a graph G = (V, E) in which every vertex
appears in a triangle and set n = |V |. Let T be a set of triangles that covers V , i. e., each vertex in V
appears in at least one triangle in T . The triangles will be specified by characteristic vectors τ. Let
NG = 3|V | + |T |. Note that NG ≤ 4n since we need no more than n triangles to cover V .
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 29
M ATTHEW M C K AGUE
For a graph state computation we need only two different measurement angles per vertex, ±θv . As
well, the measurement angle θv + π can be simulated by measuring with angles θv and flipping the
outcome. Hence there is no loss of generality by assuming that 0 ≤ θv ≤ π so that cos θv ≥ 0.
The test procedure is as follows:
Procedure 2 (One-shot test for graph states and measurements).
1. Randomly select either “VERTEX” with probability |V |/NG , “TRIANGLE” with probability
|T |/NG , or “RTHETA” with probability 2|V |/NG .
2. if “VERTEX,”
(a) Select v ∈R V .
(b) Query the provers with bases according to SV = Xv Z A1v .
(c) Accept if the product of the replies is 1, otherwise reject.
3. if “TRIANGLE,”
(a) Select τ ∈R T .
(b) Query the provers with bases according to X τ Z Aτ .
(c) Accept if the product of the replies is -1, otherwise reject.
4. if “RTHETA,”
(a) Choose t ∈R {1, −1} and v ∈R V and let u be a vertex adjacent to v. (u can be fixed ahead of
time for each v.)
cos θv | sin θv |
(b) Choose either X with probability or Z with probability .
cos θv + | sin θv | cos θv + | sin θv |
(c) if X,
i. Query the provers with Rv (tθv )v Z A1v .
ii. Accept if the product of the replies is 1, otherwise reject.
(d) if Z,
i. Query the provers with tRv (tθv )Xu Z A1u ⊕1v .
ii. Accept if the product of the replies is 1, otherwise reject.
To clarify, if the basis for a prover is I then we simply ignore that prover, and its “reply” is taken to be
1.
The test is naturally grouped into NG subtests. From the graph state test we have |V | subtests testing
the “physical stabilizers,” and |T | subtests testing the triangles. Additionally, there are 2|V | “RTHETA”
subtests, one for each choice of v and t. Each of these consists of two queries chosen according to some
random coin.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 30
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
Lemma 3.8. Let n non-communicating quantum provers be given that each take one of four measurement
bases, labeled X, Z and Rv (±θv ) as inputs and measure joint state |ψ 0 i according to operators in
{Xv0 , Zv0 , R0v (θv )}. Then Procedure 2 accepts with probability at most
2|V | + |T | + ∑v cos θv +|1 sin θv |
ctest = (honest case) (3.80)
NG
and if there exist v and M ∈ {Xv , Zv , Rv ± θv )v } such
Φ M0 ψ 0
− |junkiM|Gi > δ (3.81)
then Procedure 2 accepts with probability at most
4
δ2
1
ctest − √ (dishonest case). (3.82)
2NG 22 + 25 n
Proof. Honest case. First let us derive the maximum probability of passing the test. This is attained
in the honest case. The “VERTEX” and “TRIANGLE” subtests can all be passed simultaneously with
probability 1 in the honest case since the observables are all in the stabilizer group of the graph state.
Let us now consider the “RTHETA” subtests. First, we fix a vertex v. The queries to the provers in
this subtest can be seen as one large random variable taking values ±1 and having the expected value
1
ψ 0 R0v (θv ) cos θv Z 0A1v + sin θv Xu0 Z 0A1u ⊕1v ψ 0
2(cos θv + | sin θv |)
+ ψ 0 R0v (−θv ) cos θv Z 0A1v − sin θv Xu0 Z 0A1u ⊕1v ψ 0 . (3.83)
Note the similarity to the CHSH correlation, which is obtained for θv = π/4.
The honest provers (with R0v (θv ) = Rv (θv )) will attain an expected value of
1
.
2(cos θv + | sin θv |)
To see this, we notice that Z A1v |ψi = Xv |ψi and Xu Z A1u ⊕1v = Zv |ψi, which we obtain from the stabilizers
Sv and Su , respectively. Applying the definition of R(θ ), the expected value becomes
1 1
hψ| Rv (θv )2 + Rv (−θv )2 |ψi =
(3.84)
2(cos θv + | sin θv |) cos θv + | sin θv |
since R2v (θv ) = I.
Now we show that this is in fact the maximal quantum expected value. Using a standard technique
introduced by Cirel’son [6], the maximum value is the same as
1
max hψ1 | (cos θv |φ1 i + sin θv |φ2 i)+hψ2 | (cos θv |φ1 i − sin θv |φ2 i) (3.85)
2(cos θv + | sin θv |) |ψ1 i,|ψ2 i,|φ1 i,|φ2 i
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 31
M ATTHEW M C K AGUE
where the maximization is taken over normalized states, all of dimension four. Clearly the maximum is
found when |ψ1 i is taken to be in the direction of cos θv |φ1 i + sin θv |φ2 i and |ψ2 i is in the direction of
cos θv |φ1 i − sin θv |φ2 i. In this case the value becomes
1
max ||cos θv |φ1 i + sin θv |φ2 i|| + ||cos θv |φ1 i − sin θv |φ2 i|| . (3.86)
2(cos θv + | sin θv |) |φ1 i,|φ2 i
Expanding using the definition of ||·|| we obtain
1 p p
max 1 + 2 cos θv sin θv Re hφ1 |φ2 i + 1 − 2 cos θv sin θv Re hφ1 |φ2 i . (3.87)
2(cos θv + | sin θv |) |φ1 i,|φ2 i
We next use the identity cos θ sin θ = (1/2) sin 2θ to get
1 p p
max 1 + sin 2θv Re hφ1 |φ2 i + 1 − sin 2θv Re hφ1 |φ2 i . (3.88)
2(cos θv + | sin θv |) |φ1 i,|φ2 i
√ √ q√ √ p √
Now, 1 + a + 1 − a = ( 1 + a + 1 − a)2 = 2 + 2 1 − a2 so the above becomes
r
1
q
max 2 + 2 1 − (sin 2θv Re hφ1 |φ2 i)2 (3.89)
2(cos θv + | sin θv |) |φ1 i,|φ2 i
which attains the value of
1
cos θv + | sin θv |
when hφ1 |φ2 i = 0.
We now have the expected value of the honest case and a matching upper bound. The expected
value of any ±1 valued random variable X is related to the probability of obtaining 1 (i. e., the “success”
probability) by
hXi 1
Prob(X = 1) = + . (3.90)
2 2
So the probability of success for the “RTHETA” portion of the test for a specific v is bounded above by
1 1
cvtest := + . (3.91)
2(cos θv + | sin θv |) 2
Combining this with the maximum probability of success for the “VERTEX” and “TRIANGLE”
subtests, the overall maximum probability of success for any set of quantum provers, attained for honest
provers, is
1
|V | + |T | + 2 ∑v cvtest 2|V | + |T | + ∑v cos θv +| sin θv |
ctest := = . (3.92)
NG NG
The factor 2 in front of the summation represents the fact that for each v the “RTHETA” subtest occurs
with probability 2/NG .
Dishonest case. Now that we have an upper bound, we translate the probability of success into an
error bound on the expectation value of each subtest.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 32
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
From now on fix a set of provers, which fixes the observables and state. Suppose that the provers
pass the test with probability ctest − ε/(2NG ). Then each “VERTEX” or “TRIANGLE” subtest passes
with probability at least 1 − ε/2, which is obtained when all the error happens on a single subtest. This
means that the expected value for the corresponding random variable is 1 − ε and the conditions for
Theorem 3.1, (3.1) and (3.2) are satisfied. Hence for M ∈ {Xv , Zv } the left side of (3.81) is bounded above
by
√ √ p 1
δ1 := 2 p · p + 2 2n + |E| + n (2ε) 4 (3.93)
5
√ √ 1
≤ 2 4 1 + (1 + 2) n ε 4 (3.94)
√ 1
≤ 2.5 1 + 2.5 n ε 4 . (3.95)
We have used the estimations p · p ≤ 1, since this is all we need to apply Corollary 3.7, and |E| ≤ 3n,
since we are using a triangular cluster state which has a maximum degree of 6.
For the “RTHETA” subtests, fix a v. As above, the expected value for the corresponding ±1 random
variable is at least cvtest − ε. Hence the conditions of Lemma 3.5 are satisfied for each v and ±θ . Then for
M ∈ {Rv ± θv )v } the left hand side of inequality (3.81) is bounded above by
√ 1
q
δ2 := 2ε + 10 1 + 2.5 n ε 4 (3.96)
√ 1
q
≤ 22 + 25 nε 8 (3.97)
where we have used ε ≤ ε 1/4 for 0 ≤ ε ≤ 1. When ε ≤ 1 the error bound for R0v (±θv ) will be larger than
for X or Z, so we will use
√ 1
q
δ = 22 + 25 nε 8 . (3.98)
We have just shown that if the provers pass the test with probability at least ctest − ε/(2NG ) then the
left side of (3.81) is bounded by δ as above (i. e., (3.81) is false for all M). This is the contrapositive of
our desired result which is that, if (3.81) is true for some M, then the probability of passing is at most
ctest − ε/(2NG ). So we need only solve for ε in terms of δ . We find
4
δ2
ε≥ √ . (3.99)
22 + 25 n
Now the probability of passing is at most ctest − ε/(2NG ), which is bounded above by
2|V | + |T | + ∑v (cos θv +|1 sin θv |) 1
δ2
4
− √ . (3.100)
NG 2NG 22 + 25 n
This one-shot test gives us an error bound on the states and measurements. Combining this with
Lemma 3.6 we can relate the probability of passing the test to the error in an adaptive measurement, i. e.,
our final measurement-based quantum computation.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 33
M ATTHEW M C K AGUE
Corollary 3.9. Let a set of quantum provers be given where prover v takes inputs in {Xv , Zv , Rv ± (θv )v }
and outputs ±1. For honest provers, Procedure 2 accepts with probability
2|V | + |T | + ∑v (cos θv +|1 sin θv |)
ctest = . (3.101)
NG
For general provers, if for any adaptive measurement pattern the probability of any outcome on the
provers’ final outcome differs from the ideal by more than δ then Procedure 2 accepts with probability no
more than
1
2|V | + |T | + ∑v 2(cos θv +| sin θv |) δ8
stest = − 17.7 11 . (3.102)
NG 10 n
Proof. We will again prove the contrapositive of the desired statement. We would like to show that the
outcome of any measurement pattern differs from the ideal by no more than δ . By Corollary 3.7, if we
achieve error less than
δ
δ0 =
2(8n + 1)
on equation (3.74) then we achieve our goal, since m = 4 here. Lemma 3.8 says that we can in turn
achieve this level of error if the provers pass with probability no more than
stest = ctest − ε (3.103)
with
4
δ 02
1
ε= √ (3.104)
2NG 22 + 25 n
4
δ2
1
≥ √ (3.105)
4n 8(8n + 1)2 (22 + 25 n)
4
δ2
1
≥ √ (3.106)
8n 4(9n)2 (47 n)
δ8
≥ 17.7 11 (3.107)
10 n
√
using the pessimistic bounds NG ≤ 4n and 1 ≤ n ≤ n. Hence if the provers pass with probability higher
than
|V | + |T | + 2 ∑v (cos θv +|1 sin θv |) δ8
stest = − 17.7 11 (3.108)
NG 10 n
then any adaptive measurement will differ by no more than δ from our goal. Taking the contrapositive, if
some adaptive measurement differs by more than δ then the provers will pass the test with probability no
more than stest .
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 34
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
4 Interactive proofs
We are now in a position to construct an interactive proof for any language in BQP. To this end, let L be
a language in BQP. Then from Theorem 2.1 and the definition of BQP for any input x there exists an
adaptive measurement6 on a polynomially sized triangular graph state such that
• If x ∈ L then the measurement outputs “ACCEPT” with probability ccalc ≥ 2/3.
• If x ∈
/ L then the measurement outputs “ACCEPT” with probability scalc ≤ 1/3.
The adaptive measurement supplies the measurements required for each vertex via angles θv . It also
supplies the functions required for the adaptation. The interactive proof is given by the following
procedure.
Procedure 3.
1. Randomly choose “CALCULATE” with probability q or “TEST” with probability 1 − q.
2. If “CALCULATE”:
(a) Query provers according to the measurement-based computation.
(b) Accept if the computation accepts.
3. if “TEST”:
(a) Perform the test for honesty given in Procedure 2.
(b) Accept if the test accepts.
Now we calculate the optimal value of q.
Lemma 4.1. Let L be a language and x in input. Suppose we are given an adaptive measurement on a
triangular cluster state on n vertices which implements a measurement-based computation which decides
whether x ∈ L with error at most 1/3 (i. e., ccalc ≥ 2/3 and scalc ≤ 1/3). Let 0 < δ < 1/6 be given and set
ctest − stest
q= . (4.1)
1 + ctest − scalc − stest − δ
Then
• if x ∈ L then for honest provers Procedure 3 accepts with probability at least cip ,
• if x ∈
/ L then for any set of provers Procedure 3 accepts with probability at most sip ,
where
δ8
cip − sip ≥ . (4.2)
1018.8 n11
6 The adaptive measurement is a member of a uniformly generated set.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 35
M ATTHEW M C K AGUE
Proof. Let ctest be the probability of honest provers passing the test, and let stest be the probability of
dishonest provers passing the test, given in Corollary 3.9. Here, by dishonest we mean that the probability
of some outcome of an adaptive measurement made using the provers differs from the honest case by
more than the given δ .
Then we have two cases:
• The input is in the language: then we only care about the honest case, in which the probability of
accepting is cip ≥ qccalc + (1 − q)ctest .
• The input is not in the language: then there are two subcases:
– The provers pass the test with probability at least stest . Then by Corollary 3.9 the probability
of accepting on the calculation is at most scalc + δ and the probability of accepting on the test
is at most ctest for an overall probability of at most q(scalc + δ ) + (1 − q)ctest .
– The provers pass the test with probability less than stest . Then the probability of accepting on
the calculation could be as high as 1, since we gain no information from the test. The overall
probability of accepting is then less than q + (1 − q)stest .
The two different cases in the x ∈
/ L case give two different gaps which are, in the first case
qccalc + (1 − q)ctest − q(scalc + δ ) − (1 − q)ctest = q(ccalc − scalc − δ ) (4.3)
and in the second case
qccalc + (1 − q)ctest − q − (1 − q)stest = q(ccalc − 1) + (1 − q)(ctest − stest ) . (4.4)
The overall gap is the minimum of these two. We wish to find q which maximizes the minimum. The
two equations are just lines in q which cross each other. At the point where they are equal we find the
maximum overall gap. The crossing point is easily found to be at
ctest − stest
q= (4.5)
1 + ctest − stest − scalc − δ
which gives a gap of
(ccalc − scalc − δ )(ctest − stest )
cip − sip = (4.6)
1 + ctest − stest − scalc − δ
1 δ8
≥ . (4.7)
12 1017.7 n11
On the first line, we see that the denominator can be no larger than 2, and the first factor in the numerator
is at least 1/6 (when δ = 1/6 and ccalc − scalc = 1/3). So we can lower bound the gap by
1
(ctest − stest ) ,
12
which is estimated in Corollary 3.9.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 36
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
We are now in a position to prove our main claim. This is obtained by applying a standard gap
amplification procedure.
Procedure 4.
1. Perform Procedure 3 N times and let the number of times the procedure accepts be M.
cip + sip
2. If M > N then accept.
2
3. Otherwise reject.
Note that there is ambiguity in Procedure 4. In particular, it does not mention whether the repetition
of Procedure 3 should be done serially or in parallel. In fact this does not matter, as we shall see in the
proof below. We can add N sets of n provers and query each prover once, or use one set of n provers and
query each one N times.
Proof of Theorem 1.1. Let L ∈ BQP be given along with input x. Theorem 2.1 tells us that we can find
an adaptive measurement on a triangular cluster state on n = poly(|x|) vertices whose outcome tells us
whether x ∈ L with error less than 1/3. From Lemma 4.1 we have an interactive proof such that if x ∈ L
then we accept with probability at least cip for honest provers, and if x ∈/ L we accept with probability at
most sip .
Now we amplify using Procedure 4. Let us first consider the case x ∈ L. Then we are interested in the
case of honest provers, in which case we have N independent and identical Bernoulli trials with some
probability of accepting p ≥ cip . Using Hoeffding’s inequality, the probability that we mistakenly reject
is bounded by
cip +sip 2
cip + sip
N p − N 2
P M≤N ≤ exp −2 (4.8)
2 N
N(cip + sip )2
≤ exp − . (4.9)
2
Setting this equal to 1/3 we solve for N to find the minimum number of trials to achieve our desired error
rate.
2 ln 3
N≥ . (4.10)
(cip + sip )2
Substituting in for cip − sip as estimated in Lemma 4.1 we obtain
1037.9 n22
N≥ . (4.11)
δ 16
The same number of repetitions also suffices to bound the probability of accepting when x ∈ / L to
below 1/3. The analysis is similar, however if the provers are not honest they may vary their behavior
on each trial, so the trials are not necessarily identically distributed. However, since the probability p of
accepting satisfies p ≤ sip for every trial we can still use Hoeffding’s inequality.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 37
M ATTHEW M C K AGUE
To make this argument formal, let A j be the random variable corresponding to the verifier accepting
on the jth trial with 1 indicating acceptance and 0 indicating rejection. Further, let e be some event which
may depend on trials 1, . . . , j − 1. Now consider the probability P(A j = 1 | e).
First note that all operations that contribute to A j commute with operations on all other trials (parallel
repetition with fresh provers), or happen before the jth trial (sequential repetition with a single set of
provers). Also, the verifier’s actions are independent for each trial. Therefore we may assume without
loss of generality that the jth trial happens after everything else has completed. Because everything else
in independent from the verifier’s actions on the jth trial, the provers can simulate their actions for all
other trials by choosing randomness themselves. Hence one option for the provers’ strategy on a single
trial is to perform the N trial protocol for trials 1, . . . , j − 1, repeating until the event e is observed, and
then proceeding. This is effectively a state preparation for the jth trial. The probability of acceptance is
then bounded by the single trial upper bound, P(A j = 1 | e) ≤ sip .
j
Let M j = ∑k=1 Ak . We will apply induction on j and show that P(M j ≥ T ) is upper bounded by
the case of a binomial distribution on j trials with probability sip . The case for j = 1 is trivial. For the
inductive step let 0 ≤ T be given.
P(M j ≥ T ) = P(A j = 1 | M j−1 ≥ T − 1)P(M j−1 ≥ T − 1) + P(A j = 0 | M j−1 ≥ T )P(M j−1 ≥ T ) . (4.12)
Applying the upper bound on P(A j | e) we find
P(M j ≥ T ) ≤ sip P(M j−1 ≥ T − 1) + (1 − sip )P(M j−1 ≥ T ) (4.13)
and with the induction hypothesis we see that this is further upper bounded by assuming the binomial
distribution with j trials and probability of a 1 given by sip . We may thus apply an argument similar
that for x ∈ L, finding that the same number of trials suffices to bound the probability of error to within
1/3.
5 Discussion
5.1 Assumptions
For our result to hold, we must assume that the provers behave according to quantum mechanics. This is
because we model the provers using the quantum formalism. Currently this appears to be a reasonable
assumption since quantum mechanics has been a very successful theory. However, we run into a problem
if we wish to use this result in certain circumstances. For example, we may wish to verify that quantum
mechanics generates accurate predictions for very complex systems. In this case it becomes infeasible
to classically compute predictions from the quantum model. Quantumly, this is still possible, and we
might be tempted to use an interactive proof in order to verify that our quantum computer has done the
computation correctly. However, if we use the arguments in this paper we run into a problem of circularity
since we must assume that quantum mechanics is correct in order for the argument to go through, but
quantum mechanics is exactly what we want to verify! Hence it remains an important open question
whether it is possible to achieve interactive proofs for problems in BQP where the prover’s actions are
easy for quantum computers but for which we do not assume a priori that quantum mechanics holds.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 38
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
5.2 Time-space trade-offs
As discussed in the proof of Theorem 1.1, there are space-time trade-offs. In particular we may perform
the gap amplification by repeating in parallel or serially, or some mixture of the two. Hence we could
perform N repetitions on n provers, each of which then performs N measurements, or we can repeat in
parallel with nN provers, each of which performs a single measurement.
Another factor, which we have not mentioned, is the time required to build the necessary graph states.
Graph states are built by applying CTRL-Z gates, one for each edge. At worst this can take no more than
O(n2 ) operations. For triangular cluster states, such as we use here, the degree of each vertex in bounded
above by 6 so at most 3n 2-qubit operations are required (plus n single-qubit state preparations). These
can be parallelized in a constant depth circuit by exploiting the localized structure of triangular cluster
states. Regardless, the state preparation can be accomplished in a polynomial number of steps.
5.3 Other considerations
The work of RUV [26] can be used to prove that MIP∗ = QIP, by using additional provers to simulate
a quantum verifier. Although the same argument can be used to build an interactive proof using our
construction, this does not prove MIP∗ = QIP. The reason is that the number of provers will in general
grow with the input size, which is not allowed in MIP∗ .
The RUV paper also claims that their protocol is blind, which in this case means that an individual
prover cannot determine what computation has been performed. Both provers together, however, will still
be able to reconstruct the computation. Note that this is a different notion of blindness than considered by
Broadbent et al. [5]. For our construction, a similar property holds: a universal graph can be chosen, and
an individual prover has no idea when the computation has happened (as opposed to a self-test) and so
cannot determine what computation was carried out.
5.4 Future work
Our error bounds are clearly suboptimal and clearly not tight enough to be of practical relevance. In many
places we have made only loose estimates which suffice for our purposes of establishing a polynomial
bound, but could be made more robust. Hence one avenue of future improvement is to tighten these
bounds.
Currently our construction uses many simple provers, providing a nice complement to Reichardt et
al.’s result using a constant number provers. Much of our result could easily be adapted to the case of
two provers. The most difficult part is the graph-state test. Likely it is not possible to prove a self-testing
theorem for two provers if there are any odd cycles in the graph since it would be necessary at some point
to test the entanglement across an edge with both vertices held by a single prover. However, bipartite
graph states could yet be self-tested with two provers.
Acknowledgements. Thanks to Serge Massar, Stefano Pironio, Iordanis Kerenidis, Frédéric Magniez,
David Hutchinson and Michael Albert for helpful discussions.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 39
M ATTHEW M C K AGUE
References
[1] A NTONIO ACÍN , N ICOLAS B RUNNER , N ICOLAS G ISIN , S ERGE M ASSAR , S TEFANO P IRONIO ,
AND VALERIO S CARANI: Device-independent security of quantum cryptography against collective
attacks. Physical Review Letters, 98(23):230501, 2007. [doi:10.1103/PhysRevLett.98.230501,
arXiv:quant-ph/0702152] 2, 3
[2] D ORIT A HARONOV, M ICHAEL B EN -O R , AND E LAD E BAN: Interactive proofs for quantum
computations. In Innovations in Computer Science (ICS’10), pp. 453–469. Tsinghua Univ. Press,
2010. Available at ICS’10 website. [arXiv:0810.5375] 2, 3
[3] 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. MIT Press, 2013. [arXiv:1206.3686] 2
[4] C HARLES -E DWOURD BARDYN , T IMOTHY C. H. L IEW, S ERGE M ASSAR , M ATTHEW M C K AGUE ,
AND VALERIO S CARANI: Device-independent state estimation based on Bell’s inequalities. Physical
Review A, 80(6):062327, 2009. [doi:10.1103/PhysRevA.80.062327, arXiv:0907.2170] 2, 3
[5] A NNE B ROADBENT, J OSEPH F ITZSIMONS , AND E LHAM K ASHEFI: Universal blind quan-
tum computation. In Proc. 50th FOCS, pp. 517–526. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/FOCS.2009.36, arXiv:0807.4154] 2, 3, 39
[6] B ORIS S. C IREL’ SON: Quantum generalizations of Bell’s inequality. Letters in Mathematical
Physics, 4(2):93–100, 1980. [doi:10.1007/BF00417500] 31
[7] R EINHARD D IESTEL: Graph Theory. Volume 173 of Graduate Texts in Mathematics. Springer,
2010. 12
[8] J OSEPH F. F ITZSIMONS AND E LHAM K ASHEFI: Unconditionally verifiable blind computation.
2012. [arXiv:1203.5217] 3
[9] DANIEL G OTTESMAN: Stabilizer Codes and Quantum Error Correction. Ph. D. thesis, Caltech,
1997. [arXiv:quant-ph/9705052] 12, 14
[10] C ARSTEN L UND , L ANCE F ORTNOW, H OWARD J. K ARLOFF , AND N OAM N ISAN: Algebraic
methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in
FOCS’90. [doi:10.1145/146585.146605] 2
[11] F RÉDÉRIC M AGNIEZ , D OMINIC M AYERS , M ICHELE M OSCA , AND H AROLD O LLIVIER: Self-
testing of quantum circuits. In 33rd International Colloquium on Automata, Languages and Program-
ming (ICALP’06), volume 4051 of LNCS, pp. 72–83. Springer, 2006. [doi:10.1007/11786986_8,
arXiv:quant-ph/0512111v1] 2, 3
[12] D OMINIC M AYERS AND A NDREW C HI -C HIH YAO: Quantum cryptography with im-
perfect apparatus. In Proc. 39th FOCS, pp. 503–509. IEEE Comp. Soc. Press, 1998.
[doi:10.1109/SFCS.1998.743501, arXiv:quant-ph/9809039] 2
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 40
I NTERACTIVE P ROOFS FOR BQP VIA S ELF -T ESTED G RAPH S TATES
[13] D OMINIC M AYERS AND A NDREW C HI -C HIH YAO: Self testing quantum apparatus. Quantum Inf.
Comput., 4(4):273–286, 2004. ACM DL. [arXiv:quant-ph/0307205] 2
[14] M ATTHEW M C K AGUE: Quantum Information Processing with Adversarial Devices. Ph. D. thesis,
University of Waterloo, 2010. [arXiv:1006.2352] 3
[15] M ATTHEW M C K AGUE: Self-testing graph states. In 6th Conference on Theory of Quantum
Computation, Communication, and Cryptography (TQC’11), volume 6745 of LNCS, pp. 104–120.
Springer, 2011. [doi:10.1007/978-3-642-54429-3_7, arXiv:1010.1989] 2, 3, 5, 16, 18, 19
[16] M ATTHEW M C K AGUE: Interactive proofs with efficient quantum prover for recursive Fourier
sampling. Chicago J. Theor. Comput. Sci., 2012(6):1–10, 2012. [doi:10.4086/cjtcs.2012.006,
arXiv:1012.5699] 2
[17] M ATTHEW M C K AGUE AND M ICHELE M OSCA: Generalized self-testing and the security of the
6-state protocol. In 5th Conference on Theory of Quantum Computation, Communication, and
Cryptography (TQC’10), volume 6519 of LNCS, pp. 113–130. Springer, 2010. [doi:10.1007/978-3-
642-18073-6_10, arXiv:1006.0150] 3, 15
[18] M ATTHEW M C K AGUE , T ZYH H AUR YANG , AND VALERIO S CARANI: Robust self-testing of
the singlet. Journal of Physics A, 45(45):455304, 2012. [doi:10.1088/1751-8113/45/45/455304,
arXiv:1203.2976] 2, 3, 19
[19] M EHDI M HALLA AND S IMON P ERDRIX: Graph states, pivot minor, and universality of (X, Z)-
measurements. Internat. J. Unconventional Comput., 9(1-2):153–171, 2013. [arXiv:1202.6551] 3,
8
[20] C ARL A. M ILLER AND YAOYUN S HI: Optimal robust quantum self-testing by binary nonlocal
XOR games. In 8th Conference on the Theory of Quantum Computation, Communication and Cryp-
tography, (TQC’13), volume 22 of LIPIcs, pp. 254–262, 2013. [doi:10.4230/LIPIcs.TQC.2013.254,
arXiv:1207.1819] 2, 3
[21] M ICHAEL A. N IELSEN AND I SAAC L. C HUANG: Quantum Computation and Quantum Information.
Cambridge Univ. Press, 2000. 6
[22] S TEFANO P IRONIO , A NTONIO ACÍN , N ICOLAS B RUNNER , N ICOLAS G ISIN , S ERGE M ASSAR ,
AND VALERIO S CARANI : Device-independent quantum key distribution secure against collective
attacks. New Journal of Physics, 11(4):045021, 2009. [doi:10.1088/1367-2630/11/4/045021,
arXiv:0903.4460] 2
[23] S TEFANO P IRONIO , A NTONIO ACÍN , S ERGE M ASSAR , A NTOINE B OYER DE LA G IRODAY,
D ZMITRY N. M ATSUKEVICH , P ETER M AUNZ , S TEVEN O LMSCHENK , DAVID H AYES , L. L UO ,
T.A. M ANNING , AND C HRISTOPHER M ONROE: Random numbers certified by Bell’s theorem.
Nature, 464(7291):1021–1024, 2010. [doi:10.1038/nature09008, arXiv:0911.3427] 2, 29
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 41
M ATTHEW M C K AGUE
[24] ROBERT R AUSSENDORF AND H ANS J. B RIEGEL: A one-way quantum computer. Physical Review
Letters, 86(22):5188–5191, 2001. [doi:10.1103/PhysRevLett.86.5188, arXiv:quant-ph/0010033] 3,
5
[25] ROBERT R AUSSENDORF, DANIEL E. B ROWNE , AND H ANS J. B RIEGEL: Measurement-
based quantum computation on cluster states. Physical Review A, 68(2):022312, 2003.
[doi:10.1103/PhysRevA.68.022312, arXiv:quant-ph/0301052] 3, 5
[26] B EN W. R EICHARDT, FALK U NGER , AND U MESH VAZIRANI: Classical command of quantum
systems. Nature, 496(7446):456–460, 2013. [doi:10.1038/nature12035] 2, 3, 4, 39
[27] A DI S HAMIR: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146609] 2
[28] W IM VAN DAM , F RÉDÉRIC M AGNIEZ , M ICHELE M OSCA , AND M IKLOS S ANTHA: Self-testing
of universal and fault-tolerant sets of quantum gates. SIAM J. Comput., 37(2):611–629, 2007.
Preliminary version in STOC’00. [doi:10.1137/S0097539702404377, arXiv:quant-ph/9904108] 2
AUTHOR
Matthew McKague
Lecturer
University of Otago, Dunedin, NZ
matthew.mckague otago ac nz
http://www.cs.otago.ac.nz/staffpriv/mckaguem
ABOUT THE AUTHOR
M ATTHEW M C K AGUE is a staff member in the Department of Computer Science at the
University of Otago. He completed his Ph. D. at the Institute for Quantum Computing at
the University of Waterloo under Michele Mosca. He held research positions at the Centre
for Quantum Technologies in Singapore and the Department of Physics at the University
of Otago. His research interests include quantum computing and cryptography.
T HEORY OF C OMPUTING, Volume 12 (3), 2016, pp. 1–42 42