Plaintext
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42
www.theoryofcomputing.org
Classical Verification of Quantum Proofs
Zhengfeng Ji
Received January 30, 2017; Revised March 26, 2018; Published September 15, 2019
Abstract: We present a classical interactive protocol that checks the validity of a quantum
witness state for the local Hamiltonian problem. It follows from this protocol that approxi-
mating the nonlocal value of a multi-player one-round game to inverse polynomial precision
is QMA-hard. Our result makes a connection between the theory of QMA-completeness and
Hamiltonian complexity on one hand and the study of nonlocal games and Bell inequalities
on the other.
ACM Classification: F.1.2, F.1.3
AMS Classification: 68Q10, 68Q12, 81P40, 81P68
Key words and phrases: quantum interactive proofs, local Hamiltonian problem, nonlocal games,
entanglement, Bell inequalities
1 Introduction
The concept of efficient proof verification is of fundamental importance to the theory of computation.
The complexity class NP abstracts the notion of checking written proof strings by a polynomial-time
deterministic verifier. It is hard to overstate the importance of NP and NP-completeness theory [21, 47, 38]
to the development of theoretical computer science in the past several decades.
Interactive models of proof verification were proposed and studied by Babai [7] and Goldwasser,
Micali, and Rackoff [29]. They were generalized to the multiple-prover setting by Ben-Or, Goldwasser,
Kilian and Wigderson [11]. The efforts to understand these interactive proof systems opened the door to
a series of breakthroughs in computational complexity theory (e. g., [48, 64, 8, 6, 5]).
Of particular interest to this paper is the multi-player one-round game, a game theoretical model for
interactive proof verification, first studied by Feige and Lovász [24]. In this model, the verifier samples a
An extended abstract of this paper appeared in the Proceedings of the 48th annual ACM Symposium on Theory of
Computing (STOC’16) [35].
© 2019 Zhengfeng Ji
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2019.v015a005
Z HENGFENG J I
list of questions and sends them to the players and receives answers back from the players in one round.
The players may agree on a particular strategy in advance but are not allowed to communicate with each
other during the game. The verifier decides whether to accept or to reject based on the questions and
answers. We use both the terms of multi-player one-round games and multi-prover one-round interactive
proofs in this paper. A multi-player one-round game is, roughly speaking, a one-round interactive proof
for a fixed input instance and can be specified completely by the representation of both its question
distribution and the truth table of the verifier predicate.
A method called oracularization [27] that enforces the non-adaptive behavior of the players provides
a multi-player-game characterization of NP, in which the questions are bit strings of length logarithmic in
the input length and the answers are strings of a constant number of bits. We emphasize that this is an
exponential savings in the number of bits communicated from the provers to the verifier compared with
the standard method of proof communication in which the prover sends the full proof string to the verifier.
This is one of the reasons behind the unexpected power of multi-prover interactive proof systems [8] and
the possibility of achieving probabilistically checkable proofs [6, 5, 23].
The study of quantum variants of proof verification systems (see, e. g., [41, 43, 72, 73, 33, 18, 32, 2,
26, 15]) provides both a fruitful way to understand proof verification in the context of quantum computing
and an insightful angle to examine unique quantum phenomena such as superposition, entanglement
and nonlocality. Interested readers are referred to the recent review article on this topic by Vidick and
Watrous [71].
A quantum analog of efficient verification of written proofs was proposed by Kitaev [41, 42, 4]. In
this generalization, a quantum witness state plays the role of the written proof and a polynomial-time
quantum computer checks whether the witness state is valid for the input. Kitaev introduces the class
QMA of problems that admit efficiently verifiable quantum proofs. He also establishes the quantum
analog of the Cook-Levin theorem by showing that the local Hamiltonian problem, the natural quantum
version of the constraint satisfaction problems, is complete for QMA. The study of local Hamiltonian
problems, the structure of entanglement in the ground states of local Hamiltonians, and the quantum PCP
conjecture (see, e. g., [2]) form a research direction called Hamiltonian complexity [59, 28].
Quantum interactive proof systems, a model in which a quantum polynomial-time verifier exchanges
quantum messages with an all-powerful prover, were first studied by Kitaev and Watrous [43, 72]. It is
now known that the class of languages expressible by such proof systems, QIP, is the same as its classical
counterpart, IP [33].
In quantum multi-prover interactive proof systems, shared entanglement among the provers plays an
essential role. It is known that, without shared entanglement, or with a limited amount of entanglement,
the collection of languages that have quantum multi-prover interactive proof systems, QMIP, equals
its classical counterpart, MIP [44] (and, hence, also equals NEXP [8]). The classes QMIP∗ and MIP∗ ,
corresponding to the collections of languages that have entangled multi-prover interactive proofs with
quantum and classical messages respectively, are also known to be the same [63]. There is recent
evidence showing that entangled provers may be more powerful than classical provers [26]. But a full
understanding of these two complexity classes is still out of reach.
In this article, we focus on multi-prover one-round games with entangled provers. For a multi-player
one-round game, its classical value is the maximum acceptance probability that classical strategies can
achieve and its nonlocal value is the maximum acceptance probability that entangled players can achieve.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 2
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
In general, the nonlocal value can be strictly larger than the classical value of a multi-player game. It is
pointed out in [18] that this may cause problems in multi-prover interactive proof systems as provers with
shared entanglement may break the soundness condition of a classically sound protocol. One striking
example is given by the so-called magic square game [53, 60], which has nonlocal value one even though
it corresponds to a system of constraints with no classical solution [18]. Strong evidence is also given
in that paper that entanglement between the players may indeed weaken the power of two-player XOR
games.
Several methods have been proposed to control the cheating ability of entangled provers and recover
soundness in certain cases. It is known that approximating the nonlocal value of a multi-player game
to inverse-polynomial precision is NP-hard [40, 31], and therefore at least as hard as approximating
the classical value [27]. Several natural problems arise from the study of nonlocality, including the
binary constraint system game [19], the quantum coloring game [16] and the game corresponding to the
Kochen-Specker sets [45], are shown to be NP-hard in [34]. By proving that the multi-linearity test [8] is
sound against entangled provers, Ito and Vidick proved the containment of NEXP in MIP∗ [32]. This was
later improved to the result that three-player XOR games are NP-hard to approximate even to constant
precision [70].
In this paper, we present a multi-player one-round game for the local Hamiltonian problem in which
the verifier is classical and samples questions of logarithmic size and expects answers of constant size.
As a corollary, the problem of approximating the nonlocal value of a multi-prover one-round game is
QMA-hard, improving the NP-hardness results in prior work. It makes an interesting connection between
the theory of QMA-completeness and Hamiltonian complexity on one hand, and the study of nonlocal
games and Bell inequalities on the other. This also provides an example in which a classical verifier can
design protocols making essential use of the shared entanglement between the provers and expects them
to do things that are impossible for provers without shared entanglement unless NP = QMA.
Our protocol can be thought of as a de-quantization of the Fitzsimons-Vidick protocol [26] of both the
verifier and the messages. The verifier communicates with multiple entangled provers and delegates the
quantum verification procedure to the provers. In this sense, this work is also relevant to the developments
in the delegation of quantum computation and blind quantum computing [14, 3, 63, 25]. Previous articles
usually use a cluster state [62] or EPR states and teleportation to encode quantum computation, while our
approach has the additional freedom to encode quantum data directly among the provers. This allows us
to go from the delegation of quantum computation to the delegation of quantum proof verification.
The main result of this paper is stated in the following theorem.
Theorem 1.1. For any integer r ≥ 4, any promise problem L = (Lyes , Lno ) in QMA, and any instance x of
the problem, there exists an r-player one-round game and real numbers c, s ∈ [0, 1], c − s ≥ 1/ poly(|x|)
such that
1. The description of the game and the numbers c, s can be computed in polynomial time given x as
input.
2. The questions are classical bit strings of length O(log(|x|)).
3. The answers are classical bit strings of length O(1).
4. If x ∈ Lyes , then the nonlocal value of the game is at least c.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 3
Z HENGFENG J I
5. If x ∈ Lno , then the nonlocal value of the game is at most s.
A direct corollary is that approximating the nonlocal value of a multi-player game is QMA-hard.
Corollary 1.2. Given a multi-player one-round game in which the questions are strings of O(log n) bits
and answers are of strings of O(1) bits, it is QMA-hard to approximate the nonlocal value of the game to
inverse polynomial precision.
The same problem for the classical value is obviously in NP. This means that the nonlocal value of
multi-player one-round games is strictly harder to approximate than the classical value unless NP = QMA.
Our result has the following consequence for multi-prover interactive proofs with entangled provers
by scaling up the problem size. It is a slight improvement of the results obtained in [26]. Let QMAEXP
be the collection of problems that have quantum witnesses of exponentially many qubits verifiable by a
quantum exponential-time machine, and let MIP∗ (r,t, c, s) be the class of languages that have r-prover,
t-round interactive proofs with a classical polynomial-time verifier, entangled provers, and completeness
c, soundness s.
Corollary 1.3. For some choices of completeness and soundness c, s and polynomial p(n), with c − s =
Ω(exp(−p(n))),
QMAEXP ⊆ MIP∗ (4, 1, c, s),
and hence
MIP(4, 1, c, s) = MIP ( MIP∗ (4, 1, c, s)
unless NEXP = QMAEXP .
1.1 Techniques and proof overview
The main technical difficulty we face is how a classical verifier can check the quantum witness state
distributed among a number of players. In a one-round game, the only thing that the classical verifier
can collect is some information about the conditional distributions Pr(a | q) for all possible questions
q and answers a. Consider the situation of remote state certification, in which two players A and B
share a quantum√ state ρAB and want to convince the verifier of this fact. If the state ρAB is an EPR state
(|00i + |11i)/ 2, this is possible in some sense by the verifier playing the CHSH game [17] with the
players. The rigidity of the CHSH game [52, 63] implies that if the players win the CHSH game with
almost optimal probability, then the state is close to the EPR state up to local isometries. If the state is
mixed, however, the situation becomes problematic in a very strong sense. Suppose the two players want
to prove that ρAB is the Werner state [74]
(d − φ )I + (dφ − 1) SWAPd
ρW (φ ) = ,
d3 − d
where SWAPd is unitary operator satisfying SWAPd |i, ji = | j, ii for all 0 ≤ i, j ≤ d −1. It is known [74, 9]
that, for some choices of φ , the state is an entangled state, but any prescribed local measurement setting on
A and B performed on the state ρW produces distributions Pr(a | q) that have local hidden variable models.
That is, the distribution can be exactly reproduced by two classical players with shared randomness and
no shared entangled states whatsoever!
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 4
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
It is natural to consider methods from the study of device-independent quantum information processing
or self-testing quantum devices (e. g., [49, 67, 54, 50]). For example, such ideas have successful
applications in achieving the classical command of quantum systems as shown in [63]. A key ingredient
behind such device-independent methods is the rigidity of nonlocal games such as the CHSH game. By
the definition of rigidity, however, the players will
√ essentially share a specific entangled state, such as
the EPR state or the GHZ state (|000i + |111i)/ 2, and perform prescribed measurements on the state.
This seems contradictory to what we need here—the ability to store the quantum witness state distributed
among the players. The quantum witness state is usually an entangled state with complex structures that
are far away from what EPR or GHZ states can represent.
Our solution that resolves the above-mentioned difficulties is to encode the quantum witness state by
a certain stabilizer code and play a new game, which we call the stabilizer game, defined by the stabilizer.
We prove a rigidity theorem for the stabilizer game which roughly states that the only way for the players
to win the game with high probability is to share a correctly encoded state of the stabilizer code, perform
measurements according to the measurement specifications given in the questions, and respond with
the measurement outcome. That is, the stabilizer game we construct provides a device-independent
verification of the encoding of the corresponding stabilizer code. Having both the rigidity property and the
ability to encode quantum data, the stabilizer game serves as an essential tool for our work and may find
other applications in device-independent quantum information processing. For example, in the remote
state certification problem discussed above, although it is impossible for the players to certify the Werner
state ρW , the stabilizer games provide a way to certify an encoded Werner state using a stabilizer code.
In [26], quantum error correcting codes are also employed in an essential way. The intuition is that, by
the quantum error correction property, there will be only one qubit of the player that can pass the encoding
check of the error correcting code once the rest of the players respond with the correct qubit. The protocol
using quantum error correcting codes proposed in [26] can be thought of as a quantum analog of the
oracularization technique [27]—the classical oracularization is based on the classical repetition code in
this perspective. One crucial difference between the classical and quantum oracularization techniques
is that, in the quantum setting, the referee has to query all pairs of qubits in order to be able to argue
about the commutativity between observables on different qubits. This is obviously not necessary in the
classical setting.
In our case, the stabilizer codes have the same effects but also have an important additional use.
Namely, they are responsible for enforcing the players to measure their systems according to the measure-
ment specifications they receive. Instead of using the decoding circuit of the code, we measure the logical
X, Z operators on the encoded state. As a result, our proof directly applies to quantum error detecting
codes as well.
The proof of rigidity for stabilizer games consists of two steps. In the first step, an idea motivated
by the CHSH game is employed and we introduce the special-player stabilizer game. Using similar
techniques for proving the rigidity of the CHSH game, we establish a pair of anti-commuting reflections
in the strategy for the special player. Then, a quantity called consistency is used to promote this partial
rigidity of the special-player stabilizer game to the full rigidity property of the stabilizer game itself.
Consistency and another state dependent distance measure of two quantum measurements appeared
before in the analysis of nonlocal games and are intensively used in many proofs of this paper.
We then consider the multi-qubit stabilizer game, the nonlocal game version of the stabilizer encoding
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 5
Z HENGFENG J I
check in [26]. We prove a partial rigidity theorem for the multi-qubit stabilizer game. This is achieved by
establishing the approximate commutativity of reflections corresponding to measurement specifications
on different qubits, the proof of which uses the consistency property again in an essential way. Finally,
the multi-qubit stabilizer game is performed in the game for the local Hamiltonian problem with high
probability to regularize the behavior of the players.
Two additional difficulties arise as the verifier only has limited access to the quantum witness state.
First, since the verifier can only enforce Pauli measurements on the witness state, the measurement of the
energy of the local Hamiltonian uses Pauli measurements only. This will be less efficient than having the
quantum data and measuring directly the POVM corresponding to each term of the Hamiltonian as is
done in [26], but there will only be a constant overhead compared to the direct measurement approach.
Second, for convenience, we work with stabilizer codes whose generators are the tensor products
of Pauli I, X, Z operators. Alternatively, one may design an extended version of the stabilizer game
using ideas from the extended CHSH game proposed in [63] to include Pauli Y operators in the problem.
The current form of the stabilizer game is, however, much easier to analyze. As a result, by the rigidity
property, the verifier only has access to Pauli X, Z measurements on the quantum witness state. This
requires that the Hamiltonian in the local Hamiltonian problem has terms in the real linear span of tensor
products of I, X and Z operators. Fortunately, as observed in [13], such a restricted version of the local
Hamiltonian problem remains QMA-complete.
1.2 Follow-up work and open problems
There have been several interesting follow-up papers after our manuscript appeared on arXiv. Natarajan
and Vidick designed a constant-soundness interactive protocol for the local Hamiltonian problem [56] and
later improved their result to achieve robust self-testing for multi-qubit states [57]. The QMA-hardness of
nonlocal games has been improved by the author to QMIP∗ -completeness (and, hence, NEXP-hardness)
in [36].
We briefly mention several related open problems. This paper and the improved results in [36] study
the complexity of approximating the nonlocal value to inverse polynomial precision. A natural question
to ask is how hard is the constant approximation problem for nonlocal game values. Similarly, one major
weakness of our result for the multi-prover interactive proofs with entangled provers in Corollary 1.3 is
the exponentially small gap between the completeness and soundness parameters. It is an intriguing and
challenging problem to improve this and show, for example, QMAEXP is contained in MIP∗ .
It is also an interesting question to understand the relationship between the proof checking variant of
the quantum PCP conjecture, which asks whether there is a format to encode quantum proofs to allow
probabilistic checking, and the multi-player game variant, which asks whether a constant approximation
of the nonlocal value is QMA-hard. Our result already demonstrates a connection between Hamiltonian
complexity and nonlocal games. But the constant gap will be washed out by the polynomial overhead of
the transformation.
1.3 Organization
The rest of the paper is organized as follows. In Section 2, we introduce notation and related concepts
used in this paper. Stabilizer games are introduced and analyzed in Section 3. A nonlocal game for the
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 6
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
local Hamiltonian problem is given and analyzed in Section 4.
2 Preliminaries
2.1 Concepts and notation
We use calligraphic H to denote Hilbert spaces, and D(H), L(H), Herm(H), Pos(H) to denote the set of
density operators, bounded linear operators, Hermitian operators and positive semidefinite operators on
H. The two-dimensional Hilbert spaces C2 corresponding to a qubit are denoted by B. For two Hermitian
√ M, N ∈ Herm(H), we write M ≤ N to mean N − M ∈ Pos(H). For a matrix M, |M| is defined
operators
to be M † M. For a string x, |x| denotes its length. For a positive integer k, [k] is the abbreviation of
the set {1, 2, . . . , k}. For two complex numbers x, y, we use x ≈ε y as a shorthand for |x − y| ≤ O(ε).
Two-qubit unitary gates CNOT and SWAP are defined as
CNOT |i, ji = |ii|i ⊕ ji, SWAP |i, ji = | j, ii,
for i, j ∈ {0, 1}.
Let ρ ∈ D(H) be a quantum state on H. For operators M ∈ L(H), N0 , N1 ∈ L(H, K), introduce the
following notation:
hN0 , N1 i = tr(N0† N1 ), (2.1a)
trρ (M) = tr(Mρ), (2.1b)
hN0 , N1 iρ = trρ (N0† N1 ), (2.1c)
q
kN0 kρ = hN0 , N0 iρ . (2.1d)
It is straightforward to verify that h·, ·iρ is a semi-inner-product, k·kρ is a seminorm and they become an
inner product and a norm, respectively, when ρ is a full-rank state. In particular, the Cauchy-Schwarz
inequality holds
hN0 , N1 iρ ≤ kN0 kρ kN1 kρ ,
or more explicitly,
h i1/2
trρ (N0† N1 ) ≤ trρ (N0† N0 ) trρ (N1† N1 ) .
For a state ρ ∈ D(HA ⊗ HB ), and an operator M ∈ L(HA ), we may also write trρ (M) even though the
state ρ and the operator M do not act on the same space. In this case, it is understood that trρ (M) = trρA (M)
where ρA is the reduced state of ρ on system A. This is one reason that makes trρ (·) easy to use as it is
not necessary to specify the correct reduced state explicitly all the time.
A quantum measurement is described by a collection M = {M a } of measurement operators. These
are operators acting on the state space H of the system being measured. In this paper, we always use
superscript to index the measurement outcomes and subscript to index different quantum measurements.
The measurement operators satisfy the completeness equation
∑(Ma )† Ma = I.
a
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 7
Z HENGFENG J I
If the state of the system before the measurement is ρ ∈ D(H), the probability that outcome a occurs is
given by
tr (M a )† M a ρ = kM a k2ρ ,
and the post-measurement state of the system is
M a ρ(M a )†
.
kM a k2ρ
A positive operator valued measure (POVM) is a collection of positive semidefinite operators {M a },
such that
∑ Ma = I.
a
POVMs give descriptions of quantum measurements when the post-measurement state is not important in
the analysis. The probability that the measurement has outcome a on state ρ is given by trρ (M a ).
A projective quantum measurement is described by {M a } where each operator M a is a projection
and ∑a M a = I. A reflection R is a Hermitian matrix squared to I. It naturally describes a two-outcome
projective quantum measurement {Ra } where
I + (−1)a R
Ra = ,
2
for a = 0, 1. The Pauli operators
1 0 0 1 0 −i 1 0
I= , X= , Y= , Z= ,
0 1 1 0 i 0 0 −1
are examples of 2-by-2 reflections. We also use σ0 , σ1 , σ2 , σ3 to represent the four Pauli operators. A
multi-qubit Pauli operator is of XZ-form if each tensor factor is one of I, X and Z. A Hermitian matrix H
is of XZ-form if it is in the real linear span of XZ-form Pauli operators.
Define X 0 and Z 0 as
X +Z X −Z
X0 = √ , Z0 = √ , (2.2)
2 2
and W as
W = cos(π/8)X + sin(π/8)Z. (2.3)
It is easy to verify that W is a reflection and
X = W X 0W, X 0 = W XW,
Z = W Z 0W, Z 0 = W ZW.
That is, under the conjugation of W , X 0 and Z 0 are mapped to X and Z respectively, and vice versa. The
reflections X, Z, X 0 , Z 0 and W are illustrated in Figure 1. They play an important role in the CHSH game
and the stabilizer games introduced in this paper.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 8
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
Z
X0
W
X π/8
Z0
Figure 1: Reflections X, Z, X 0 , Z 0 , W in the x, z-plane of the Bloch sphere.
2.2 Nonlocal games
A multi-player one-round game involves two or more players and a verifier who communicates with the
players classically in one round. The verifier samples questions and sends them out to the players and
expects to receive answers back. He then decides whether to accept or reject based on the questions and
answers. The players are allowed to agree on a strategy before the game starts, but cannot communicate
with each other during the game.
Let there be r players, (1), (2), . . . , (r). Let Γ(i) be a finite set of questions for player (i) and Λ(i)
be a finite set of possible answers from player (i). An r-player game is defined by a distribution π
over ∏ri=1 Γ(i) and a function V : ∏ri=1 Λ(i) × ∏ri=1 Γ(i) → [0, 1], specifying the acceptance probability.
By a convexity argument, it suffices to consider the strategy of classical players described by functions
f (i) : Γ(i) → Λ(i) . The value of the strategy is the acceptance probability
ω = E V (a(q), q),
q∼π
for q = (q1 , q2 , . . . , qr ) distributed according to π and a(q) = f (1) (q1 ), f (2) (q2 ), . . . , f (r) (qr ) . The
classical value of the game is the maximum of the values of all classical strategies. An XOR game is a
multi-player game in which each player answers a bit ai and the verifier accepts or rejects depending only
on the parity of ri=1 ai . More precisely, there is a function V̂ : {0, 1} × ∏ri=1 Γ(i) → [0, 1] such that
L
r
M
V (a, q) = V̂ ai , q ,
i=1
for all q ∈ ∏ri=1 Γ(i) , a ∈ ∏ri=1 Λ(i) . In most of the games considered in this paper, the verifier accepts or
rejects only depending on the parity of some, not all, of the answer bits. We call them generalized XOR
games.
In a nonlocal game, the players are allowed to share an arbitrary entangled state before the game starts.
A quantum strategy S for the nonlocal game is described by the shared state ρ, and the measurements
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 9
Z HENGFENG J I
(i)
Mqi that player (i) performs when the question is qi ∈ Γ(i) . The value of the strategy is defined as
r
∗
O (i),ai
ω (S) = E ∑ trρ Mqi V (a, q) ,
q∼π a
i=1
for a = (a1 , a2 , . . . , ar ) and q = (q1 , q2 , . . . , qr ). The nonlocal value of the game is the supremum of the
values of all quantum strategies.
The CHSH game [17] is arguably one of the most important nonlocal games. It arises from the
study of fundamental questions in quantum mechanics such as entanglement and nonlocality via Bell
inequalities [10]. The CHSH game is a two-player XOR game. The verifier samples two bits q1 and q2
independently and uniformly at random, sends q1 to the first player and q2 to the second player. The
verifier accepts if and only if two answer bits a1 and a2 satisfy a1 ⊕ a2 = q1 ∧ √q2 . The classical value of
∗
the game is 3/4 = 0.75 and the nonlocal value of the game is ωCHSH = (2 + 2)/4 ≈ 0.85 [66]. √
In an optimal strategy for the CHSH game, the players share an EPR state (|00i + |11i)/ 2, and the
first player obtains the answer by measuring X (or Z) if the question is 0 (or 1 respectively), while the
second player measures X 0 (or Z 0 ) in Equation (2.2) if the question is 0 (or 1). The rigidity property of the
CHSH game roughly states that this is essentially the only strategy for the players to achieve the nonlocal
value, up to local isometries. Furthermore, any strategy that has a value close to the game value must
be close to this optimal strategy in some sense. Rigidity of the CHSH game and other nonlocal games
has found interesting applications in certifiable randomness generation (e. g., [20, 61, 68, 55]), device-
independent quantum cryptography (e. g., [1, 69, 55]) and classical command of quantum systems [63].
2.3 Quantum proofs and local Hamiltonian problems
The idea of efficient proof verification of NP has a natural quantum generalization given in the following
definition.
Definition 2.1. The complexity class QMA is the set of promise problems L = (Lyes , Lno ) such that there
is a polynomial p(·) and a quantum polynomial-time verifier V , and
• Completeness. If x ∈ Lyes , there exists a state |ψi of p(|x|) qubits such that
2
Pr V accepts |xi ⊗ |ψi ≥ ,
3
• Soundness. If x ∈ Lno , then for all state |ψi of p(|x|) qubits,
1
Pr V accepts |xi ⊗ |ψi ≤ .
3
Definition 2.2 (Local Hamiltonian Problem). An instance of the k-local Hamiltonian problem of n-qubits
is described by the tuple (H, a, b), where the Hamiltonian H = ∑mj=1 H j and each term H j acts non-
trivially on at most k qubits, H j is positive semidefinite and H j ≤ 1, a, b ∈ R are numbers satisfying
b − a ≥ 1/ poly(n). Let the ground state energy of the Hamiltonian H be λmin = minρ∈D hH, ρi. In the
k-local Hamiltonian problem, (H, a, b) is a yes-instance if λmin ≤ am and a no-instance if λmin ≥ bm.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 10
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
The quantum analog of the Cook-Levin theorem by Kitaev states that the k-local Hamiltonian problem
is QMA-complete for k ≥ 5 [41, 4]. This was later improved to 2-local and more physical Hamiltonians
in a series of articles (see e. g., [39, 58, 22]).
2.4 Quantum error correction and stabilizer formalism
A quantum error correcting code encodes a number of qubits, called the logical qubits, into a larger
number of physical qubits with the aim of protecting the quantum information in the logical qubits from
certain types of noise.
The stabilizer formalism provides a convenient language and a great number of examples of quantum
error correcting codes. We present several relevant definitions and facts about stabilizer codes and refer
the reader to the thesis of Gottesman [30] for more details. Let Pr be the group generated by the r-fold
tensor product of Pauli operators
r
Pr = eiφ
O
Pj , for φ ∈ {0, π/2, π, 3π/2}, Pj ∈ {I, X,Y, Z} .
j=1
A stabilizer S is an abelian subgroup of Pr not containing −I ⊗r . The stabilizer provides a succinct
description of a subspace of (C2 )⊗r , the simultaneous +1-eigenspace of the operators in S. This subspace
is called the code space of the stabilizer. A set of operators in S is called the a set of generators of S if
they generate the group S.
The weight of an operator in Pr is the number of non-identity tensor factors in it. Let C(S) be the
centralizer of S in Pr , the set of operators in Pr that commutes with S. The distance of the stabilizer
code is d if there is no operator of weight less than d in C(S) − S. The logical X and Z operators LX and
LZ are a pair of anti-commuting operators in C(S) − S.
As a simple example, the operators XX and ZZ generate a stabilizer for the EPR state. The famous
five-qubit code [46, 12] has a stabilizer representation given in Figure 2a. The five-qubit code encodes
one logical qubit in five physical qubits and has distance 3. The logical X and Z operators are X ⊗5 and
Z ⊗5 . This will be the stabilizer code we use most of the time as an example. Operators X ⊗4 and Z ⊗4
generate the stabilizer for the four-qubit quantum error detecting code. It has distance 2 and encodes
two qubits. The operators XXII and ZIZI form a pair of anti-commuting operators and can serve as the
logical X and Z operators. There is another pair of logical operators for the other encoded qubit that we
do not use.
2.5 State-dependent distance measures of quantum measurements
We introduce a distance measure and a consistency measure of quantum measurements that will be helpful
in our treatment of nonlocal games. They grew out of the study of nonlocal games [31, 32, 70] and may
be useful in more general contexts. A common feature of them is that they are both state-dependent.
A general question that one usually faces is what the consequences are if a measurement {M1a } is
used in place of {M0a } in a nonlocal game by one of the players. Will it change the overall analysis
significantly? More concretely, suppose that the state of a joint quantum system HA and HB is ρ and that
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 11
Z HENGFENG J I
{M0a }, {M1a } are quantum measurements on system A. The post-measurement states are
ρi = ∑ |ai ha| ⊗ Mia ρ(Mia )† , (2.4)
a
for i = 0, 1, respectively, depending on which measurement is performed. By the monotonicity of the trace
distance, the difference will be bounded by Dtr (ρ0 , ρ1 ) no matter what operation follows the measurement.
In particular, in a nonlocal game, if Bob measures on his system HB and then the verifier makes the
decision, the acceptance probabilities will differ by at most Dtr (ρ0 , ρ1 ).
The quantity defined next provides a way to bound the distance Dtr (ρ0 , ρ1 ).
Definition 2.3. For two quantum measurements Mi = Mia with i = 0, 1 that have the same set of
possible outcomes, define
h i1/2
dρ (M0 , M1 ) = ∑ kM0a − M1a k2ρ . (2.5)
a
More explicitly,
1/2
a † a
dρ (M0 , M1 ) = 2 − 2 Re ∑ trρ (M0 ) M1 . (2.6)
a
Lemma 2.4. Let Mi = Mia for i = 0, 1 be two quantum measurements with the same set of possible
outcomes, and ρi be the post-measurement states in Equation (2.4). Then
Dtr (ρ0 , ρ1 ) ≤ dρ (M0 , M1 ).
Proof. Let |ψi ∈ HA ⊗ HB ⊗ HC be a purification of ρ. Then
Dtr (ρ0 , ρ1 ) ≤ Dtr ∑ |ai ⊗ (M0a |ψi), ∑ |ai ⊗ (M1a |ψi)
a a
2 1/2
a † a
= 1 − ∑hψ|(M0 ) M1 |ψi
a
1/2
a † a
≤ 2 1 − ∑hψ|(M0 ) M1 |ψi
a
1/2
≤ 2 − 2 Re ∑ trρ (M0a )† M1a
a
= dρ (M0 , M1 ).
The first inequality follows from the monotonicity of the trace distance. The second line follows by a
direct calculation of the trace distance for two pure states. The third line is from 1 − x2 ≤ 2(1 − x) for
x ∈ [0, 1].
As discussed above, a direct corollary of the above lemma is that when measurement M0 is replaced
with M1 in a strategy for a nonlocal game using shared state ρ, the acceptance probability change by
at most dρ (M0 , M1 ). This claim works for all types of quantum measurements including the general
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 12
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
quantum measurement, POVMs, projective quantum measurements and binary projective measurements
described by reflections.
For Mi = Mia , i = 0, 1, describing two POVMs that satisfy ∑a Mia = I, we define the corresponding
distance as
dρ (M0 , M1 ) = inf a dρ (N0 , N1 ),
Ni ={Ni }
where the infimum is taken over all possible measurement operators Nia such that Mia = (Nia )† Nia . The
inclusion of all possible measurement operators in the definition makes
a it technically easier to establish
upper bounds on the distance. For projective measurements Mi = Mi , define
1/2
dρ (M0 , M1 ) = 2 − 2 Re ∑ trρ M0a M1a .
a
Finally, for reflections R0 , R1 , let
I + (−1)a Ri
Rai =
2
be the projective measurement operators corresponding to Ri . Define
dρ (R0 , R1 ) = dρ ({Ra0 }, {Ra1 })
I + (−1)a R0 I + (−1)a R1 1/2
= 2 − 2 Re ∑ trρ
a 2 2
1/2
= 1 − Re trρ R0 R1 .
It is easy to verify that dρ satisfies the triangle inequality.
Lemma 2.5. Let M0 , M1 , M2 be three measurements on state ρ. Then
dρ (M0 , M2 ) ≤ dρ (M0 , M1 ) + dρ (M1 , M2 ).
The next important quantity measures the consistency of two quantum measurements.
H
a
Definition 2.6. Let ρ ∈ D(H A ⊗ B ) be the shared state between system A and B, let M = M ,
N = N a be POVMs on system A and B respectively having the same set of possible outcomes. Define
the consistency of M, N on state ρ as
Cρ (M, N) = ∑ trρ (M a ⊗ N a ). (2.7)
a
M and N are called ε-consistent on state ρ if Cρ (M, N) ≥ 1 − ε.
For two reflections R, S, let {Ra }, {Sa } be their corresponding projective measurements. Define
1 + trρ (R ⊗ S)
Cρ (R, S) = Cρ ({Ra }, {Sa }) = . (2.8)
2
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 13
Z HENGFENG J I
The condition trρ (R ⊗ S) ≈ε 1, or equivalently, R, S are O(ε)-consistent on ρ, can be thought of as a
quantitative way of saying that ρ is approximately stabilized by R ⊗ S.
The consistency of measurements puts strong structural constraints on the strategies of nonlocal
games. It will be a key ingredient in our proof of the main result. In the following lemma, it is proved that
if two measurements M0 , M1 are consistent with the same measurement N, then M0 , M1 must be close to
each other in terms of the distance dρ .
Lemma 2.7. Let ρ∈ D(HA ⊗ HB ) be a state on system A and B. Let Mi = Mia for i = 0, 1 be POVMs
on system A, N = N a be a POVM on system B. If
Cρ (Mi , N) ≥ 1 − ε,
for i = 0, 1, then √
dρ (M0 , M1 ) ≤ O( ε).
Proof. First prove that
a
p a p a
∑ trρ 1 − M0 1 − M1 ⊗ N ≈ε 0. (2.9)
a
By the Cauchy-Schwarz inequality, the absolute value of the left hand side is at most
s
p a 2 p a 2
a a
∑ trρ 1 − M0 ⊗ N trρ 1 − M1 ⊗ N
a
q
≤∑ trρ 1 − M0a ⊗ N a trρ 1 − M1a ⊗ N a
a
r
≤ ∑ trρ 1 − M0a ⊗ N a ∑ trρ 1 − M1a ⊗ N a
a a
≤ ε,
√
where the first inequality follows from the fact that (1 − x)2 ≤ 1 − x for x ∈ [0, 1], the second inequality
is another Cauchy-Schwarz inequality and the last inequality follows from the condition that Cρ (Mi , N) ≥
1 − ε.
Similarly, by using the Cauchy-Schwarz inequality twice, we have
a
p ap a
∑ ρtr M 0 M 1 ⊗ 1 − N ≈ε 0. (2.10)
a
Adding Equations (2.9) and (2.10) gives
a a
p ap a p a p a
∑ trρ M0 M1 ≈ε ∑ trρ M0 ⊗ N + ∑ trρ M1 ⊗ N − 1
a a a
≈ε 1 + 1 − 1 = 1.
The lemma follows by the definition of dρ for POVMs.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 14
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
In the analysis, it is useful to have a quantity characterizing the approximate commutativity of two
projective measurements M = {M a } and N = {N a } on a state ρ. The quantity we choose is
∑ k[Ma , N a ]k2ρ .
a
For reflections R, S, let {Ra } and {Sa } be the projective measurements corresponding to R and S
respectively. The commutativity of these two measurements on state ρ is
I + (−1)a R I + (−1)a S 2
a a 2
∑ k[R , S ]kρ = ∑ 2
,
2
a∈{0,1} a∈{0,1} ρ
1
= k[R, S]k2ρ .
8
For this reason, k[R, S]k2ρ equivalently serves as a bound on the approximate commutativity of the two
projective measurements defined by R, S.
3 Stabilizer games and rigidity
3.1 CHSH game revisited
Before introducing stabilizer games, it is beneficial to√revisit the CHSH game in the stabilizer formalism.
Recall that the EPR state |Φi = (|00i + |11i)/ 2 is a stabilizer state defined by two generators
g1 = XX and g2 = ZZ, and the eigenstate of eigenvalue 2 of the operator g1 + g2 . If a verifier has trusted
measuring devices, it suffices to perform the projective measurements associated with the reflections
g1 , g2 to check whether the state is an EPR state. However, this simple measurement setting does not
correspond to any non-trivial schemes that allow device-independent certification of the EPR state.
In the CHSH game, one of the two players is asked to measure her share of |Φi with X, Z, while the
other is asked to measure X 0 , Z 0 in Equation (2.2), the π/4 rotated versions of X, Z. This motivates us
to consider the generators g01 = XX 0 and g02 = ZZ 0 . By the conjugation relation of X, Z and X 0 , Z 0 , they
generate a stabilizer for the state |Φ0 i = I ⊗W |Φi and
2
Φ0 ∑ g0i Φ0 = 2. (3.1)
i=1
Expanding X 0 and Z 0 in g01 and g02 using X and Z gives four operators
h1 = XX, h2 = XZ, h3 = ZX, h4 = −ZZ, (3.2)
√ 0 √ 0
such that h1 + h2 = 2g1 and h3 + h4 = 2g2 . The four operators hi in Equation (3.2) recover exactly
the CHSH game by encoding the Pauli operators X, Z in hi as questions 0, 1 and the sign ±1 of hi as the
expected parity of answers. Equation (3.1) becomes
4 √
Φ0 ∑ hi Φ0 = 2 2,
i=1
√
which is an explanation of the 2 quantum advantage in the CHSH game.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 15
Z HENGFENG J I
3.2 Special-player stabilizer game
In this section, we introduce stabilizer games with a special player. The construction works with any
non-trivial stabilizer code that has a set of generators all in the tensor product form of I, X, Z.
Consider the generators of the stabilizer group for the five-qubit quantum code in Figure 2a. Its code
space is the two-dimensional eigenspace of eigenvalue 4 of the operator ∑4j=1 g j , where the g j operators
are defined in Figure 2a.
Name Operator Name Operator
g1 I XZ ZX g01 I X Z ZX 0
g2 X I XZZ g02 X I X Z Z0
g3 ZX I X Z g03 ZX I X Z 0
g4 Z ZX I X g04 Z ZX I X 0
(a) Standard generators (b) Generators with the last qubit rotated.
Figure 2: Stabilizer generators for the five-qubit code.
Motivated by the CHSH game, we apply the π/4-trick to the last column of the four generators in
Figure 2a. That is, we replace X and Z in the last column with X 0 and Z 0 in Equation (2.2). This gives
us another set of generators, as in Figure 2b, which generates the stabilizer for the five-qubit code with
the last qubit rotated by the single-qubit unitary W in Equation (2.3). If |ψi is in the code space of the
five-qubit code, the state
|ψ 0 i = (I ⊗W )|ψi (3.3)
is in the eigenspace of ∑4j=1 g0j with eigenvalue 4.
Expanding the primed X, Z operators in each of the generators in Figure 2b into X, Z, we get a set of
eight operators h j as in Figure 3a. For state |ψ 0 i in Equation (3.3),
8 √
ψ 0 ∑ h j ψ 0 = 4 2. (3.4)
j=1
The table in Figure 3b is obtained by translating the operators I, X, Z in Figure 3a to the questions in
the alphabet of ∗, 0, 1, 2, 3. The I operator is always translated to ∗, which denotes a null question. The
verifier will not send anything to the player and does not expect any answers if the question is the null
question ∗. For convenience, we sometimes assume that the verifier will replace ∗ with either 0 or 1 as
the question and ignore the answers corresponding to this question. The operators X, Z are translated to
0, 1 respectively in the first four columns and to 2, 3 respectively in the last column. One can of course
also use 0, 1 in the last column and the change is only for later convenience. Finally, the parity column is
read off from the ±1 signs in the hi operators.
The table in Figure 3b specifies a five-player game in Figure 4 called the Special-Player Stabilizer
Game. In the game, the verifier randomly selects four players each time, asks a question encoded with a
single bit and expects a single bit answer. He accepts or rejects depending on the parity of the answers
received. The fifth player is special because of the π/4-rotation applied on the fifth column of the
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 16
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
Name Operator Parity Question
h1 I X Z ZX 0 ∗ 0 1 1 2
h2 I XZZZ 0 ∗ 0 1 1 3
h3 X I X ZX 0 0 ∗ 0 1 2
h4 −X I X Z Z 1 0 ∗ 0 1 3
h5 ZX I XX 0 1 0 ∗ 0 2
h6 −ZX I X Z 1 1 0 ∗ 0 3
h7 Z ZX I X 0 1 1 0 ∗ 2
h8 Z ZX I Z 0 1 1 0 ∗ 3
(a) Eight operators obtained from Figure 2b. (b) The table for the game with a special player.
Figure 3: Translation from measurement operators to game specifications.
stabilizer generators. This breaks the translation invariance of the five-qubit code and, in the honest
strategy, the fifth player performs differently from other players.
Special-Player Stabilizer Game
Let s1 , . . . , s8 be the eight entries in the parity column of Figure 3b and let w j = (w j,i ) be the
j-th row of the question column. The verifier does the following:
1. Select an index j ∈ [8] uniformly at random.
2. For i ∈ [5], send w j,i in Figure 3b to the player (i) if w j,i is not ∗, the null question.
3. Receive a bit a(i) from player (i) if she was asked a question.
L (i)
4. Accept if and only if the parity of the answers i a equals s j .
Figure 4: Special-player stabilizer game for the five-qubit code. The fifth player is the special player.
It turns out that the special-player stabilizer game in Figure 4 has nonlocal value
√
∗ 2+ 2
ωSPS = , (3.5)
4
the same as that of the CHSH game. The following strategy achieves the value. The five players share
the state |ψ 0 i as in Equation (3.3) and measure X (or Z) if the question is even (or odd, respectively) and
reply with the outcome. Let h j,i be the i-th Pauli operator of h j . The value this strategy achieves is
N5
1 + (−1)s j hψ 0 |
0
∗ i=1 h j,i |ψ i
ωSPS = E
j 2 (3.6)
0 0
1 + E j hψ | h j |ψ i
= ,
2
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 17
Z HENGFENG J I
which gives the desired value using Equation (3.4). It is beneficial to restate the above optimal strategy
using |ψi instead of |ψ 0 i. By the conjugation relation between X, Z and X 0 and Z 0 , the fifth player
essentially measures X 0 and Z 0 on the state |ψi in the code space when the question is 2, 3 respectively. If
we think of questions 0, 1, 2, 3 as measurement specifications of X, Z, X 0 , Z 0 , then players who honestly
follow the measurement instructions on an encoded state have acceptance probability ωSPS ∗ . We mention
without proof that the classical value of the game is 3/4, again
√ the same as that of the CHSH game.
We have seen a strategy for the game with value (2 + 2)/4. The fact that this value is optimal is
given in the following theorem. The theorem also proves an important structural result about strategies
that almost achieve the nonlocal value of the game. Namely, the special player (the fifth player) must
measure honestly the X 0 and Z 0 measurements up to an isometry. It is a partial rigidity property of the
special-player stabilizer games. It will be technically convenient to apply Naimark’s theorem and assume
without loss of generality that the measurement operators considered in this paper are projective and have
the same rank. By this assumption, it suffices to consider players that use traceless reflections in their
strategies.
(i)
Theorem 3.1. Let S = ρ, Rw be a strategy for the special-player stabilizer game in Figure 4 for
(i)
the five-qubit code, where ρ is the state shared between the players before the game starts and Rw
is the traceless reflection on Hilbert space Hi describing the projective measurements the player (i)
performs when receiving question w ∈ {0, 1, 2, 3}. Then the value of the strategy S is at most ωSPS
∗ given
∗
in Equation (3.5). Furthermore, if the value is at least ωSPS − ε, then there exists a unitary operator
(5)
V ∈ L(H5 , B ⊗ Ĥ5 ) such that R3 = V † (Z ⊗ I)V , and
(5) √
dρ R2 ,V † (X ⊗ I)V ≤ O( ε).
We note that some previous papers use different distance measures for measurements in the statement
of rigidity theorem. For example, the quantity k(R − S) ⊗ I|ψik is used in [63] for reflections R, S on
state |ψi. It is easy to verify that this is the same as our distance measure dρ (R, S) up to a constant for
ρ = |ψihψ|.
The proof of the above theorem relies on the following lemmas.
Lemma 3.2 (Jordan’s Lemma [37]). For any two reflections R0 , R1 acting on a finite dimensional Hilbert
space H, there exists a decomposition of H into orthogonal one- and two-dimensional subspaces invariant
under both R0 and R1 .
Lemma 3.3. Let R be a reflection and H be a Hermitian matrix. Then
trρ (R ⊗ H) ≤ trρ |H| .
Proof. We first prove that
trρ (R ⊗ H) ≤ trρ |H| .
Let H + and H − be the positive and negative part of H = H + − H − for positive semidefinite H + and H − .
The claim follows by a direct calculation
trρ (R ⊗ H) − trρ |H|
= trρ (R ⊗ (H + − H − )) − trρ (I ⊗ (H + + H − ))
= − trρ ((I − R) ⊗ H + ) − trρ ((I + R) ⊗ H − ) ≤ 0.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 18
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
A similar argument establishes
trρ (R ⊗ H) ≥ − trρ |H| ,
which completes the proof.
Lemma 3.4. For θl ∈ [0, π], Cl = cos θl , Sl = sin θl , and any probability distribution over l, if
p 2
E 1 +Cl − 1 ≤ ε,
l
then
E Sl ≥ 1 − O(ε).
l
√
Proof. Let εl be ( 1 +Cl − 1)2 . Then El εl ≤ ε. For each l, εl ≤ 1. We claim that for all l, Sl ≥ 1 − 9εl .
This will obviously finish the proof.
As
√ √ √
−2 εl ≤ Cl = εl ± 2 εl ≤ 3 εl ,
it follows that Cl2 ≤ 9εl . If εl ≥ 1/9, the claim is trivial since θl ∈ [0, π] and Sl ≥ 0. Otherwise,
q p
Sl = 1 −Cl2 ≥ 1 − 9εl ≥ 1 − 9εl .
Proof of Theorem 3.1. We first give an expression of the game value for the strategy S. For each operator
h j in Figure 3a, define h j (S) as the operator obtained by substituting the X, Z operators in h j with the
players’ corresponding reflections in the strategy S. That is
5
O (i)
h j (S) = (−1)s j Rw j,i ,
i=1
(i)
where s j , w j,i are defined in Figure 4 and R∗ is defined to be I. Following similar steps as in Equation (3.6),
the value of S is computed as
1 + E j trρ (h j (S))
ω ∗ (S) = .
2
Consider four matrices
(5) (5)
(2) (3) (4) R2 + R3
∆1 (S) = I ⊗ R0 ⊗ R1 ⊗ R1 ⊗ I − I ⊗4 ⊗ √ , (3.7a)
2
(5) (5)
(1) (3) (4) ⊗4 R2 − R3
∆2 (S) = R0 ⊗ I ⊗ R0 ⊗ R1 ⊗ I − I ⊗ √ , (3.7b)
2
(5) (5)
(1) (2) (4) R2 − R3
∆3 (S) = R1 ⊗ R0 ⊗ I ⊗ R0 ⊗ I − I ⊗4 ⊗ √ , (3.7c)
2
(5) (5)
(1) (2) (3) ⊗4 R2 + R3
∆4 (S) = R1 ⊗ R1 ⊗ R0 ⊗ I ⊗ I − I ⊗ √ . (3.7d)
2
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 19
Z HENGFENG J I
In the following, we write them as ∆l and hide their dependence on the strategy S when there is no
ambiguity. The sum-of-squares of the four matrices is
4 √
∑ ∆2l = 8I − 2 ∑ h j (S).
l=1 j
This gives the following expression for the game value
√ √
∗ 1 8 2 − 2 ∑4l=1 trρ (∆2l )
ω (S) = + ,
2 32
∗ is obvious. It also implies that for any strategy S having value at least
from which the optimality of ωSPS
∗ − ε,
ωSPS
4
trρ (∆21 ) ≤ ∑ trρ (∆2l ) ≤ O(ε). (3.8)
l=1
We remark that the definition of the matrices ∆l and the sum of square conditions are motivated by similar
analysis for the CHSH rigidity in [63] and are generalized here to the four-player stabilizer game.
(5) (5)
For simplicity, let R2 and R3 be shorthand for R2 and R3 for the remainder of the proof. Following
a similar truncation argument as in [63], we may assume without loss of generality that the underlying
Hilbert spaces of the players are finite dimensional so that Jordan’s Lemma applies. By Jordan’s lemma,
one obtains simultaneous 2-by-2 block diagonalizations of R2 and R3 such that each 2-by-2 block is a
reflection having both ±1 eigenvalues. Hence, there is a unitary operator V ∈ L(H5 , B ⊗ Ĥ5 ) such that
R3 = V † (Z ⊗ I)V,
and
Cl
† Sl
R2 = V ∑ ⊗ |li hl| V,
l
Sl −Cl
where Cl = cos θl , Sl = sin θl for θl ∈ [0, π] and l is the index of the two-dimensional invariant subspaces
obtained by Jordan’s lemma.
Substituting the expression for R2 and R3 in Equation (3.8),
1 √
O(ε) ≥ trρ (∆21 ) = 2 + trρ (R2 R3 + R3 R2 ) + 2 trρ R ⊗ (R2 + R3 )
2
1 √
≥ 2 + trρ (R2 R3 + R3 R2 ) − 2 trρ |R2 + R3 |
2 "
# (3.9)
1 2Cl 0 p
= 2 + trρ̃ ∑ ⊗ |li hl| − 2 trρ̃ ∑ 1 +Cl I ⊗ |li hl|
2 l
0 2Cl l
p 2
= E( 1 +Cl − 1) ,
l
(2) (3) (4)
where R is the reflection I ⊗ R0 ⊗ R1 ⊗ R1 , the second line follows from Lemma 3.3, ρ̃ = V ρV † , and
the expectation El is over the probability distribution Pr(l) = trρ̃ (I ⊗ |li hl|).
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 20
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
To complete the proof, consider the state dependent distance between reflections R2 and V † (X ⊗ I)V
1
dρ R2 ,V † (X ⊗ I)V = 1 − Re trρ R2V † (X ⊗ I)V 2
1
= 1 − E Sl 2 .
l
This equation and Equation (3.9) together with Lemma 3.4 give the second part in the theorem.
In the above discussion, the fifth player plays the role of the special player in the game. It is natural
to generalize this to a game with player (t) as the special player. The five-qubit code game with special
player (t) is the game defined by the table in Figure 3b after a cyclic rotation of the question columns
such that the special column becomes the t-th one. This makes use of the translation invariance of the
five-qubit code.
For a general r-qubit stabilizer S that has a set of XZ-form generators g1 , g2 , . . . , gl , we need to select
(t) (t) (t)
two generators gX , gZ among g1 , . . . , gl for each qubit t ∈ [r] such that gX has X operator on the t-th
(t)
qubit and gZ has Z operator on the t-th qubit. This is possible in most cases as long as the distance of the
stabilizer is larger than or equal to 2 and the t-th qubit is not fixed to a pure state for all code states. We
call a stabilizer non-trivial if such choices of a pair of generators are possible for all t ∈ [r]. The choice of
(t) (t)
gX and gZ may not be unique, but any such choice will work. To play the special player stabilizer game
(t) (t)
with special player (t), we follow the procedure in Figure 4 with generators gX and gZ . Even though the
game may not essentially depend on all the generators, the proof of partial rigidity still follows in this
general case.
(t) (t)
More specifically, for t ∈ [r], let gX and gZ be generators that have X and Z on the t-th qubit
respectively. Following the idea in the design of the game for the five-qubit code, define four operators
obtained by doing the π/4-trick on the t-th qubit to this pair of generators
(t) (t) (t) (t) (t) (t) (t) (t)
h1 = gX , h2 = gX7→Z , h3 = gZ7→X , h4 = −gZ , (3.10)
(t) (t)
where gX7→Z is the operator obtained by changing the X operator of the t-th qubit of gX to Z and, similarly,
(t) (t)
gZ7→X is the operator obtained by changing the Z on t-th qubit of gZ to X.
(t)
As in the case for the five-qubit code game, we translate the operators h j to questions w j = (w j,i )
where w j,i is in {∗, 0, 1, 2, 3}. Following the translation rule, w j,i is ∗ if the i-th tensor factor of h j is I. It
is 0, 1 if i 6= t and the corresponding tensor factor is X, Z respectively, and it is 2, 3 if i = t and the tensor
(t)
factor is X, Z respectively. Similarly, define s j to be 0 or 1 if the sign of h j is 1 or −1 respectively.
The stabilizer game with special player (t) is the game defined as in Figure 5.
3.3 Stabilizer game
The partial rigidity of the special-player stabilizer game applies only to the measurements performed by
the special player. It essentially forces the special player to measure X 0 and Z 0 on her system. There are,
however, no rigidity results known for the other players’ measurements and nothing is proved about the
shared state of the strategy. The stabilizer game uses the special-player stabilizer game as a sub-module
to achieve the full rigidity properties for all players.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 21
Z HENGFENG J I
Special-Player Stabilizer Game (General Case)
For a stabilizer S with XZ-form generators, let w j,i and s j be the questions and parities defined
(t)
by the operators h j in Equation (3.10) for j ∈ [4]. In the special-player stabilizer game with
player (t) as the special player, the verifier performs the following steps:
1. Select an index j ∈ [4] uniformly at random.
2. For i ∈ [r], send w j,i in Figure 3b to the player (i) if w j,i is not ∗, the null question.
3. Receive a bit a(i) from player (i) if she was asked a question.
L (i)
4. Accept if and only if the parity of the answers i a equals s j .
Figure 5: Special-player stabilizer game.
The specification of the Stabilizer Game is given in Figure 6. It is defined by the r-qubit stabilizer
(t) (t)
S with XZ-form generators. It also implicitly depends on a fixed choice of generators gX , gZ for each
t ∈ [r] in order to perform the second test. The game involves r players, each of whom may receive a
question of two bits, and is required to answer one bit. The verifier’s decision depends only on the parity
of some of the answer bits, so that game is a generalized XOR game. In this paper, the number r of qubits
of the stabilizer is always assumed to be a constant, and it may be subsumed by the Big-O notation in the
rest of the paper.
Stabilizer Game
For an r-qubit non-trivial stabilizer S with XZ-form generators g1 , g2 , . . . , gl , define the stabi-
lizer game of S as follows. Let w j,i for j ∈ [l], i ∈ [r] be ∗, 0, or 1 if g j has I, X, or Z on the
i-th qubit respectively. Let s j for j ∈ [l] be the 0, 1 if the sign of g j is 1, −1 respectively. The
verifier performs the following two tests with equal probability:
1. Select an index j ∈ [l] uniformly at random. Send w j,i to the player (i) if w j,i 6= ∗.
Receives a bit from each player. Accept if the answers not corresponding to the null
questions have the same parity as s j . Reject otherwise.
2. Select t ∈ [r] uniformly at random. Play the special-player stabilizer game with special
player (t) in Figure 5.
Figure 6: Stabilizer game for a stabilizer S.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 22
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
The nonlocal value of the game is
∗
√
1 + ωSPS 6+ 2
ωS∗ = = ,
2 8
which can be achieved by players who share an encoded state of the stabilizer code and measures X, Z,
X 0 , Z 0 when receiving 0, 1, 2, 3, respectively. This value is easily seen to be optimal as it saturates the
winning probability in both tests of the stabilizer game.
The stabilizer game has the following rigidity property. We remark that it is important for us to obtain
rigidity not only for the X 0 and Z 0 operators but for the X and Z operators as well which are used later
to construct the energy checks by the measuring the logical operators of the four qubit code. The error
dependence on ε may be improved and we did not try to optimize it as this will not be important for our
final result.
Theorem 3.5. For any non-trivial r-qubit stabilizer with XZ-form generators, the stabilizer game in
Figure 6 has the following rigidity property. For any strategy S of the game specified by Hilbert spaces
(i)
{Hi }ri=1 , a state ρ ∈ D( ri=1 Hi ), and traceless reflections Rw on Hi for i ∈ [r], w ∈ {0, 1, 2, 3}, if the
N
value of the strategy is at least ωS∗ − ε, then there are unitary operators Vi ∈ L(Hi , B ⊗ Ĥi ) for i ∈ [r]
such that the following properties hold:
(i)
• For all i ∈ [r], R3 = Vi† (Z 0 ⊗ I)Vi and
(i)
dρ R2 ,Vi† (X 0 ⊗ I)Vi ≤ O(ε 1/2 ),
(3.11a)
(i)
dρ R1 ,Vi† (Z ⊗ I)Vi ≤ O(ε 1/4 ),
(3.11b)
(i)
dρ R0 ,Vi† (X ⊗ I)Vi ≤ O(ε 1/4 ),
(3.11c)
where X 0 , Z 0 are defined in Equation (2.2).
• Let Π be the projection to the code space of the stabilizer code of S, and let V be the unitary
operator ri=1 Vi . It holds that
N
Π ⊗ I,V ρV † ≥ 1 − O(ε 1/4 ),
where Π acts on the r qubits, each of which is the first qubit of each player after the application of
V.
Proof. By the symmetry of the game, it suffices to prove the statement for one of the players, say, the
(r)
player (r). For simplicity, use Rw to represent the reflection Rw of player (r). It is easy to see that
strategy S wins the special-player stabilizer game of special player (r) with probability ωSPS
∗ − O(ε). By
Theorem 3.1, there exists a unitary operator V such that R3 = V † (Z ⊗ I)V and
dρ R2 ,V † (X ⊗ I)V ≤ O(ε 1/2 ).
Taking Vr = (W ⊗ I)V , we get the first two conditions in the first item of the theorem, where W is the
reflection defined in Equation (2.3).
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 23
Z HENGFENG J I
Next, we prove the claim in Equations (3.11b) and (3.11c). For any XZ-form Pauli operator g, define
(i) (i)
g(S) to be the operator obtained by replacing X with R0 and Z with R1 . Let R be the product of the
(r) (r)
first r − 1 tensor factors of gX (S). Here, gX is the chosen generator that has X on the r-th qubit in the
stabilizer game with special player (r). As the strategy S has value at least ωS∗ − ε, it has value at least
1 − O(ε) for the first test of the stabilizer game, and therefore,
(r)
trρ (R ⊗ R0 ) = trρ gX (S) ≥ 1 − O(ε). (3.12)
In other words, the reflection R0 is O(ε)-consistent with R on ρ. We emphasize that the reflection R acts
on the joint system of the first r − 1 players. This does not cause any problem as it is only used for our
proof and is never actually measured on the joint system.
Consider a new strategy Ŝ modified from√strategy S by changing R2 in the strategy S to Vr† (X 0 ⊗ I)Vr .
This new strategy has value at least ωS∗ − O( ε) by Lemma 2.4. Consider the matrix ∆1 for strategy Ŝ, as
in Equation (3.7),
h X 0 + Z0 i
∆1 (Ŝ) = R ⊗ I − I ⊗ Vr† √ ⊗ I Vr ,
2
†
= R ⊗ I − I ⊗Vr (X ⊗ I)Vr .
√
By a similar argument that gives Equation (3.8) and the fact that Ŝ has value at least ωSPS
∗ − O( ε) in the
second part of the game, we have
√
trρ (∆21 (Ŝ)) ≤ O( ε).
This gives
√
trρ (R ⊗Vr† (X ⊗ I)Vr ) ≥ 1 − O( ε), (3.13)
√
which proves the O( ε)-consistency of Vr† (X ⊗ I)Vr and R on ρ.
Equations (3.12) and (3.13) and Lemma 2.7 imply that
dρ R0 ,Vr† (X ⊗ I)Vr ≤ O(ε 1/4 ).
This completes the proof for Equation (3.11c). A similar argument establishes Equation (3.11b).
Finally, to prove the second item of the theorem, consider a strategy S̃ that uses the same state ρ and
reflections
(i) (i)
R0 = Vi† (X ⊗ I)Vi , R2 = Vi† (X 0 ⊗ I)Vi ,
(i) (i)
R1 = Vi† (Z ⊗ I)Vi , R3 = Vi† (Z 0 ⊗ I)Vi .
By Lemma 2.4 and the first part of the theorem, strategy S̃ has value at least ωS∗ − O(ε 1/4 ). Hence, it has
acceptance probability at least 1 − O(ε 1/4 ) in the first test of the stabilizer game. This means that
1 + E j trρ̃ (g j )
= 1 − O(ε 1/4 ),
2
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 24
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
where j is uniformly random over [l], the g j operators are the generators of the stabilizer, and ρ̃ = V † ρV .
This is equivalent to
l
trρ̃ ∑ g j = l − O(ε 1/4 ).
(3.14)
j=1
Operator ∑lj=1 g j has eigenvalues in {−l, −l + 2, . . . , l − 2, l} and Π projects to the eigenspace of eigen-
value l. Hence
l
∑ g j ≤ lΠ + (l − 2)(I − Π) = (l − 2)I + 2Π.
j=1
This, together with Equation (3.14), implies that
trρ̃ (Π) = 1 − O(ε 1/4 ),
which is equivalent to the second part of the theorem.
3.4 Multi-qubit stabilizer game
In this section, we consider a multi-qubit variant of the stabilizer game called the (k, n)-stabilizer game. It
is a nonlocal game implementation of the stabilizer check of the Fitzsimons-Vidick protocol [26]. Instead
of asking for the qubits and performing an encoding check on them, the verifier sends the measurement
instructions on the corresponding qubits to the players. The optimal strategy of the game is to encode each
qubit with the stabilizer code and measure X, Z, X 0 and Z 0 honestly on the encoded data on corresponding
qubits. We prove a partial rigidity theorem for the multi-qubit stabilizer game, which suffices for our
purpose. In particular, we only prove the rigidity for the reflections corresponding to questions in 0, 1.
The full rigidity properties can be proved with some extra effort. The overall proof idea is similar to
that of [26] which extracts the qubits one by one sequentially, but our proof provided here is more
modularized.
The (k, n)-stabilizer game is given in Figure 7. For simplicity, we assume in the multi-qubit stabilizer
game that, when the question is ∗, the verifier replaces it with either 0 or 1 and ignores the corresponding
answer. With this convention, each player will either see a question of the form (u, w) for u ∈ [n]
and w = 0, 1, 2, 3 or a tuple of k such questions. Answers are either a single bit or a string of k-bits
correspondingly. The verifier accepts or rejects depending on the parity of some of the answer bits.
∗
It is easy to see that the nonlocal value ωMQS of the (k, n)-stabilizer game in Figure 7 equals the value
of the stabilizer game ωS . Let Hi be the state space of player (i). A strategy for the k-qubit stabilizer
∗
game,
(i) (i)
S = ρ, Rq , M~q ,
(i)
consists of a state ρ ∈ D ri=1 Hi , reflections Rq the players measure for question q and measurements
N
(i)
M~q with k-bit outcomes for question ~q. The superscripts of the measurements indexing the players are
sometimes omitted if there will be no ambiguity.
Without loss of generality, it is assumed that the measurements M~q are projective measurements of
the same rank. For each q that occurs as the i-th entry in the tuple ~q, define a reflection
Sq|~q = ∑ (−1)b M~qb .
i
b∈{0,1}k
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 25
Z HENGFENG J I
Multi-Qubit Stabilizer Game
Let S be a non-trivial r-qubit stabilizer with a set of generators of XZ-form. Let [n] be the
index of n qubits and let k ≥ 2 be a constant. The (k, n)-stabilizer game for S is an r-player
nonlocal game where the verifier does the following with equal probability:
1. Select a subset J ⊂ [n] of size k, an index u ∈ J, and a player t ∈ [r], all uniformly
at random. For each qubit v ∈ J, randomly select questions wv = (wv,i ), where wv,i ∈
(i)
{0, 1, 2, 3} and each wv is sampled as in the stabilizer game. Define qv = (v, wv,i ) for
(i)
i ∈ [r] and v ∈ J. Send qu to player (i) and receive an answer bit a(i) if i 6= t. Send
(t)
~q = qv v∈J to player (t), and receive a k-bit string b = (bv )v∈J . Define a(t) = bu and
a = (a(1) , a(2) , . . . , a(r) ). The verifier accepts if and only if the verifier for the stabilizer
game accepts when the questions are wu and answers are a.
2. Select a qubit u ∈ [n] uniformly at random. Play the stabilizer game on qubit u. That is,
the verifier samples w = (wi ) as in the stabilizer game. Define q(i) = (u, wi ) for i ∈ [r].
Send q(i) to player (i) and receive an answer bit a(i) . The verifier accepts if the verifier
for the stabilizer game accepts on questions w and answers a = (a(i) ).
Figure 7: Multi-qubit stabilizer game.
The reflections Rq and Sq|~q are all traceless. For ~q = (q1 , q2 , . . . , qk ), the measurement M~q has a one-to-one
correspondence with the collection of k pairwise commuting reflections
k
Sqs |~q s=1 ,
and we refer to these reflections as the reflections associated with the projective measurement M~q . We
also write Sq|~q as Su,w|~q for q = (u, w). On the other hand, for any collection of k pairwise commuting
reflections, there associates a projective measurement with k-bit outcome as the repeated application of
the two-outcome measurements defined by the reflections.
We prove the following partial rigidity property of the (k, n)-stabilizer game.
Theorem 3.6. For any constant integer k ≥ 2, there exists a constant κ > 0 that depends only on k such
that the (k, n)-stabilizer game in Figure 7 has the following rigidity property. For any quantum strategy
(i) (i)
S = ρ, Rq , M~q that has value at least ωS∗ − ε, there are isometries Vi ∈ L(Hi , B⊗n ⊗ Ĥi ), such
that the following properties hold
• For all i ∈ [r], all q = (u, w), qs = (us , ws ) with u ∈ [n], us ∈ [n], w ∈ {0, 1}, ws ∈ {0, 1}, s ∈ [k],
and ~q = (q1 , q2 , . . . , qk ),
(i)
dρ Rq ,Vi† DqVi ≤ O(nκ ε 1/κ ),
(3.15a)
(i) (i)
dρ M~q , N~q ≤ O(nκ ε 1/κ ), (3.15b)
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 26
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
(i)
where Dq is the X, Z operator on the u-th qubit for w = 0, 1 respectively, and N~q is the measurement
that measures Dqs for s = 1, 2, . . . , k sequentially after the application of Vi .
Nr
• Let Π be the projection to the code space of the stabilizer code, V be the isometry i=1 Vi , then
Π⊗n ⊗ I,V ρV † ≥ 1 − O(nκ ε 1/κ ), (3.16)
where the t-th tensor factor of Π⊗n acts on r qubits, each of which is the t-th qubit of each player’s
system after the application of V .
The proof of Theorem 3.6 relies on the following lemmas.
Lemma 3.7. Let ρ ∈ D(HA ⊗ HB ) be a state on systems A and B. Let M0 , M1 , N0 , N1 be four projective
measurements on HA such that M1a , N1a commute for all a. Let M, N be two projective measurements on
HB . Suppose that M0 , M1 are both ε-consistent with M, and N0 , N1 are both ε-consistent with N on state
ρ. Then
√
∑ k[M0a , N0a ]k2ρ ≤ O( ε).
a
Proof. We first prove that
∑ trρ M0a N0a M0a N0a ≈√ε ∑ trρ N0a M0a N0a M1a .
a a
Namely, we can move operator M0a in the front to the end of the product and change it to M1a without
incurring too much error in the expression.
By ε-consistency between M0 and M,
∑ trρ M0a N0a M0a N0a ≈√ε ∑ trρ M0a N0a M0a N0a ⊗ Ma ,
a a
as the absolute value of the difference on the two sides is
∑ trρ M0a N0a M0a N0a ⊗ (1 − Ma )
a
r
≤ ∑ trρ M0a ⊗ (1 − M a ) ∑ trρ N0a M0a N0a M0a N0a
a a
√
≤ ε.
By similar arguments,
∑ trρ M0a N0a M0a N0a ⊗ Ma ≈√ε ∑ trρ N0a M0a N0a ⊗ Ma
a a
≈√ε ∑ trρ N0a M0a N0a M1a ⊗ M a
a
≈√ε ∑ trρ N0a M0a N0a M1a .
a
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 27
Z HENGFENG J I
This proves our claim about moving and changing M0a to M1a . We do this for the four operators in the
product sequentially,
∑ trρ M0a N0a M0a N0a ≈√ε ∑ trρ M1a N1a M1a N1a .
a a
Expand the ρ-norm in left-hand side of the claim in the lemma,
∑ k[M0a , N0a ]k2ρ = ∑ trρ M0a N0a M0a + N0a M0a N0a − M0a N0a M0a N0a − N0a M0a N0a M0a .
a a
Now the proof follows by applying the above operator moving procedure to each of the four terms in the
expansion and the condition that M1a commutes with N1a for all a.
Lemma 3.8. Let B1 , B10 , B be two-dimensional Hilbert spaces. Let V ∈ L(H, B ⊗ Ĥ) be an isometry,
R ∈ L(H) be an operator and |Φi be the EPR state on B1 ⊗ B10 . Define isometry C ∈ L(H, B1 ⊗ B10 ⊗ H)
as
C = (I ⊗V † ) SWAP(|Φi ⊗V ),
where the SWAP acts on B1 and B. Then
C† RC = V † σ jV R V † σ jV ,
E
j=0,1,2,3
where σ j are Pauli operators.
Proof. This follows by substituting the two SWAP gates using the identity
I + XX +YY + ZZ
SWAP = ,
2
and a direct calculation.
Lemma 3.9. Let ρ ∈ D(H ⊗ H0 ) be a state, T ∈ L(H) be an operator with constant operator norm, R
be a reflection on H that has an ε-consistent reflection S on H0 . Then
trρ (RT R) ≈√ε trρ (T ).
Proof. We first prove that
trρ (RT ) ≈√ε trρ (T ⊗ S). (3.17)
By consistency of R and S, we have
trρ (RT ) = ∑ trρ (Ra (−1)a T )
a∈{0,1}
≈√ε ∑ trρ (Ra (−1)a T ⊗ Sa )
a∈{0,1}
≈√ε ∑ trρ ((−1)a T ⊗ Sa )
a∈{0,1}
= trρ (T ⊗ S).
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 28
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
Similarly,
trρ (T R) ≈√ε trρ (T ⊗ S). (3.18)
Taking T = T R in Equations (3.17) and (3.18), we have trρ (RT R) ≈√ε trρ (T R ⊗ S), and
trρ (T ) = trρ (T RR) ≈√ε trρ (T R ⊗ S).
This completes the proof.
Lemma 3.10. Let M = M a be a projective measurement having
k-bit outcomes on quantum system A
and let R1 , R2 , . . . , Rk be the associated reflections. Let N = N a be a projective measurement having
k-bit outcomes on quantum system B and let S1 , S2 , . . . , Sk be its associated reflections. Let V ∈ L(HA , HB )
be an isometry and ρ ∈ D(HA ⊗ HC ) a quantum state. For i ∈ [k], define Ši = V † SiV ∈ Herm(HA ). Let
Ň be the quantum measurement that measures N after the application of isometry V .
If both Ri and Ši have ε-consistent reflections on HC for i ∈ [k], then
dρ (M, Ň) ≤ O(ε 1/2 ).
Proof. The measurement Ň is a POVM with measurement operators
k
I + (−1)ai Si
Ň a = V † ∏ V
i=1 2
1 k
= k ∑ (−1)ha,xiV † ∏ Sixi V.
2 x∈{0,1}k i=1
This implies that
k k
a a 1 ha,x⊕yi xi
† yi
∑ Re trρ (M Ň ) = 22k ∑ (−1) Re trρ ∏ Ri V ∏ Si V
a a,x,y i=1 i=1
k k
1
= k ∑ Re trρ ∏ Rxi i V † ∏ Sixi V .
2 x i=1 i=1
In this proof, the superscript of an operator represents the corresponding power of the operator and is not
the index for measurement outcome as in the other parts of the paper.
We claim that for all x ∈ {0, 1}k , the term in the summand
k k
Re trρ ∏ Rxi i † xi
V ∏ Si V ≈ε 1.
i=1 i=1
This will conclude the proof by the definition of dρ for POVMs by choosing {V M a } and {N aV } as the
measurement operators for the two POVMs M and Ň respectively.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 29
Z HENGFENG J I
We prove this claim by an induction on k. For k = 1, the claim follows from Lemma 2.7 and the
consistency conditions. Assume now the claim holds for k − 1. We have
k k−1
xi † xi xk
Re trρ ∏ Ri V ∏ Si V Rk ≈ε 1, (3.19a)
i=1 i=1
k k−1
xi † xi xk
Re trρ ∏ Ri V ∏ Si V Šk ≈ε 1, (3.19b)
i=1 i=1
where the approximations follow from the induction hypothesis, the consistency conditions and the
Cauchy-Schwarz inequality. Then, we use the Cauchy-Schwarz inequality again to remove the VV † , and
it follows that k k
xi † xi
Re trρ ∏ Ri V ∏ Si V ≈ε 1.
i=1 i=1
Proof of Theorem 3.6. Consider first the claim in Equation (3.15a) of the theorem for i = r.
In the proof, Dw denotes X, Z for w = 0, 1 respectively, and Dq denotes Dw acting on the u-th qubit if
q = (u, w). Let δ be nε and δk be nk ε. For simplicity, we omit the superscript (r) in the reflections for
player (r).
Since the strategy S has value at least ωS∗ − ε for the (k, n)-stabilizer game, it must have value at
least ωS∗ − O(δ ) for the stabilizer games for each u ∈ [n] in the second part of the game. More precisely,
(i)
Su = ρ, Ru,w forms a strategy for the stabilizer game with value at least ωS∗ − O(δ ).
By Theorem 3.5, for all u ∈ [n], there exist a unitary operators Vu ∈ L(Hr , B ⊗ H̃r ) such that
dρ Ru,w ,Vu† (Dw ⊗ I)Vu ≤ O(δ 1/4 ).
Define R̂u,w = Vu† (Dw ⊗ I)Vu . The above equation becomes
dρ Ru,w , R̂u,w ≤ O(δ 1/4 ).
(3.20)
Similarly, for all J ⊆ [n] and u ∈ J, all choices of wv for v ∈ J and v 6= u, consider state ρ, reflections
(i)
Ru,w for i ∈ [r − 1] and Su,w|~q for player (r). They form a strategy for the stabilizer game with value at
least ωS∗ − O(δk ) for qu = (u, w), qv = (v, wv ) and ~q = (qv )v∈J . We clarify that only w is the index of
questions for the stabilizer game in this strategy and everything else in the subscripts
p are fixed.
By Equations (3.12) and (3.13), reflections Su,w|~q and R̂u,w have the same O( δk )-consistent mea-
surement on ρ. Let (u, w) and (v, w0 ) be two entries of ~q, then the reflections R̂u,w , Su,w|~q , Sv,w0 |~q , R̂v,w0
correspond to measurements that satisfy the conditions for M0 , M1 , N1 , N0 in Lemma 3.7. Hence,
2 1/4
R̂u,w , R̂v,w0 ρ ≤ O(δk ), (3.21)
for all u 6= v ∈ [n].
Consider 2n two-dimensional Hilbert spaces Bu , Bu0 for u ∈ [n]. Denote H[n] = nu=1 Bu and
N
H[n]0 = u=1 Bu0 . We sometimes call the system of Bu the u-th qubit. Let |Φiu,u0 be the EPR state on
Nn
systems Bu , Bu0 . For each u ∈ [n], define isometry Cu ∈ L(H, Bu ⊗ Bu0 ⊗ H) as
Cu = (I ⊗Vu† ) SWAPu (|Φiu,u0 ⊗Vu ),
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 30
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
where SWAPu is the SWAP gate acting on the u-th qubit and the first output qubit of Vu . This isometry
was previously used in [51, 26, 36] in related contexts.
Define isometry V ∈ L Hr , H[n] ⊗ H[n]0 ⊗ Hr as the sequential application of C1 ,C2 , . . . ,Cn ,
V = CnCn−1 · · ·C1 . (3.22)
We claim that this choice of V works for the claims of the theorem by taking Ĥr to be H[n]0 ⊗ Hr . Define
R̃q = V † DqV,
for q = (u, w). There are single-qubit Pauli X, Z operators that are close to the reflections used by in the
strategy and help us to establish the rigidity theorem.
Define a quantum channel
Tu (ρ) = E
†
Tu,i ρTu,i ,
i∈{0,1,2,3}
where
Tu,0 = I, Tu,1 = R̂u,0 , Tu,2 = R̂u,0 R̂u,1 , Tu,3 = R̂u,1 . (3.23)
Recalling the definition of R̂q , the action of quantum channel Tu essentially traces out the qubit corre-
sponding to R̂u,0 , R̂u,1 , the Pauli X, Z operators up to the unitary operator Vu .
As Dq and Cv commute for all v > u and q = (u, w), we have
R̃q = C1†C2† . . .Cu−1
†
R̂qCu−1Cu−2 . . .C1 .
A series of applications of Lemma 3.8 gives the expression of R̃q for q = (u, w),
R̃q = T1 ◦ T2 ◦ · · · ◦ Tu−1 (R̂q ).
This gives a useful alternative representation for R̃q in terms of operators R̂u,w and the corresponding
trace-out channels.
The aim is to first prove that
dρ (R̂q , R̃q ) ≤ O(nκ ε 1/κ ).
For convenience, define
R = T2 ◦ · · · ◦ Tu−1 (R̂q ).
Then
†
R̃q = E T1,i RT1,i ,
i∈{0,1,2,3}
and
†
trρ R̃q R̂q = E trρ T1,i RT1,i R̂q .
i∈{0,1,2,3}
†
For each of the four cases for i, it is claimed that trρ T1,i RT1,i R̂q is close to trρ (RR̂q ). In words, removing
the superoperator T1,s1 induces a bounded error in the expression.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 31
Z HENGFENG J I
Consider the case i = 1 first. In this case
†
trρ T1,1 (R)T1,1 R̂q = trρ R̂1,0 RR̂1,0 R̂q
≈δ 1/8 trρ R̂1,0 RR̂q R̂1,0
k
≈δ 1/4 trρ (RR̂q ),
where the first approximation follows from Equation (3.21) and Cauchy-Schwarz inequality, and the
second approximation follows from Lemma 3.9 and the fact that R̂1,0 has an O(δ 1/2 )-consistency reflection
on ρ by Equation (3.13).
A similar argument applies for the other cases of i. Repeating this procedure of removing the quantum
channel T j one by one, we have
trρ (R̃q , R̂q ) ≈u δ 1/8 trρ (R̂q , R̂q ) = 1,
k
and q
1/8 1/16
dρ (R̃q , R̂q ) ≤ O u δk ≤ O n1/2 δk .
By the triangle inequality of dρ and Equation (3.20)
1/16
dρ (R̃q , Rq ) ≤ O n1/2 δk . (3.24)
This proves the bound in Equation (3.15a) by choosing κ sufficiently large.
Recall that there exists a reflection R that is δk -consistent with both Rq and Sq|~q on ρ. By the bound in
Equation (3.24) and Lemma 2.4,
1/16
Cρ (R, R̃q ) ≥ 1 − O n1/2 δk .
The bounds in Equation (3.15b) follow from Lemma 3.10 and the consistency of R̃q , Sq|~q with the same
reflection R on the first r − 1 players’ systems.
The second part of the theorem follows by a similar argument used to prove the second part of
Theorem 3.5.
4 Nonlocal games for local Hamiltonian problems
In this section, we give the nonlocal game for the local Hamiltonian problem. Consider a restricted form
of the local Hamiltonian problem in the following definition.
Definition 4.1. For a k-local Hamiltonian of m terms on n qubits H = ∑mj=1 H j , where 0 ≤ H j ≤ I acts
on at most k qubits, the Hamiltonian H is in XZ-form if H j is a real linear combination of tensor products
of I, X, Z for each j.
Lemma 4.2. There exists a constant k such that the XZ-form k-local Hamiltonian problem is QMA-
complete.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 32
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
Proof. This is a simple corollary of the results in [13]. The gate set {CNOT, X,W = cos(π/8)X +
sin(π/8)Z} is known to be universal by the result of Shi [65] and each gate Ut in the gate set is of
XZ-form and Ut = Ut† . Start with a circuit using this particular set of gates and perform the circuit to
Hamiltonian construction of Kitaev. The 5-local terms resulting from the construction will have the
XZ-form. For example, the term checking the propagation of the t-th step of the circuit is
Hprop,t =I ⊗ |100i h100|t−1,t,t+1 −Ut ⊗ |110i h100|t−1,t,t+1
−Ut† ⊗ |100i h110|t−1,t,t+1 + I ⊗ |110i h110|t−1,t,t+1
I − Z(t−1) I + Z(t+1) I − Z(t−1) 1 + Z(t+1)
= ⊗ −Ut ⊗ ⊗ X(t) ⊗ ,
2 2 2 2
which is easily seen to have XZ-form for Ut in the chosen gate set. Other terms in the construction can be
checked similarly. This proves the claim for k = 5.
Using more advanced results from [22], such as their Lemma 22, one can prove the claim for k = 2
and the two-local terms H j have the form α j (XZ − ZX).
Let H = ∑mj=1 H j be the Hamiltonian and assume that 0 ≤ H j ≤ I. We will consider two different
types of energy measurements for a k-local Hamiltonian H on a state ρ. The first type of measurement is
the one used in [26] and does the following. The verifier randomly selects j ∈ [m] and gets the k-qubit
state ρ j on which H j acts. Then the verifier measures the POVM {H j , I − H j } and rejects when the
measurement result is ‘H j ’. It is easy to see that the verifier rejects with probability
1 m 1
∑ H j , ρ = hH, ρi .
m j=1 m
In the second type of energy measurement, we only measure Pauli operators. Let PXZ be the set of
the 3k k-fold tensor products of I, X, Z operators. For XZ-form Hamiltonians, it suffices to measure the
Pauli operators in PXZ only. Expand each term
Hj = ∑ α j,P P. (4.1)
P∈PXZ
Computing the trace of squared operators on both sides of Equation (4.1), we have
∑ α 2j,P ≤ 1.
P∈PXZ
The verifier randomly selects j ∈ [m] and gets the k-qubit state ρ j on which H j acts. He then chooses P
uniformly at random and measures P on ρ j . The verifier rejects with probability α j,P if either α j,P > 0
and the measurement result is +1, or α j,P < 0 and the measurement result is −1. The probability of
rejection is computed as
1 α j,P + α j,P P, ρ j αm + hH, ρi
∑∑ = ,
3k m j P 2 2 · 3k m
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 33
Z HENGFENG J I
where
1
α= (4.2)
m∑
α j,P
j,P
is a constant determined by the Hamiltonian.
We note that the second type of the energy measurement is less efficient but the probabilities of
rejection in these two settings are linearly related. In fact, it is easy to see that the rejection probability in
the first setting is p if and only if the rejection probability of the second setting is
α+p
.
2 · 3k
We now give the nonlocal game for the local Hamiltonian problem as in Figure 8. To measure the
energy, we further assume that the stabilizer S used in the game has the logical X, Z operators LX and LZ
that are products of I, X, Z. This is the case for both the five-qubit code and the four-qubit quantum error
detecting code.
Nonlocal Game for The Local Hamiltonian Problem
Let S be a non-trivial r-qubit stabilizer code with XZ-form generators that encodes at least
one qubit and has a pair of logical LX , LZ operators of XZ-form. Define two question vectors
wX = (wX,i ) and wZ = (wZ,i ) as follows. The entry wD,i is ∗, 0, or 1, if the i-th Pauli factor of the
logical operator LD is I, X, Z respectively for D = X, Z. For an XZ-form, k-local Hamiltonian
problem (H, a, b), and a small probability p chosen later, we consider the following multi-
player nonlocal game. It involves a classical verifier and r players (i) for i ∈ [r]. The verifier
performs the first test with probability p, and the second test with probability 1 − p:
1. Energy Check. Select j ∈ [m] uniformly at random. Expand H j as
Hj = ∑ α j,P P,
P∈PXZ
and let J ⊂ [n] be the set of k qubits H j acts on non-trivially. Select an operator P in PXZ
uniformly at random. For each u ∈ J, define wu,i to be wX,i or wZ,i if the tensor factor
(i) (i)
in P acting on qubit u is X or Z, respectively. Define qu = (u, wu,i ) and ~q = qu u∈J .
(i)
Send the question ~q to the r players. Receive a k-bit answer a(i) = au from each
player. The verifier rejects with probability α j,P if either the parity of the answer bits
not corresponding to the null question is even and α j,P > 0, or the parity is odd and
α j,P < 0.
2. Encoding Check. Play the (k, n)-stabilizer game.
Figure 8: The nonlocal game for local Hamiltonian problems
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 34
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
Theorem 4.3. There exist constants C and κ such that the following holds. If p in the r-player game for
an XZ-form, k-local Hamiltonian problem in Figure 8 is chosen to be C(b − a)κ /nκ , and α is defined as
in Equation (4.2), then
1. For yes-instances of the k-local Hamiltonian problem, the nonlocal value of the game is at least
∗ α +a
(1 − p)ωS + p 1 − .
2 · 3k
2. For no-instances of the k-local Hamiltonian problem, the nonlocal value of the game is at most
∗ α + (a + b)/2
(1 − p)ωS + p 1 − .
2 · 3k
Proof. First consider the completeness of the game. If the local Hamiltonian problem is a yes-instance,
there exists a quantum witness state |ψi ∈ B⊗n such that
hψ|H|ψi ≤ am.
We construct the strategy for the r players as follows. For each qubit u of |ψi, we encode it with the
stabilizer code S and let player (i) hold the i-th encoded qubit of u. When receiving the question
(u, w) from the verifier, the players measure their share of qubit u with X, Z, X 0 , Z 0 correspondingly if
w = 0, 1, 2, 3.
For this strategy, the players can win the Encoding Check part with optimal probability ωS∗ . In
the Energy Check part of the game, the measurement of the logical X and logical Z is essentially an
implementation of the second type of energy measurement on the state ψ. The rejection probability in
this part is
αm + hH, |ψi hψ|i
.
2 · 3k m
Therefore, the acceptance probability of the game ω ∗ is at least
α +a
(1 − p)ωS∗ + p 1 − .
2 · 3k
Next, we prove the soundness of the game. If the local Hamiltonian problem defined by (H, a, b) is a
no-instance, we need to prove an upper bound of the nonlocal value of the game.
Consider any strategy S that has acceptance probability ωS∗ − ε in the Encoding Check part of the
game. Theorem 3.6 states that there are isometries Vi ∈ L(Hi , B⊗n ⊗ Ĥi ), measurements N~q associated
k
with Vi† Dqs Vi s=1 , such that
dρ (M~q , N~q ) ≤ O(nκ ε 1/κ ).
Consider the strategy S̃ = (ρ, {Rq }, {N~q }). The values of S and S̃ for the Energy Check differ at most
by O(nκ ε 1/κ ) by Lemma 2.4.
Strategy S̃ uses honest X, Z measurement on the logical space of the error correcting code and we
claim that it must have value at most
α +b
1− ,
2 · 3k
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 35
Z HENGFENG J I
N
in the Energy Check part. Otherwise, the state of the first rn qubits after the application of i Vi has
rejection probability at most (α + b)/(2 · 3k ) in the energy measurement using logical X, Z operators LX ,
LZ . This implies the existence of n-qubit state that has rejection probability at most (α + b)/(2 · 3k ) in
the second type energy measurement, which is a contradiction to the no-instance condition of the local
Hamiltonian problem.
Therefore, the value of strategy S is at most
α +b
(1 − p)(ωS∗ − ε) + p 1 − + cnκ ε 1/κ ,
k
(4.3)
2·3
for constants c, κ large enough.
Maximizing the expression as a function of ε, it is easy to see that the maximum value is achieved at
pcnκ κ/(κ−1)
ε= .
(1 − p)κ
Substituting this into Equation (4.3), ω ∗ (S) is upper bounded by
α +b
(1 − p)ωS∗ + p 1 −
+ ∆ ,
2 · 3k
for
1 κ pcnκ 1/(κ−1)
∆ = 1− cn .
κ (1 − p)κ
Choosing κ large and p small such that (1 − p)κ ≥ 1, we can bound ∆ as
2 1/(κ−1)
∆ ≤ cnκ (pcnκ )1/(κ−1) = pcκ nκ .
Finally, if we choose a constant C small enough and
2
p = C(b − a)κ−1 /nκ ,
we have
b−a
∆≤ ,
4 · 3k
and
α + (a + b)/2
ω ∗ (S) ≤ (1 − p)ωS∗ + p 1 − .
2 · 3k
This concludes the proof of the theorem by choosing κ large enough.
Finally, Theorem 1.1 follows by using the stabilizer for the four-qubit error detecting code in the
game and noticing that the completeness and soundness have an inverse polynomial gap in Theorem 4.3.
Acknowledgments
The author acknowledges helpful discussions with Richard Cleve, Debbie Leung, Fang Song, Thomas
Vidick, Guoming Wang, John Watrous, Xiaodi Wu and Bei Zeng on related problems. The major part
of the paper was done while the author was with the Institute for Quantum Computing, University of
Waterloo.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 36
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
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. Phys. Rev. Lett., 98(23):230501, 2007. [doi:10.1103/PhysRevLett.98.230501, arXiv:quant-
ph/0702152] 10
[2] D ORIT A HARONOV, I TAI A RAD , AND T HOMAS V IDICK: Guest Column: The Quantum PCP
Conjecture. SIGACT News, 44(2):47–79, 2013. [doi:10.1145/2491533.2491549] 2
[3] D ORIT A HARONOV, M ICHAEL B EN -O R , E LAD E BAN , AND U RMILA M AHADEV: Interactive
proofs for quantum computations. 2017. Preliminary version in ICS’10, see arXiv:0810.5375.
[arXiv:1704.04487] 3
[4] D ORIT A HARONOV AND T OMER NAVEH: Quantum NP - a survey, 2002. [arXiv:quant-ph/0210077]
2, 11
[5] S ANJEEV A RORA , C ARSTEN L UND , R AJEEV M OTWANI , M ADHU S UDAN , AND M ARIO
S ZEGEDY: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555,
1998. Preliminary version in FOCS’92. [doi:10.1145/278298.278306] 1, 2
[6] S ANJEEV A RORA AND S HMUEL S AFRA: Probabilistic checking of proofs: a new characterization
of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]
1, 2
[7] L ÁSZLÓ BABAI: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM
Press, 1985. [doi:10.1145/22145.22192] 1
[8] L ÁSZLÓ BABAI , L ANCE F ORTNOW, AND C ARSTEN L UND: Nondeterministic exponential time
has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991. Preliminary version in
FOCS’90. [doi:10.1007/BF01200056] 1, 2, 3
[9] J ONATHAN BARRETT: Nonsequential positive-operator-valued measurements on entangled
mixed states do not always violate a Bell inequality. Phys. Rev. A, 65(4):042302, 2002.
[doi:10.1103/PhysRevA.65.042302, arXiv:quant-ph/0107045] 4
[10] J OHN S. B ELL: On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1(3):195–200,
1964. [doi:10.1103/PhysicsPhysiqueFizika.1.195] 10
[11] M ICHAEL B EN -O R , S HAFI G OLDWASSER , J OE K ILIAN , AND AVI W IGDERSON: Multi-prover
interactive proofs: How to remove intractability assumptions. In Proc. 20th STOC, pp. 113–131.
ACM Press, 1988. [doi:10.1145/62212.62223] 1
[12] C HARLES H. B ENNETT, DAVID P. D I V INCENZO , J OHN A. S MOLIN , AND W ILLIAM K. W OOT-
TERS : Mixed-state entanglement and quantum error correction. Phys. Rev. A, 54(5):3824–3851,
1996. [doi:10.1103/PhysRevA.54.3824, arXiv:quant-ph/9604024] 11
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 37
Z HENGFENG J I
[13] JACOB D. B IAMONTE AND P ETER J. L OVE: Realizable Hamiltonians for universal adiabatic
quantum computers. Phys. Rev. A, 78(1):012352, 2008. [doi:10.1103/PhysRevA.78.012352,
arXiv:0704.1287] 6, 33
[14] 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] 3
[15] A NNE B ROADBENT, Z HENGFENG J I , FANG S ONG , AND J OHN WATROUS: Zero-knowledge
proof systems for QMA. In Proc. 57th FOCS, pp. 31–40. IEEE Comp. Soc. Press, 2016.
[doi:10.1109/FOCS.2016.13, arXiv:1604.02804] 2
[16] P ETER J. C AMERON , A SHLEY M ONTANARO , M ICHAEL W. N EWMAN , S IMONE S EVERINI , AND
A NDREAS W INTER: On the quantum chromatic number of a graph. Electronic J. Combinatorics,
14:R81, 2007. [arXiv:quant-ph/0608016] 3
[17] J OHN F. C LAUSER , M ICHAEL A. H ORNE , A BNER S HIMONY, AND R ICHARD A. H OLT: Pro-
posed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969.
[doi:10.1103/PhysRevLett.23.880] 4, 10
[18] R ICHARD C LEVE , P ETER H ØYER , B ENJAMIN T ONER , AND J OHN WATROUS: Consequences and
limits of nonlocal strategies. In Proc. 19th IEEE Conf. on Computational Complexity (CCC’04),
pp. 236–249. IEEE Comp. Soc. Press, 2004. [doi:10.1109/CCC.2004.1313847, arXiv:quant-
ph/0404076] 2, 3
[19] R ICHARD C LEVE AND R AJAT M ITTAL: Characterization of binary constraint system games. In
Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 320–331.
Springer, 2014. [doi:10.1007/978-3-662-43948-7_27, arXiv:1209.2729] 3
[20] ROGER C OLBECK: Quantum And Relativistic Protocols For Secure Multi-Party Computation. Ph. D.
thesis, University of Cambridge, 2006. [arXiv:0911.3814] 10
[21] S TEPHEN A. C OOK: The complexity of theorem-proving procedures. In Proc. 3rd STOC, pp.
151–158. ACM Press, 1971. [doi:10.1145/800157.805047] 1
[22] T OBY S. C UBITT AND A SHLEY M ONTANARO: Complexity classification of local Hamilto-
nian problems. SIAM J. Comput., 45(2):268–316, 2016. Preliminary version in FOCS’14.
[doi:10.1137/140998287, arXiv:1311.3161] 11, 33
[23] I RIT D INUR: The PCP theorem by gap amplification. J. ACM, 54(3):12:1–12:44, 2007. Preliminary
version in STOC’06. [doi:10.1145/1236457.1236459] 2
[24] U RI F EIGE AND L ÁSZLÓ L OVÁSZ: Two-prover one-round proof systems: their power and their
problems. In Proc. 24th STOC, pp. 733–744. ACM Press, 1992. [doi:10.1145/129712.129783] 1
[25] J OSEPH F. F ITZSIMONS AND E LHAM K ASHEFI: Unconditionally verifiable blind computation.
Phys. Rev. A, 96(1):012303, 2017. [doi:10.1103/PhysRevA.96.012303, arXiv:1203.5217] 3
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 38
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
[26] J OSEPH F. F ITZSIMONS AND T HOMAS V IDICK: A multiprover interactive proof system for
the local Hamiltonian problem. In Proc. 6th Innovations in Theoretical Computer Science Conf.
(ITCS’15), pp. 103–112. ACM Press, 2015. [doi:10.1145/2688073.2688094, arXiv:1409.0260] 2, 3,
4, 5, 6, 25, 31, 33
[27] L ANCE F ORTNOW, J OHN ROMPEL , AND M ICHAEL S IPSER: On the power of multi-prover
interactive protocols. Theoret. Comput. Sci., 134(2):545–557, 1994. Preliminary version in SCT’88.
[doi:10.1016/0304-3975(94)90251-8] 2, 3, 5
[28] S EVAG G HARIBIAN , Y ICHEN H UANG , Z EPH L ANDAU , AND S EUNG W OO S HIN: Quantum
Hamiltonian complexity. Foundations and Trends in Theoretical Computer Science, 10(3):159–282,
2014. [doi:10.1561/0400000066, arXiv:1401.3916] 2
[29] S HAFI G OLDWASSER , S ILVIO M ICALI , AND C HARLES R ACKOFF: The knowledge complexity of
interactive proof-systems. SIAM J. Comput., 18(1):186–208, 1989. Preliminary version in STOC’85.
[doi:10.1137/0218012] 1
[30] DANIEL G OTTESMAN: Stabilizer Codes and Quantum Error Correction. Ph. D. thesis, California
Institute of Technology, 1997. [arXiv:quant-ph/9705052] 11
[31] T SUYOSHI I TO , H IROTADA KOBAYASHI , AND K EIJI M ATSUMOTO: Oracularization and
two-prover one-round interactive proofs against nonlocal strategies. In Proc. 24th IEEE
Conf. on Computational Complexity (CCC’09), pp. 217–228. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/CCC.2009.22, arXiv:0810.0693] 3, 11
[32] T SUYOSHI I TO AND T HOMAS V IDICK: A multi-prover interactive proof for NEXP sound
against entangled provers. In Proc. 53th FOCS, pp. 243–252. IEEE Comp. Soc. Press, 2012.
[doi:10.1109/FOCS.2012.11, arXiv:1207.0550] 2, 3, 11
[33] R AHUL JAIN , Z HENGFENG J I , S ARVAGYA U PADHYAY, AND J OHN WATROUS: QIP = PSPACE. J.
ACM, 58(6):30:1–30:XX, 2011. Preliminary version in STOC’10. [doi:10.1145/2049697.2049704,
arXiv:0907.4737] 2
[34] Z HENGFENG J I: Binary constraint system games and locally commutative reductions, 2013.
[arXiv:1310.3794] 3
[35] Z HENGFENG J I: Classical verification of quantum proofs. In Proc. 48th STOC, pp. 885–898. ACM
Press, 2016. [doi:10.1145/2897518.2897634, arXiv:1505.07432] 1
[36] Z HENGFENG J I: Compression of quantum multi-prover interactive proofs. In Proc. 49th STOC, pp.
289–302. ACM Press, 2017. [doi:10.1145/3055399.3055441, arXiv:1610.03133] 6, 31
[37] C AMILLE J ORDAN: Essai sur la géométrie à n dimensions. Bull. de la Soc. Math. de France,
3:103–174, 1875. [doi:10.24033/bsmf.90] 18
[38] R ICHARD M. K ARP: Reducibility among combinatorial problems. In Proc. Symp. Complexity of
Computer Computations, pp. 85–103. Springer, 1972. [doi:10.1007/978-1-4684-2001-2_9] 1
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 39
Z HENGFENG J I
[39] J ULIA K EMPE , A LEXEI K ITAEV, AND O DED R EGEV: The complexity of the local Hamilto-
nian problem. SIAM J. Comput., 35(5):1070–1097, 2006. Preliminary version in FSTTCS’04.
[doi:10.1137/S0097539704445226, arXiv:quant-ph/0406180] 11
[40] J ULIA K EMPE , H IROTADA KOBAYASHI , K EIJI M ATSUMOTO , B EN T ONER , AND T HOMAS
V IDICK: Entangled games are hard to approximate. SIAM J. Comput., 40(3):848–877, 2011.
Preliminary version in FOCS’08. [doi:10.1137/090751293, arXiv:0704.2903] 3
[41] A LEXEI Y. K ITAEV: Lecture given in Hebrew University, Jerusalem, Israel, 1999. 2, 11
[42] A LEXEI Y. K ITAEV, A LEXANDER H. S HEN , AND M IKHAIL . N. V YALYI: Classical and Quantum
Computation. American Mathematical Society, 2002. 2
[43] A LEXEI Y. K ITAEV AND J OHN WATROUS: Parallelization, amplification, and exponential time
simulation of quantum interactive proof systems. In Proc. 32nd STOC, pp. 608–617. ACM Press,
2000. [doi:10.1145/335305.335387] 2
[44] H IROTADA KOBAYASHI AND K EIJI M ATSUMOTO: Quantum multi-prover interactive proof systems
with limited prior entanglement. J. Comput. System Sci., 66(3):429–450, 2003. Preliminary version
in ISAAC’02. [doi:10.1016/S0022-0000(03)00035-7, arXiv:cs/0102013] 2
[45] S IMON B. KOCHEN AND E RNST S PECKER: The problem of hidden variables in quantum mechanics.
J. Math. Mech., 17(1):59–87, 1967. JSTOR. 3
[46] R AYMOND L AFLAMME , C ESAR M IQUEL , J UAN PABLO PAZ , AND W OJCIECH H UBERT
Z UREK: Perfect quantum error correcting code. Phys. Rev. Lett., 77(1):198–201, 1996.
[doi:10.1103/PhysRevLett.77.198, arXiv:quant-ph/9602019] 11
[47] L EONID L EVIN: Universal search problems. Problems of Information Transmission, 9(3):115–116,
1973. 1
[48] C ARSTEN L UND , L ANCE F ORTNOW, H OWARD K ARLOFF , AND N OAM N ISAN: Algebraic meth-
ods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146605] 1
[49] D OMINIC M AYERS AND A NDREW YAO: Quantum cryptography with imperfect apparatus. In
Proc. 39th FOCS, p. 503. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743501] 5
[50] M ATTHEW M C K AGUE: Self-testing graph states. In Proc. 6th Conf. Quantum Computation,
Communication, and Cryptography (TQC’11), pp. 104–120. Springer, 2014. [doi:10.1007/978-3-
642-54429-3_7, arXiv:1010.1989] 5
[51] M ATTHEW M C K AGUE: Interactive proofs for BQP via self-tested graph states. Theory of Comput-
ing, 12(3):1–42, 2016. [doi:10.4086/toc.2016.v012a003, arXiv:1309.5675] 31
[52] 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: Mathematical and Theoretical, 45(45):455304, 2012.
[doi:10.1088/1751-8113/45/45/455304, arXiv:1203.2976] 4
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 40
C LASSICAL V ERIFICATION OF Q UANTUM P ROOFS
[53] NATHANIEL DAVID M ERMIN: Simple unified form for the major no-hidden-variables theorems.
Phys. Rev. Lett., 65(27):3373–3376, 1990. [doi:10.1103/PhysRevLett.65.3373] 3
[54] C ARL A. M ILLER AND YAOYUN S HI: Optimal robust self-testing by binary nonlocal XOR games.
In Proc. 8th Conf. Quantum Computation, Communication, and Cryptography (TQC’13), pp.
254–262. Springer, 2013. [doi:10.4230/LIPIcs.TQC.2013.254] 5
[55] C ARL A. M ILLER AND YAOYUN S HI: Robust protocols for securely expanding randomness and
distributing keys using untrusted quantum devices. J. ACM, 63(4):33, 2016. Preliminary version in
STOC’14. [doi:10.1145/2885493, arXiv:1402.0489] 10
[56] A NAND NATARAJAN AND T HOMAS V IDICK: Constant-soundness interactive proofs for local
Hamiltonians, 2015. [arXiv:1512.02090] 6
[57] A NAND NATARAJAN AND T HOMAS V IDICK: Robust self-testing of many-qubit states, 2016.
Conference version STOC’17. [arXiv:1610.03574] 6
[58] ROBERTO O LIVEIRA AND BARBARA M. T ERHAL: The complexity of quantum spin systems
on a two-dimensional square lattice. Quantum Inf. Comput., 8(10):900–924, 2008. [arXiv:quant-
ph/0504050] 11
[59] T OBIAS J. O SBORNE: Hamiltonian complexity. Reports on Progress in Physics, 75(2):022001,
2012. [doi:10.1088/0034-4885/75/2/022001, arXiv:1106.5875] 2
[60] A SHER P ERES: Incompatible results of quantum measurements. Physics Letters A, 151(3–4):107–
108, 1990. [doi:10.1016/0375-9601(90)90172-K] 3
[61] S. P IRONIO , A. ACÍN , S. M ASSAR , A. B OYER DE LA G IRODAY, D. N. M ATSUKE -
VICH , P. M AUNZ , S. O LMSCHENK , D. H AYES , L. L UO , T. A. M ANNING , AND C. M ON -
ROE : Random numbers certified by Bell’s theorem. Nature, 464(7291):1021–1024, 2010.
[doi:10.1038/nature09008, arXiv:0911.3427] 10
[62] ROBERT R AUSSENDORF, DANIEL E. B ROWNE , AND H ANS J. B RIEGEL: Measurement-
based quantum computation on cluster states. Phys. Rev. A, 68(2):022312, 2003.
[doi:10.1103/PhysRevA.68.022312, arXiv:quant-ph/0301052] 3
[63] 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, 5, 6, 10, 18, 20
[64] A DI S HAMIR: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146609] 1
[65] YAOYUN S HI: Both Toffoli and controlled-NOT need little help to do universal quantum computing.
Quantum Inf. Comput., 3(1):84–92, 2003. [arXiv:quant-ph/0205115] 33
[66] B ORIS S. T SIREL’ SON: Quantum generalizations of Bell’s inequality. Letters in Mathematical
Physics, 4(2):93–100, 1980. [doi:10.1007/BF00417500] 10
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 41
Z HENGFENG J I
[67] W IM VAN DAM , F RÉDÉIC 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] 5
[68] U MESH VAZIRANI AND T HOMAS V IDICK: Certifiable quantum dice: or, true random number
generation secure against quantum adversaries. In Proc. 44th STOC, pp. 61–76. ACM Press, 2012.
[doi:10.1145/2213977.2213984, arXiv:1111.6054] 10
[69] U MESH VAZIRANI AND T HOMAS V IDICK: Fully device-independent quantum key dis-
tribution. Phys. Rev. Lett., 113(14):140501, 2014. Conference version in ITCS’14.
[doi:10.1103/PhysRevLett.113.140501, arXiv:1210.1810] 10
[70] T HOMAS V IDICK: Three-player entangled XOR games are NP-hard to approximate. SIAM J.
Comput., 45(3):1007–1063, 2016. Preliminary version in FOCS’13. [doi:10.1137/140956622,
arXiv:1302.1242] 3, 11
[71] T HOMAS V IDICK AND J OHN WATROUS: Quantum proofs. Foundations and Trends in Theoretical
Computer Science, 11(1–2):1–215, 2015. [doi:10.1561/0400000068, arXiv:1610.01664] 2
[72] J OHN WATROUS: PSPACE has constant-round quantum interactive proof systems. Theoret. Comput.
Sci., 292(3):575–588, 2003. Preliminary version in FOCS’99. [doi:10.1016/S0304-3975(01)00375-
9] 2
[73] J OHN WATROUS: Zero-knowledge against quantum attacks. SIAM J. Comput., 39(1):25–58, 2009.
Preliminary version in STOC’06. [doi:10.1137/060670997, arXiv:quant-ph/0511020] 2
[74] R EINHARD F. W ERNER: Quantum states with Einstein-Podolsky-Rosen correlations admitting a
hidden-variable model. Phys. Rev. A, 40(8):4277–4281, 1989. [doi:10.1103/PhysRevA.40.4277] 4
AUTHOR
Zhengfeng Ji
Centre for Quantum Software and Information
School of Software
Faculty of Engineering and Information Technology
University of Technology Sydney, NSW, Australia
Zhengfeng Ji uts edu au
http://www.uts.edu.au/staff/zhengfeng.ji
ABOUT THE AUTHOR
Z HENGFENG J I graduated from Tsinghua University in 2007; his advisor was Mingsheng
Ying. His interests in the theory of quantum multiprover interactive proof systems and
nonlocal games were influenced by Richard Cleve and John Watrous, from the Institute
for Quantum Computing (IQC) at the University of Waterloo, while he was a postdoctoral
fellow at IQC.
T HEORY OF C OMPUTING, Volume 15 (5), 2019, pp. 1–42 42