Authors Scott Aaronson, Greg Kuperberg,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157
http://theoryofcomputing.org
Quantum Versus Classical Proofs and Advice
Scott Aaronson∗ Greg Kuperberg†
Received: July 27, 2006; revised: August 23, 2007; published: September 14, 2007.
Abstract: This paper studies whether quantum proofs are more powerful than classical
proofs, or in complexity terms, whether QMA = QCMA. We prove three results about this
q QMA
question. First, we give a “quantum oracle separation” between and QCMA. More
concretely, we show that any quantum algorithm needs Ω 2 n
m+1 queries to find an n-
qubit “marked state” |ψi, even if given an m-bit classical description of |ψi together with
a quantum black box that recognizes |ψi. Second, we give an explicit QCMA protocol
that nearly achieves this lower bound. Third, we show that, in the one previously-known
case where quantum proofs seemed to provide an exponential advantage, classical proofs
are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying
non-membership in finite groups. Under plausible group-theoretic assumptions, we give
a QCMA protocol for the same problem. Even with no assumptions, our protocol makes
only polynomially many queries to the group oracle. We end with some conjectures about
quantum versus classical oracles, and about the possibility of a classical oracle separation
between QMA and QCMA.
ACM Classification: F.1.2, F.1.3
AMS Classification: 03F20, 68Q10, 68Q15, 81P68
Key words and phrases: quantum computing, QMA, black-box groups, oracles, hidden subgroup prob-
lem
∗ MIT. Email: aaronson@csail.mit.edu.
† UC Davis. Email: greg@math.ucdavis.edu.
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2007 Scott Aaronson and Greg Kuperberg DOI: 10.4086/toc.2007.v003a007
S. A ARONSON AND G. K UPERBERG
1 Introduction
If someone hands you a quantum state, is that more “useful” than being handed a classical string with a
comparable number of bits? In particular, are there truths that you can efficiently verify, and are there
problems that you can efficiently solve, using the quantum state but not using the string? These are the
questions that this paper addresses, and that it answers in several contexts.
Recall that QMA, or Quantum Merlin-Arthur, is the class of decision problems for which a “yes”
answer can be verified in quantum polynomial time, with help from a polynomial-size quantum wit-
ness state |ψi. Many results are known about QMA: for example, it has natural complete promise
problems [19], allows amplification of success probabilities [22], and is contained in PP [22]. Raz and
Shpilka [27] have also studied communication complexity variants of QMA.
Yet, as Aharonov and Naveh [3] pointed out in 2002, the very definition of QMA raises a fundamental
question. Namely: is it really essential that the witness be quantum, or does it suffice for the algorithm
verifying the witness to be quantum? To address this question, Aharonov and Naveh defined the class
QCMA, or “Quantum Classical Merlin-Arthur,” to be the same as QMA except that now the witness is
classical.1 We can then ask whether QMA = QCMA. Not surprisingly, the answer is that we don’t know.
If we can’t decide whether two complexity classes are equal, the usual next step is to construct a
relativized world that separates them. This would provide at least some evidence that the classes are
different. But in the case of QMA versus QCMA, even this limited goal has remained elusive.
Closely related to the question of quantum versus classical proofs is that of quantum versus classical
advice. Compared to a proof, advice has the advantage that it can be trusted, but the disadvantage that it
can’t be tailored to a particular input. More formally, let BQP/qpoly be the class of problems solvable in
quantum polynomial time, with help from a polynomial-size “quantum advice state” |ψn i that depends
only on the input length n. Then the question is whether BQP/qpoly = BQP/poly, where BQP/poly
is the class of problems solvable in quantum polynomial time with help from polynomial-size classical
advice. Aaronson [2] showed that BQP/qpoly ⊆ PP/poly, which at least tells us that quantum advice
is not “infinitely” more powerful than classical advice. But, like the QMA versus QCMA question, the
BQP/qpoly versus BQP/poly question has remained open, with not even an oracle separation known.
1.1 Our results
This paper introduces new tools with which to attack QMA versus QCMA and related questions.
First, we achieve an oracle separation between QMA and QCMA, but only by broadening the defi-
nition of “oracle.” In particular, we introduce the notion of a quantum oracle, which is just an infinite
sequence of unitaries U = {Un }n≥1 that a quantum algorithm can apply in a black-box fashion. Just as
a classical oracle models a subroutine to which an algorithm has black-box access, so a quantum oracle
models a quantum subroutine, which can take quantum input and produce quantum output. We are able
to give a quantum oracle that separates QMA from QCMA:
Theorem 1.1. There exists a quantum oracle U such that QMAU 6= QCMAU .
1 Some say that this class would more accurately be called CMQA, for “Classical Merlin Quantum Arthur.” But QCMA
has stuck.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 130
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Similarly, there exists a quantum oracle V such that BQPV /qpoly 6= BQPV /poly.
Theorem 1.1 implies that if QMA = QCMA, then any proof of this fact will require “quantumly
nonrelativizing techniques”: techniques that are sensitive to the presence of quantum oracles. Currently,
we do not know of any quantumly nonrelativizing techniques that are not also classically nonrelativizing.
For this reason, we believe that quantum oracle separations merit the same informal interpretation as
classical oracle separations: almost any argument that one might advance against the former, is also an
argument against the latter! The difference is that quantum oracle results are sometimes much easier to
prove than classical ones. To our knowledge, this paper provides the first example of this phenomenon,
but other examples have since emerged [1, 24].
It might be objected that, even if quantum oracle separations are no less trustworthy than classical
ones, they certainly aren’t more trustworthy, and complexity theorists have known since the celebrated
IP = PSPACE theorem [28] that oracle results sometimes “point in the wrong direction.” We wish to
stress two points in response. First, oracle results provide at least some understanding, thereby opening
the way to further progress. This is particularly true in quantum computing, where even the oracle
results tend to be much less intuitively obvious than they are in the classical world. Second, complexity
theorists do not currently have any nonrelativizing technique for “non-interactive” classes such as QMA
and QCMA even remotely analogous to the arithmetization technique that Shamir [28] used to show
IP = PSPACE. We hope such a technique will someday be discovered.
Underlying Theorem 1.1 is the following lower bound. Suppose a unitary oracle Un acts on n qubits,
and suppose that either (i) Un is the identity, or (ii) there exists a secret n-qubit “marked state” |ψn i such
that Un |ψn i = − |ψn i, but Un |ϕi = |ϕi whenever |ϕi is orthogonal to |ψn i. Then evenpif a quantum
algorithm is given m bits of classical advice about |ψn i, the algorithm still needs Ω 2n /(m + 1)
√
queries to Un to distinguish these cases. Note that when m = 0, we recover the usual Ω 2n lower
bound for Grover search as a special case. At the other extreme, if m ≈ 2n then our bound gives nothing—
not surprisingly, since the classical advice might contain explicit instructions for preparing |ψn i. The
point is that, if m is not exponentially large, then exponentially many queries are needed.
Since |ψn i is an arbitrary 2n -dimensional unit vector, it might be thought obvious that 2Ω(n) bits are
needed to describe that vector. The key point, however, is that the QCMA verifier is given not only a
classical description of |ψn i, but also oracle access to Un . So the question is whether some combination
of these resources might be exponentially more powerful than either one alone. We prove that the answer
is no, using the hybrid argument of Bennett et al. [10] together with geometric results about partitionings
of the unit sphere.
p 4, we show that our lower bound is basically tight, by giving an algorithm that finds |ψn i
In Section
using O 2n /m queries when m ≥ 2n. This algorithm has the drawback of being computationally
p
inefficient. To fix this, we give another algorithm that finds |ψn i using O n 2n /m queries together
p
with O n2 2n /m + poly (m) computational steps.
Having separated QMA from QCMA by a quantum oracle, we next revisit the question of whether
these classes can be separated by a classical oracle. Right now, we know of only one candidate problem
for such a separation in the literature: the Group Non-Membership (GNM) problem, which Watrous [31]
placed in QMA even though Babai [5] showed it is not in MA as an oracle problem.2 In Group Non-
Membership, Arthur is given black-box access to a finite group G, together with a subgroup H ≤ G
2 Interestingly, the classes MA and AM were originally defined by Babai in connection with GNM [4].
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 131
S. A ARONSON AND G. K UPERBERG
specified by its generators and an element x ∈ G. Arthur’s goal is to verify that x ∈
/ H, using a number
of group operations polynomial in log |G|. (Note that the group membership problem is in NP by a
result of Babai and Szemerédi [8].) In Watrous’s protocol, the quantum witness is simply an equal
superposition |Hi over the elements of H. Given such a witness, Arthur can check non-membership by
comparing the states |Hi and |xHi, and can similarly check the veracity of |Hi by comparing it to |hHi,
where h is an almost-uniformly random element of H.
Evidently a classical proof of non-membership would have to be completely different. Nevertheless,
in Section 5 we show the following:
Theorem 1.2. GNM has polynomially-bounded QCMA query complexity.
Theorem 1.2 implies that it is pointless to try to prove a classical oracle separation between QMA
and QCMA by proving a lower bound on the quantum query complexity of Group Non-Membership. If
such a separation is possible, then a new approach will be needed.
The idea of the proof of Theorem 1.2 is that Merlin can “pull the group out of the black box.” In
other words, he can claim an embedding of a model group Γ into G. This claim is entirely classical,
but verifying it requires solving the Normal Hidden Subgroup Problem (NHSP) in Γ. This problem has
low query complexity by a result of Ettinger, Høyer, and Knill [14], but is not known to be in BQP. In
addition, analyzing the description of Γ is not known to be computationally efficient. Nonetheless, in
Section 5.1 we discuss evidence that NHSP is in BQP and that non-membership for Γ is in NP. Based
on this evidence, we conjecture the following:
Conjecture 1.3. GNM is in QCMA.
Given our results in Section 5, the question remains of whether there is some other way to prove a
classical oracle separation between QMA and QCMA. In Section 6, we conjecture that the answer is
yes:
Conjecture 1.4. There exists a classical oracle A such that QMAA 6= QCMAA . Furthermore, this can
be proven by exhibiting an oracle problem with polynomial QMA query complexity but exponential
QCMA query complexity.
The reason we believe Conjecture 1.4 is that it seems possible, for many purposes, to “encode” a
quantum oracle into a classical one. In Section 6 we explain more concretely what we mean by that, and
present some preliminary results. For example, we show that there exists a BQP algorithm that maps
an oracle string A to an n-qubit pure state |ψA i, such that if A is uniformly random, then |ψA i is (under
a suitable metric) close to uniformly random under the Haar measure. We also study the question of
applying a random N × N unitary matrix using a random classical oracle in the same way. We do not
know how to do this, but we show that one quantum query will not suffice for this purpose. To prove
this, we show that a quantum algorithm that uses just one query can apply at most 4N different N × N
unitaries, whereas the number of unitaries required to approximate the uniform distribution grows like
2Θ(N ) .
2
We end in Section 7 with some open problems.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 132
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
2 Preliminaries
Throughout this paper, we refer to the set of N-dimensional pure states as CPN−1 (that is, complex
projective space with N − 1 dimensions). We use Pr to denote probability, and E to denote expectation.
We assume familiarity with standard complexity classes such as BQP and MA. For completeness,
we now define QMA, QCMA, BQP/qpoly, and BQP/poly.
Definition 2.1. QMA is the class of languages L ⊆ {0, 1}n for which there exists a polynomial-time
quantum verifier Q and a polynomial p such that, for all x ∈ {0, 1}n :
(i) If x ∈ L then there exists a p (n)-qubit quantum proof |ϕi such that Q accepts with probability at
least 2/3 given |xi |ϕi as input.
/ L then Q accepts with probability at most 1/3 given |xi |ϕi as input, for all purported proofs
(ii) If x ∈
|ϕi.
The class QCMA is defined similarly, except that |ϕi is replaced by a classical string z ∈ {0, 1} p(n) .
Definition 2.2. BQP/qpoly is the class of languages L ⊆ {0, 1}n for which there exists a polynomial-
time quantum algorithm Q, together with a set of states {|ψn i}n≥1 (where |ψn i has size p (n) for some
polynomial p), such that for all x ∈ {0, 1}n :
(i) If x ∈ L then Q accepts with probability at least 2/3 given |xi |ψn i as input.
/ L then Q accepts with probability at most 1/3 given |xi |ψn i as input.
(ii) If x ∈
The class BQP/poly is defined similarly, except that |ψn i is replaced by a classical string an ∈
{0, 1} p(n) .
Let us now explain what we mean by a “quantum oracle.” For us, a quantum oracle is simply an
infinite sequence of unitary transformations, U = {Un }n≥1 . We assume that each Un acts on p (n) qubits
for some known polynomial p. We also assume that given an n-bit string as input, a quantum algorithm
calls only Un , not Um for any m 6= n. This assumption is only made for simplicity; our results would go
through without it.3 When there is no danger of confusion, we will refer to Un simply as U.
Formally, the oracle access mechanism is as follows. Assume a quantum computer’s state has the
form
|Φi = ∑ αz |zi |φz i ,
z
where |zi is a workspace register and |φb,z i is a p (n)-qubit answer register. Then to “query Un ” means
to apply the p (n)-qubit unitary transformation that maps |Φi to
Φ0 = ∑ αz |ziUn |φz i .
z
3 If one made the analogous assumption in classical complexity—that given an input of length n, an algorithm can query
the oracle only on strings of length n—one could simplify a great many oracle results without any loss of conceptual content.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 133
S. A ARONSON AND G. K UPERBERG
Let C be a quantum complexity class, and let U = {Un }n≥1 be a quantum oracle. Then by CU , we will
mean the class of problems solvable by a C machine that, given an input of length n, can query Un at
unit cost as many times as it likes.
In defining the notion of quantum oracle, at least two choices present themselves that have no coun-
terpart for classical oracles:
(1) If we can apply a quantum oracle U, then can we also apply controlled-U (that is, U conditioned
on a control qubit |bi)?
(2) If we can apply U, then can we also apply U −1 ?
At least for the present paper, the answers to these questions will not matter, for the following
reasons. First, all of the quantum oracles U that we consider will be self-inverse (that is, U = U −1 ).
Second, while our algorithms will need to apply controlled-U, that is only for the technical reason that
we will define U so that U |ψi = − |ψi if |ψi is the marked state, and U |ϕi = |ϕi whenever hϕ|ψi = 0.
If we stipulated instead that U |ψi |bi = |ψi |b ⊕ 1i and U |ϕi |bi = |ϕi |bi whenever hϕ|ψi = 0, then U
alone would suffice.
Yet even though these choices will not matter for our results, it still seems worthwhile to discuss
them a bit, since they might arise in future work involving quantum oracles.
One could argue that (i) the purpose of an oracle is to model a subroutine that an algorithm can call
without understanding its internal structure, and that (ii) given a quantum circuit for applying some uni-
tary operation U, one can easily produce a circuit for applying controlled-U or U −1 , without understand-
ing anything about the original circuit’s structure. In particular, to produce a circuit for controlled-U, one
simply conditions each gate on the control qubit; while to produce a circuit for U −1 , one simply inverts
all the gates and reverses their order. These considerations suggest that the answers to questions (1) and
(2) should both be ‘yes.’ On the other hand, it would still be interesting to know whether disallowing
controlled-U or U −1 would let us prove more quantum oracle separations. (Note that if we disallow
these operations, then the set of inequivalent quantum oracles becomes larger.)
3 Quantum oracle separations
The aim of this section is to prove Theorem 1.1: that there exists a quantum oracle U such that QMAU 6=
QCMAU . The same ideas will also yield a quantum oracle V such that BQPV /qpoly 6= BQPV /poly.
To prove these oracle separations, we first need a geometric lemma about probability measures on
quantum states. Let µ be the uniform probability measure over N-dimensional pure states (that is, over
CPN−1 ). The following notion will play a key role in our argument.
Definition 3.1. For all p ∈ [0, 1], a probability measure σ over CPN−1 is called p-uniform if pσ ≤ µ.
Equivalently, σ is p-uniform if it can be obtained by starting from µ, and then conditioning on an event
that occurs with probability at least p.
So for example, we obtain a p-uniform measure if we start from µ and then condition on log2 1/p
bits of classical information about |ψi. Our geometric lemma says that if |ψi is drawn from a p-uniform
measure, then for every mixed state ρ, the squared fidelity between |ψi and ρ has small expectation.
More precisely:
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 134
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Lemma 3.2. Let σ be a p-uniform probability measure over CPN−1 . Then for all ρ,
1 + log 1/p
E [hψ|ρ|ψi] = O .
|ψi∈σ N
The proof of Lemma 3.2 is deferred to Section 3.1. In this section we assume the lemma, and
show
p how to useit to prove our main result. In particular, we show that any quantum algorithm needs
Ω 2n /(m + 1) queries to find an n-qubit marked state |ψi, even if given m bits of classical advice
about |ψi.
Theorem 3.3. Suppose we are given oracle access to an n-qubit unitary U, and want to decide which of
the following holds:
(i) There exists an n-qubit “quantum marked state” |ψi such that U |ψi = − |ψi, but U |φ i = |φ i
whenever hφ |ψi = 0; or
(ii) U = I is the identity operator.
q
Then even if we have an m-bit classical witness w in support of case (i), we still need Ω 2n
m+1
queries to verify the witness, with bounded probability of error.
Proof. If m = Ω (2n ) then the theorem is certainly true, so suppose m = o (2n ). Let A be a quantum
algorithm that queries U. Also, let Uψ be an n-qubit unitary such that Uψ |ψi = − |ψi, but Uψ |φ i = |φ i
whenever hφ |ψi = 0. Then A’s goal is to accept if and only if U = Uψ for some |ψi.
For each n-qubit pure state |ψi, let us fix a classical witness w ∈ {0, 1}m that maximizes the proba-
bility that A accepts, given Uψ as oracle. Let S (w) be the set of |ψi’s associated with a given witness w.
n
Since the S (w)’s form a partition of CP2 −1 , clearly there exists a witness, call it w∗ , such that
1
Pr [|ψi ∈ S (w∗ )] ≥ .
|ψi∈µ 2m
Fix that w∗ (or in other words, hardwire w∗ into A). Then to prove the theorem, it suffices to pestablish the
following claim: A cannot distinguish the case U = Uψ from the case U = I by making o 2n /(m + 1)
queries to U, with high probability if |ψi is chosen uniformly at random from S (w∗ ).
To prove the claim, we use a generalization of the hybrid argument of Bennett et al. [10]. Suppose
that A makes T queries to U. (Technically speaking, we should also allow queries to controlled-U, but
this will make no difference in our analysis.) Then for all 0 ≤ t ≤ T , let |Φt i be the final state of A,
assuming that U = I for the first t queries, and U = Uψ for the remaining T − t queries. Thus |Φ0 i is
the final state in case (i), while |ΦT i is the final state in case (ii). We will argue that |Φt i cannot be very
far from |Φt−1 i, with high probability over the choice of marked state |ψi. Intuitively, this is because
the computations of |Φt i and |Φt−1 i differ in only a single query, and with high probability that query
cannot have much overlap with |ψi. We will then conclude, by the triangle inequality, that |Φ0 i cannot
be far from |ΦT i unless T is large.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 135
S. A ARONSON AND G. K UPERBERG
More formally, let ρt be the marginal state of the query register just before the t th query, assuming
the “control case” U = I. Also, let ρt = ∑ pi |ϕi i hϕi | be an arbitrary decomposition of ρt into pure states.
Then for every i, the component of |ϕi i orthogonal to |ψi is unaffected by the t th query. Therefore
k|Φt i − |Φt−1 ik2 ≤ ∑ pi · 2 |hϕi |ψi| = 2 ∑ pi
p
hψ|ϕi i hϕi |ψi
i i
≤ 2 ∑ pi hψ|ϕi i hϕi |ψi = 2 hψ|ρt |ψi ,
r p
i
where the third line uses the Cauchy-Schwarz inequality (the average of the square root is at most the
square root of the average). Now let σ be the uniform probability measure over S (w∗ ), and observe that
σ is 2−m -uniform. So by Lemma 3.2,
hp i r
E [k|Φt i − |Φt−1 ik2 ] ≤ 2 E hψ|ρt |ψi ≤ 2 E [hψ|ρt |ψi]
|ψi∈σ |ψi∈σ |ψi∈σ
r r !
1 + ln (1/2−m ) m+1
≤2 =O ,
2n 2n
where the second line again uses the Cauchy-Schwarz inequality. Finally,
r !
T
m+1
E [k|ΦT i − |Φ0 ik2 ] ≤ ∑ E [k|Φt i − |Φt−1 ik2 ] = O T
|ψi∈S(w∗ ) t=1 |ψi∈S(w )
∗ 2n
by the triangle inequality. This implies that, for |ΦT i and |Φ0 i to be distinguishable with Ω (1) bias, we
must have T = Ω 2n /(m + 1) .
p
Using Theorem 3.3, we can straightforwardly show a quantum oracle separation between QMA and
QCMA.
Proof of Theorem 1.1. Let L be a unary language chosen uniformly at random. The oracle U = {Un }n≥1
is as follows: if 0n ∈ L, then Un |ψn i = − |ψn i for some n-qubit marked state |ψn i chosen uniformly at
random, while Un |ϕi = |ϕi whenever hϕ|ψn i = 0. Otherwise, if 0n ∈ / L, then Un is the n-qubit identity
operation.
U
Almost by √ definition, L ∈ QMA . For given a quantum witness |ϕi, the QMA verifier first prepares
the state (1/ 2) (|0i |ϕi + |1i |ϕi), then applies Un to the second register conditioned on the first register
being |1i. Next the verifier applies a Hadamard gate to the first register, measures it, and accepts if and
only if |1i is observed. If 0n ∈ L, then there exists a witness—namely |ϕi = |ψn i—that causes the
verifier to accept with probability 1. On the other hand, if 0n ∈/ L, then no witness causes the verifier to
accept with nonzero probability.
On the other hand, we claim that L ∈ / QCMAU with probability 1 over the choice of L and U. This
can be seen as follows. Fix a QCMA machine M, and let SM (n) be the event that MU succeeds on 0n :
that is, either 0n ∈ L and there exists a string w such that MU accepts |0n i |wi with probability at least
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 136
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
2/3, or 0n ∈
/ L and MU accepts |0n i |wi with probability at most 1/3 for all w. Then Theorem 3.3 readily
implies that there exists a positive integer N such that for all n ≥ N,
2
Pr [SM (n) | SM (1) , . . . , SM (n − 1)] ≤ .
L,U 3
Hence
Pr [SM (1) ∧ SM (2) ∧ · · · ] = 0 .
L,U
Now, because of the Solovay-Kitaev Theorem [21], the number of possible QCMA machines is only
countably infinite. So by the union bound,
Pr [∃M : SM (1) ∧ SM (2) ∧ · · · ] = 0
L,U
as well.
We can similarly show a quantum oracle separation between BQP/qpoly and BQP/poly.
Theorem 3.4. There exists a quantum oracle U such that BQPU /qpoly 6= BQPU /poly.
Proof. In this case Un will act on 2n qubits. Let L be a binary language chosen uniformly at random,
and let L (x) = 1 if x ∈ L and L (x) = 0 otherwise. Also, for all n, let |ψn i be an n-qubit state chosen
uniformly at random. Then Un acts as follows: for all x ∈ {0, 1}n ,
Un (|ψn i |xi) = (−1)L(x) |ψn i |xi ,
but Un (|φ i |xi) = |φ i |xi whenever hφ |ψn i = 0. Clearly L ∈ BQPU /qpoly; we just take |ψn i as the
advice. On the other hand, by essentially the same argument as for Theorem 1.1, one can show that
L∈/ BQPU /poly with probability 1 over L and U.
3.1 Proof of geometric lemma
In this section we fill in the proof of Lemma 3.2, thereby completing the oracle separation theorems.
In proving Lemma 3.2, the first step is to ask the following question: among all p-uniform probability
2
measures σ , which is the one that maximizes E|ψi∈σ |hψ|0i| ? We can think of the set of quantum
states CPN−1 as a container, which contains a fluid σ that is gravitationally attracted to the state |0i.
Then intuitively, the answer is clear: the way to maximize E|ψi∈σ |hψ|0i|2 is to “fill the container
from the bottom,” subject to the density constraint pσ ≤ µ. In other words, the optimal σ should be
the uniform measure over the region R (p) given by |hψ|0i| ≥ h (p), where h (p) is chosen so that the
volume of R (p) is a p fraction of the total volume of CPN−1 . The following lemma makes this intuition
rigorous.
Lemma 3.5. Among all p-uniform probability measures σ over CPN−1 , the one that maximizes
h i
E |hψ|0i|2
|ψi∈σ
is τ (p), the uniform measure over the region R (p) defined above.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 137
S. A ARONSON AND G. K UPERBERG
Proof. Since |hψ|0i|2 is nonnegative, we can write
h i Z∞ h i
E |hψ|0i|2 = Pr |hψ|0i|2 ≥ y dy .
|ψi∈σ 0 |ψi∈σ
We claim that setting σ := τ (p) maximizes the integrand for every value of y. Certainly, then, setting
σ := τ (p) maximizes the integral itself as well.
To prove the claim, we consider two cases. First, if y ≤ h (p)2 , then
h i
Pr |hψ|0i|2 ≥ y = 1 ,
|ψi∈τ(p)
which is certainly maximal. Second, if y > h (p)2 , then
h i 1 h i
Pr |hψ|0i|2 ≥ y = · Pr |hψ|0i|2 ≥ y .
|ψi∈τ(p) p |ψi∈µ
This is maximal as well, since
h i 1 h i
Pr |hψ|0i|2 ≥ y ≤ · Pr |hψ|0i|2 ≥ y
|ψi∈σ p |ψi∈µ
for all p-uniform probability measures σ .
Lemma 3.5 completely describes the probability measure that maximizes E|ψi∈σ |hψ|0i|2 , except
for one detail: the value of h (p) (or equivalently, the radius of R (p)). The next lemma completes the
picture.
Lemma 3.6. For all p,
r !
log 1/p
q
h (p) = 1 − p1/(N−1) = Θ .
N
Proof. We will show that for all h,
N−1
Pr [|hψ|0i| ≥ h] = 1 − h2 ,
|ψi∈µ
where µ is the uniform probability measure over CPN−1 . Setting p := Pr|ψi∈µ [|hψ|0i| ≥ h] and solving
for h then yields the lemma.
Let~z = (z0 , . . . , zN−1 ) be a complex vector; then let~r = (r0 , . . . , rN−1 ) and ~θ = (θ0 , . . . , θN−1 ) be real
vectors such that zk = rk eiθk for each coordinate k. Also, let D be a Gaussian probability measure on
CN , with density function
1 2
P (~z) = P (~r) = N e−k~rk2 .
π
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 138
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Let d~r be shorthand for dr0 · · · drN−1 . Then we can express the probability that |hψ|0i| ≥ h as
Pr [|hψ|0i| ≥ h] = Pr [|z0 | ≥ h k~zk2 ]
|ψi∈µ ~z∈D
= Pr [r0 ≥ h k~rk2 ]
~r,~θ
Z
= P (~r) r0 · · · rN−1 d~rd~θ
~r,~θ : r0 ≥hk~rk2
1 −k~rk22
Z
N
= (2π) N
e r0 · · · rN−1 d~r
~r : r0 ≥hk~rk2 π
Z ∞
!
Z ∞ 2 2 2
= r
r12 +···+rN−1
2 2e−r0 r0 dr0 2N−1 e−r1 −···−rN−1 r1 dr1 · · · rN−1 drN−1
r1 ,...,rN−1 =0 r0 =h
1−h2
Z ∞
2 2 2 2 2 2
= e−(r1 +···+rN−1 )·h /(1−h ) 2N−1 e−r1 −···−rN−1 r1 dr1 · · · rN−1 drN−1
r ,...,rN−1 =0
Z 1∞
2 2 2
= 2N−1 e−(r1 +···+rN−1 )/(1−h ) r1 dr1 · · · rN−1 drN−1
r1 ,...,rN−1 =0
Z ∞ N−1
2 2
= 2e−r /(1−h ) rdr
r=0
N−1
= 1 − h2 .
By combining Lemmas 3.5 and 3.6, we can now prove Lemma 3.2: that if σ is p-uniform, then for
all mixed states ρ,
1 + log 1/p
E [hψ|ρ|ψi] = O .
|ψi∈σ N
Proof of Lemma 3.2. If p ≤ e−Ω(N) then the lemma is certainly true, so suppose p ≥ e−O(N) . Since the
concluding inequality is linear in ρ, we can assume without loss of generality that ρ is a pure state.
Indeed, by symmetry we can assume that ρ = |0i h0|. So our aim is to upper-bound E|ψi∈σ |hψ|0i|2 ,
where σ is any p-uniform probability measure. By Lemma 3.5, we can assume without loss of generality
that σ = τ (p) is the uniform measure over all |ψi such that |hψ|0i| ≥ h (p). Then letting
|ψi = α0 |0i + · · · + αN−1 |N − 1i ,
q
r = |α1 |2 + · · · + |αN−1 |2 ,
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 139
S. A ARONSON AND G. K UPERBERG
we have
h i h i
E |hψ|0i|2 = E |α0 |2
|ψi∈τ(p) |ψi : |α0 |≥h(p)
1 − r2
= E
|ψi : r2 ≤1−h(p)2
√
1−h(p)2 2N−3
1 − r2 dr
R
0 r
= √
R 1−h(p)2 2N−3
0 r dr
√
h 2N−2 i 1−h(p)2
r r2N
2N−2 − 2N 0
= √
h i 1−h(p)2
r2N
2N 0
1 − 1 − N1 1 − h (p)2
=
1 − N1 1 − h (p)2
1 2
=O + h (p)
N
1 + log 1/p
=O ,
N
where the last line follows from Lemma 3.6.
4 Upper bound
In this section we show that the lower bound of Theorem 3.3 is basically tight. In particular, let U be an
n-qubit quantum oracle, and suppose we are given an m-bit classical proof that U is not the identity, but
instead conceals a marked state |ψi such thatpU |ψi = n
− |ψi. Then provided 2n ≤ m ≤ 2 , a quantum
n
algorithm can verify the proof by making O 2 /m oracle calls to U. This matches our lower bound
when m ≥ 2n.4
Let N = 2n be the dimension of U’s Hilbert space. Then the idea of our algorithm is to use a “mesh”
of states |φ1 i , . . . , |φM i ∈ CPN−1 , at least one of which has nontrivial overlap with every pure state in
CPN−1 . A classical proof can then help the algorithm by telling it the |φi i that is closest to |ψi. More
formally, define the h-ball about |φ i to be the set of |ϕi such that |hφ |ϕi| ≥ h. Then define an h net
for CPN−1 of size M to be a set of states |φ1 i , . . . , |φM i such that every |ψi ∈ CPN−1 is contained in the
h-ball about |φi i for some i.5 We will use the following theorem, which follows from Corollary 1.2 of
Böröczky and Wintsche [11].
√ p
4 When m 2n, the best upper bound we know is the trivial O 2n . However, we conjecture that O 2n /m is
achievable in this case as well.
5 These objects are often called ε-nets, with the obvious relation h = cos ε.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 140
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Theorem 4.1 ([11]). For all 0 < h < 1, there exists an h-net for CPN−1 of size
!
N 3/2 log 2 + Nh2
O .
(1 − h2 )N
Böröczky and Wintsche do not provide an explicit construction of such an h-net; they only prove
that it exists.6 Later, we will give an explicit construction with only slightly worse parameters than those
of Theorem 4.1. But first, let us prove an upper bound on query complexity.
Theorem 4.2. Suppose we have an n-qubit quantum oracle U such that either (i) U = Uψ for some |ψi,
or (ii) U = I is the identity operator. Then given an m-bit classical witness p
in support of case (i), where
m ≥ 2n, there exists a quantum algorithm that verifies the witness using O 2n /m + 1 queries to U.
n
Proof. By Theorem 4.1, there exists an h-net S for CP2 −1 of cardinality
!
23n/2 log 2 + 2n h2
|S| = O n .
(1 − h2 )2
Setting |S| = 2m gives
3n n 1
m≤ + 2 log + O (log n) .
2 1 − h2
Solving for h, we obtain r
m − 3n/2 − O (log n)
h≥ ,
2n
which is Ω m/2n provided m ≥ 2n. So there exists a collection of M = 2m states, |φ1 i , . . . , |φM i ∈
p
n
CP2 −1 , such that for every |ψi, there exists an i such that |hφi |ψi| ≥ h where h = Ω m/2n .
p
Given an oracle U = U|ψi , the classical witness w ∈ {0, 1}m will simply encode an index i such that
|hφi |ψi| ≥ h. If we prepare |φi i and feed it to U, then the probability of finding the marked state |ψi
is |hφi |ψi|2 ≥ h2 . Furthermore, if we do find |ψi, we will know we did (i. e. a control qubit will be |1i
instead of |0i). From these facts, it follows immediately from the amplitude amplification theorem of
Grover [15] and Brassard et al. [12] that we can find |ψi with probability Ω (1) using
r ! r !
1 2n
O +1 = O +1
h2 m
queries to U.
Of course, if we care about computational complexity as well as query complexity, then it is not
enough for an h-net to exist—we also need the states in the h-net to be efficiently preparable. Fortunately,
proving an explicit version of Theorem 4.1 turns out to be simpler than one might expect. We will do so
with the help of the following inequality.
6 Note that we cannot just start from an explicit construction of a sphere-packing, and then double the radius of the spheres
to get a covering. We could do that if we wanted a covering of CPN−1 by small balls. But in our case, h is close to zero, which
means that the balls already have close to the maximal radius.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 141
S. A ARONSON AND G. K UPERBERG
Lemma 4.3. Let x1 ≥ · · · ≥ xN ≥ 0 be nonnegative real numbers with x12 + · · · + xN2 = 1. Then for all
k ∈ {1, . . . , N},
s
x1 + · · · + xt k
max √ ≥ .
1≤t≤k t N dlog 2 Ne
Proof. Let L = dlog2 Ne. Then for all i ∈ {1, . . . , L}, let si = x22i−1 + · · · + x22i −1 , where we adopt the
convention that x j = 0 if j > N. Then
s1 + · · · + sL = x12 + · · · + xN2 = 1 ,
so certainly there exists an i ∈ {1, . . . , L} such that si ≥ 1/L. Fix that i. Then since the x j ’s are arranged
in nonincreasing order, we have
r r
si 1
x2i−1 ≥ i−1
≥ i−1
.
2 2 L
There are now two cases. First, if k ≤ 2i−1 then
r s
x1 + · · · + xt x1 + · · · + xk k k k
max √ ≥ √ ≥ √ x2i−1 ≥ i−1
≥ .
1≤t≤k t k k 2 L N dlog2 Ne
Second, if 2i−1 ≤ k then
r s
2i−1
x1 + · · · + xt x1 + · · · + x2i−1 1 k
max √ ≥ √ ≥√ x2i−1 ≥ ≥ .
1≤t≤k t 2i−1 2i−1 L N dlog2 Ne
This completes the proof.7
We now use Lemma 4.3 to construct an h-net.
Theorem 4.4. For all 0 < h < 1, there exists an h-net |φ1 i , . . . , |φM i for CPN−1 of size
2 2
M = 4N · 2O(h N log N ) ,
as well as a quantum algorithm that runs in time polynomial in log M and that prepares the state |φi i
given i as input.
7 One might wonder whether the
p
1/ dlog2 Ne factor
q can be eliminated. However, a simple example shows that it can be
jw , where w = ∑ j=1 j ≈ ln N. Then for all t ∈ {1, . . . , N}, we have
1 n 1
improved by at most a constant factor. Suppose x j :=
x1 + · · · + xt 2
√ ≈√ .
t ln N
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 142
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Proof. Assume without loss of generality that N = 2n and M = 2m are both powers of 2, and let |ψi be
an n-qubit target state. Then it suffices to show that a quantum algorithm, using
m = log2 M = n + 2 + O h2 2n n2
bits of classical
madvice,
can prepare a state |φ i such that |hφ |ψi| ≥ h in time polynomial in m.
Let k := n+2 . Also, let us express |ψi in the computational basis as
|ψi = ∑ αz |zi ,
z∈{1,...,N}
and let |z1 i , . . . , |zN i be an ordering of basis states with the property that |αz1 | ≥ · · · ≥ |αzN |. Then by
Lemma 4.3, there exists an integer t ∈ {1, . . . , k} such that
s r
|αz1 | + · · · + |αzt | k k
√ ≥ = .
t N dlog2 Ne Nn
Here we can assume that αz1 , . . . , αzt are all nonzero, since otherwise we simply decrease t. Now let
βz be the element of {1, −1, i, −i} that is closest to αz / |αz |, with ties broken arbitrarily. Then our
approximation to |ψi will be the following:
1 t
|φ i := √ ∑ βzi |zi i .
t i=1
To specify |φ i, the classical advice just needs to list z1 , . . . , zt and βz1 , . . . , βzt . Since t ≤ k, this requires
at most k (n + 2) ≤ m bits. Given the specification, it is clear that |φ i can be prepared in time polynomial
in tn ≤ m. Moreover, r
1 t ∗ 1 t |αzi | k
hφ |ψi = √ ∑ βzi αzi ≥ √ ∑ √ ≥ .
t i=1 t i=1 2 2Nn
q
k
We can therefore set h := 2Nn , so that k = 2h2 Nn. Hence
m ≤ (n + 2) (k + 1) = (n + 2) 2h2 Nn + 1 = n + 2 + O h2 2n n2 .
The following is an immediate consequence of Theorem 4.4.
Corollary 4.5. Suppose we have an n-qubit quantum oracle U such that either (i) U = Uψ for some
|ψi, or (ii) U = I is the identity. Then given an m-bit classical
p witness in support of case (i), there
exists a quantum algorithm that verifies the witness using O n 2n /m + 1 queries to U, together with
p
O n2 2n /m + poly(m) steps of auxiliary computation.
It is natural to ask whether we could construct
p a smaller
explicit h-net,pand thereby
improve the
query complexity in Corollary 4.5 from O n 2n /m + 1 to the optimal O 2n /m + 1 . We certainly
believe that this is possible, but it seems to require more complicated techniques from the theory of
sphere coverings.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 143
S. A ARONSON AND G. K UPERBERG
5 Group non-membership
The Group Non-Membership (GNM) problem is defined as follows. We are given a finite group G, a
subgroup H ≤ G, and an element x ∈ G. The problem is to decide whether x ∈ / H.
But how are G, H, and x specified? To abstract away the details of this question, we will use Babai
and Szemerédi’s model of black-box groups [8]. In this model, we know generators for H, and we know
how to multiply and invert the elements of G, but we “do not know anything else.” More formally, we
are given access to a group oracle O, which represents each element x ∈ G by a randomly-chosen label
` (x) ∈ {0, 1}n for some n log2 |G|. We are also given the labels of generators hh1 , . . . , hl i for H. We
are promised that every element has a unique label.
Suppose that our quantum computer’s state has the form
|Φi = ∑ αx,y,z |` (x) , ` (y)i |zi ,
x,y∈G, z
where ` (x) and ` (y) are labels of group elements and |zi is a workspace register. Then the oracle O
maps this state to
O |Φi = ∑ αx,y,z ` (x) , ` xy−1
|zi .
x,y∈G, z
Note that if the first register does not contain valid labels of group elements, then O can behave arbitrar-
ily. Thus, from now on we will ignore labels, and talk directly about the group elements they represent.
Using O, it is easy to see that we can perform group inversion (by putting the identity element e in
the x register) and multiplication (by first inverting y, then putting y−1 in the y register), as well as any
combination of these operations.
We will show that GNM has polynomially-bounded QCMA query complexity. In other words, if
x∈ / H, then Merlin can provide Arthur with a poly (n)-bit classical witness of that fact, which enables
Arthur to verify it with high probability using poly (n) quantum queries to the group oracle O.
To prove this result, we first need to collect various facts from finite group theory. Call g1 , . . . , gk an
efficient generating set for a finite group G if (i) k = O (log |G|), and (ii) every x ∈ G is expressible as
ge11 · · · gekk where e1 , . . . , ek ∈ {0, 1}. The following lemma was shown by Babai and Erdős [6].
Lemma 5.1 ([6]). Every finite group G has an efficient generating set.
Given finite groups Γ and G, we say that functions f , g : Γ → G are ε-close if
Pr [ f (x) 6= g (x)] ≤ ε .
x∈Γ
Also, recall that f : Γ → G is a homomorphism if f (xy) = f (x) f (y) for all x, y ∈ Γ. The following two
propositions relate ε-closeness to homomorphisms.
Proposition 5.2. If two homomorphisms f , g : Γ → G are (1/2 − ε)-close for any ε > 0, then f = g.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 144
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Proof. Fix x ∈ Γ; then for all y ∈ Γ, we have f (x) = f (y) f y−1 x and g (x) = g (y) g y−1 x . By the
union bound,
Pr f (y) = g (y) ∧ f y−1 x = g y−1 x ≥ 1 − Pr [ f (y) 6= g (y)] − Pr f y−1 x 6= g y−1 x > 0 .
y∈Γ y∈Γ y∈Γ
Hence there exists a y such that f (y) = g (y) and f y−1 x = g y−1 x . But this implies that f (x) =
g (x).
In particular, Proposition 5.2 implies that if a function f is 1/5-close to a homomorphism, then it is
1/5-close to a unique homomorphism (1/5 being an arbitrary constant less than 1/4).
Proposition 5.3 (Ben-Or et al. [9]). Given finite groups Γ and G, a function f : Γ → G, and a real
number ε > 0, if
Pr [ f (xy) 6= f (x) f (y)] ≤ ε
x,y∈Γ
then f is ε-close to a homomorphism.
Together, Propositions 5.2 and 5.3 have the following easy corollary.
Corollary 5.4. There is a randomized algorithm which, given finite groups Γ and G and a function
f : Γ → G as input, makes O (1) oracle queries to f , accepts with probability 1 if f is a homomorphism,
and rejects with probability at least 2/3 if f is not 1/5-close to a homomorphism. Also, if f is 1/5-close
to some homomorphism fe, then there exists a randomized algorithm that, given an input x ∈ Γ, makes
O (r) oracle queries to f , and outputs fe(x) with probability at least 1 − 1/2r .
In the present context, our algorithms are not limited in space or time, and we can say for simplicity
that Γ is represented by its entire multiplication table. It is then easy, as the proof will require, to pick
elements of Γ uniformly at random. By contrast, G is represented by oracle access, but there will be no
need to choose its elements at random.
Proof. The first algorithm simply chooses O (1) pairs x, y ∈ Γ uniformly at random, accepts if f (xy) =
f (x) f (y) for all of them, and rejects otherwise. Let k = O (r). Then the second algorithm chooses
z1 , . . . , zk ∈ Γ uniformly at random, and outputs the plurality answer among
f (z1 ) f z−1 −1
1 x , . . . , f (zk ) f zk x
breaking ties arbitrarily.
It follows from the Classification of Finite Simple Groups that there are at most two finite simple
groups of any particular order (see [13] for example). The following well-known result is a combination
of that fact and of a theorem due to Neumann [25].
2
Theorem 5.5. There are N O((log2 N) ) groups of order N up to isomorphism.8
8 The most accurate asymptotic result on the number of groups of order N, in terms of the prime factorization of N, appears
in a paper by Pyber [26].
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 145
S. A ARONSON AND G. K UPERBERG
Finally, recall that the Hidden Subgroup Problem (HSP) is defined as follows. We are given a fi-
nite group G, and oracle access to a function f : G → Z. We are promised that there exists a “hidden
subgroup” H ≤ G such that f (x) = f (y) if and only if x and y belong to the same left coset of H. The
problem is then to output a set of generators for H. Whether HSP can be solved in quantum polynomial
time, for various non-abelian groups G, is one of the most actively studied questions in quantum com-
puting. However, if we only care about query complexity, then Ettinger, Høyer, and Knill [14] proved
the following useful result.
Theorem 5.6 ([14]). There is a quantum algorithm such that, given any finite group G as oracular input,
solves HSP using only polylog (|G|) quantum queries to f (together with a possibly exponential amount
of postprocessing).9
We can now prove Theorem 1.2: that GNM has polynomially-bounded QCMA query complexity.
Proof of Theorem 1.2. Let G be a group of order at most 2n , and let O be a group oracle that maps each
element of G to an n-bit label. Also, given (the labels of) group elements x, h1 , . . . , hm ∈ G, let H be the
subgroup of G generated by hh1 , . . . , hm i. Then the problem is to decide if x ∈
/ H.
In our QCMA protocol for this problem, Merlin’s witness will consist of the following:
• An explicit “model group” Γ, of order at most 2n .
• A list of elements γ1 , . . . , γk ∈ Γ, where k = O (log |Γ|).
• A corresponding list g1 , . . . , gk ∈ G.
• Another list z, λ1 , . . . , λm ∈ Γ.
We should be more explicit about the notion of an “explicit” group Γ, and about the syntax of
this witness. By Theorem 5.5, there are at most 2poly(n) groups of order |Γ| ≤ 2n up to isomorphism.
Since Arthur is allowed unlimited computation and is only restricted in queries, he can construct a
full multiplication table for Γ using only the name of its isomorphism type. The multiplication table
is not unique, because the elements of Γ can be permuted; but for instance Arthur could construct
the lexicographically first such table. Since Merlin can anticipate Arthur’s construction of Γ, he can
then refer to elements of Γ using the same construction. He can also refer to elements of G since he
understands the oracle. In conclusion, Merlin can specify the witness using only poly (n) bits.
If Merlin is honest, then the witness will have the following three properties:
(1) γ1 , . . . , γk is an efficient generating set for Γ.
/ Λ, where Λ is the subgroup of Γ generated by hλ1 , . . . , λm i.
(2) z ∈
(3) There exists an embedding fe : Γ → G, such that (i) fe(γi ) = gi for all i ∈ {1, . . . , k}, (ii) fe(λ j ) = h j
for all j ∈ {1, . . . , m}, and (iii) fe(z) = x.
9 Indeed, for Normal HSP (which is the special case we care about), Hallgren, Russell, and Ta-Shma [16] improved this
result, showing how to find a hidden subgroup using only O (log |G|) queries to f (again, with exponential postprocessing).
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 146
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Suppose for the moment that (1)-(3) all hold. Then there exists an embedding fe : Γ → G, which maps
the set hγ1 , . . . , γk i in Γ to the set hg1 , . . . , gk i in G. Furthermore, this embedding satisfies fe(Λ) = H and
fe(z) = x. Since z ∈ / Λ by (2), it follows that x ∈ / H as well, which is what Arthur wanted to check.
So it suffices to verify (1)-(3). In the remainder of the proof, we will explain how to do this using a
possibly exponential amount of computation, but only poly (n) quantum queries to the group oracle O.
First, since properties (1) and (2) only involve the explicit group Γ, not the black-box group G,
Arthur can verify these properties “free of cost.” In other words, regardless of how much computation
he needs, he never has to query the group oracle.
The nontrivial part is to verify (3). It will be convenient to split (3) into the following sub-claims:
(3a) There exists a homomorphism fe : Γ → G such that fe(γi ) = gi for all i ∈ {1, . . . , k}.
(3b) fe satisfies fe(z) = x and fe(λ j ) = h j for all j ∈ {1, . . . , m}.
(3c) fe is injective (i. e. is an embedding into G).
To verify (3a), first Arthur fixes a “canonical representation” of each element γ ∈ Γ. This represen-
tation has the form
γ = γ1e1 · · · γkek ,
where hγ1 , . . . , γk i is the efficient generating set for Γ, and e1 , . . . , ek ∈ {0, 1} are bits depending on γ.
Next he defines a function f : Γ → G by
f (γ) := ge11 · · · gekk
for all γ ∈ Γ. By using the canonical representation of γ, Arthur can evaluate f (γ) using at most k − 1
queries to the group oracle O. Finally Arthur appeals to Corollary 5.4. If f is not 1/5-close to a
homomorphism, then by using O (1) queries to f , with high probability Arthur can detect that f is not a
homomorphism. In that case Merlin has been caught cheating, so Arthur rejects. On the other hand, if
f is 1/5-close to some homomorphism fe, then by using O (log |Γ|) queries to f , with high probability
Arthur can “correct” f to fe. In that case it remains only to check that fe(γi ) = gi for all i ∈ {1, . . . , k}.
Once Arthur has an efficient procedure for computing fe—that is, a procedure that involves only
poly (n) queries to O—he can then verify property (3b) directly.
To verify (3c), Arthur runs the algorithm of Ettinger, Høyer, and Knill [14] for the Hidden Subgroup
Problem. Notice that, since fe : Γ → G is a homomorphism, there must be a “hidden subgroup” K ≤
Γ—namely the kernel of fe—such that fe is constant on cosets of K and distinct on distinct cosets.
Furthermore, fe is injective if and only if K is trivial. But deciding whether K is trivial is just an instance
of HSP, and can therefore be solved using poly (n) quantum queries by Theorem 5.6.
5.1 Computational complexity
Theorem 1.2 showed that one can always verify group non-membership using a polynomial-size clas-
sical witness, together with polynomially many quantum queries to the group oracle O. Unfortunately,
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 147
S. A ARONSON AND G. K UPERBERG
while the query complexity is polynomial, the computational complexity might be exponential. How-
ever, as mentioned in Section 1.1, we conjecture that this shortcoming of Theorem 1.2 can be removed,
and that GNM is in QCMA for any group oracle O.
In our QCMA protocol, the main computational problem that needs to be solved is not the general
HSP, but rather the Normal Hidden Subgroup Problem (NHSP)—that is, HSP where the hidden sub-
group is normal. This is because the kernel of a homomorphism is always a normal subgroup. Hallgren,
Russell, and Ta-Shma [16] showed that NHSP is in BQP for an explicit group Γ, provided that the
quantum Fourier transform over Γ can be implemented efficiently (and its output can be interpreted).
Furthermore, Moore, Rockmore, and Russell [23] showed that many classes of finite groups G have an
explicit model Γ ∼= G for which this assumption holds.
Even if NHSP is in BQP, there are two remaining obstacles to showing that GNM is in QCMA. First,
we need to be able to verify group non-membership in the explicit model group Γ, possibly with the help
of additional classical information from Merlin. Second, we need an efficient algorithm to compute the
function fe : Γ → G for every γ ∈ Γ, even though fe is explicitly defined only on the generators γ1 , . . . , γk .
In the context of computational complexity (as opposed to query complexity), the notion of an
“explicit group” needs to be better explained. Keeping in mind that this entire section is only one
possible path to showing that GNM is in QCMA, here is one definition that captures the ideas of previous
sections.
Definition 5.7. A (polylog-time) explicit sequence of finite groups is a sequence Γn such that each
term is a group law on the set {1, . . . , |Γn |}. Moreover the multiplication function mn (x, y) = xy and
the inversion function in (x) = x−1 can both be computed in polynomial time in log |Γn |. An explicit
sequence is universal if every finite group is isomorphic to at least one Γn .
For example, the symmetric group (sequence) Sn is explicit, because the standard notation for per-
mutations can be compressed to the integers from 1 to n!. Likewise the matrix groups GL(n, q) form an
explicit sequence in the joint parameter (n, a(x)), where a(x) is a polynomial whose splitting field is Fq .
But there is no reason to believe that an explicit model of a group is unique up to polylog-time bijections.
On the contrary, if the discrete logarithm problem is hard, then (Fq )× and Z/(q − 1) are inequivalent
explicit models for isomorphic groups; and both models appear naturally in the obvious explicit model
for matrix groups.
It is not known whether there is a universal explicit sequence of finite groups. The current best
result for solvable groups is quasipolylogarithmic time [17]. Theorem 5.5 implies that the number of
isomorphism classes of finite groups does not by itself preclude a universal explicit sequence.
If there is a universal sequence of explicit finite groups with the following additional properties, then
following the methods of the previous section, it would show that GNM is in QCMA. (We drop the
formal subscript n.)
(i) Each Γ has a list of generators γ1 , . . . , γk ∈ Γ that can be computed in O(polylog |Γ|) time. More-
over, given an element γ ∈ Γ, there is a polylog algorithm to express it as a (polylogarithmic
length) product of γ1 , . . . , γk . It suffices if this algorithm is polylog time on average for random γ.
A straight-line program rather than a product also suffices.
(ii) NHSP over Γ is in BQP.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 148
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
(iii) GNM over Γ is in QCMA.
If the Hallgren-Russell-Ta-Shma algorithm is used for condition (ii), then there should be an al-
gorithm for the quantum Fourier transform over Γ. In this case the QFT produces randomly-chosen
characters of the quotient group Γ/Λ for some normal subgroup Λ. The characters must also be listed in
some explicit form so that so that Λ can be recognized in polylog time, or at least that the triviality of Λ
can be so recognized. (Here, too, “explicit” means that the characters of Γ are numbered consecutively
and that the relevant algorithms use this numbering.)
If Γ is the symmetric group Sn , or an abelian group expressed as a product of cyclic groups, or if it
is a matrix group GL(n, q), then there is an easy generating set that satisfies (i) (exercise for the reader).
In the abelian case, NHSP is in BQP by the work of Shor [29] and Kitaev [20]; GNM is in P by linear
algebra. If Γ = Sn , then NHSP is trivial (since the only normal subgroup is An ) and GNM is in P by the
work of Sims [30]. Meanwhile Babai and Szemerédi [8] showed that if every finite simple group has an
explicit polylogarithmic presentation, then GNM is in NP for GL(n, q).
Since the point of condition (ii) is to allow Arthur to confirm Merlin’s claimed homomorphism from
Γ to G, a polylogarithmic presentation of Γ would yield an alternative method that does not rely on the
algorithm of Corollary 5.4. The status of this problem is that the only unknown case among finite simple
groups is Ree groups of type 2 G2 (q); all other finite simple groups are known to have such a presentation
[7, 18]. Moreover, it is known that short presentations of a sequence {Γ1 , . . . , Γk } of finite simple groups
can be combined to obtain a short presentation for any finite Γ composed of {Γ1 , . . . , Γk } [7]. However,
there is no known polylog-time algorithm to generate an explicit presentation of each such Γ, even given
a presentation of each simple Γ j as input. In summary, the groups 2 G2 (q) and the extension problem
are the remaining obstructions to a universal, explicit sequence of polylog presentations of finite groups,
which would provide a simple alternative to condition (ii). Regardless, all known QFT algorithms
employ flags of subgroups, which are structures that can also be used to satisfy condition (ii).
Obviously the entire program is far from complete, and each step is open to variations. But we
optimistically conjecture that all steps can be completed for arbitrary finite groups.
6 Mimicking random quantum oracles
We have seen, on the one hand, that there exists a quantum oracle separating QMA from QCMA; and on
the other hand, that separating these classes by a classical oracle seems much more difficult. Together,
these results raise a general question: how much “stronger” are quantum oracles than classical ones?
In particular, are there complexity classes C and D that can be separated by quantum oracles, but such
that separating them by classical oracles is almost as hard as separating them in the unrelativized world?
Whatever the answer, we conjecture that QMA and QCMA are not examples of such classes. The reason
is that it seems possible, using only classical oracles, to approximate quantum oracles similar to ones
that would separate QMA from QCMA.
To illustrate, let σ be the uniform probability measure over 2n × 2n unitary diagonal matrices. (In
other words, each diagonal entry of D ∈ σ is a random complex number with norm 1.) Also, let H ⊗n
be a tensor product of n Hadamard matrices. Then let ςk be the probability measure over 2n × 2n unitary
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 149
S. A ARONSON AND G. K UPERBERG
matrices
U = Dk H ⊗n Dk−1 H ⊗n · · · H ⊗n D1 H ⊗n
induced by drawing each Di independently from σ . In other words, U ∈ ςk is obtained by first applying
a Hadamard gate to each qubit, then a random 2n × 2n diagonal matrix, then Hadamard gates again, then
another random diagonal matrix, and so on k times.
Note that we can efficiently apply such a U—at least to polynomially many bits of precision—if
given a classical random oracle A. To do so, we simply implement the random diagonal matrix Di as
∑ αx |xi → ∑ ω A(i,x) αx |xi ,
x∈{0,1}n x∈{0,1}n
n
where A (i, x) is a uniformly random n-bit integer indexed by i and x, and ω = e2πi/2 .
Now let µ be the uniform probability measure over 2n × 2n unitary matrices. If k 2n , then ςk is
not close to µ in variation distance, since the former has only Θ (k2n ) degrees of freedom while the
latter has Θ (k4n ).10 On the other hand, we conjecture that a U drawn from ςk will “look random” to
any polynomial-time algorithm, and that this property can be used to prove a classical oracle separation
between QMA and QCMA.
Let us explain what we mean in more detail. Suppose we are given access to an n-qubit unitary
oracle U, and want to decide whether
(i) U was drawn uniformly at random (that is, from µ), or
(ii) U was drawn random conditioned on there existing n/2-qubit pure states |ψi and |ϕi
uniformly at
⊗n/2
such that U |0i |ψi ≈ |0i⊗n/2 |ϕi.
In case (i), the states |ψi and |ϕi will exist only with negligible probability.11 It follows that the
above problem is in QMAU —since if case (ii) holds, then a succinct quantum proof of that fact is just
|ψi itself. We now state three conjectures about this problem, in increasing order of difficulty.
Conjecture 6.1. The above problem is not in QCMAU . In other words, if case (ii) holds, there is no
succinct classical proof of that fact that can be verified with high probability using poly (n) quantum
queries to U.
Presumably Conjecture 6.1 can be proved using ideas similar to those in Section 3. If so, then the
next step is to replace the uniform measure µ by the “pseudorandom” measure ςk .
10 Admittedly, it is still conceivable that the finite-precision version of ς is close in variation distance to the finite-precision
k
version of µ. However, a more sophisticated argument that counts distinguishable unitaries rules out that possibility as well.
11 Indeed, the reason we did not ask for (n − 1)-qubit states |ψi and |ϕi such that U (|0i |ψi) ≈ |0i |ϕi is that such states will
exist (almost) generically. For the choice of |ψi gives us 2n−1 − 1 independent complex variables, whereas the requirement
that U (|0i |ψi) have the form |0i |ϕi imposes only 2n−1 constraints. Asking for (n − 2)-qubit states |ψi and |ϕi such that
U (|00i |ψi) ≈ |00i |ϕi might suffice (since now we have 2n−2 − 1 variables versus 3 · 2n−2 constraints), but we wish to stay
on the safe side.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 150
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
Conjecture 6.2. Suppose that instead of being drawn from µ, the unitary U is drawn from ςk for some
k = Ω (n). Then the probability that there exist n/2-qubit states |ψi and |ϕi such that
U |0i⊗n/2 |ψi ≈ |0i⊗n/2 |ϕi
is still negligibly small.
Now suppose we want to decide whether
(i’) U was drawn from ςk , or
(ii’) U was drawn from ςk conditioned on there existing n/2-qubit states |ψi and |ϕi such that
U |0i⊗n/2 |ψi ≈ |0i⊗n/2 |ϕi .
Also, let A be a classical oracle that encodes the diagonal matrices D1 , . . . , Dk such that
U = Dk H ⊗n Dk−1 H ⊗n · · · H ⊗n D1 H ⊗n .
If Conjecture 6.2 is true, then case (ii’) can be verified in QMAA . So to obtain a classical oracle separa-
tion between QMA and QCMA, the one remaining step would be to prove the following.
Conjecture 6.3. Case (ii’) cannot be verified in QCMAA .
6.1 From random oracles to random unitaries
The previous discussion immediately suggests even simpler questions about the ability of classical or-
acles to mimic quantum ones. In particular, could a BQP machine use a classical random oracle to
prepare a uniformly random n-qubit pure state? Also, could it use such an oracle to apply a random
n-qubit unitary?
In this section we answer the first question in the affirmative, and present partial results about the
second question. We first need a notion that we call the “ε-smoothing” of a probability measure.
n
Definition 6.4. Let σ be a probability measure over |ψi ∈ CP2 −1 . Then the ε-smoothing of σ , or
Sε (σ ), is the probability measure obtained by first drawing a state |ψi from σ , and then drawing a state
|ϕi uniformly at random subject to hϕ|ψi ≥ 1 − ε.
n
Let µ be the uniform measure over CP2 −1 . Also, let Q be a quantum algorithm that queries a
n
classical oracle A. Suppose that, given 0n as input, QA outputs the pure state |ψA i ∈ CP2 −1 . Then we say
that Q “approximates the uniform measure within ε” if, as we range over uniform random A ⊆ {0, 1}n ,
the induced probability measure σ over |ψA i satisfies kSε (σ ) − µk ≤ ε.
Theorem 6.5. For all polynomials p, there exists a quantum algorithm Q that runs in polynomial time,
and that approximates the uniform measure within 2−p(n) .
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 151
S. A ARONSON AND G. K UPERBERG
Proof Sketch. The algorithm Q is as follows: first prepare a uniform superposition over n-bit strings.
Then, using the classical random oracle A as a source of random bits, map this state to
q
1
|Ψi = n/2 ∑ |xi 2
1 − |αx | |0i + αx |1i ,
2 x∈{0,1}n
where each αx is essentially a Gaussian random variable. More precisely, let q (n) = (n + p (n))2 . Then
each αx is drawn independently from a complex Gaussian distribution with mean 0 and variance 1/q (n),
with the two technicalities that (1) αx is rounded to q (n) bits of precision, and (2) the cutoff |αx | ≤ 1 is
imposed. (By a tail bound, with overwhelming probability we will have |αx | ≤ 1 for all x anyway.)
Next measure the second register of |Ψi in the standard basis. The outcome |1i will be observed
with probability Ω (1/q (n)). Furthermore, conditioned on |1i being observed, one can check that the
distribution σ over the reduced state of the first register satisfies kS2−p(n) (σ ) − µk ≤ 2−p(n) . (We omit
the calculation.) Hence it suffices to repeat the algorithm O (q (n)) times.
Theorem 6.5 shows that, by using a classical random oracle A, we can efficiently prepare a uniformly
random n-qubit state |ψA i. But what if we want to use a random oracle to apply a uniformly random
n-qubit unitary UA ? It is clear that we can do this if we have exponential time: given an oracle A,
we simply query an exponentially long prefix A∗ of A, and then treat A∗ as an explicit description of a
quantum circuit for UA . But what if we can make only polynomially many quantum queries to A? We do
not know whether that suffices for applying a random unitary; indeed, we do not even have a conjecture
about this.
What we can show is that a single quantum query to the classical oracle A does not suffice for
applying a random unitary. In particular, suppose every entry of an n-qubit unitary matrix UA is a
degree-1 polynomial in the bits of A (as it must be, if UA is the result of a single quantum query). Then
UA can assume at most 42 distinct values as we range over the possible A’s, as opposed to the Ω c2
n 2n
that would be needed to approximate every n-qubit unitary. To prove this statement, we first need a
lemma about matrices satisfying a certain algebraic relation.
Lemma 6.6. Let E1 , . . . , EM be nonzero N × N matrices over C, and suppose that Ei E †j + E j Ei† = 0 for
all i 6= j. Then M ≤ 2N.
(k)
Proof. Suppose by contradiction that M > 2N. Let ei be vector in CN corresponding to the kth row of
Ei . Then the condition Ei E †j + E j Ei† = 0 implies that
(k) (l) (k) (l)
ei · e j + e j · ei = 0
for all i 6= j and k, l, where · denotes the complex inner product. Now for all i, let k (i) be the minimum
(k) (k(1)) (k(M))
k such that ei 6= 0, and consider the vectors e1 , . . . , eM ∈ CN . Certainly
these vectors
are not all
(k(i)) (k( j))
orthogonal—indeed, since M > 2N, there must exist i 6= j such that Re ei ·ej 6= 0. There are
now two cases: if k (i) = k ( j), then
(k(i)) (k(i)) (k(i)) (k(i))
ei ·ej +ej · ei 6= 0
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 152
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
and we are done. On the other hand, if k (i) 6= k ( j), then
(k(i)) (k( j)) (k(i)) (k( j))
ej · ei = −ei ·ej
(k(i)) (k( j))
is nonzero. Hence e j and ei must themselves be nonzero. But if k (i) > k ( j), then this contradicts
the minimality of k (i), while if k (i) < k ( j) then it contradicts the minimality of k ( j).
We can now prove the main result.
Theorem 6.7. Let U (X) be an N × N matrix, every entry of which is a degree-1 complex polynomial in
variables X = (x1 , . . . , xk ). Suppose U (X) is unitary for all X ∈ {0, 1}k . Then U (X) can assume at most
4N distinct values as we range over X ∈ {0, 1}k .
Proof. By suitable rotation, we can assume without loss of generality that U 0k is the N × N identity
I. Let Xi be the k-bit string with a ‘1’ only in the ith position, and let Ei := U (Xi ) − I. Then for all i,
Ei Ei† = (U (Xi ) − I) U (Xi )† − I † = I −U (Xi ) −U (Xi )† + I = −Ei − Ei† .
Next, for all i 6= j, let Xi j be the k-bit string with ‘1’s only in the ith and jth positions. Since U (X) is an
affine function of X, we have
U (Xi j ) = U 0k + U (Xi ) −U 0k + U (X j ) −U 0k = I + Ei + E j .
Therefore
0 = U (Xi j )U (Xi j )† − I
= (I + Ei + E j ) I † + Ei† + E †j − I
= Ei Ei† + E j E †j + Ei E †j + E j Ei† + Ei + Ei† + E j + E †j
= Ei E †j + E j Ei† .
Here the first line uses unitarity, and the fourth line uses the fact that Ei + Ei† = −Ei Ei† and E j + E †j =
−E j E †j . Lemma 6.6 now implies that there can be at most 2N nonzero Ei ’s. Hence U (X) can depend
nontrivially on at most 2N bits of X, and can assume at most 22N values.
7 Open problems
The most obvious problems left open by this paper are, first, to prove a classical oracle separation
between QMA and QCMA, and second, to prove that the Group Non-Membership problem is in QCMA.
We end by listing four other problems.
(1) The class QMA (2) is defined similarly to QMA, except that now there are two quantum provers
who are guaranteed to share no entanglement. Is there a quantum oracle relative to which
QMA (2) 6= QMA?
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 153
S. A ARONSON AND G. K UPERBERG
(2) Is there a quantum oracle relative to which BQP/qpoly 6⊂ QMA/poly? This would show that the
containment BQP/qpoly ⊆ PP/poly proved in [2] is in some sense close to optimal.
(3) Can we use the ideas of Section 6 to give a classical oracle relative to which BQP 6⊂ PH? What
about a classical oracle relative to which NP ⊆ BQP but PH 6⊂ BQP?12
(4) Is there a polynomial-time quantum oracle algorithm Q, such that for every n-qubit unitary trans-
formation U, there exists a classical oracle A such that QA approximately implements U? Alter-
natively, would any such algorithm require more than poly (n) queries to A?13
8 Acknowledgments
We thank the anonymous reviewers for their suggestions, and Dorit Aharonov, Laci Babai, Robert Beals,
Robert Guralnick, Bill Kantor, and Cris Moore for helpful correspondence.
References
[1] * S. A ARONSON: Quantum copy-protection. In preparation. 1.1
[2] * S. A ARONSON: Limitations of quantum advice and one-way communication. Theory of Comput-
ing, 1:1–28, 2005. quant-ph/0402095. Conference version in Proc. of CCC’2004. [ToC:v001/a001,
arXiv:quant-ph/0402095]. 1, 7
[3] * D. A HARONOV AND T. NAVEH: Quantum NP - a survey. quant-ph/0210077, 2002.
[arXiv:quant-ph/0210077]. 1
[4] * L. BABAI: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429, 1985.
[STOC:10.1145/22145.22192]. 2
[5] * L. BABAI: Bounded round interactive proofs in finite groups. SIAM J. Discrete Math, 5(1):88–
111, 1992. [SIDMA:10.1137/0405008]. 1.1
[6] * L. BABAI AND P. E RD ŐS: Representation of group elements as short products. Annals of
Discrete Math., 12:27–30, 1982. 5, 5.1
[7] * L. BABAI , A. J. G OODMAN , W. M. K ANTOR , E. M. L UKS , AND P. P. P ÁLFY: Short pre-
sentations for finite groups. J. Algebra, 194:79–112, 1997. [Elsevier:10.1006/jabr.1996.6980].
5.1
[8] * L. BABAI AND E. S ZEMER ÉDI: On the complexity of matrix group problems I. In Proc. 25th
FOCS, pp. 229–240, 1984. 1.1, 5, 5.1
12 Note that a simple relativizing argument shows that if NP ⊆ BPP then PH ⊆ BPP.
13 We do not even know whether a single query suffices. Note that Theorem 6.7 does not apply here, since we have dropped
the requirement that QA must implement some n-qubit unitary (as opposed to a more general superoperator) for every oracle A.
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 154
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
[9] * M. B EN -O R , D. C OPPERSMITH , M. L UBY, AND R. RUBINFELD: Non-abelian homomorphism
testing, and distributions close to their self-convolutions. In Proc. of 8th Intern. Workshop on
Randomization and Computation (RANDOM’04), pp. 273–285. Springer-Verlag, 2004. ECCC
TR04-052. [Springer:x1tlgm3cexcj]. 5.3
[10] * C. B ENNETT, E. B ERNSTEIN , G. B RASSARD , AND U. VAZIRANI: Strengths and weak-
nesses of quantum computing. SIAM J. Computing, 26(5):1510–1523, 1997. quant-ph/9701001.
[SICOMP:10.1137/S0097539796300933, arXiv:quant-ph/9701001]. 1.1, 3
[11] * K. B ÖR ÖCZKY J R . AND G. W INTSCHE: Covering the sphere by equal spherical balls. In
Discrete and Computational Geometry: The Goodman-Pollack Festschrift, pp. 237–253. Springer,
2003. 4, 4.1
[12] * G. B RASSARD , P. H ØYER , M. M OSCA , AND A. TAPP: Quantum amplitude amplification
and estimation. In S. J. L OMONACO AND H. E. B RANDT, editors, Quantum Computation and
Information, Contemporary Mathematics Series. AMS, 2002. quant-ph/0005055. [arXiv:quant-
ph/0005055]. 4
[13] * J. H. C ONWAY, R. T. C URTIS , S. P. N ORTON , R. A. PARKER , AND R. A. W ILSON: Atlas of
Finite Groups. Clarendon Press, Oxford, 1985. 5
[14] * M. E TTINGER , P. H ØYER , AND E. K NILL: The quantum query complexity of the hidden
subgroup problem is polynomial. Inform. Proc. Lett., 91(1):43–48, 2004. quant-ph/0401083.
[IPL:10.1016/j.ipl.2004.01.024, arXiv:quant-ph/0401083]. 1.1, 5, 5.6, 5
[15] * L. K. G ROVER: A framework for fast quantum mechanical algorithms. In Proc. 30th STOC, pp.
53–62, 1998. quant-ph/9711043. [STOC:10.1145/276698.276712, arXiv:quant-ph/9711043]. 4
[16] * S. H ALLGREN , A. RUSSELL , AND A. TA -S HMA: The hidden subgroup problem and quantum
computation using group representations. SIAM J. Computing, 32(4):916–934, 2003. Conference
version in STOC’2000, p. 627-635. [SICOMP:10.1137/S009753970139450X]. 9, 5.1
[17] * B. H ÖFLING: Efficient multiplication algorithms for finite polycyclic groups, 2007. Submitted.
www-public.tu-bs.de/~bhoeflin/preprints/collect.pdf. 5.1
[18] * A. H ULPKE AND Á. S ERESS: Short presentations for three-dimensional unitary groups. J.
Algebra, 245:719–729, 2001. [Elsevier:10.1006/jabr.2001.8943]. 5.1
[19] * J. K EMPE , A. K ITAEV, AND O. R EGEV: The complexity of the Local Hamil-
tonian problem. SIAM J. Computing, 35(5):1070–1097, 2006. quant-ph/0406180.
[SICOMP:10.1137/S0097539704445226, arXiv:quant-ph/0406180]. 1
[20] * A. K ITAEV: Quantum measurements and the abelian stabilizer problem. ECCC TR96-003,
quant-ph/9511026, 1996. [arXiv:quant-ph/9511026]. 5.1
[21] * A. K ITAEV: Quantum computation: algorithms and error correction. Russian Math. Surveys,
52(6):1191–1249, 1997. 3
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 155
S. A ARONSON AND G. K UPERBERG
[22] * C. M ARRIOTT AND J. WATROUS: Quantum Arthur-Merlin games. Computational Complexity,
14(2):122–152, 2005. [CC:h0521k6666871652]. 1
[23] * C. M OORE , D. N. ROCKMORE , AND A. RUSSELL: Generic quantum Fourier transforms. In
Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 778–787, 2004. quant-ph/0304064.
[SODA:982792.982910, arXiv:quant-ph/0304064]. 5.1
[24] * M. M OSCA AND D. S TEBILA: Unforgeable quantum money. In preparation, 2006. 1.1
[25] * P. M. N EUMANN: An enumeration theorem for finite groups. Quart. J. Math. Ser., 2(20):395–
401, 1969. 5
[26] * L. P YBER: Enumerating finite groups of given order. Annals of Mathematics, 137:203–220,
1993. 8
[27] * R. R AZ AND A. S HPILKA: On the power of quantum proofs. In Proc. 19th Ann. IEEE Conf. on
Computational Complexity, pp. 260–274, 2004. [CCC:10.1109/CCC.2004.1313849]. 1
[28] * A. S HAMIR: IP=PSPACE. J. ACM, 39(4):869–877, 1992. [JACM:10.1145/146585.146609].
1.1
[29] * P. S HOR: Polynomial-time algorithms for prime factorization and discrete logarithms on a quan-
tum computer. SIAM J. Computing, 26(5):1484–1509, 1997. Earlier version in IEEE FOCS 1994.
quant-ph/9508027. [SICOMP:10.1137/S0097539795293172, arXiv:quant-ph/9508027]. 5.1
[30] * C. S IMS: Computational methods in the study of permutation groups. In Computational Prob-
lems in Abstract Algebra, pp. 169–183. Pergamon Press, 1970. 5.1
[31] * J. WATROUS: Succinct quantum proofs for properties of finite groups. In Proc. 41st FOCS, pp.
537–546, 2000. cs.CC/0009002. [FOCS:10.1109/SFCS.2000.892141]. 1.1
AUTHORS
Scott Aaronson [About the author]
assistant professor
MIT, Cambridge, MA
aaronson@csail.mit.edu
http://www.scottaaronson.com
Greg Kuperberg [About the author]
professor
UC Davis, Davis, CA
greg@math.ucdavis.edu
http://www.math.ucdavis.edu/~greg
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 156
Q UANTUM VS . CLASSICAL PROOFS AND ADVICE
ABOUT THE AUTHORS
S COTT A ARONSON dropped out of Council Rock High School in Newtown, PA, before
receiving a bachelor’s degree from Cornell University and a Ph. D. from UC Berkeley.
This is his third paper in Theory of Computing.
Like Scott, G REG K UPERBERG is also a high-school dropout. He received a bachelor’s
degree from Harvard University (1987) and a Ph. D. in geometric topology and quantum
algebra from UC Berkeley (1991). His advisor was Andrew Casson. Both of his parents
are mathematicians, and every subset of the three have authored at least one paper,
including the empty subset if one allows other coauthors. He has compiled a computer-
assisted survey of complexity classes called “Complexity Zoology.”
T HEORY OF C OMPUTING, Volume 3 (2007), pp. 129–157 157