Authors Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400
www.theoryofcomputing.org
On the Power of a Unique Quantum Witness
Rahul Jain Iordanis Kerenidis Greg Kuperberg Miklos Santha
Or Sattath Shengyu Zhang
Received: January 31, 2012; published: August 14, 2012.
Abstract: In a celebrated paper, Valiant and Vazirani (1985) raised the question of whether
the difficulty of NP-complete problems was due to the wide variation of the number of
witnesses of their instances. They gave a strong negative answer by showing that distin-
guishing between instances having zero or one witnesses is as hard as recognizing NP, under
randomized reductions.
We consider the same question in the quantum setting and investigate the possibility
of reducing quantum witnesses in the context of the complexity class QMA, the quantum
analogue of NP. The natural way to quantify the number of quantum witnesses is the
dimension of the witness subspace W in some appropriate Hilbert space H. We present an
efficient deterministic procedure that reduces any problem where the dimension d of W is
bounded by a polynomial to a problem with a unique quantum witness. The main idea of
our reduction is to consider the alternating subspace of the tensor power H⊗d . Indeed, the
intersection of this subspace with W ⊗d is one-dimensional, and therefore can play the role of
the unique quantum witness.
ACM Classification: F.1.3
AMS Classification: 81P68
Key words and phrases: Valiant-Vazirani Theorem, unique witness, quantum, QMA
1 Introduction
One of the most fundamental ideas of modern complexity theory is that the study of decision-making
procedures involving a single party should be extended to the study of more complex procedures where
several parties interact.
2012 Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v008a017
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
The notions of verification and witness are at the heart of those complexity classes whose definition
inherently involves interaction. The complexity class P is the set of languages decidable by a polynomial-
time deterministic algorithm. Similarly, BPP is the set of promise problems decidable by a polynomial-
time bounded-error randomized algorithm. We can think of such an algorithm as a verifier acting alone.
The simplest interactive extensions of P and BPP are their non-deterministic analogues, respectively NP
and MA [11, 6]. These classes also involve an all-powerful prover that sends a single message which is
used by the verifier’s decision making procedure together with the input. We require that on positive
instances there is some message (called in that case a witness) that makes the verifier accept, whereas on
negative instances, all the possible messages are rejected by the verifier. In the case of MA we can fix the
permitted error of the verifier, rather arbitrarily to any constant, say 1/3.
Quantum complexity classes are often defined by analogy to their classical counterparts. Since
quantum computation is inherently probabilistic, the quantum analogue of MA is considered to be the
right definition of non-deterministic quantum polynomial-time. The quantum extension is twofold: the
verifier has the power to decide promise problems in BQP, quantum polynomial-time, and the messages
he receives from the prover are also quantum. Thus, QMA is the set of promise problems such that on
positive instances there exists a quantum witness accepted with probability at least 2/3 by the polynomial-
time quantum verifier and on negative instances the verifier accepts every quantum state with probability
at most 1/3. While the idea that a quantum state might play the role of a witness goes back to Knill [20],
the class was formally defined by Kitaev [19] under the name of BQNP. The currently used name QMA
was given to the class by Watrous [32]. Kitaev established several error probability reduction properties of
QMA, and proved that the Local Hamiltonian, the quantum analogue of SAT, is complete for it. Watrous
showed that Group non-Membership was a problem in QMA and based on this result he constructed an
oracle under which MA is strictly included in QMA. Since then, various problems have been proven
to be complete for QMA [16, 18, 23, 17, 24]. A potentially weaker quantum extension of MA, namely
QCMA, was defined by Aharonov and Naveh [3]: in the case of QCMA, the verifier is still a quantum
polynomial-time algorithm, but the message of the prover can only be classical.
The number of witnesses for positive instances of problems in NP can be exponentially high. Also,
known NP-complete problems have different instances with widely varying numbers of solutions. In a
celebrated paper, Valiant and Vazirani [31] have raised the question of whether the difficulty of the class
NP was due to this wide variation. They gave a strong negative answer to this question in the following
sense. Let UP be the set of problems in NP where in addition on positive instances there exists a unique
witness. We denote by PromiseUP the extension of UP from languages to promise problems. The theorem
of Valiant and Vazirani states that any problem in NP can be reduced in randomized polynomial-time to a
promise problem in PromiseUP, or in set-theoretical terms, NP ⊆ RPPromiseUP .1 The importance of the
class UP also stems from its connection to one-way functions: worst-case one-way functions exist if and
only if UP 6= P [21, 12].
In a recent paper Aharonov, Ben-Or, Brandão and Sattah [1] have asked a similar question for
MA, QCMA and QMA. The restriction of the classical-witness classes MA and QCMA to their unique
variants UMA and UQCMA is rather natural: no change for negative instances, but on positive instances
1 RP is the subclass of problems in BPP where the computation does not err on negative instances, and RPPromiseUP is the
same, except that the RP machine has oracle access to any PromiseUP problem (the oracle can answer arbitrarily when asked
about instances that do not obey the promise).
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 376
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
there has to be exactly one witness that makes the verifier accept with probability at least 2/3, while
all other messages make him accept with probability at most 1/3. The definition of UQMA, the unique
variant of QMA is the following: there is no change for negative instances with respect to QMA, but
on positive instances there has to be a quantum witness state |ψi which is accepted by the verifier with
probability at least 2/3, whereas all states orthogonal to |ψi are accepted with probability at most 1/3.
Aharonov et al. extended the Valiant-Vazirani proof for the classical witness classes by showing that
MA ⊆ RPUMA and QCMA ⊆ RPUQCMA . On the other hand, they left the existence of a similar result for
QMA as an open problem.
Why is it so difficult to reduce the witnesses to a single witness in the quantum case? The basic idea
of Valiant and Vazirani is to use pairwise-independent universal hash functions, having polynomial-size
descriptions, that eliminate independently each witness with some constant probability. The size of
the original witness set can be guessed approximately by a polynomial-time probabilistic procedure,
and in case of a correct guess the hashing keeps alive exactly one witness with again some constant
probability. The same idea basically works for MA and QCMA as long as one additional difficulty is
overcome: on positive instances there can be exponentially more “pseudo-witnesses,” accepted with
probability between 1/3 and 2/3, than witnesses which are accepted with probability at least 2/3. In
this case, the Valiant-Vazirani proof technique will with high probability eliminate all witnesses before
the elimination of the pseudo-witnesses. The solution of Aharonov et al. for this problem is to divide
the interval (1/3, 2/3) into polynomially many smaller intervals, and to show that there exists at least
one interval such that there are approximately as many witnesses accepted with probability within this
interval as above it.
In the quantum case, the set of quantum witnesses can be infinite. For a promise problem in QMA,
we can suppose without loss of generality that on positive instances there exists a subspace W such that
all unit vectors in W are accepted with high probability. The dimension of W could be large and we wish
to reduce it to one. Aharonov et al. [1] considered the special case where the dimension of W is two.
Although classically two witnesses are trivially reducible to the unique witness case, they have shown
that the natural generalization of the Valiant-Vazirani construction cannot solve even the two-dimensional
quantum witness case.
Indeed, the natural generalization of the Valiant-Vazirani construction to this situation is to use random
projections and hope that some one-dimensional subspace of W will be accepted with substantially higher
probability than its orthogonal. A first difficulty is to implement such projections efficiently. But more
importantly, a random projection would not create a polynomial gap in the acceptance probabilities for
the pure states of W : fact all states in W which were accepted with exponentially close probabilities, will
still be accepted after the random projection with exponentially close probabilities. In fact, if two states
in W were accepted with probabilities p1 , p2 where |p1 − p2 | = O(exp(−n)), they will be accepted after
the random projection with probabilities p01 , p02 such that |p01 − p02 | = O(exp(−n)), with high probability
over the choice of the random projection.
Here we describe a fundamentally different proof technique to tackle this problem, which is sufficiently
powerful to solve the case when the dimension of the witness subspace W is polynomially bounded in
the length of the input. This leads us naturally to the quantum analogue of the promise problem class
FewP. This complexity class was defined by Allender [4] as the set of problems in NP with the additional
constraint that there is a polynomial q such that on every positive instance of length n, the number of
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 377
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
witnesses is at most q(n). The class FewP was extensively studied in the context of counting complexity
classes [5, 30, 22, 14, 28]. We define FewQMA, the quantum analogue of FewP, as the set of promise
problems in QMA for which there exists a polynomial q with the following properties: on negative
instances every message of the prover is accepted by the verifier with probability at most 1/3; on a
positive instance x there exists a subspace Wx of dimension between 1 and q(|x|), such that all pure states
in Wx are accepted with probability at least 2/3, while all pure states orthogonal to Wx are accepted with
probability at most 1/3. Our main theorem extends the result of Valiant and Vazirani to this complexity
class. More precisely, we show that FewQMA is deterministic polynomial-time Turing-reducible to
UQMA.
Main Theorem. FewQMA ⊆ PUQMA .
The main result can alternatively be formulated by using Hamiltonian Complexity terminology.
Informally, estimating the ground state energy of a poly-gapped local Hamiltonian with a polynomial
degeneracy, is not harder than estimating the ground state energy of a poly-gapped local Hamiltonian
with a unique ground state. See Theorem 4.9 for the formal statement.
To explain the intuition behind the construction, let us first examine a simple proof for FewP ⊆
P PromiseUP . Suppose the FewP problem had d witnesses. Instead of asking for one witness, we ask for
the concatenation of t witnesses and require that each one of the witnesses pass the original FewP test. At
first glance, this does not seem to be going in the right direction because the number of witnesses at this
point is d t . Then, we check that the witnesses are in a specific increasing order,
such as the increasing
lexicographic order, and therefore the total number of witnesses is reduced to dt . If t = d, there is exactly
one witness. Of course, we do not know d in advance, but since we have a polynomial bound q(|x|) on it,
we try every possible value t between 1 and q(|x|).
We use a similar technique in the quantum case: instead of manipulating the states within the original
space H of dimension K, we consider its t-fold tensor powers H⊗t . At this point, like in the classical
case, the dimension of W ⊗t grows as d t , where d is the dimension of the witness space W . In the quantum
case, instead of forcing the witnesses to be in one specific order, we force the witnesses to be a signed
superposition of all possible permutations, where the sign depends on the parity (also known as the
signature or sign) of the permutation. Thesubspace spanned by such states is called the alternating
subspace Alt of H⊗t whose dimension is Kt . The important thing to notice is that the dimension of the
intersection Alt ∩W ⊗t is equal to 1 when t = d. The reason is that this intersection is in fact equal to the
alternating subspace of W ⊗t whose dimension is dt . Therefore, we will choose this one-dimensional
subspace as our unique quantum witness. Again, as in the classical case, we do not know the exact
dimension of W , but since we have a polynomial upper bound q(|x|) on it, we just try every possible
value t between 1 and q(|x|).
To give a concrete example, suppose the orthogonal states |1i, |2i and |3i span W . Then, the state
1 1
|ψi = √ (|123i − |213i − |132i − |321i + |231i + |312i) = √ ∑ sgn(σ )|σ (1)σ (2)σ (3)i ,
3! 3! σ ∈S3
is the unique state, up to a global phase, in Alt ∩W ⊗3 , where |i jki is a shorthand for |ii ⊗ | ji ⊗ |ki.
More details are presented as follows. For illustration, let us assume that there are d orthogonal
witnesses that make the verifier accept with probability 1, and all other states in W orthogonal to these
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 378
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
d witnesses make the verifier accept with probability 0. For a fixed t, we would ideally implement
ΠW ⊗t · ΠAlt , the projection to Alt followed by the projection to W ⊗t . This procedure would accept only
one state for the following reason. The unique pure state in Alt ∩W ⊗t (up to a global phase) is clearly
accepted with probability 1. On the other hand, we claim that any state |φ i orthogonal to that is rejected
⊥
with probability 1. Indeed, |φ i can be decomposed as |φ1 i + |φ2 i, where |φ1 i ∈ Alt⊥ and |φ2 i ∈ W ⊗t .
Therefore |φ1 i is rejected by ΠAlt and |φ2 i is rejected by ΠW ⊗t . This implies the claim since we can show
that the two projectors actually commute.
We can efficiently implement ΠAlt by a procedure we call the Alternating Test. A similar procedure
to ours, implementing efficiently the projection to the symmetric subspace Sym of H⊗t , was proposed by
Barenco et al. [7] as the basis of a method for the stabilization of quantum computations. In fact, in the
two-fold tensor product case, the two procedures coincide and become the well-known Swap Test which
was used by Buhrman et al. [9] for deciding if two given pure states are close or far apart.
We cannot implement ΠW ⊗t exactly, but we can approximate it efficiently by a procedure called the
Witness Test. This test just applies independently to all the t components of the state the procedure
at our disposal which decides in H whether a state is a witness or not, and accepts if all applications
accept. There is only one difficulty left: since ΠAlt and the Witness Test do not necessarily commute,
⊥
our previous argument which showed that states in W ⊗t were rejected with probability 1 does not work
anymore. We overcome this difficulty by showing that the commutativity of the two projections implies
⊥
that the projections to Alt of such states are also in W ⊗t , and therefore get rejected with high probability
by the Witness Test.
Note that our reduction (from FewQMA to UQMA) is a deterministic Turing reduction, while the
reduction (from FewP to PromiseUP) used by Valiant-Vazirani is a randomized many-one reduction.
As mentioned after the main theorem, a deterministic Turing reduction can be shown, implying that
FewP ⊆ PPromiseUP . Furthermore, it is easy to convert our reduction to a randomized many-one reduction
by choosing t in our algorithm uniformly between 1 and q(|x|), instead of trying all possible t between 1
and q(|x|); by doing that, we lose a multiplicative factor of 1/q(|x|) in the completeness parameter. Our
reduction is also non-adaptive, similar to the reduction used by Valiant-Vazirani. We believe that reducing
QMA to a unique witness, which this paper leaves as an open question, will require a probabilistic or a
quantum procedure.
The rest of the paper is structured as follows. In Section 2 we state some facts about the interaction of
the tensor products of subspaces with the alternating subspace. In Section 3 we define the complexity
classes we are concerned with. We give two definitions for FewQMA and show that they are equivalent.
Section 4 is devoted to the proof of our main result, and to the proof of the alternative Hamiltonian
complexity formulation of this theorem. Finally, in Section 5 we consider a third definition and show a
weak equivalence with the previous ones. The results in the paper appeared initially as Arxiv preprint
quant-ph/0906.4425v1 by Jain, Kerenidis, Santha and Zhang. Some of this work was done independently
by Sattath and Kuperberg and an initial result in that direction appeared in p. 30 of [29]. The joint version
of the paper appears as Arxiv preprint quant-ph/0906.4425v2.
2 Preliminaries
In this section we present definitions and lemmas that we will need in the proof of our main result.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 379
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
We represent by [t] the set {1, 2, . . . ,t}. For a Hilbert space H, we denote by dim(H) the dimension
of H. For a subspace S of H, let S⊥ represent the subspace of H orthogonal to S, and let ΠS denote the
projector onto S. For subspaces S1 , S2 of H, their direct sum S1 + S2 is defined as span(S1 ∪ S2 ), and
when S1 , S2 are orthogonal subspaces, we denote their (orthogonal) direct sum by S1 ⊕ S2 . The following
relations are standard.
Fact 2.1.
1. Let S1 , S2 be subspaces of a Hilbert space H. Then (S1 ∩ S2 )⊥ = S1⊥ + S2⊥ .
2. Let S1 , S2 be subspaces of Hilbert spaces H1 , H2 respectively. Then
(S1 ⊗ S2 )⊥ = (S1⊥ ⊗ H2 ) + (H1 ⊗ S2⊥ ) = (S1⊥ ⊗ H2 ) ⊕ (S1 ⊗ S2⊥ ) .
Let B represent the two-dimensional complex Hilbert space and let {|0i, |1i} be the computational
basis for B. For a natural number k, the computational basis of B⊗k (the k-fold tensor of B) consists of
{|ri : r ∈ {0, 1}k }, where |ri denotes the tensor product |r1 i ⊗ · · · ⊗ |rk i for the k-bit string r = r1 . . . rk .
Fix k and let H denote B⊗k and let K = 2k . By a pure state in H, we mean a unit vector in H. A mixed
state or just state is a positive semi-definite operator in H with trace 1. We refer the reader to the text [26]
for concepts related to quantum information theory. For a natural number t ∈ [K], we will think of states
of H⊗t as consisting of t registers, where the content of each register is a state with support in H.
We will consider the intersection of W ⊗t , where W is a d-dimensional subspace of H for some d
satisfying 2 ≤ t ≤ d ≤ K, with the alternating and symmetric subspaces of H⊗t . Let St denote the set of
all permutations π : [t] → [t].
For a permutation π ∈ St , let the unitary operator Uπ , acting on H⊗t , given by
Uπ |ψ1 i ⊗ · · · ⊗ |ψt i = |ψπ(1) i ⊗ · · · ⊗ |ψs(t) i ,
and extended by linearity to the entire space H⊗t .
For permutations π1 , π2 , let π1 ◦ π2 represent their composition. It is easily seen that Uπ1 ◦π2 = Uπ1 Uπ2 .
For distinct i, j ∈ [t], let πi j be the transposition of i and j. For all distinct i, j ∈ [t], the symmetric subspace
of W ⊗t with respect to i and j is given by
⊗t
SymW
ij = {|φ i ∈ W ⊗t : Uπi j |φ i = |φ i} ,
and the symmetric subspace of W ⊗t is defined as
⊗t \ ⊗t
SymW = SymW
ij .
i6= j
Similarly, for all distinct i, j ∈ [t], the alternating subspace of W ⊗t with respect to i and j is defined as
⊗t
AltW
ij = {|φ i ∈ W ⊗t : Uπi j |φ i = −|φ i} ,
and the alternating subspace of W ⊗t is defined as
⊗t \ ⊗t
AltW = AltW
ij .
i6= j
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 380
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
⊗t ⊗t
The subspaces SymW and AltW are of dimension d+t−1 d
t and respectively [8, Ch. I.5]. In
H⊗2 H⊗2 K+1 K
t
particular, Alt and Sym have respective dimensions 2 and 2 and, since they are orthogonal,
H⊗2 H⊗2
we have H = Alt
⊗2 ⊕ Sym . This implies that for every distinct i, j ∈ [t], we have
⊗t ⊗t
AltW W
i j ⊕ Symi j = W ⊗t .
⊗t ⊥ ⊗t
Claim 2.2. AltW ∩ W ⊗t = ∑i6= j SymW
ij .
⊗t ⊗t ⊗t ⊥ ⊗t ⊥
Proof. Since AltW W
i j ⊕ Symi j = W ⊗t , we have AltW
ij = SymW
ij ⊕ W
⊗t . Therefore
!
\ ⊥
W ⊗t ⊥ ⊗t ⊗t ⊗t
AltW ∩ W ⊗t (by definition of AltW )
Alt ∩W = ij
i6= j
!
⊗t ⊥
= ∑ AltWi j ∩ W ⊗t (from Fact 2.1)
i6= j
!
W ⊗t ⊗t ⊥
= ∑ Symi j ⊕ W ∩ W ⊗t
i6= j
!
⊗t ⊗t ⊥
SymW ∩ W ⊗t
= ∑ ij ⊕ W
i6= j
⊗t
= ∑ SymW
ij .
i6= j
⊗t
The last equality holds since ∑i6= j SymW
ij ⊆ W ⊗t .
Note that for W = H the claim states that
⊗t ⊥
AltH = ∑ SymH
⊗t
ij .
i6= j
For us, a particularly important case is when the number of registers t is equal to d, the dimension of
⊗d
the subspace W . Then the alternating subspace AltW is one-dimensional. Let {|ψ1 i, . . . , |ψd i} be any
orthonormal basis of W , and let the vector |Walt i ∈ W ⊗d be defined as
1
|Walt i = √ ∑ sgn(π) Uπ |ψ1 i ⊗ · · · ⊗ |ψd i, (2.1)
d! π∈Sd
where sgn(π) denotes the sign of the permutation π. The following claim states that |Walt i spans the
⊗d
one-dimensional subspace AltW . This immediately implies that |Walt i is independent of the choice of
the basis (up to a global phase).
⊗d
Claim 2.3. AltW = span{|Walt i}.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 381
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
⊗d ⊗d
Proof. We show that |Walt i ∈ AltW . This implies the statement since dim AltW = dd = 1. For any
⊗d
distinct i, j ∈ [d] we show |Walt i ∈ AltW 0
i j . For a permutation π ∈ Sd , we set π = πi j ◦ π. We then have
1
Uπi j |Walt i = Uπi j √ ∑ sgn(π) Uπ |ψ1 i ⊗ · · · ⊗ |ψd i
d! π∈Sd
1
= √ ∑ sgn(π) Uπi j ◦π |ψ1 i ⊗ · · · ⊗ |ψd i
d! π∈Sd
1
= √ ∑ sgn(πi−1j ◦ π 0 ) Uπ 0 |ψ1 i ⊗ · · · ⊗ |ψd i
d! π 0 ∈Sd
1
= (−1) · √ ∑ sgn(π 0 ) Uπ 0 |ψ1 i ⊗ · · · ⊗ |ψd i
d! π 0 ∈Sd
= −|Walt i ,
where we used that sgn(πi−1 0 0
j ◦ π ) = −sgn(π ).
Next, we show that the projections on the spaces AltH and W ⊗t commute for any 2 ≤ t ≤ d.
⊗t
Claim 2.4. Let 2 ≤ t ≤ d. Then, ΠAltH⊗t · ΠW ⊗t = ΠW ⊗t · ΠAltH⊗t .
⊗t ⊥ ⊗t
Proof. Set T = AltW ∩W ⊗t . Then W ⊗t = AltW ⊕ T and hence, ΠW ⊗t = ΠAltW ⊗t + ΠT . We have
⊗t ⊥
T = AltW ∩ W ⊗t
⊗t
= ∑ SymW
ij (from Claim 2.2)
i6= j
⊆ ∑ SymH
⊗t
ij (by definition)
i6= j
⊥
= AltH
⊗t
(from Claim 2.2) .
This implies that ΠAltH⊗t · ΠT = ΠT · ΠAltH⊗t = 0. Also, AltW ⊆ AltH since AltW = AltH ∩W ⊗t .
⊗t ⊗t ⊗t ⊗t
Therefore, we have
ΠAltH⊗t · ΠW ⊗t = ΠAltH⊗t · (ΠAltW ⊗t + ΠT ) = ΠAltW ⊗t .
Similarly
ΠW ⊗t · ΠAltH⊗t = ΠAltW ⊗t .
Hence ΠAltH⊗t · ΠW ⊗t = ΠW ⊗t · ΠAltH⊗t .
This commutativity relation enables us to derive the following property
⊗d ⊥
Claim 2.5. For any state |φ i ∈ AltW , we have ΠAltH⊗d |φ i ∈ (W ⊗d )⊥ .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 382
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
⊥ ⊥
= AltH ∩ W ⊗d , and therefore, AltW = AltH ∩ W ⊗d
⊗d ⊗d ⊗d ⊗d
Proof. First note that AltW and by
Fact 2.1,
⊗d ⊥ ⊗d ⊥
⊥
AltW = AltH + W ⊗d .
⊥ ⊥
Hence we can decompose |φ i as |φ1 i + |φ2 i, where |φ1 i ∈ AltH
⊗d
and |φ2 i ∈ W ⊗d . As
ΠAltH⊗d |φ1 i = 0 ,
it suffices to show that ΠAltH⊗d |φ2 i ∈ (W ⊗d )⊥ . For this, we prove that
Π(W ⊗d )⊥ · ΠAltH⊗d |φ2 i = ΠAltH⊗d |φ2 i .
Claim 2.4 implies that
ΠAltH⊗d · Π(W ⊗d )⊥ = Π(W ⊗d )⊥ · ΠAltH⊗d .
⊥
Also, |φ2 i = Π(W ⊗d )⊥ |φ2 i since |φ2 i ∈ W ⊗d . Therefore we can conclude by the following equalities:
Π(W ⊗d )⊥ · ΠAltH⊗d |φ2 i = ΠAltH⊗d · Π(W ⊗d )⊥ |φ2 i = ΠAltH⊗d |φ2 i.
3 Complexity classes
In this section we define the relevant complexity classes and state the facts needed about them. We assume
without loss of generality that there is only a measurement of a single qubit at the end of the quantum
computation. For a quantum circuit V , we let V also represent the unitary transformation performed by
the circuit. We call a verification procedure a family of quantum circuits {Vx : x ∈ {0, 1}∗ } uniformly
generated in polynomial-time, together with polynomials k and m such that Vx acts on k(|x|) + m(|x|)
qubits. We refer to the first k(|x|) qubits as message qubits and to the last m(|x|) qubits as auxiliary qubits.
To simplify notation, when the input x is implicit in the discussion, we refer to k(|x|) by k, and to m(|x|)
by m. We will make repeated use of the following projections in B⊗(k+m) :
Πacc = |1ih1| ⊗ Ik+m−1 , Πinit = Ik ⊗ |0m ih0m | ,
where In is the identity operator on n qubits. We will also make use of the operator Πx defined as
Πx = Πinit Vx† Πacc Vx Πinit . (3.1)
It is easy to see that Πx is positive semi-definite.
Given a verification procedure, on input x, a Quantum Merlin-Arthur protocol proceeds in the
following way: the prover Merlin sends a pure state |ψi ∈ B⊗k to the verifier Arthur, who then applies
the circuit Vx to |ψi ⊗ |0m i, and accepts if the measurement of the first qubit of the result gives 1. We
will denote the probability that Arthur accepts x with state |ψi by Pr[Vx outputs Accept on |ψi], which is
equal to kΠaccVx (|ψi ⊗ |0m i)k2 .
A promise problem is a tuple L = (Lyes , Lno ) with Lyes ∪ Lno ⊆ {0, 1}∗ and Lyes ∩ Lno = 0.
/ We now
define the following complexity classes.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 383
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
Definition 3.1. A promise problem L = (Lyes , Lno ) is in the complexity class Quantum Merlin-Arthur
(denoted QMA) if there exists a verification procedure {Vx : x ∈ {0, 1}∗ } with polynomials k and m such
that
2
1. for all x ∈ Lyes , there exists a state |ψi, called a witness, such that ΠaccVx (|ψi ⊗ |0m i) ≥ 2/3,
2
2. for all x ∈ Lno , and for all state |ψi, ΠaccVx (|ψi ⊗ |0m i) ≤ 1/3.
If the input x is not in Lyes ∪ Lno then there is no requirement put on the verification procedure. Same
thing holds for all the relevant definitions below.
For a promise problem in QMA, it can be shown that on positive instances there exists a subspace W
such that all unit vectors in W are accepted with probability higher than the completeness parameter; see
equation (3.3) for a precise definition. Hence, by putting a polynomial upper bound on the dimension of
this subspace, we derive the following definition:
Definition 3.2. Let c, w, s : N → [0, 1] be polynomial-time computable functions such that c(n) >
max{w(n), s(n)} for all n ∈ N. A promise problem L = (Lyes , Lno ) is in the complexity class Few Quantum
Merlin-Arthur (denoted FewQMA(c, w, s)) if there exists a verification procedure {Vx : x ∈ {0, 1}∗ } with
polynomials k and m, and a polynomial q such that
1. for all x ∈ Lyes there exists a subspace Wx of B⊗k with dim(Wx ) ∈ [q(|x|)] such that
2
(a) for all states |ψi ∈ Wx , ΠaccVx (|ψi ⊗ |0m i) ≥ c(|x|), and
2
(b) for all states |φ i ∈ Wx ⊥ , ΠaccVx (|φ i ⊗ |0m i) ≤ w(|x|),
2
2. for all x ∈ Lno and for all pure states |ψi ∈ B⊗k , ΠaccVx (|ψi ⊗ |0m i) ≤ s(|x|).
Definition 3.3. The class Few Quantum Merlin-Arthur (denoted FewQMA) is FewQMA(2/3, 1/3, 1/3).
We next provide an alternative definition of FewQMA(c, w, s) and show that the two definitions are
equivalent.
Definition 3.4. Let c, w, s : N → [0, 1] be polynomial-time computable functions such that, for all n ∈ N,
c(n) > max{w(n), s(n)}. A promise problem L = (Lyes , Lno ) is in the complexity class Alternative
Few Quantum Merlin-Arthur (denoted Alt-FewQMA(c, w, s)) if there exists a verification procedure
{Vx : x ∈ {0, 1}∗ } with polynomials k and m, and a polynomial q such that
1. for all x ∈ Lyes , the number of eigenvalues of Πx which are at least c(|x|) is in [q(|x|)], and no
eigenvalue of Πx is in the open interval (w(|x|), c(|x|)),
2. for all x ∈ Lno , all eigenvalues of Πx are at most s(|x|).
We prove the following equivalence between the two definitions.
Theorem 3.5. Let c, w, s : N → [0, 1] be polynomial-time computable functions such that, for all n ∈ N,
c(n) > max{w(n), s(n)}. Then FewQMA(c, w, s) = Alt-FewQMA(c, w, s).
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 384
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
Proof. Part 1 (Definition 3.4 ⇒ Definition 3.2): Let L be a promise problem in Alt-FewQMA(c, w, s)
with some verification procedure {Vx } and polynomial q according to Definition 3.4. We show that {Vx }
and q satisfy also Definition 3.2 with the same parameters.
We first consider the case x ∈ L. For every |ui ∈ B⊗(k+m) , we have
2
Πacc Vx Πinit |ui = hu|Πx |ui . (3.2)
It is easy to check that all eigenvectors of Πx are also eigenvectors of Πinit . The 1-eigenvectors of
the projector Πinit are of the form |ui ⊗ |0m i with |ui ∈ B⊗k , and any vector orthogonal to these is
an eigenvector with eigenvalue 0. Let r be the number of eigenvalues of Πx that are at least c(|x|),
by hypothesis r ∈ [q(|x|)]. Let {|vi i ⊗ |0m i : i ∈ [r]} be a set of orthonormal eigenvectors of Πx with
respective eigenvalues {λi ≥ c(|x|) : i ∈ [r]}, we set Wx = span({|vi i : i ∈ [r]}). Then all remaining
2k+m −r eigenvalues of Πx are less than or equal to w(|x|). Let {|vi i⊗|0m i : i ∈ {r +1, . . . , 2k+m }} be a set
of orthonormal eigenvectors with such eigenvalues. It is clear then that Wx⊥ = span({|vi i : r < i ≤ 2k+m }).
We consider a pure state |ψi = ∑i∈[r] αi |vi i in Wx . Then,
2 2
ΠaccVx (|ψi ⊗ |0m i) = ΠaccVx Πinit (|ψi ⊗ |0m i) = hψ| ⊗ h0m | Πx |ψi ⊗ |0m i
m m
= (hψ| ⊗ h0 |) ∑ λi αi · |vi i ⊗ |0 i
i∈[r]
2
= ∑ |αi | · λi ≥ c(|x|) .
i∈[r]
If |φ i ∈ Wx⊥ is a pure state then by similar arguments we get kΠaccVx (|φ i ⊗ |0m i) k2 ≤ w(|x|).
When x ∈/ L, condition 2 of Definition 3.2 gets satisfied analogously from condition 2 of Definition 3.4.
Part 2 (Definition 3.2 ⇒ Definition 3.4): Let L ∈ FewQMA(c, w, s) with some verification procedure
{Vx } and polynomial q according to Definition 3.2. We claim that {Vx } and q satisfy also Definition 3.4
with the same parameters.
First consider the case x ∈ L. The cardinality of the dimension of the subspace of witnesses Wx in
B⊗k is in [q(|x|)] by hypothesis. We set
Wc = span{|vi ∈ B⊗k : |vi ⊗ |0m i is an eigenvector of Πx with eigenvalue ≥ c(|x|)} (3.3)
and
Ww = span{|vi ∈ B⊗k : |vi ⊗ |0m i is an eigenvector of Πx with eigenvalue > w(|x|)}
We will show that dim(Wx ) = dim(Wc ) and that Wc = Ww , from which the claim follows. For this, it is
sufficient to prove that dim(Wc ) = dim(Wx ) = dim(Ww ), since clearly Wc is a subspace of Ww .
First observe that the definitions of Wc and Ww imply that
Wc⊥ = span{|vi ∈ B⊗k : |vi ⊗ |0m i is an eigenvector of Πx with eigenvalue < c(|x|)}
and
Ww⊥ = span{|vi ∈ B⊗k : |vi ⊗ |0m i is an eigenvector of Πx with eigenvalue ≤ w(|x|)} .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 385
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
Let us suppose that dim(Wx ) < dim(Wc ). Then there exists a vector |ui in Wc ∩Wx⊥ . Since |ui ∈ Wc , using
arguments as in Part 1 above, we have kΠaccVx (|ui ⊗ |0m i)k2 ≥ c(|x|). However, since |ui ∈ Wx⊥ , from
condition 1b of Definition 3.2 we have kΠaccVx (|ui ⊗ |0m i)k2 ≤ w(|x|) < c(|x|) which is a contradiction.
We similarly reach a contradiction assuming dim(Wx ) > dim(Wc ) and hence dim(Wx ) = dim(Wc ).
The equality dim(Ww ) = dim(Wx ) can be proven by an argument analogous to the proof of dim(Wx ) =
dim(Wc ).
In the case x ∈
/ L, assume for contradiction that there is an eigenvalue λ > s(|x|) of Πx with eigenvector
|vi ⊗ |0m i. Then as before,
2 2
Πacc Vx (|ψi ⊗ |0m i) = Πacc Vx Πinit (|vi ⊗ |0m i)
= (hv| ⊗ h0m |)Πx (|vi ⊗ |0m i) = λ > s(|x|) ,
which contradicts condition 2 of Definition 3.2.
The alternative definition of FewQMA(c, w, s) is useful in arriving at the following strong error-
probability reduction theorem whose proof is the same as the QMA strong error-probability reduction
proof in Marriott and Watrous [25] and hence is skipped.
Theorem 3.6 (Error reduction). Let c, w, s : N → [0, 1] be polynomial-time computable functions such that
for some polynomial p, for all n, they satisfy c(n) > max{w(n), s(n)} + 1/p(n). Let r be any polynomial.
Then for any L ∈ FewQMA(c, w, s) having a verification procedure with polynomials k, m, q, there exists
a verification procedure for L with parameters (c0 , w0 , s0 ) = (1 − 2−r , 2−r , 2−r ) and polynomials k0 = k,
m0 = poly(m, r) and q0 = q.
Definition 3.7. A promise problem L = (Lyes , Lno ) is in the complexity class Unique Quantum Merlin-
Arthur (denoted UQMA) if L is in FewQMA with the additional constraint that for all x ∈ Lyes , the
subspace Wx of witnesses in the definition of FewQMA is one-dimensional.
Definition 3.8. UQMA-CPP is the promise problem (UQMA-CPPyes , UQMA-CPPno ) where the ele-
ments of UQMA-CPPyes ∪ UQMA-CPPno are descriptions of quantum circuits V with k message qubits
and m auxiliary qubits, such that
1. V ∈ UQMA-CPPyes if
(a) there exists a witness |ψi such that Pr[V outputs Accept on |ψi] ≥ 2/3,
(b) for all states |φ i orthogonal to |ψi, Pr[V outputs Accept on |φ i] ≤ 1/3,
2. V ∈ UQMA-CPPno if for all pure states |ψi, Pr[V outputs Accept on |ψi] ≤ 1/3.
UQMA-CPP can be regarded as the canonical UQMA-complete promise problem.
4 Reducing the dimension of the witness subspace
This section will be entirely devoted to the proof of our main result.
Theorem 4.1. (Main Theorem) FewQMA ⊆ PUQMA .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 386
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
Proof. Let L ∈ FewQMA have a verification procedure {Vx0 : x ∈ {0, 1}∗ } with polynomials k, m0 , q. Let
r be a polynomial such that q2−r ≤ 1/3. Then, we know from Theorem 3.6 that
L ∈ FewQMA(1 − 2−r , 2−r , 2−r )
with verification procedure {Vx : x ∈ {0, 1}∗ } and polynomials k, m, q.
Our goal is to describe a deterministic polynomial-time algorithm A, with access to the oracle O
for the promise problem UQMA-CPP, that decides the promise problem L. Broadly, our algorithm
works in the following way. On input x and for all t ∈ [q(|x|)], A calls O with a quantum circuit Atx
that uses t · k message qubits and t · m auxiliary qubits, and outputs Accept if and only if the message
has the following two properties: first, it belongs to the alternating subspace of H⊗t and second the
circuit Vx , when performed on each of the t registers separately, outputs Accept on all of them. A accepts
iff for some t, oracle O accepts. We will prove that for x ∈ Lyes , we have Adx ∈ UQMA-CPPyes , where
d = dim(Wx ). Hence O accepts Adx and therefore A accepts. On the other hand, for x ∈ Lno , we show that
for all t ∈ [q(|x|)], Atx ∈ UQMA-CPPno and hence A rejects.
We first describe in detail the Alternating Test and the Witness Test that appear in the algorithm. In
our descriptions below k, m, q, r represent the integers k(|x|), m(|x|), q(|x|) and r(|x|) respectively.
4.1 Alternating test
Let H be the Hilbert space B⊗k and let t ∈ [2k ]. Let us fix some polynomial-time computable bijection
between the set [t!] and the set of permutations St . Let Pt be the (t!)-dimensional Hilbert space spanned
by vectors |ii, for i ∈ [t!]. We will use the elements of St for describing the above basis vectors via the
fixed bijection.
The Alternating Test with parameter t receives, as input, a pure state in H⊗t and performs a unitary
operation in the Hilbert space Pt ⊗ H⊗t , followed by a measurement. We will refer to the elements of
Pt ⊗ H⊗t as consisting of two registers R and S, where the content of each register is a mixed state with
support over the corresponding Hilbert space.
Let us define
1
|sgnt i = √ ∑ sgn(π)|πi .
t! π∈St
Alternating Test(t)
Input: A pure state |ψi ∈ H⊗t in the (t · k)-qubit register S.
Output: The content of S and Accept or Reject.
1
1. Create the state √ ∑ |πi ⊗ |ψi.
t! π∈St
2. Apply the unitary U : |πi ⊗ |ψi → |πi ⊗Uπ |ψi.
3. Perform the measurement (M, I − M), where M = |sgnt ihsgnt | ⊗ IH⊗t . Output the content of S.
Output Accept if the state has been projected onto M and output Reject otherwise.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 387
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
It is easily verified that the Alternating Test(t) runs in time polynomial in t · k. Since we will only
call it with t ∈ [q], its running time will be polynomial in |x|. The following lemma states that the
Alternating Test(t) is a projection onto the subspace AltH .
⊗t
Lemma 4.2.
1. For any pure state |ψi ∈ AltH , the Alternating Test(t) outputs the state |ψi and Accept with
⊗t
probability 1.
⊥
2. For any |φ i ∈ AltH
⊗t
, the Alternating Test(t) outputs Accept with probability 0.
Proof. Part 1: Since |ψi ∈ AltH we have Uπ |ψi = sgn(π) · |ψi, and therefore the state after Step 2 is
⊗t
1 1
√ ∑ |πi ⊗Uπ |ψi = √ ∑ sgn(π) · |πi ⊗ |ψi = |sgnt i ⊗ |ψi .
t! π∈St t! π∈St
Part 2: By Claim 2.2, we have
⊗t ⊥
AltH = ∑ SymH
⊗t
ij .
i6= j
Hence it is enough to show that for all distinct i, j ∈ [t] and for any vector |φ i ∈ SymH
⊗t
i j , the probability
p that the Alternating Test(t) outputs Accept is 0. We have
1 1
p = √ ∑ hσ | ⊗ hφ |Uσ† |sgnt ihsgnt | ⊗ IH⊗t √ ∑ |πi ⊗Uπ |φ i
t! σ ∈St t! π∈St
1 2
=
t! σ ,π∈S∑ sgn(σ ) · sgn(π) · hφ |Uσ†Uπ |φ i .
t
H ⊗t
We define π 0 = π ◦ πi j . Then π = π 0 ◦ πi−1 0 0
j = π ◦ πi j and sgn(π) = −sgn(π ). Since |φ i ∈ Symi j , we
have Uπi j |φ i = |φ i and hence Uπ 0 ◦πi j |φ i = Uπ 0 · (Uπi j |φ i) = Uπ 0 |φ i. Therefore,
1 2
p =
t! ∑ sgn(σ ) · sgn(π) · hφ |Uσ†Uπ |φ i
σ ,π∈St
−1
= sgn(σ ) · sgn(π 0 ) · hφ |Uσ† Uπ 0 ◦πi j |φ i
(t!)2 σ ,π∑
0 ∈S
t
−1
= sgn(σ ) · sgn(π 0 ) · hφ |Uσ† Uπ 0 |φ i
(t!)2 σ ,π∑
0 ∈S
t
= −p .
Hence p = 0.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 388
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
4.2 Witness test
The Witness Test with parameter t ∈ [q] receives as input a pure state in H⊗t and performs a unitary
operation in the Hilbert space H⊗t ⊗ B⊗(tm) followed by a measurement. We will refer to the elements of
H⊗t ⊗ B⊗(tm) as consisting of t pairs of registers (Ti , Zi ) respectively on k and m qubits, for i ∈ [t]. All
registers Zi will be initialized to |0m i.
Witness Test(t)
Input: A pure state |ψi ∈ H⊗t in the k-qubit registers Ti , for i ∈ [t].
Output: Accept or Reject.
1. For all i ∈ [t], append a register Zi initialized to |0m i and apply the circuit Vx on registers
(Ti , Zi ).
2. Output Accept if for all i ∈ [t], Vx outputs Accept; otherwise output Reject.
We can describe the Witness Test(t) as the operator (ΠaccVx )⊗t acting on a state2 |ψi ⊗ |0tm i. Hence,
Pr[Witness Test(t) outputs Accept on |ψi] = k(ΠaccVx )⊗t (|ψi ⊗ |0tm i)k2 . Note that the description of
the circuit Vx⊗t can be generated in polynomial-time, since the circuit family {Vx , x ∈ {0, 1}∗ } is uniformly
generated in polynomial-time.
In what follows we will have to argue about the probability that the verification procedure Vx outputs
Accept when its input is some mixed state. Even though we have only considered pure states as inputs
in the definition of the class FewQMA, we will see that it is not hard to extend our arguments to mixed
states.
Lemma 4.3.
1. If x ∈ Lyes , then for every |ψi ∈ Wx⊗t , the Witness Test(t) outputs Accept with probability at least
2/3.
2. If x ∈ Lyes , then for every |φ i ∈ (Wx⊗t )⊥ , the Witness Test(t) outputs Accept with probability at
most 1/3.
3. If x ∈ Lno , then for every |ψi ∈ H⊗t , the Witness Test(t) outputs Accept with probability at most
1/3.
Proof. Part 1: By completeness we know that for any pure state |ψ 0 i ∈ Wx , we have
Pr[Vx outputs Reject on |ψ 0 i] ≤ 2−r .
Let ρi denote the reduced density matrix of |ψi on register Ti . Since |ψi ∈ Wx ⊗t , then for every i ∈ [t],
the density matrix ρi is a distribution of pure states that all belong to Wx and hence
Pr[Vx outputs Reject on ρi ] ≤ 2−r .
2 More accurately, the operator (Π V )⊗t acts on a reordered version of |ψi ⊗ |0tm i, but this will be ignored for the sake of
acc x
clarity.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 389
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
It follows from the union bound that
t
Pr[Witness Test(t) outputs Accept on |ψi] ≥ 1 − ∑ Pr[Vx outputs Reject on ρi ]
i=1
≥ 1 − t · 2−r ≥ 2/3 ,
where the last inequality follows from the choice of r.
Part 2: For i ∈ [t], let
Si = Wx ⊗ · · · ⊗Wx ⊗Wx⊥ ⊗ H ⊗ · · · ⊗ H ,
where Wx⊥ stands in the ith component of the tensor product. By Fact 2.1 we have (Wx ⊗t )⊥ = i∈[t] Si .
L
Let us therefore consider a pure state |φ i ∈ i∈[t] Si and let |φ i = ∑i∈[t] ai |φi i, where |φi i is a pure
L
state in Si . Then ∑ti=1 |ai |2 = 1 because the |φi i’s are also orthogonal. Furthermore, let ρi be the reduced
density matrix of |φi i on register Ti . Then the support of ρi is over Wx⊥ . Since for any pure state |φ 0 i ∈ Wx⊥
we have Pr[Vx outputs Accept on |φ 0 i] ≤ 2−r , we conclude that Pr[Vx outputs Accept on ρi ] ≤ 2−r .
The probability that the Witness Test(t) outputs Accept on |φi i is equal to the probability that all t
applications of Vx output Accept, which is less than the probability that the ith application of Vx outputs
Accept, since the projections, performed in different registers, commute. Hence,
Pr[Witness Test(t) outputs Accept on |φi i] ≤ Pr[Vx outputs Accept on ρi ] ≤ 2−r .
Now for the input |φ i we have
2
Pr[Witness Test(t) outputs Accept on |φ i] = (ΠaccVx )⊗t (|φ i ⊗ |0tm i)
2
= ∑ ai (ΠaccVx )⊗t (|φi i ⊗ |0tm i)
i∈[t]
!2
≤ ∑ |ai | · (ΠaccVx )⊗t (|φi i ⊗ |0tm i)
i∈[t]
! !
2 ⊗t tm 2
≤ ∑ |ai | · ∑ (ΠaccVx ) (|φi i ⊗ |0 i)
i∈[t] i∈[t]
≤ t · 2−r ≤ 1/3 .
In the above calculation the first two inequalities follow respectively from the triangle inequality and the
Cauchy-Schwarz inequality.
Part 3: By the soundness of the original protocol we know that for any pure state |ψ 0 i ∈ H,
Pr[Vx outputs Accept on |ψ 0 i] ≤ 2−r .
The same holds for any mixed state as well. Since the probability that the Witness Test(t) outputs Accept
is at most the probability that the procedure Vx accepts the state on the first register T1 we conclude that
Pr[Witness Test(t) outputs Accept on |ψi] ≤ Pr[Vx outputs Accept on ρ1 ] ≤ 2−r ≤ 1/3 .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 390
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
4.3 Putting it all together
Finally we describe the algorithm A in the figure below and proceed to analyze its properties.
Running time We have seen that the description of the circuit that performs the Alternating Test(t)
can be generated in time polynomial in t · k which is polynomial in |x|. The description of the circuit
that performs the Witness Test(t) can also be generated in polynomial-time, since the circuit family
{Vx : x ∈ {0, 1}∗ } can be generated uniformly in polynomial-time. Hence the description of the circuit Atx
can be generated in polynomial-time and the overall algorithm A runs in polynomial-time.
Algorithm A
Input: x ∈ Lyes ∪ Lno .
Output: Accept or Reject.
1. For t = 1, . . . , q(|x|) do:
(a) Call the oracle O with input Atx , where Atx is the description of the circuit of the following
procedure on t · k message qubits and t · m auxiliary qubits
Input: A pure state |ψi ∈ H⊗t ; Output: Accept or Reject.
i. Run the Alternating Test(t) with input |ψi.
ii. Run the Witness Test(t) with input being the output state of
the Alternating Test(t).
iii. Output Accept iff both Tests output Accept.
(b) If O outputs Accept then output Accept and halt.
2. Output Reject.
Correctness in case x ∈ Lyes Let us consider the oracle call with input Adx where d is the dimension
of Wx . We prove that Adx ∈ UQMA-CPPyes , hence the oracle O outputs Accept and therefore A outputs
Accept as well. Our claim is immediate from the following lemma.
Lemma 4.4.
1. Pr[Adx outputs Accept on |Walt i] ≥ 2/3, where |Walt i is defined in equation (2.1).
2. Let |φ i ∈ H⊗d be orthogonal to |Walt i. Then Pr[Adx outputs Accept on |φ i] ≤ 1/3.
Proof. Part (1): By Claim 2.3, |Walt i ∈ AltH and Lemma 4.2 tells us that the Alternating Test(d)
⊗d
outputs the state |Walt i and Accept with probability 1. Then, since for every i ∈ [d] the support of the
reduced density matrix of |Walt i on register Ti is on Wx , Lemma 4.3 tells us that the Witness Test outputs
Accept with probability at least 2/3.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 391
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
Part (2): By Claim 2.5 and the fact that the state |φ i is orthogonal to |Walt i, we can conclude that if
the Alternating Test(d) outputs Accept then the output state is a pure state |φ 0 i ∈ (W ⊗d )⊥ . Now, by
Lemma 4.3, the probability that the Witness Test(d) outputs Accept on input |φ 0 i is at most 1/3.
Correctness in case x ∈ Lno By Lemma 4.3 it follows easily that for all t ∈ [q] : Atx ∈ UQMA-CPPno .
In this case, O outputs Reject in every iteration, and hence A outputs Reject.
This concludes the proof of Theorem 4.1.
4.4 Implications to gapped Hamiltonians
The Local Hamiltonian is a QMA-complete problem defined as follows.
Definition 4.5 (k-local Hamiltonian). A Hermitian H acting on n qubits is a k-local Hamiltonian if
H = ∑mi=1 Hi , where m ≤ poly(n), and for all i, Hi acts non-trivially on at most k qubits, and kHi k ≤ poly(n)
where k · k is the operator norm.
Definition 4.6 (k-Local Hamiltonian promise problem). The input contains a k-local Hamiltonian H, and
two real numbers a and b such that b − a > 1/ poly(n). In a YES instance, the smallest eigenvalue of H
is at most a, and in a NO instance, all eigenvalues of H are at least b.
The gap between the two lowest eigenvalues of the Hamiltonian plays an important role. For example,
Hastings [13] has shown that under certain conditions on the Hamiltonian and the gap, the ground state
has an efficient classical description. Therefore, a certain variant of the Local Hamiltonian problem is
in NP (which implies that this variant of the problem is not QMA-complete, under the assumption that
NP 6= QMA).
Also, in the adiabatic computation paradigm [10], the gap governs the running time. Therefore, it is
natural to define a variant of the Local Hamiltonian problem with an additional promise on the gap.
Definition 4.7 (Unique k-Local Hamiltonian promise problem). The input is the same as that of the
k-Local Hamiltonian problem. In a YES instance, there is a unique eigenvector of H with eigenvalue at
most a, and no eigenvalues in the interval (a, b), and in a NO instance, all the eigenvalues of H are at
least b.
Since we are interested in the relationship between a unique quantum witness, and polynomially
many quantum witnesses, it is natural to define the following problem:
Definition 4.8 (Few k-Local Hamiltonian promise problem). The input is the same as that of the
k-Local Hamiltonian problem, together with a function q(n) < poly(n). In a YES instance, there are at
most q orthogonal eigenvectors of H with eigenvalues at most a, and no eigenvalues in the interval (a, b),
where in a NO instance, all eigenvalues of H are at least b.
Note that Unique k-Local Hamiltonian is Karp-reducible to Few k-Local Hamiltonian: every Unique
k-Local Hamiltonian instance is also a Few k-Local Hamiltonian instance with q = 1. Now we show that
these two problems are actually equivalent.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 392
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
Theorem 4.9. Few k-Local Hamiltonian is Cook-reducible to Unique k-Local Hamiltonian in polynomial
time.
Proof. Aharonov et al. [1] observed that known proofs [19, 27, 18, 2] of the fact that k-Local Hamiltonian
is QMA-hard, preserve the dimension of the satisfying subspace. Using this observation, they have
shown that Unique k-Local Hamiltonian is UQMA-complete. The same argument also shows that Few
k-Local Hamiltonian is FewQMA-complete.
Since Few k-Local Hamiltonian ∈ FewQMA, Theorem 4.1 shows that Few k-Local Hamiltonian is
Cook-reducible to UQMA-CPP in polynomial time. Combining this with the above facts shows that Few
k-Local Hamiltonian is Cook-reducible to Unique k-Local Hamiltonian in polynomial time.
5 Yet another definition of FewQMA
We have seen two definitions for FewQMA and have proven their equivalence. In high level, one says that
in the yes instances there is a polynomial number of eigenvalues of the projection operator Πx that are
larger than 2/3, while no eigenvalue is in the interval (1/3, 2/3). The other definition says that in a yes
instance there exists a subspace of polynomial dimension such that every state in the subspace is accepted
with probability at least 2/3 and every state orthogonal to this subspace is accepted with probability at
most 1/3.
A natural question is whether the use of a subspace is necessary in the second definition or we could
have just talked about a set of orthonormal vectors of polynomial size, where each vector is accepted with
probability 2/3 and every vector orthogonal to these ones is accepted with probability at most 1/3. While
we are unable to show the equivalence of the complexity class defined this way and FewQMA, a weak
equivalence can indeed be shown. For this we include the parameters of the verification procedure and the
bound on the number of witnesses in the definition of the class, and we also require strong amplification.
More precisely, consider the following definition.
Definition 5.1. Let c, w, s : N → [0, 1] be polynomial-time computable functions such that c(n) >
max{w(n), s(n)} for all n ∈ N. Let q, k, m be polynomials such that q(n) ≤ 2k(n) for all n ∈ N. A
promise problem L = (Lyes , Lno ) is in the complexity class Vector Few Quantum Merlin-Arthur (denoted
Vector-FewQMA(c, w, s, q, k, m)) if there exists a verification procedure {Vx : x ∈ {0, 1}∗ } with k witness
qubits and m ancilla qubits, such that
1. for all x ∈ Lyes there exists an orthonormal basis {|ψ1 i, . . . , |ψ2k i} of the witness space and d ∈
[q(|x|)] such that
2
(a) for all pure states |ψi i with i ∈ [d], ΠaccVx (|ψi i ⊗ |0m i) ≥ c(|x|),
2
(b) for all pure states |ψi i with d + 1 ≤ i ≤ 2k , ΠaccVx (|ψi i ⊗ |0m i) ≤ w(|x|),
2
2. for all x ∈ Lno and for all pure states |ψi ∈ B⊗k , ΠaccVx (|ψi ⊗ |0m i) ≤ s(|x|).
Finally we define
[ 1 1 1
Vector-FewQMA = Vector-FewQMA 1 − , , , q, k, m .
q,k,m
3q 3 · 2k 3
q≤2k
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 393
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
We show Vector-FewQMA = FewQMA by using Horn’s Theorem that states that for a Hermitian
matrix, the vector of the eigenvalues majorizes the diagonal.
Theorem 5.2 ([15]). Let R be a natural number. Let Λ = {λi }Ri=1 and A = {µi }Ri=1 where
λ1 ≥ λ2 ≥ . . . ≥ λR and µ1 ≥ µ2 ≥ . . . ≥ µR .
Then there exists an R × R Hermitian matrix with set of eigenvalues Λ and set of diagonal elements A if
and only if ∑ti=1 (λi − µi ) ≥ 0 for all t ∈ [R] and with equality for t = R.
Theorem 5.3. FewQMA = Vector-FewQMA.
Proof. We first show FewQMA ⊆ Vector-FewQMA. Let L ∈ FewQMA have a verification procedure
{Vx0 : x ∈ {0, 1}∗ } with polynomials k, m0 , q. Let r be a polynomial such that 2−r ≤ 1/(3 · 2k ) and
2−r ≤ 1/(3q). We know from Theorem 3.6 that L ∈ FewQMA(1 − 2−r , 2−r , 2−r ) with verification
procedure {Vx : x ∈ {0, 1}∗ } and polynomials k, m, q, where m = poly(m0 , r). Then the eigenbasis of Πx
(see equation (3.1)) satisfies the requirements of the definition of
1 1 1
Vector-FewQMA 1 − , , , q, k, m .
3q 3 · 2k 3
This shows that L ∈ Vector-FewQMA.
We now show Vector-FewQMA ⊆ FewQMA. Let
1 1 1
L ∈ Vector-FewQMA 1 − , , , q, k, m ,
3q 3 · 2k 3
for some polynomials q, k, m such that q ≤ 2k . Let N = 2k and H = B⊗k . If x ∈ Lyes , then there exist
an orthonormal basis {|ψ1 i, . . . , |ψN i} for H and d ∈ [q], such that for i ∈ [d], µi ≥ 1 − 1/(3q) and for
d + 1 ≤ i ≤ N, µi ≤ 1/(3N), where by definition
def 2
µi = ΠaccVx (|ψi i ⊗ |0m i) = hψi | ⊗ h0m |Πx |ψi i ⊗ |0m i .
Consider now the Hermitian matrix M that describes the projection operator Πx in a basis that is an
extension of {|ψ1 i ⊗ |0m i, . . . , |ψN i ⊗ |0m i}. Note that µi , i ∈ [N] are the first N diagonal elements of M.
Observe that an eigenvector of Πx with non-zero eigenvalue is also an eigenvector of Πinit with non-zero
eigenvalue. Since there are N non-zero eigenvalues of Πinit (counting with multiplicity), there are at most
N non-zero eigenvalues of Πx . This also implies that µi = 0 for N < i ≤ 2k+m . Let the first N eigenvalues
of Πx in decreasing order be λi , i ∈ [N]. Then, using Horn’s theorem,
d d 1
∑ λi ≥ ∑ µi ≥ d · 1 −
i=1 i=1 3q
which implies (since λi ≤ 1, for all i ∈ [N]) that
1 d 2
λd ≥ −(d − 1) + d · (1 − ) ≥ 1− ≥ .
3q 3q 3
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 394
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
Also, we have that
2k+m 2k+m 2k
1 1
λd+1 ≤ ∑ λi ≤ ∑ µi = ∑ µi ≤ (N − d) 3N ≤ 3 .
i=d+1 i=d+1 i=d+1
If x ∈ Lno then by the soundness condition λ1 ≤ 1/3. This shows that L ∈ FewQMA.
Acknowledgments
Most of this work was conducted when R.J., I.K., M.S. and S.Z. were at the Centre for Quantum
Technologies (CQT) in Singapore, and partially funded by the Singapore Ministry of Education and
the National Research Foundation. Research partially supported by European Commission IST project
Quantum Computer Science (QCS) 25596, by the CHIST-ERA project DIQIP, by the French ANR
programs under contract ANR-08-EMER-012 (QRAC project) and ANR-09-JCJC-0067-01 (CRYQ
project), by the French MAEE STIC-Asie program FQIC, by NSF grant DMS-0606795 and by Research
Grants Council of the Hong Kong S.A.R. (Project no. CUHK419309, CUHK418710, CUHK419011).
R.J., I.K., M.S. and S.Z. would like to thank Hartmut Klauck for several insightful discussions during
the process of this work. G.K. and O.S. would like to thank Scott Aaronson and Dorit Aharonov for
discussions.
References
[1] D ORIT A HARONOV, M ICHAEL B EN -O R , F ERNANDO G. S. L. B RANDÃO , AND O R S ATTATH:
The pursuit for uniqueness: extending Valiant-Vazirani theorem to the probabilistic and quantum
settings, 2008. arXiv:0810.4840. 376, 377, 393
[2] D ORIT A HARONOV, DANIEL G OTTESMAN , S ANDY I RANI , AND J ULIA K EMPE: The power
of quantum systems on a line. Comm. Math. Phys., 287(1):41–65, 2009. Preliminary version in
FOCS’07. [doi:10.1007/s00220-008-0710-3] 393
[3] D ORIT A HARONOV AND T OMER NAVEH: Quantum NP - A survey, 2002. arXiv:quant-ph/0210077.
376
[4] E RIC W. A LLENDER: The complexity of sparse sets in P (preliminary report). In Proc. 1st Structure
in Complexity Theory Conf. (1986), volume 223 of Lecture Notes in Comput. Sci., pp. 1–11. Springer,
1986. [doi:10.1007/3-540-16486-3_85] 377
[5] E RIC W. A LLENDER AND ROY S. RUBINSTEIN: P-printable sets. SIAM J. Comput., 17(6):1193–
1202, 1988. [doi:10.1137/0217075] 378
[6] L ÁSZLÓ BABAI: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM
Press, 1985. [doi:10.1145/22145.22192] 376
[7] A DRIANO BARENCO , A NDRÉ B ERTHIAUME , DAVID D EUTSCH , A RTUR E KERT, R ICHARD
J OZSA , AND C HIARA M ACCHIAVELLO: Stabilization of quantum computations by symmetrization.
SIAM J. Comput., 26(5):1541–1557, 1997. [doi:10.1137/S0097539796302452] 379
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 395
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
[8] R AJENDRA B HATIA: Matrix Analysis. Volume 169 of Graduate Texts in Mathematics. Springer,
1997. Springer. 381
[9] H ARRY B UHRMAN , R ICHARD C LEVE , J OHN WATROUS , AND RONALD DE W OLF:
Quantum fingerprinting. Phys. Rev. Lett., 87(16), 2001. arXiv:quant-ph/0102001.
[doi:10.1103/PhysRevLett.87.167902] 379
[10] E DWARD FARHI , J EFFREY G OLDSTONE , S AM G UTMANN , AND M ICHAEL S IPSER: Quantum
computation by adiabatic evolution. 2000. arXiv:quant-ph/0001106. 392
[11] S HAFI G OLDWASSER , S ILVIO M ICALI , AND C HARLES R ACKOFF: The knowledge complexity of
interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989. Preliminary version in STOC’85.
[doi:10.1137/0218012] 376
[12] J OACHIM G ROLLMANN AND A LAN L. S ELMAN: Complexity measures for public-key cryp-
tosystems. SIAM J. Comput., 17(2):309–335, 1988. Preliminary version in FOCS’84.
[doi:10.1137/0217018] 376
[13] M ATTHEW B. H ASTINGS: An area law for one-dimensional quantum systems. J. Statistical
Mechanics: Theory and Experiment, 2007(8):P08024, 2007. arXiv:0705.2024. [doi:10.1088/1742-
5468/2007/08/P08024] 392
[14] L ANE A. H EMASPAANDRA , S ANJAY JAIN , AND N IKOLAI K. V ERESHCHAGIN: Banishing robust
Turing completeness. Internat. J. Found. Comput. Sci., 4(3):245–265, 1993. Preliminary version in
LFCS’92. [doi:10.1142/S012905419300016X] 378
[15] A LFRED H ORN: Doubly stochastic matrices and the diagonal of a rotation matrix. Amer. J. Math.,
76(3):620–630, 1954. [doi:10.2307/2372705] 394
[16] D OMINIK JANZING , PAVEL W OCJAN , AND T HOMAS B ETH: Identity check is QMA-complete,
2003. arXiv:quant-ph/0305050. 376
[17] A LASTAIR K AY: Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem
and the complexity of finding ground-state energies in physical systems. Phys. Rev. A, 76(3):030307,
2007. arXiv:0704.3142. [doi:10.1103/PhysRevA.76.030307] 376
[18] J ULIA K EMPE , A LEXEI K ITAEV, AND O DED R EGEV: The complexity of the Local Hamilto-
nian problem. SIAM J. Comput., 35(5):1070–1097, 2006. Preliminary version in FSTTCS’04.
[doi:10.1137/S0097539704445226] 376, 393
[19] A LEXEI K ITAEV, A LEXANDER S HEN , AND M IKHAIL V YALYI: Classical and Quantum Computa-
tion. Volume 47 of Graduate Studies in Mathematics. Amer. Math. Soc., 2002. Translated from the
1999 Russian original by Lester J. Senechal, AMS. 376, 393
[20] E MANUEL K NILL: Quantum randomness and nondeterminism, 1996. arXiv:quant-ph/9610012.
376
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 396
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
[21] K ER -I KO: On some natural complete operators. Theoret. Comput. Sci., 37(1):1–30, 1985.
[doi:10.1016/0304-3975(85)90085-4] 376
[22] J OHANNES K ÖBLER , U WE S CHÖNING , S EINOSUKE T ODA , AND JACOBO T ORÁN: Turing
machines with few accepting computations and low sets for PP. J. Comput. System Sci., 44(2):272–
286, 1992. Preliminary version in Structure In Complexity Theory, 1989. [doi:10.1016/0022-
0000(92)90022-B] 378
[23] Y I -K AI L IU: Consistency of local density matrices is QMA-complete. In Proc. 10th Internat.
Workshop on Randomization and Computation (RANDOM’06), volume 4110 of Lecture Notes in
Comput. Sci., pp. 438–449. Springer, 2006. arXiv:quant-ph/0604166. [doi:10.1007/11830924_40]
376
[24] Y I -K AI L IU , M ATTHIAS C HRISTANDL , AND F RANK V ERSTRAETE: Quantum computational
complexity of the N-representability problem: QMA-complete. Phys. Rev. Lett., 98(11), 2007.
arXiv:quant-ph/0609125. [doi:10.1103/PhysRevLett.98.110503] 376
[25] C HRIS M ARRIOTT AND J OHN WATROUS: Quantum Arthur-Merlin games. Comput. Complexity,
14(2):122–152, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0194-x] 386
[26] M ICHAEL A. N IELSEN AND I SAAC L. C HUANG: Quantum Computation and Quantum Information.
Cambridge University Press, 2000. [doi:10.1017/CBO9780511976667] 380
[27] ROBERTO O LIVEIRA AND BARBARA T ERHAL: The complexity of quantum spin systems on a two-
dimensional square lattice. Quantum Inf. Comput., 8(10):900–924, 2008. arXiv:quant-ph/0504050.
[ACM:2016987] 393
[28] R AJESH P. N. R AO , J ÖRG ROTHE , AND O SAMU WATANABE: Upward separation for FewP and
related classes. Inform. Process. Lett., 52(4):175 – 180, 1994. [doi:10.1016/0020-0190(94)90123-6]
378
[29] O R S ATTATH: The pursuit of uniqueness: Extending Valiant-Vazirani theorem to the probabilistic
and quantum settings. Master’s thesis, Hebrew University in Jerusalem, 2009. 379
[30] JACOBO T ORÁN: Counting the number of solutions. A survey of recent inclusion results in the area
of counting classes. In Mathematical Foundations of Computer Science (MFCS’90), volume 452 of
Lecture Notes in Comput. Sci., pp. 121–134. Springer, 1990. [doi:10.1007/BFb0029600] 378
[31] L ESLIE G. VALIANT AND V IJAY V. VAZIRANI: NP is as easy as detecting unique solutions.
Theoret. Comput. Sci., 47(1):85–93, 1986. Preliminary version in STOC’85. [doi:10.1016/0304-
3975(86)90135-0] 376
[32] J OHN WATROUS: Succinct quantum proofs for properties of finite groups. In Proc. 41st FOCS, pp.
537–546. IEEE Comp. Soc. Press, 2000. arXiv:cs/0009002. [doi:10.1109/SFCS.2000.892141] 376
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 397
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
AUTHORS
Rahul Jain [About the author]
Assistant professor
National University of Singapore
rahul comp nus edu sg
http://comp.nus.edu.sg/~rahul
Iordanis Kerenidis [About the author]
Senior Researcher
Université Paris Diderot 7, Paris, France
jkeren liafa univ-paris-diderot fr
http://www.liafa.jussieu.fr/~jkeren
Greg Kuperberg [About the author]
Professor
UC Davis, Davis, CA
greg math ucdavis edu
http://www.math.ucdavis.edu/~greg
Miklos Santha [About the author]
Directeur de Recherche
Université Paris Diderot
miklos santha lri fr
http://www.liafa.univ-paris-diderot.fr/~santha
Or Sattath [About the author]
Ph. D. candidate
The Hebrew University, Jerusalem, Israel
sattath cs huji ac il
http://www.cs.huji.ac.il/~sattath
Shengyu Zhang [About the author]
Assistant professor
The Chinese University of Hong Kong
syzhang cse cuhk edu hk
http://www.cse.cuhk.edu.hk/~syzhang
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 398
O N THE P OWER OF A U NIQUE Q UANTUM W ITNESS
ABOUT THE AUTHORS
R AHUL JAIN obtained his Ph. D. in computer science from the Tata Institute of Fundamental
Research, Mumbai, India in 2003. His Ph. D. advisor was Jaikumar Radhakrishnan.
He was a postdoctoral fellow for two years at the University of California, Berkeley
(2004-2006) and for two years at the Institute for Quantum Computing (IQC), University
of Waterloo, Canada (2006-2008). In 2008, he joined NUS as an Assistant Professor in
the Computer Science Department with a cross appointment with CQT. His research
interests are in the areas of information theory, quantum computation, cryptography,
communication complexity, and computational complexity theory.
I ORDANIS K ERENIDIS received his Ph. D. in 2004 from the Computer Science department
at the University of California, Berkeley. His advisor was Umesh Vazirani. After a
two-year postdoctoral position at the Massachusetts Institute of Technology, he moved to
France, where he now holds a Senior Researcher CNRS position, based at the Université
Paris-Diderot. Since 2009, he has also been a long-term visiting scholar at the Centre
for Quantum Technologies, Singapore. His research interests lie in the intersection of
quantum cryptography and complexity theory.
G REG K UPERBERG received a bachelor’s degree from Harvard University (1987) and a Ph. D.
in geometric topology and quantum algebra from University of California, 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.”
M IKLOS S ANTHA received his Diploma in mathematics in 1979 from Eötvös University
in Budapest, and his Ph. D. in mathematics in 1983 from the Université Paris 7. His
advisor was Jacques Stern. Since 1988 he has been a CNRS researcher, currently at the
Université Paris Diderot, LIAFA. He is also a principal investigator at CQT in Singapore.
O R S ATTATH received his B. S. in Physics and Computer Science in 2005, and his M. S. in
Computer Science in 2009, both from the Hebrew University. His Ph. D. advisors are
Dorit Aharonov and Julia Kempe. He is the proud father of Nadav, his newly born son.
His main research interest is quantum complexity theory.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 399
R. JAIN , I. K ERENIDIS , G. K UPERBERG , M. S ANTHA , O. S ATTATH , AND S. Z HANG
S HENGYU Z HANG received his B. S. in Mathematics at Fudan University in 1999, his M. S.
in Computer Science at Tsinghua University under the supervision of Mingsheng Ying in
2002, and his Ph. D. in Computer Science at Princeton University under the supervision
of Andrew Chi-Chih Yao in 2006. After working at NEC Laboratories America for a
summer, and at the California Institute of Technology for two years as a postdoctoral
researcher, he joined The Chinese University of Hong Kong as an assistant professor.
His main research interests are complexity theories in various randomized and quantum
models.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 375–400 400