Authors Salman Beigi, Peter Shor, John Watrous,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117
www.theoryofcomputing.org
Quantum Interactive Proofs
with Short Messages
Salman Beigi∗ Peter Shor† John Watrous‡
Received: March 31, 2010; published: April 5, 2011.
Abstract: This paper considers three variants of quantum interactive proof systems in
which short (meaning logarithmic-length) messages are exchanged between the prover and
verifier. The first variant is one in which the verifier sends a short message to the prover, and
the prover responds with an ordinary, or polynomial-length, message; the second variant is
one in which any number of messages can be exchanged, but where the combined length
of all the messages is logarithmic; and the third variant is one in which the verifier sends
polynomially many random bits to the prover, who responds with a short quantum message.
We prove that in all of these cases the short messages can be eliminated without changing
the power of the model, so the first variant has the expressive power of QMA and the second
and third variants have the expressive power of BQP. These facts are proved through the use
of quantum state tomography, along with the finite quantum de Finetti theorem for the first
variant.
ACM Classification: F.1.2, F.1.3
AMS Classification: 68Q12, 68Q10, 81P68
Key words and phrases: quantum interactive proof systems, quantum state tomography, quantum
de Finetti theorem, quantum computation
∗ Research partially supported by NSF under Grant No. PHY-0803371 and by NSA/ARO under Grant No. W911NF-09-1-
0442.
† Research supported in part by NSF grant CCF-0829421, and by funds provided by the W. M. Keck Foundation Center for
Extreme Quantum Information Theory.
‡ Research supported by NSERC, CIFAR, MITACS and QuantumWorks.
2011 Salman Beigi, Peter Shor, and John Watrous
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2011.v007a007
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
1 Introduction
The interactive proof system model extends the notion of efficient proof verification to an interactive
setting, where a computationally unrestricted prover tries to convince a computationally bounded verifier
that an input string satisfies a particular fixed property. They have been studied extensively in computa-
tional complexity theory since their introduction over 25 years ago [9, 10, 2, 3], and as a result much is
known about them. (See [1] and [7], for instance, for further discussions of classical interactive proof
systems.)
Quantum interactive proof systems are a natural quantum computational extension of the interactive
proof system model, where the prover and verifier can perform quantum computations and exchange
quantum information. The expressive power of quantum interactive proofs is no different from classical
interactive proofs: it holds that QIP = PSPACE = IP, and therefore any problem having a quantum
interactive proof system also has a classical one [14, 19, 22]. However, quantum interactive proof systems
may be significantly more efficient than classical interactive proofs in terms of the number of messages
they require, as every problem in PSPACE has a quantum interactive proof system requiring just three
messages to be exchanged between a prover and verifier [24, 17]. This is not possible classically unless
AM = PSPACE, an equality that implies the collapse of the polynomial-time hierarchy [3, 11].
In this paper we consider quantum interactive proof systems in which some of the messages are short,
by which we mean that the messages consist of a number of qubits that is logarithmic in the input length.
Three particular variants of quantum interactive proofs with short messages are considered. The first
variant is one in which the verifier sends a short message to the prover, and the prover responds with an
ordinary, or polynomial-length, message. We prove that this model has the expressive power of QMA.
The second variant is one in which any number of messages can be exchanged between the prover and
verifier, but where the combined length of all the messages is logarithmic. We prove that this model has
the expressive power of BQP. The third variant is one in which the verifier sends polynomially many
random bits to the prover, who responds with a short quantum message. We prove that this model also
has the expressive power of BQP. Thus, in each of these three cases, logarithmic-length messages are
effectively worthless and can be removed without changing the power of the model.
It should be noted that classical analogues of these results are immediate. For instance, one can enu-
merate all logarithmic-length interactions between a classical verifier and prover in polynomial time, and
this implies that a classical variant of our second model has the expressive power of BPP. This argument,
however, does not work in the quantum case: one would need to iterate over an exponential number of
logarithmic-length quantum interactions to be sure that every interaction is closely approximated.
To illustrate the basic idea through which our results are proved, consider the following simplification
of our second model: instead of an arbitrary number of messages with logarithmic combined length, there
is only one logarithmic-length message, sent by the prover to the verifier. Upon receiving this logarithmic-
length message from the prover, the verifier applies a binary measurement {Pacc , Prej } to decide whether
to accept or reject. The corresponding complexity class is denoted QMAlog , and was proved to be
equal to BQP by Marriott and Watrous [20] using their error reduction method for QMA. Our methods
lead to a different proof that QMAlog = BQP. We first note that the verifier’s maximum acceptance
probability is the maximum eigenvalue of Pacc . Although Pacc acts on a logarithmic number of qubits, it is
given by a polynomial-size circuit, so one cannot directly compute the matrix representation of Pacc in
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 102
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
polynomial time. Nevertheless, using quantum process tomography, one can perform the measurement
{Pacc , Prej } on polynomially many known states, and then compute an accurate approximation of Pacc
using the data collected. The matrix representation of Pacc has only polynomially many entries, so the
approximation may be represented explicitly. One then simply computes the maximum eigenvalue of
this approximation. (Instead of considering quantum process tomography on measurements, we actually
consider quantum state tomography on the normalized Choi-Jamiołkowski representation of the quantum
channel corresponding to the measurement in this paper. The two approaches are equivalent, but the
second one unifies the arguments made in the different sections of the paper.)
In addition to quantum state tomography and the Choi-Jamiołkowski representation of quantum
channels, the finite quantum de Finetti theorem is a useful tool in this work. Suppose that we are given
several copies of an unknown quantum state, and we want to verify that it is close to some given state.
Using quantum state tomography on the copies, one can find an approximation of the unknown state and
solve the problem. In an adversarial setting represented by a potentially dishonest prover, however, one
may not be guaranteed that the states are indeed copies of the same unknown state—and there could even
be entanglement among different copies. To overcome these difficulties, we use the finite quantum de
Finetti theorem to reduce the problem to the first case.
One possible application of our work is to the design of new quantum algorithms or QMA verification
procedures. Although we do not yet have interesting examples, we believe it is possible that an intuition
about quantum interactive proof systems with short messages may lead to new problems being shown to
be in BQP or QMA, based on characterizations of the sort we prove.
The remainder of this paper has the following organization. Section 2 discusses some of the back-
ground information needed for the rest of the paper, including background on the Choi-Jamiołkowski
representation of quantum channels, quantum state tomography, the finite quantum de Finetti theorem,
and quantum interactive proof systems. Sections 3, 4, and 5 then discuss the three variants of quantum
interactive proof systems with short messages described above. A couple of open problems are described
in Section 6.
2 Background
We assume the reader is familiar with quantum information and computation, including the basic quantum
complexity classes BQP and QMA, simple properties of mixed states, measurements, channels, and so
on [16, 21]. The purpose of the present section is to highlight background knowledge on three topics,
represented by the three subsections below, that are particularly relevant to this paper. These topics are:
the Choi-Jamiołkowski representation of quantum channels, quantum state tomography, and quantum
interactive proof systems.
Before discussing these three topics, it is appropriate to mention a few simple points of notation and
terminology. Throughout this paper we let Σ = {0, 1} denote the binary alphabet, and for each k ∈ N
we write C(Σk ) to denote the finite-dimensional Hilbert space whose standard basis vectors are indexed
by Σk (i. e., the Hilbert space associated with a k-qubit quantum register). The Dirac notation is used to
describe vectors in spaces of this sort.
For a given space Q = C(Σk ), we write L (Q) to denote the space of all linear mappings from Q to
itself, which is associated with the space of all complex matrices with rows and columns indexed by Σk
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 103
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
in the usual way. The subsets of this space representing the positive semidefinite operators and density
operators on Q are denoted Pos (Q) and D (Q), respectively. A standard inner product on L (Q) is defined
as hX,Y i = Tr(X ∗Y ) for all X,Y ∈ L (Q) (where X ∗ denotes the adjoint,
√ or conjugate-transpose, of X).
∗
The trace norm of an operator X ∈ L (Q) is defined as kX k1 = Tr X X, and the spectral (or operator)
norm of X is denoted kX k.
2.1 Quantum channels and the Choi-Jamiołkowski representation
A quantum channel from a k-qubit space Q = C(Σk ) to an `-qubit space R = C(Σ` ) is a completely
positive and trace-preserving linear mapping of the form Φ : L (Q) → L (R). (A mapping Φ is completely
positive if Φ ⊗ 1L(S) is positive for every choice of a space S = C(Σm ), meaning that it maps positive
semidefinite operators to positive semidefinite operators. To say that Φ is trace-preserving means that
Tr(Φ(ρ)) = Tr(ρ) for all operators ρ.) We will write C (Q, R) to denote the set of all such quantum
channels. For any quantum channel Φ ∈ C (Q, R) one defines the (normalized) Choi-Jamiołkowski
representation [15, 4] of Φ as
1
ρ = k ∑ Φ(|yihz|) ⊗ |yihz| . (2.1)
2 y,z∈Σk
In other words, this is the `√+ k qubit state that results from applying Φ to one-half of k pairs of qubits in
the |φ + i = (|00i + |11i)/ 2 state.
The action of the mapping Φ can be recovered from its normalized Choi-Jamiołkowski representation
in the following way that makes use of post-selection. Suppose that Q and Q0 are k-qubit registers and R
is an `-qubit register, that the pair (R, Q0 ) is initialized to the state ρ as defined by Φ in (2.1), and that Q
is in an arbitrary quantum state (and is possibly entangled with additional registers not including Q0 and
R). Consider the following procedure:
1. Measure each qubit of Q together with its corresponding qubit in Q0 with respect to the Bell basis.
2. If every one of these k measurements results in an outcome corresponding to the Bell state |φ + i, then
output “success,” else output “failure.”
This procedure gives the outcome “success” with probability 4−k , and conditioned on success the
register R is precisely as it would be had it resulted from the channel Φ being applied to Q. (The registers
Q and Q0 can safely be discarded if the procedure succeeds.) To see this, assume first that the joint state
of (R, Q0 , Q) is ρ ⊗ ξ before the measurement takes place. Then the (unnormalized) state of R after the
measurements are performed, assuming the end result is “success,” is
1 1 1
∑0 k Φ(|yihz|)hy0 |yihz|z0 ihy0 |ξ |z0 i = 4k ∑ k Φ (|yihy| ξ |zihz|) = 4k Φ(ξ ) .
22k y,y0 ,z,z ∈Σ y,z∈Σ
The probability of success is therefore 4−k , and conditioned on this outcome the process implements
the channel Φ. In our applications, k will be logarithmic in the size of the problem, in which case Φ is
implemented with an inverse-polynomial probability of success. The fact that this process implements
the channel Φ exactly for all density operators ξ implies that it also operates correctly in the case that Q
is entangled with additional registers.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 104
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
2.2 Quantum state tomography
Quantum state tomography is the process by which an approximate description of an unknown quantum
state is obtained by measurements on many independent copies of the unknown state. To be more
precise, let Q = C(Σk ) denote the space corresponding to a k-qubit register, and suppose that Q1 , . . . , QN
are k-qubit quantum registers independently prepared in an unknown k-qubit state ρ ∈ D (Q). The
purpose of quantum state tomography is to obtain an explicit description of a k-qubit state that closely
approximates ρ.
One way to perform quantum state tomography is through the use of an information-complete
measurement. A measurement {Pa : a ∈ Γ} on k-qubit registers is information-complete if and only if the
set {Pa : a ∈ Γ} spans the entire 4k -dimensional space L (Q). When such a measurement is performed on
a k-qubit state ρ, each measurement outcome is obtained with probability
p(a) = hPa , ρi .
Based on the assumption that {Pa : a ∈ Γ} is information-complete, this vector p of probabilities uniquely
determines the state ρ. A close approximation of p, which may be obtained by sufficiently many
independent measurements, leads to an approximate description of ρ.
The accuracy of an approximation based on the process just described naturally depends on the
choice of an information-complete measurement as well as the specific notion of approximation that is
considered. Our interest will be on the trace distance kρ − σ k1 between the approximation σ and the true
state ρ. To describe the “quality” of an information-complete measurement, it is appropriate to describe
the specific process that is used to reconstruct ρ from the vector of probabilities p.
For any spanning set {Pa : a ∈ Γ} of L (Q), there exists a set {Ma : a ∈ Γ} ⊆ L (Q) that satisfies
∑ Ma hPa , Xi = X
a∈Γ
for every X ∈ L (Q). (One may find such a set {Ma : a ∈ Γ} by solving a system of linear equations.)
The set {Ma : a ∈ Γ} allows one to reconstruct a given state from the measurement outcome probabilities
it generates. This set is uniquely determined when {Pa : a ∈ Γ} has exactly 4k elements (i. e., is a
basis), and hereafter we will restrict our attention to this case. Notice that if ρ is a density matrix, the
coefficients p(a) = hPa , ρi form a probability distribution; and if q is a probability vector that represents
an approximation to p it holds that
ρ − ∑ q(a)Ma = ∑ p(a)Ma − ∑ q(a)Ma ≤ ∑ | p(a) − q(a)| kMa k1 ≤ k p − qk1 max kMa k1 .
a∈Γ a∈Γ a∈Γ a∈Γ a∈Γ
1 1
It is therefore desirable that the maximum trace norm over the set {Ma : a ∈ Γ} determined by the
measurement {Pa : a ∈ Γ} is as small as possible.
There is one additional consideration that is sometimes relevant, which is that the approximation
∑ q(a)Ma
a∈Γ
may fail to be positive semidefinite, and therefore fail to represent a valid quantum state. In this
situation one can find a quantum state near to the approximation by renormalizing the positive part of
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 105
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
the approximation. For the applications of tomography in this paper, however, this issue may safely be
disregarded, as non-positive approximations of density operators will still provide valid approximations
to the quantities we are interested in.
An example of an information-complete measurement on a single qubit is given by the following
matrices:
√ ! √ !
2+ 2 1+i 2− 2 1−i
8 8√ 8 8√
P0 = , P1 = ,
1−i 2− 2 1+i 2+ 2
8 8 8 8
√ ! √ !
2+ 2 −1−i 2− 2 −1+i
8 8√ 8 8√
P2 = , P3 = .
−1+i 2− 2 −1−i 2+ 2
8 8 8 8
The corresponding set {M0 , M1 , M2 , M3 } described above is given by
√ ! √ !
1+ 2 1− 2
2 1 + i 2 1 − i
M0 = √ , M1 = √ ,
1− 2
1−i 2 1 + i 1+2 2
√ ! √ !
1+ 2 1− 2
2 −1 − i 2 −1 + i
M2 = √ , M3 = √ .
1− 2 1+ 2
−1 + i 2 −1 − i 2
√
It holds that kMa k1 = 10 < 4 for a ∈ Γ = {0, 1, 2, 3}. The set {P0 , P1 , P2 , P3 } is not an optimal
information-complete measurement, in the sense that maxa kMa k1 could be made smaller for an al-
ternate choice of the measurement, but it has the advantage of being simple to describe and can be
implemented exactly by a quantum circuit composed of Hadamard, controlled-not, and π/8-phase gates,
and measurement in the standard basis.
An information-complete measurement for k qubits may be obtained by taking tensor products of the
above matrices. More specifically, for each x ∈ Γk , let us define 2k × 2k matrices Px and Mx as
Px = Px1 ⊗ · · · ⊗ Pxk and Mx = Mx1 ⊗ · · · ⊗ Mxk .
Then {Px : x ∈ Γk } is an information-complete measurement, and its corresponding set is given by
{Mx : x ∈ Γk }. By the multiplicativity of the trace norm, it holds that kMx k1 = 10k/2 < 4k for every k.
Now, let us suppose that ρ is a quantum state on k qubits, and tomography (using the measurements
just described) is performed on N copies of ρ. More precisely, the measurement {Px } is performed
independently on each of the N copies of ρ, a probability distribution q : Γk → [0, 1] is taken to be the
frequency distribution of the outcomes, and an approximation
H = ∑ q(x)Mx
x∈Γk
to ρ is computed. We require the following bound on the expected accuracy of this approximation. (Of
course, nothing can be said in the worst case, as any sequence of measurement outcomes could occur
with very small probability in general.)
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 106
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
Lemma 2.1. For any choice of ε > 0, taking N ≥ 210k /ε 3 will guarantee that with probability at least
1 − ε, the estimate H satisfies kρ − H k1 < ε.
Proof. For any δ > 0, and any fixed choice of x ∈ Γk , it follows from Hoeffding’s inequality that
Pr [|q(x) − p(x)| ≥ δ ] ≤ 2 exp −2Nδ 2 .
By the union bound it follows that
h i h i
Pr kq − pk1 ≥ 4k δ ≤ Pr |q(x) − p(x)| ≥ δ for at least one x ∈ Γk ≤ 22k+1 exp −2Nδ 2 .
Setting δ = ε/16k and using the inequality e−α < 1/α for all α > 0, we have
h i
Pr kq − pk1 ≥ ε/4k ≤ 22k+1 exp −22k+1 /ε < ε .
It follows that
Pr[kρ − H k1 ≥ ε] ≤ Pr[kq − pk1 ≥ ε/4k ] < ε.
The notion of quantum process tomography has also been considered, where a quantum measurement
or channel is approximated through many independent evaluations of an appropriate sort. (See for
example [21].) In this paper, however, it is not necessary to consider this sort of tomography as being
any different from state tomography. Specifically, we will approximate channels (and measurements,
modeled as channels) by evaluating them on maximally entangled states, followed by ordinary quantum
state tomography on the normalized Choi-Jamiołkowski representations that result.
2.3 The finite quantum de Finetti theorem
Suppose that Q1 , . . . , QN are all k-qubit registers. A state on (Q1 , . . . , QN ) is said to be symmetric if it
is invariant under any permutation of its registers. For instance, any product state of the form ρ ⊗N is
symmetric, and any convex combination of such states is symmetric as well. Note, however, that there
are symmetric states that cannot be written as convex combinations of symmetric product states as above;
the pure state
1
|ψ i = √ ∑ |xi ⊗ · · · ⊗ |xi
2k x∈Σk
provides one such example. Nevertheless, by tracing out any subsystem of |ψ i, the resulting reduced
density matrix is in the convex hull of the set of symmetric product states. The following theorem [18, 5]
generalizes this observation.
Theorem 2.2 (The finite quantum de Finetti theorem). Let ρN+m be a symmetric state over registers
(Q1 , . . . , QN+m ), and let ρN = TrQN+1 ···QN+m (ρN+m ). There exist states {ξ j } and associated probabilities
{p j } such that
2k+1 N
ρN − ∑ p j ξ j⊗N ≤ .
j 1 N +m
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 107
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
2.4 Quantum interactive proof systems
Quantum interactive proof systems are a natural quantum analogue of ordinary, classical interactive proof
systems, where the prover and verifier may process and exchange quantum information. We will only
consider quantum interactive proof systems having an even number of messages in this paper, so for
simplicity we will restrict our discussion to this case.
For t being a function of the form t : N → N, we define a t-round (or (2t)-message) quantum verifier
V to be a collection of quantum circuits
V = Vx, j : x ∈ Σ∗ , 0 ≤ j ≤ t(|x|)
that can be generated in polynomial-time given x and j. We will generally write t rather than t(|x|)
hereafter in this paper, keeping in mind that t might vary with the input length. We assume that the
verifier’s circuits are composed of standard unitary quantum gates (controlled-not, Hadamard, and π/8-
phase gates, let us say), as well as ancillary and erasure gates. Included in the description of these circuits
is a specification of which input and output qubits are to be considered private memory qubits and which
are considered message qubits. The message qubits refer to qubits that are sent to or received from
a prover (to be described shortly). The following properties are required of the circuits describing a
verifier:
1. For each x, the circuit Vx,0 takes no input qubits, and the circuit Vx,t produces a single output qubit
(called the acceptance qubit).
2. There exist functions v1 , v2 , . . . such that Vx, j−1 outputs v j (|x|) private memory qubits and Vx, j inputs
v j (|x|) private memory qubits for 1 ≤ j ≤ t.
3. There exist functions q1 , q2 , . . . and r1 , r2 , . . . that specify the number of message qubits the verifier
sends to or receives from the prover on each round, for a given input length. More precisely, each
circuit Vx, j−1 outputs q j (|x|) message qubits and each circuit Vx, j inputs r j (|x|) message qubits, for
1 ≤ j ≤ t.
Similar to the function t, we will often omit the argument |x| from the functions v j , q j , and r j for the
sake of readability. When it is convenient, we will refer to the message qubits sent from the verifier to the
prover as question qubits and qubits sent from the prover to the verifier as response qubits.
A t-round (or (2t)-message) prover is defined in a similar way to a t-round verifier, but no computa-
tional restrictions are made. Specifically, a t-round prover is a collection of quantum channels
P = Px, j : x ∈ Σ∗ , 1 ≤ j ≤ t(|x|) .
Again, the input and output qubits of these channels are specified as private memory qubits or message
qubits. When a particular prover P is considered to interact with a given verifier V , one naturally assumes
that they agree on the number of messages and the number of qubits sent in each message, as suggested
by Figure 1. There is no restriction on p j , the number of private memory qubits used by the prover at the
j-th round—but although each p j could in principle be unbounded, it is not difficult to show that for any
choice of a prover, there is an equivalent one giving rise to precisely the same behavior as the first that
uses at most a polynomial number of private memory qubits [13].
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 108
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
v1 v2 v3
accept
Vx,0 Vx,1 Vx,2 Vx,3 or
reject
q1 r1 q2 r2 q3 r3
Px,1 p1 Px,2 p2 Px,3
Figure 1: An illustration of an interaction between a prover and verifier in a quantum interactive proof
system. In the picture it is assumed that t = 3. The labels v j , p j , q j and r j on the arrows refer to the
number of qubits represented by each arrow.
Now, on a given input string x, the prover P and verifier V have an interaction by composing their
circuits/channels as described in Figure 1. The maximum acceptance probability for a given verifier V on
an input x refers to the maximum probability for the circuit Vx,t to output 1, assuming it is measured in the
standard basis, over all choices of a compatible prover P. It is always the case that a maximal probability
is achieved by some prover.
Classes of promise problems may be defined by quantum interactive proof systems in a variety of
ways. We will delay the definitions of the classes we consider to the individual sections in which they are
discussed.
3 Two-message quantum interactive proofs with short questions
The first specific variant of quantum interactive proof systems we consider are those in which just a
single round of communication takes place, with the first message being short (at most logarithmic in
length) and the second message being normal (at most polynomial in length). In particular, let us say
that a 1-round verifier V is a [log, poly] quantum verifier if the number q = q1 of question qubits it sends
during the first and only round of communication satisfies q(n) = O(log n). For functions of the form
a, b : N → [0, 1] we define QIP([log, poly], a, b) to be the class of all promise problems B = (Byes , Bno ) for
which there exists a [log, poly] quantum verifier V with completeness and soundness probability bounds a
and b, respectively. In other words, V satisfies the following properties:
1. For every string x ∈ Byes , there exists a prover P compatible with V that causes V to accept x with
probability at least a(|x|).
2. For every string x ∈ Bno , and every prover P compatible with V , it holds that P causes V to accept x
with probability at most b(|x|).
For a wide range of choices of a and b, these classes coincide with QMA as the following theorem states.
Theorem 3.1. Let a, b : N → (0, 1) be polynomial-time computable functions such that a(n) − b(n) ≥
1/p(n) for some polynomial p. Then QIP([log, poly], a, b) = QMA.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 109
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
Proof. It is clear that QMA ⊆ QIP([log, poly], a, b) for any choice of a and b that satisfy the conditions
of the theorem, so our goal is to prove the reverse containment.
Let B = (Byes , Bno ) be a promise problem in QIP([log, poly], a, b), and let V be a [log, poly] verifier
that witnesses this fact. We write q (as above) to denote the number of question qubits the verifier V
sends, and write r to denote the number of response qubits V receives. As V is a [log, poly] verifier it
holds that q(n) = O(log n). For a fixed input x, we will write Q = C(Σq ) to denote the question space and
R = C(Σr ) to denote the response space for V , corresponding to the question and response qubits in the
obvious way.
Our goal is to prove that B ∈ QMA, and to do this we will define a verification procedure (to be
referred to as Arthur) that demonstrates this fact. Suppose P is a prover that interacts with V . For a
fixed input string x, the action of P may be identified with a quantum channel Φ ∈ C (Q, R), and any
such channel defines a quantum state ρ ∈ D (R ⊗ Q) according to its normalized Choi-Jamiołkowski
representation (2.1). We will define Arthur so that he expects to receive many independent copies of
this state. He will check its validity using quantum state tomography, and will use the state to apply the
mapping Φ himself through post-selection.
More specifically, we define Arthur so that he performs the following actions:
1. Input N + m registers (R1 , Q1 ), . . . , (RN+m , QN+m ), where N and m are polynomials in the input length
n to be specified below.
2. Randomly permute the pairs (R1 , Q1 ), . . . , (RN+m , QN+m ), according to a uniformly chosen permuta-
tion π ∈ SN+m , and discard all but the first N + 1 pairs.
3. Perform quantum state tomography on the registers (Q2 , . . . , QN+1 ), and reject if the resulting
approximation is not within trace-distance δ /2 of the completely mixed state 1/2q , for δ to be
specified below.
4. Simulate the original protocol (P,V ) by post-selection using the register pair (R1 , Q1 ). Reject if the
post-selection fails, and otherwise accept or reject as the outcome of the proof system dictates.
To specify N, m and δ , we first set
1
ε=
p4q+1
for p being the polynomial whose reciprocal separates the completeness and soundness probability bounds
a and b. Now set
ε2 210q 2N4q
δ= , N= 3
and m= .
4 (δ /2) ε
Given that q is logarithmic, it holds that N, m, 1/ε and 1/δ are polynomially bounded.
Suppose first that x ∈ Byes , which implies that there exists a prover P that causes V to accept x with
probability at least a. Let Φ denote the quantum channel that describes the behavior of P, and let ρ be the
normalized Choi-Jamiołkowski representation of Φ as described in (2.1). Then for each of the register
pairs (R j , Q j ) being prepared independently in the state ρ, it holds that Arthur rejects in step 3 with
probability at most δ /2 (by Lemma 2.1), and accepts in step 4 with probability at least a/4q (conditioned
on not having rejected in step 3). Arthur therefore accepts with probability at least
δ a a
1− q
> q −ε .
2 4 4
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 110
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
Now let us suppose that x ∈ Bno . We first consider the situation in which the state of the registers
(Q1 , . . . , QN+1 ) at the beginning of step 3 has the form
ξ ⊗(N+1)
for some density operator ξ ∈ D (Q). There are two cases to consider: one is that kξ − 1/2q k1 < δ and
the other is that kξ − 1/2q k1 ≥ δ .
If it is the case that kξ − 1/2q k1 < δ , then by the Fuchs-van de Graaf inequalities [6] there must exist
a state ρ ∈ D (R ⊗ Q) satisfying TrR (ρ) = 1/2q that is within trace distance ε of the state of (R1 , Q1 ). To
be more precise, consider a fixed purification |ψ i of the state of (R1 , Q1 ) with an auxiliary register E. As
ξ = TrR1 ⊗E (|ψ ihψ |) has a high fidelity with 1/2q , and due to the characterization of fidelity in terms of
purifications, there exists a purification of 1/2q over (R, Q, E) that has a large inner product with |ψ i.
Then ρ can be chosen as the reduced density matrix of this pure state over (R, Q). Given that x ∈ Bno , the
state ρ would cause acceptance in step 4 with probability at most b/4q , and therefore acceptance may
occur in the case at hand with probability at most b/4q + ε.
If, on the other hand, it holds that kξ − 1/2q k1 ≥ δ , then rejection must occur in step 3 with
probability at least 1 − δ /2, so Arthur accepts with probability at most δ /2 (which of course is smaller
than b/4q + ε).
Thus, in both cases, acceptance occurs with probability at most b/4q + ε. It follows that if the registers
(Q1 , . . . , QN+1 ) are, at the beginning of step 3, in any state of the form
⊗(N+1)
∑ p jξ j (3.1)
j
(i. e., a convex combination of states of the form just discussed), acceptance may occur with probability
at most b/4q + ε.
Finally, by the finite quantum de Finetti theorem (Theorem 2.2), the state of (Q1 , . . . , QN+1 ) after step
2 is within trace-distance ε of a state of the form (3.1), and therefore the probability of acceptance is at
most b/4q + 2ε in the general case.
Given that a/4q − ε and b/4q + 2ε are efficiently computable and separated by the reciprocal of a
polynomial, it holds that B is in QMA as claimed.
4 Quantum interactive proofs with short interactions
Next we consider quantum interactive proof systems restricted so that the total number of qubits exchanged
by the prover and verifier is logarithmic. We prove that any problem having such a quantum interactive
proof system is contained in BQP. This fact represents a significant generalization of the equality
QMAlog = BQP proved in [20]. Like the result of the previous section, our proof of this fact is based on
quantum state tomography. In addition we will make use of the quantum games framework of [13].
It is clear that any quantum interactive proof system allowing at most a logarithmic number of qubits
to be exchanged can be simulated by one in which a logarithmic number of single-qubit messages are
permitted, because any number of these messages could consist of meaningless “dummy” qubits that
are interspersed with the qubits sent by the other party. To be more precise, let t(n) = O(log n) and
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 111
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
Vx,0 Vx,1 Vx,2 Vx,3 Vx,4
Px,1 Px,2 Px,3 Px,4
Figure 2: Illustration of a quantum interactive proof in which the messages are single bits.
consider a t-round quantum interactive proof system in which each message consists of a single qubit
(i. e., q1 = r1 = · · · = qt = rt = 1). We will write QIPlog (a, b) to denote the class of problems having
quantum interactive proof systems of this sort having completeness and soundness probability bounds a
and b, respectively. As the following theorem states, this model offers no computational advantage over
BQP.
Theorem 4.1. Let a, b : N → (0, 1) be polynomial-time computable functions such that a(n) − b(n) ≥
1/p(n) for some polynomial p. Then QIPlog (a, b) = BQP.
Proof. It is clear that BQP ⊆ QIPlog (a, b), and so it remains to prove the reverse containment. To this
end let B = (Byes , Bno ) be a promise problem in QIPlog (a, b), and let V be a verifier that witnesses this
fact. As above, let t(n) = O(log n) denote the number of rounds of communication this verifier exchanges
with any compatible prover. For a fixed input string x, we will write Q1 , . . . , Qt to denote copies of the
space C(Σ) associated with the t single-qubit messages that V sends to a given prover P, and we will
write R1 , . . . , Rt to denote copies of the same space C(Σ) corresponding to the response qubits of P.
The action of V , on a given input string x, is determined by t + 1 quantum circuits Vx,0 , . . . ,Vx,t as
defined in Section 2. Figure 2 illustrates an interaction between V and a prover P for the case that t = 4.
Now consider the channel Φ obtained from the circuits Vx,0 , . . . ,Vx,t by setting all of the response qubits
the verifier receives from the prover as input qubits and setting all of the question qubits sent by the
verifier to the prover as output qubits. More precisely, Φ maps states on the space R1 ⊗ · · · ⊗ Rt to states
on the space A ⊗ Q1 ⊗ · · · ⊗ Qt , where A denotes the single-qubit space associated with the acceptance
qubit. Figure 3 illustrates this channel for the protocol pictured in Figure 2.
Next, let
1
ρ = t ∑ Φ(|yihz|) ⊗ |yihz|
2 y,z∈Σt
be the normalized Choi-Jamiołkowski representation of Φ. The state ρ is obviously efficiently preparable
given a description of V . By independently preparing N = 210(2t+1) /ε 3 copies of ρ, for ε > 0 to be
specified later, and performing quantum state tomography, one obtains a Hermitian operator H on
A ⊗ R1 ⊗ · · · ⊗ Rt ⊗ Q1 ⊗ · · · ⊗ Qt that satisfies kH − ρ k1 < ε with probability at least 1 − ε. Let us also
define
ρ1 = (h1| ⊗ 1) ρ (|1i ⊗ 1) and H1 = (h1| ⊗ 1) H (|1i ⊗ 1)
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 112
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
Φ(σ )
Vx,0 Vx,1 Vx,2 Vx,3 Vx,4
(
σ
Figure 3: The channel Φ associated with the quantum interactive proof from Figure 2.
to denote the projection of these operators on the subspace in which the qubit A is |1i (corresponding to
accept).
Using the terminology of [13], ρ1 is a co-strategy that describes the verifier’s action, and the prover
optimizes the acceptance probability corresponding to ρ1 over all strategies. (Strategies are defined in a
similar way to co-strategies as above, but with respect to the prover’s action.) Given any strategy X of the
prover, the acceptance probability is proportional to the inner product of ρ1 and X. More precisely, the
maximum acceptance probability is the optimal value of the following optimization problem:
maximize: 2t hρ1 , Xi
subject to: X ∈ St
where St ⊂ Pos (R1 ⊗ · · · ⊗ Rt ⊗ Q1 ⊗ · · · ⊗ Qt ) is the space of all strategies. It is shown in [13] that St is
characterizes as S0 = 1 and
S j = X ≥ 0 : TrR j (X) = Y ⊗ 1Q j , Y ∈ S j−1
for j ≥ 1. This characterization of St turns the above optimization problem to a semidefinite program—at
which point we simply replace ρ1 with its approximation H1 .
It is clear that Tr(X) = 2t for every X ∈ St , and therefore
2t hρ1 , Xi − 2t hH1 , Xi ≤ 2t kX k kρ1 − H1 k1 ≤ 4t kρ1 − H1 k1 ≤ 4t kρ − H k1
for every X ∈ St . By taking
1
ε=
4t+1 p
for instance, one may therefore distinguish the cases x ∈ Byes and x ∈ Bno with probability 1 − ε, by
approximately solving the semidefinite program described above (using the ellipsoid method [12] for the
sake of concreteness).
We note that precisely the same argument allows one to conclude that quantum refereed games,
as defined in [13], allowing for at most a logarithmic number of qubits of communication, offer no
computational power beyond BQP. In other words, QRGlog = BQP, for QRGlog defined appropriately.
The details are left to the reader.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 113
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
5 Two-message quantum interactive proofs with short answers
In light of the results of Section 3, one may ask if two-message quantum interactive proofs with short
answers (as opposed to short questions) have the power of QMA or even BQP. If this is true it is likely
to be difficult to show: the graph non-isomorphism problem, which is not known to be in QMA, has a
simple and well-known classical protocol [8] requiring polynomial-length questions and constant-length
answers. (Indeed, every problem in QSZK has a two-message quantum interactive proof system with
a constant-length message from the prover to the verifier, for any choice of constant completeness and
soundness errors [23].)
We can show, however, that public-coin quantum interactive proofs in which the verifier sends
polynomially many random bits to the prover, followed by a logarithmic-length quantum message
response from the prover, have only the power of BQP.
Following a similar terminology to the classical case, we refer to a quantum interactive proof system
in which the verifier’s messages to the prover consist of uniformly-generated random bits as quantum
Arthur–Merlin games. Let us write QAM([poly, log], a, b) to denote the class of promise problems having
two-message quantum Arthur–Merlin games with completeness and soundness probability bounds a and
b, in which Merlin’s response to Arthur has logarithmic length.
Theorem 5.1. Let a, b : N → (0, 1) be polynomial-time computable functions such that a(n) − b(n) ≥
1/p(n) for some polynomial-bounded function p. Then QAM([poly, log], a, b) = BQP.
Proof. Assume that B is a promise problem in QAM([poly, log], a, b), and consider a choice of Arthur
that witnesses this fact. For r(n) = O(log n), and for any choice of an input string x, Arthur chooses a
random string y with length polynomial in |x|, and then measures r = r(|x|) qubits sent by Merlin with
respect to some binary-valued measurement {P0x,y , P1x,y } that depends on x and y. Thus, assuming that
the randomly chosen string is y, the maximum acceptance probability of Arthur is equal to the spectral
norm of P1x,y . So, to find P1x,y (and its norm), we perform quantum state tomography on the normalized
Choi-Jamiołkowski representation of the channel
Φx,y (σ ) = P0x,y , σ |0ih0| + P1x,y , σ |1ih1| ,
which describes Arthur’s measurement.
The following algorithm shows that B ∈ BQP.
1. Choose y uniformly at random (just as Arthur does).
2. Let
1 210(r+1)
ε= and N= .
2r+3 p ε3
Prepare N copies of the state ρ, defined to be the normalized Choi-Jamiołkowski representation of
Φx,y , and perform quantum state tomography on ρ. Let H denote the result. Then, by Lemma 2.1,
with probability at least 1 − ε it holds that kρ − H k1 ≤ ε.
3. Compute the value
αy = 2r k(h1| ⊗ 1)H(|1i ⊗ 1)k .
(It can easily be shown that αy is an approximation of P1x,y .) If αy ≥ 1 then accept. Otherwise,
accept with probability αy and reject otherwise.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 114
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
Because the maximum acceptance probability of Arthur is equal to the expectation value of P1x,y over
the random choice of y, and with probability 1 − ε the approximation αy is within distance 2r ε of P1x,y ,
the above procedure has acceptance probability within 1/(4p) of the maximum acceptance probability of
Arthur. It follows that B ∈ BQP.
6 Open problems
The following two questions have been raised by the anonymous referees. The first one is to find the
expressive power of the following model: the verifier and prover send messages to one other consisting of
a logarithmic number of qubits in total, and at the end the prover sends a polynomial-length message
to the verifier. This model contains QMA, and it might be possible to prove the reverse containment by
combining the ideas in Sections 3 and 4. The second question is a similar one involving an interactive
protocol in which the verifier always sends polynomial-length public-coin messages to the prover, and
the prover replies with quantum messages whose combined length is logarithmic.
References
[1] S ANJEEV A RORA AND B OAZ BARAK: Complexity Theory: A Modern Approach. Cambridge
University Press, 2009. 102
[2] L ÁSZL Ó BABAI: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM
Press, 1985. [doi:10.1145/22145.22192] 102
[3] L ÁSZL Ó BABAI AND S HLOMO M ORAN: Arthur-Merlin games: A randomized proof system, and a
hierarchy of complexity classes. J. Comput. System Sci., 36(2):254–276, 1988. [doi:10.1016/0022-
0000(88)90028-1] 102
[4] M AN -D UEN C HOI: Completely positive linear maps on complex matrices. Linear Algebra Appl.,
10(3):285–290, 1975. [doi:10.1016/0024-3795(75)90075-0] 104
[5] M ATTHIAS C HRISTANDL , ROBERT K ÖNIG , G RAEME M ITCHISON , AND R ENATO R ENNER:
One-and-a-half quantum de Finetti theorems. Comm. Math. Phys., 273(2):473–498, 2007.
[doi:10.1007/s00220-007-0189-3] 107
[6] C HRISTOPHER A. F UCHS AND J EROEN VAN DE G RAAF: Cryptographic distinguishability mea-
sures for quantum-mechanical states. IEEE Trans. Inform. Theory, 45(4):1216–1227, 1999.
[doi:10.1109/18.761271] 111
[7] O DED G OLDREICH: Computational Complexity – A Conceptual Perspective. Cambridge University
Press, 2008. 102
[8] O DED G OLDREICH , S ILVIO M ICALI , AND AVI W IGDERSON: Proofs that yield nothing but their
validity or all languages in NP have zero-knowledge proof systems. J. ACM, 38(1):691–729, 1991.
[doi:10.1145/116825.116852] 114
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 115
S ALMAN B EIGI , P ETER S HOR , AND J OHN WATROUS
[9] S HAFI G OLDWASSER , S ILVIO M ICALI , AND C HARLES R ACKOFF: The knowledge com-
plexity of interactive proof systems. In Proc. 17th STOC, pp. 291–304. ACM Press, 1985.
[doi:10.1145/22145.22178] 102
[10] 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. [doi:10.1137/0218012] 102
[11] S HAFI G OLDWASSER AND M ICHAEL S IPSER: Private coins versus public coins in interactive proof
systems. In S. M ICALI, editor, Randomness and Computation, volume 5 of Advances in Computing
Research, pp. 73–90. JAI Press, 1989. 102
[12] M ARTIN G R ÖTSCHEL , L ÁSZL Ó L OV ÁSZ , AND A LEXANDER S CHRIJVER: Geometric Algorithms
and Combinatorial Optimization. Springer–Verlag, second corrected edition, 1993. 113
[13] G US G UTOSKI AND J OHN WATROUS: Toward a general theory of quantum games. In Proc. 39th
STOC, pp. 565–574. ACM Press, 2007. [doi:10.1145/1250790.1250873] 108, 111, 113
[14] R AHUL JAIN , Z HENGFENG J I , S ARVAGYA U PADHYAY, AND J OHN WATROUS: QIP = PSPACE.
In Proc. 42nd STOC, pp. 573–581. ACM Press, 2010. [doi:10.1145/1806689.1806768] 102
[15] A. JAMIOŁKOWSKI: Linear transformations which preserve trace and positive semidefiniteness of
operators. Rep. Math. Phys., 3(4):275–278, 1972. [doi:10.1016/0034-4877(72)90011-0] 104
[16] A. Y U . K ITAEV, A. H. S HEN , AND M. N. V YALYI: Classical and Quantum Computation.
Volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002. 103
[17] A LEXEI K ITAEV AND J OHN WATROUS: Parallelization, amplification, and exponential time
simulation of quantum interactive proof system. In Proc. 32nd STOC, pp. 608–617. ACM Press,
2000. [doi:10.1145/335305.335387] 102
[18] ROBERT K ÖNIG AND R ENATO R ENNER: A de Finetti representation for finite symmetric quantum
states. J. Math. Phys., 46:122108, 2005. [doi:10.1063/1.2146188] 107
[19] 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. [doi:10.1145/146585.146605]
102
[20] C HRIS M ARRIOTT AND J OHN WATROUS: Quantum Arthur-Merlin games. Comput. Complexity,
14(2):122–152, 2005. [doi:10.1007/s00037-005-0194-x] 102, 111
[21] M ICHAEL A. N IELSEN AND I SAAC L. C HUANG: Quantum Computation and Quantum Information.
Cambridge University Press, 2000. 103, 107
[22] A DI S HAMIR: IP = PSPACE. J. ACM, 39(4):869–877, 1992. [doi:10.1145/146585.146609] 102
[23] J OHN WATROUS: Limits on the power of quantum statistical zero-knowledge. In Proc. 43rd FOCS,
pp. 459–468. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181970] 114
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 116
Q UANTUM I NTERACTIVE P ROOFS WITH S HORT M ESSAGES
[24] J OHN WATROUS: PSPACE has constant-round quantum interactive proof systems. Theoret. Com-
put. Sci., 292(3):575–588, 2003. Preliminary version in Proc. 40th FOCS, 1999, pp. 112–119.
[doi:10.1016/S0304-3975(01)00375-9] 102
AUTHORS
Salman Beigi
School of Mathematics
Institute for Research in Fundamental Sciences (IPM)
Tehran, Iran
salman beigi gmail com
Peter Shor
Department of Mathematics
Massachusetts Institute of Technology
Cambridge, Massachusetts, USA
shor math mit edu
http://www-math.mit.edu/~shor/
John Watrous
Institute for Quantum Computing and School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada
watrous cs uwaterloo ca
http://www.cs.uwaterloo.ca/~watrous/
ABOUT THE AUTHORS
S ALMAN B EIGI received his B. S. at Sharif University of Technology, Tehran in 2004. He
finished his Ph. D. at the MIT Math Department in 2009 under the direction of Peter
Shor, and continued his research as a postdoc at the Institute for Quantum Information at
Caltech. He has recently started a new job at the Institute for Research in Fundamental
Sciences. His interests include quantum complexity theory, quantum coding theory,
photography, and playing daf, a traditional Persian musical instrument.
P ETER S HOR is a professor at MIT. He is known for his factoring algorithm.
J OHN WATROUS is an associate professor in the School of Computer Science at the University
of Waterloo, and is a member of the University of Waterloo’s Institute for Quantum
Computing. He received his Ph. D. in Computer Science from the University of Wisconsin
in 1998, under the supervision of Eric Bach.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 101–117 117