Strengths and Weaknesses of Quantum Computing.
Recently a great deal of attention has been focused on quantum computation following a sequence of results [Bernstein and Vazirani, in Proc. 25th Annual ACM Symposium Theory Comput., 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339], [Simon, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 116--123, SIAM J. Comput., 26 (1997), pp. 1340--1349], [Shor, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 124--134] suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of $\NP$ can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random with probability 1 the class $\NP$ cannot be solved on a quantum Turing machine (QTM) in time $o(2^{n/2})$. We also show that relative to a permutation oracle chosen uniformly at random with probability 1 the class $\NP \cap \coNP$ cannot be solved on a QTM in time $o(2^{n/3})$. The former bound is tight since recent work of Grover [in {\it Proc.\ $28$th Annual ACM Symposium Theory Comput.}, 1996] shows how to accept the class $\NP$ relative to any oracle on a quantum computer in time $O(2^{n/2})$.
Introduction
Quantum computational complexity is an exciting new area that touches upon the foundations
of both theoretical computer science and quantum physics. In the early eighties,
Feynman [12] pointed out that straightforward simulations of quantum mechanics on a classical
computer appear to require a simulation overhead that is exponential in the size of
the system and the simulated time; he asked whether this is inherent, and whether it is
possible to design a universal quantum computer. Deutsch [9] defined a general model of
quantum computation - the quantum Turing machine. Bernstein and Vazirani [4] proved
that there is an efficient universal quantum Turing machine. Yao [17] extended this by
proving that quantum circuits (introduced by Deutsch [10]) are polynomially equivalent to
quantum Turing machines.
The computational power of quantum Turing machines (QTMs) has been explored by
several researchers. Early work by Deutsch and Jozsa [11] showed how to exploit some
inherently quantum mechanical features of QTMs. Their results, in conjunction with subsequent
results by Berthiaume and Brassard [5, 6], established the existence of oracles under
which there are computational problems that QTMs can solve in polynomial time with cer-
tainty, whereas if we require a classical probabilistic Turing machine to produce the correct
answer with certainty, then it must take exponential time on some inputs. On the other
hand, these computational problems are in BPP 1 relative to the same oracle, and therefore
efficiently solvable in the classical sense. The quantum analogue of the class BPP is
1 BPP is the class of decision problems (languages) that can be solved in polynomial time by probabilistic
Turing machines with error probability bounded by 1/3 (for all inputs). Using standard boosting techniques,
the error probability can then be made exponentially small in k by iterating the algorithm k times and
returning the majority answer.
the class BQP 2 [5]. Bernstein and Vazirani [4] proved that BPP ' BQP ' PSPACE,
thus establishing that it will not be possible to conclusively prove that BQP 6= BPP
without resolving the major open problem P ?
PSPACE. They also gave the first evidence
that BQP 6= BPP (polynomial-time quantum Turing machines are more powerful
than polynomial-time probabilistic Turing machines), by proving the existence of an oracle
relative to which there are problems in BQP that cannot be solved with small error
probability by probabilistic machines restricted to running in n o(log n) steps. Since BPP is
regarded as the class of all "efficiently computable" languages (computational problems),
this provided evidence that quantum computers are inherently more powerful than classical
computers in a model-independent way. Simon [16] strengthened this evidence by proving
the existence of an oracle relative to which BQP cannot even be simulated by probabilistic
machines allowed to run for 2 n=2 steps. In addition, Simon's paper also introduced an
important new technique which was one of the ingredients in a remarkable result proved
subsequently by Shor [15]. Shor gave polynomial-time quantum algorithms for the factoring
and discrete logarithm problems. These two problems have been well-studied, and
their presumed intractability forms the basis of much of modern cryptography. In view of
these results, it is natural to ask whether NP ' BQP; i.e. can quantum computers solve
NP-complete problems in polynomial time? 3
In this paper, we address this question by proving that relative to an oracle chosen
uniformly at random [3], with probability 1, the class NP cannot be solved on a quantum
2 BQP is the class of decision problems (languages) that can be solved in polynomial time by quantum
Turing machines with error probability bounded by 1/3 (for all inputs)-see [4] for a formal definition.
We prove in Section 4 of this paper that, as is the case with BPP, the error probability of BQP machines
can be made exponentially small.
3 Actually it is not even clear whether BQP ' BPP NP ; i.e. it is unclear whether nondeterminism
together with randomness is sufficient to simulate quantum Turing machines. In fact, Bernstein and Vazi-
rani's [4] result is stronger than stated above. They actually proved that relative to an oracle, the recursive
Fourier sampling problem can be solved in BQP, but cannot even be solved by Arthur-Merlin games [1]
with a time bound of n o(log n) (thus giving evidence that nondeterminism on top of probabilism does not
help). They conjecture that the recursive Fourier sampling cannot even be solved in the unrelativized
polynomial-time hierarchy.
Turing machine in time o(2 n=2 ). We also show that relative to a permutation oracle chosen
uniformly at random, with probability 1, the class NP " co-NP cannot be solved on a
quantum Turing machine in time o(2 n=3 ). The former bound is tight since recent work of
Grover [13] shows how to accept the class NP relative to any oracle on a quantum computer
in time O(2 n=2 ). See [7] for a detailed analysis of Grover's algorithm.
What is the relevance of these oracle results? We should emphasize that they do not
rule out the possibility that NP ' BQP. What these results do establish is that there is
no black-box approach to solving NP-complete problems by using some uniquely quantum-mechanical
features of QTMs. That this was a real possibility is clear from Grover's [13]
result, which gives a black-box approach to solving NP-complete problems in square-root
as much time as is required classically.
One way to think of an oracle is as a special subroutine call whose invocation only costs
unit time. In the context of QTMs, subroutine calls pose a special problem that has no
classical counterpart. The problem is that the subroutine must not leave around any bits
beyond its computed answer, because otherwise computational paths with different residual
information do not interfere. This is easily achieved for deterministic subroutines since any
classical deterministic computation can be carried out reversibly so that only the input and
the answer remain. However, this leaves open the more general question of whether a BQP
machine can be used as a subroutine. Our final result in this paper is to show how any
BQP machine can be modified into a tidy BQP machine whose final superposition consists
almost entirely of a tape configuration containing just the input and the single bit answer.
Since these tidy BQP machines can be safely used as subroutines, this allows us to show
that BQP BQP. The result also justifies the definition of oracle quantum machines
that we now give.
Oracle Quantum Turing Machines
In this section and the next, we shall assume without loss of generality that the Turing
machine alphabet (for each track or tape) is f0; 1; #g, where "#" denotes the blank symbol.
Initially all tapes are blank except that the input tape contains the actual input surrounded
by blanks. We shall use \Sigma to denote f0; 1g.
In the classical setting, an oracle may be described informally as a device for evaluating
some Boolean function A : \Sigma   ! \Sigma, on arbitrary arguments, at unit cost per evaluation.
This allows to formulate questions such as "if A were efficiently computable by a Turing
machine, which other functions (or languages) could be efficiently computed by Turing
machines?". In the quantum setting, an equivalent question can be asked, provided we
define oracle quantum Turing machines appropriately-which we do in this section-and
Turing machines can be composed-which we show in
Section 4 of this paper.
An oracle QTM has a special query tape (or track), all of whose cells are blank except for
a single block of non-blank cells. In a well-formed oracle QTM, the Turing machine rules may
allow this region to grow and shrink, but prevent it from fragmenting into non-contiguous
blocks. 4 Oracle QTMs have two distinguished internal states: a pre-query state q q and a
post-query state q a . A query is executed whenever the machine enters the pre-query state.
If the query string is empty, a no-op occurs, and the machine passes directly to the post-
query state with no change. If the query string is nonempty, it can be written in the form
denotes concatenation. In that case, the result of a
call on oracle A is that internal control passes to the post-query state while the contents of
4 This restriction can be made without loss of generality and it can be verified syntactically by allowing
only machines that make sure they do not break the rule before writing on the query tape.
the query tape changes from jx ffi bi to jx ffi (b \Phi A(x))i, where "\Phi" denotes the exclusive-or
(addition modulo 2). Except for the query tape and internal control, other parts of the
oracle QTM do not change during the query. If the target bit jbi is supplied in initial state
j0i, then its final state will be jA(x)i, just as in a classical oracle machine. Conversely, if
the target bit is already in state jA(x)i, calling the oracle will reset it to j0i. This ability
to "uncompute" will often prove essential to allow proper interference among computation
paths to take place. Using this fact, it is also easy to see that the above definition of oracle
Turing machines yields unitary evolutions if we restrict ourselves to machines that are well-formed
in other respects, in particular evolving unitarily as they enter the pre-query state
and leave the post-query state.
The power of quantum computers comes from their ability to follow a coherent superposition
of computation paths. Similarly oracle quantum machines derive great power
from the ability to perform superpositions of queries. For example, oracle A might be
called when the query tape is in state j/ ffi
x ff x jx ffi 0i, where ff x are complex coef-
ficients, corresponding to an arbitrary superposition of queries with a constant j0i in the
target bit. In this case, after the query, the query string will be left in the entangled state
x ff x jx ffi A(x)i. It is also useful to be able to put the target bit b into a superposition.
For example, the conditional phase inversion used in Grover's algorithm can be achieved by
performing queries with the target bit b in the nonclassical superposition
2.
It can readily be verified that an oracle call with the query tape in state x ffi fi leaves the
entire machine state, including the query tape, unchanged if leaves the entire
state unchanged while introducing a phase factor \Gamma1 if
It is often convenient to think of a Boolean oracle as defining a length-preserving function
on \Sigma   . This is easily accomplished by interpreting the oracle answer on the pair (x; i) as
the i th bit of the function value. The pair (x; i) is encoded as a binary string using any
standard pairing function. A permutation oracle is an oracle which, when interpreted as
a length-preserving function, acts for each n - 0 as a permutation on \Sigma n . Henceforth,
when no confusion may arise, we shall use A(x) to denote the length-preserving function
associated with oracle A rather than the Boolean function that gives rise to it.
Let us define BQTime(T (n)) A as the sets of languages accepted with probability at
least 2=3 by some oracle QTM M A whose running time is bounded by T (n). This bound
on the running time applies to each individual input, not just on the average. Notice that
whether or not M A is a BQP-machine might depend upon the oracle A-thus M A might
be a BQP-machine while M B might not be one.
Note: The above definition of a quantum oracle for an arbitrary Boolean function will
suffice for the purposes of the present paper, but the ability of quantum computers to perform
general unitary transformations suggests a broader definition, which may be useful in
other contexts. For example, oracles that perform more general, non-Boolean unitary operations
have been considered in computational learning theory [8] and for hiding information
against classical queries [14].
Most broadly, a quantum oracle may be defined as a device that, when called, applies
a fixed unitary transformation U to the current contents jzi of the query tape, replacing it
by U jzi. Such an oracle U must be defined on a countably infinite-dimensional Hilbert space,
such as that spanned by the binary basis vectors jffli; j0i; j1i; j00i; j01i; j10i;
where ffl denotes the empty string. Clearly, the use of such general unitary oracles still
yields unitary evolution for well-formed oracle Turing machines. Naturally, these oracles
can map inputs onto superpositions of outputs, and vice versa, and they need not even be
length-preserving. However, in order to obey the dictum that a single machine cycle ought
not to make infinite changes in the tape, one might require that U jzi have amplitude zero
on all but finitely many basis vectors. (One could even insist on a uniform and effective
version of the above restriction.) Another natural restriction one may wish to impose upon
U is that it be an involution, U so that the effect of an oracle call can be undone by
a further call on the same oracle. Again this may be crucial to allow proper interference to
take place. Note that the special case of unitary transformation considered in this paper,
which corresponds to evaluating a classical Boolean function, is an involution.
3 On the Difficulty of Simulating Nondeterminism on
QTMs
The computational power of QTMs lies in their ability to maintain and compute with
exponentially large superpositions. It is tempting to try to use this "exponential parallelism"
to simulate non-determinism. However, there are inherent constraints on the scope of this
parallelism, which are imposed by the formalism of quantum mechanics. 5 In this section,
we explore some of these constraints.
To see why quantum interference can speed up NP problems quadratically but not
exponentially, consider the problem of distinguishing the empty oracle
an oracle containing a single random unknown string y of known length n (i.e. A(y)=1, but
8 x6=y A(x)=0). We require that the computer never answer yes on an empty oracle, and seek
to maximize its "success probability" of answering yes on a nonempty oracle. A classical
computer can do no better than to query distinct n-bit strings at random, giving a success
probability 1=2 n after one query and k=2 n after k queries. How can a quantum computer do
5 There is a superficial similarity between this exponential parallelism in quantum computation and the
fact that probabilistic computations yield probability distributions over exponentially large domains. The
difference is that in the probabilistic case, the computational path is chosen by making a sequence of random
choices-one for each step. In the quantum-mechanical case, it is possible for several computational paths
to interfere destructively, and therefore it is necessary to keep track of the entire superposition at each step
to accurately simulate the system.
better, while respecting the rule that its overall evolution be unitary, and, in a computation
with a nonempty oracle, all computation paths querying empty locations evolve exactly as
they would for an empty oracle? A direct quantum analog of the classical algorithm would
start in an equally-weighted superposition of 2 n computation paths, query a different string
on each path, and finally collapse the superposition by asking whether the query had found
the nonempty location. This yields a success probability 1=2 n , the same as the classical
computer. However, this is not the best way to exploit quantum parallelism. Our goal
should be to maximize the separation between the state vector j/ k i after k interactions
with an empty oracle, and the state vector j/ k (y)i after k interactions with an oracle
nonempty at an unknown location y. Starting with a uniform superposition
x
it is easily seen that the separation after one query is maximized by a unitary evolution to
x
This is a phase inversion of the term corresponding to the nonempty location. By testing
whether the post-query state agrees with j/ 0 i we obtain a success probability
approximately four times better than the classical value. Thus, if we are allowed only one
query, quantum parallelism gives a modest improvement, but is still overwhelmingly likely
to fail because the state vector after interaction with a nonempty oracle is almost the same
as after interaction with an empty oracle. The only way of producing a large difference after
one query would be to concentrate much of the initial superposition in the y term before
the query, which cannot be done because that location is unknown.
Having achieved the maximum separation after one query, how best can that separation
be increased by subsequent queries? Various strategies can be imagined, but a good one
(called "inversion about the average" by Grover [13]) is to perform an oracle-independent
unitary transformation so as to change the phase difference into an amplitude difference,
leaving the y term with the same sign as all the other terms but a magnitude approximately
threefold larger. Subsequent phase-inverting interactions with the oracle, alternating with
oracle-independent phase-to-amplitude conversions, cause the distance between j/ 0 i and
j/ k (y)i to grow linearly with k, approximately as 2k=
N=2. This results in a
quadratic growth of the success probability, approximately as 4k 2 =2 n for small k. The proof
of Theorem 3.5 shows that this approach is essentially optimal: no quantum algorithm can
gain more than this quadratic factor in success probability compared to classical algorithms,
when attempting to answer NP-type questions formulated relative to a random oracle.
3.1 Lower Bounds on Quantum Search
We will sometimes find it convenient to measure the accuracy of a simulation by calculating
the Euclidean distance 6 between the target and simulation superpositions. The following
theorem from [4] shows that the simulation accuracy is at most 4 times worse than this
Euclidean distance.
Theorem 3.1 If two unit-length superpositions are within Euclidean distance " then observing
the two superpositions gives samples from distributions which are within total variation
distance 7 at most 4".
6 The Euclidean distance between
x
ff x jxi and
x
fijxi is defined as (
x
7 The total variation distance between two distributions D and D 0 is
x
Definition 3.2 Let jOE i i be the superposition of M A on input x at time i. We denote by
the sum of squared magnitudes in jOE i i of configurations of M which are querying
the oracle on string y. We refer to q y (jOE i i) as the query magnitude of y in jOE i i.
Theorem 3.3 Let jOE i i be the superposition of M A on input x at time i.
be a set of time-strings pairs such that
T . Now
suppose the answer to each query (i; y) 2 F is modified to some arbitrary fixed a i;y (these
answers need not be consistent with an oracle). Let jOE 0
i be the time i superposition of M
on input x with oracle A modified as stated above. Then jjOE
".
Proof. Let U be the unitary time evolution operator of M A . Let A i denote an oracle such
that if (i; y) 2 F then A i
be the
unitary time evolution operator of M A i . Let jOE i i be the superposition of M A on input x
at time i. We define jE i i to be the error in the i th step caused by replacing the oracle A
with A i . Then
So we have
Since all of the U i are unitary, jU T
The sum of squared magnitudes of all of the E i is equal to
(i;y)2F q y (jOE i i) and therefore
at most " 2
In the worst case, the U T could interfere constructively; however,
the squared magnitude of their sum is at most T times the sum of their squared magnitudes,
Corollary 3.4 Let A be an oracle over alphabet \Sigma. For y 2 \Sigma   , let A y be any oracle such
that 8x 6= y A y be the time i superposition of M A on input x and
be the time i superposition of M Ay on input x. Then for every " ? 0, there is a set
S of cardinality at most 2T 2
Proof. Since each jOE t i has unit length,
y q y (jOE i i) - T . Let S be the set of strings
y such that
.
. Therefore by Theorem 3.3
".Theorem 3.5 For any T (n) which is o(2 n=2 ), relative to a random oracle, with probability
does not contain NP.
Proof. Recall from Section 2 that an oracle can be thought of as a length-preserving
function: this is what we mean below by A(x). Let yg. Clearly, this
language is contained in NP A . Let T We show that for any bounded-error
oracle QTM M A running in time at most T (n), with probability 1, M A does not accept
the language LA . The probability is taken over the choice of a random length-preserving
oracle A. Then, since there are a countable number of QTMs and the intersection of a
countable number of probability 1 events still has probability 1, we conclude that with
probability 1, no bounded error oracle QTM accepts LA in time bounded by T (n).
pick n large enough so that T (n) - 2 n=2. We will show
that the probability that M gives the wrong answer on input 1 n is at least 1=8 for every
way of fixing the oracle answers on inputs of length not equal to n. The probability is taken
over the random choices of the oracle for inputs of length n.
Let us fix an arbitrary length-preserving function from strings of lengths other than n
over alphabet \Sigma. Let C denote the set of oracles consistent with this arbitrary function.
Let A be the set of oracles in C such that 1 n has no inverse (does not belong to LA ). If the
oracle answers to length n strings are chosen uniformly at random, then the probability
that the oracle is in A is at least 1=4. This is because the probability that 1 n has no inverse
is
which is at least 1=4 (for n sufficiently large). Let B be the set of oracles in C
such that 1 n has a unique inverse. As above, the probability that a randomly chosen oracle
is in B is (
which is at least 1=e.
Given an oracle A in A, we can modify its answer on any single input, say y, to 1 n and
therefore get an oracle A y in B. We will show that for most choices of y, the acceptance
probability of M A on input 1 n is almost equal to the acceptance probability of M Ay on
input 1 n . On the other hand, M A must reject 1 n and M Ay must accept 1 n . Therefore M
cannot accept both LA and LAy . By working through the details more carefully, it is easy
to show that M fails on input 1 n with probability at least 1=8 when the oracle is a uniformly
random function on strings of length n, and is an arbitrary function on all other strings.
Let A y be the oracle such that A y
3.4 there is a set S of at most 338T 2 (n) strings such that the difference between the
th superposition of M Ay on input 1 n and M A on input 1 n has norm at most 1=13. Using
Theorem 3.1 we can conclude that the difference between the acceptance probabilities of
M Ay on input 1 n and M A on input 1 n is at most 1=13 \Theta 4 ! 1=3. Since M Ay should accept
with probability at least 2=3 and M A should reject 1 n with probability at least 2=3, we
can conclude that M fails to accept either LA or LAy .
So, each oracle A 2 A for which M correctly decides whether 1 n 2 LA can, by changing
a single answer of A to 1 n , be mapped to at least (2 different oracles
which M fails to correctly decide whether 1 n 2 LA f
. Moreover, any particular
is the image under this mapping of at most 2 since where it
now answers 1 n , it must have given one of the possible answers. Therefore, the
number of oracles in B for which M fails must be at least 1=2 the number of oracles in A
for which M succeeds. So, calling a the number of oracles in A for which M fails, M must
fail for at least a Therefore M fails to correctly decide whether
with probability at least (1=2)P [A] - 1=8.
It is easy to conclude that M decides membership in LA with probability 0 for a uniformly
chosen oracle A. 2
Note: Theorem 3.3 and its Corollary 3.4 isolate the constraints on "quantum parallelism"
imposed by unitary evolution. The rest of the proof of the above theorem is similar in spirit
to standard techniques used to separate BPP from NP relative to a random oracle [3].
For example, these techniques can be used to show that, relative to a random oracle A,
no classical probabilistic machine can recognize LA in time o(2 n ). However, quantum machines
can recognize this language quadratically faster, in time O(
using Grover's
algorithm [13]. This explains why a substantial modification of the standard technique was
required to prove the above theorem.
The next result about NP " co-NP relative to a random permutation oracle requires a
more subtle argument; ideally we would like to apply Theorem 3.3 after asserting that the
total query magnitude with which A \Gamma1 (1 n ) is probed is small. However, this is precisely
what we are trying to prove in the first place.
Theorem 3.6 For any T (n) which is o(2 n=3 ), relative to a random permutation oracle,
with probability 1, BQTime(T (n)) does not contain NP " co-NP.
Proof. For any permutation oracle A, let first bit of A \Gamma1 (y) is 1g. Clearly,
this language is contained in (NP " co-NP) A . Let T We show that for any
bounded-error oracle QTM M A running in time at most T (n), with probability 1, M A does
not accept the language LA . The probability is taken over the choice of a random permutation
oracle A. Then, since there are a countable number of QTMs and the intersection
of a countable number of probability 1 events still has probability 1, we conclude that with
probability 1, no bounded error oracle QTM accepts LA in time bounded by T (n).
pick n large enough so that T (n) - 2 n=3. We will show
that the probability that M gives the wrong answer on input 1 n is at least 1=8 for every
way of fixing the oracle answers on inputs of length not equal to n. The probability is taken
over the random choices of the permutation oracle for inputs of length n.
Consider the following method of defining random permutations on f0; 1g
be a sequence of strings chosen uniformly at random in f0; 1g n . Pick - 0
uniformly at random among permutations such that -(x 0
- is the transposition
each - i is a random permutation on f0; 1g n .
Consider a sequence of permutation oracles A i , such that A i
and A i . Denote by jOE i i the time i superposition of M A T (n) on
input 1 n , and by jOE 0
i the time i superposition of M A T (n)\Gamma1 on input 1 n . By construction,
with probability exactly 1=2, the string 1 n is a member of exactly one of the two languages
and LA T
. We will show that E[
Here the expectation
is taken over the random choice of the oracles. By Markov's bound, P [
3=4. Applying Theorem 3.1 we conclude that if
then the
acceptance probability of M A T (n) and M A T (n)\Gamma1 differ by at most 8=25 ! 1=3, and hence
either both machines accept input 1 n or both reject that input. Therefore M A T (n) and
give the same answers on input 1 n with probability at least 3=4. By construction,
the probability that the string 1 n belongs to exactly one of the two languages LA T (n)
and
is equal to P [first bit of x T first bit of x T (n) Therefore, we can
conclude that with probability at least 1=4, either M A T (n) or M A T (n)\Gamma1 gives the wrong
answer on input 1 n . Since each of A T (n) and A T (n)\Gamma1 are chosen from the same distribution,
we can conclude that M A T (n) gives the wrong answer on input 1 n with probability at
least 1=8.
To bound E[
we show that jOE T (n) i and jOE 0
are each close to
a certain superposition j/ T (n) i. To define this superposition, run M on input 1 n with
a different oracle on each step: on step i, use A i to answer the oracle queries. Denote
by j/ i i, the time i superposition that results. Consider the set of time-string pairs
Tg. It is easily checked that the oracle queries in the computation
described above and those of M A T (n) and M A T (n)+1 differ only on the set S. We claim
that the expected query magnitude of any pair in the set is at most 1=2 n , since for j - i,
we may think of x j as having been randomly chosen during step j, after the superposition
of oracle queries to be performed has already been written on the oracle tape. Let ff be the
sum of the query magnitudes for time-string pairs in S. Then
for " be a random variable such that (n). Then by Theorem 3.3,
showed above that
But E["=
s
Therefore E[
that E[
Finally, it is easy to conclude that M decides membership in LA with probability 0 for
a uniformly random permutation oracle A. 2
Note: In view of Grover's algorithm [13], we know that the constant ``1=2'' in the statement
of Theorem 3.5 cannot be improved. On the other hand, there is no evidence that the
constant "1=3" in the statement of Theorem 3.6 is fundamental. It may well be that
Theorem 3.6 would still hold (albeit not its current proof) with 1=2 substituted for 1=3.
Corollary 3.7 Relative to a random permutation oracle, with probability 1, there exists
a quantum one-way permutation. Given the oracle, this permutation can be computed
efficiently even with a classical deterministic machine, yet it requires exponential time to
invert even on a quantum machine.
Proof. Given an arbitrary permutation oracle A for which A \Gamma1 can be computed in time
n=3 ) on a quantum Turing machine, it is just as easy to decide LA as defined in the proof
of Theorem 3.6. It follows from that proof that this happens with probability 0 when A is
a uniformly random permutation oracle. 2
4 Using a Bounded-Error QTM as a Subroutine
The notion of a subroutine call or an oracle invocation provides a simple and useful abstraction
in the context of classical computation. Before making this abstraction in the context of
quantum computation, there are some subtle considerations that must be thought through.
For example, if the subroutine computes the function f , we would like to think of an invocation
of the subroutine on the string x as magically writing f(x) in some designated spot
(actually xoring it to ensure unitarity). In the context of quantum algorithms, this abstraction
is only valid if the subroutine cleans up all traces of its intermediate calculations, and
leaves just the final answer on the tape. This is because if the subroutine is invoked on a
superposition of x's, then different values of x would result in different scratch-work on the
tape, and would prevent these different computational paths from interfering. Since erasing
is not a unitary operation, the scratch-work cannot, in general, be erased post-facto. In the
special case where f can be efficiently computed deterministically, it is easy to design the
subroutine so that it reversibly erases the scratch-work-simply compute f(x), copy f(x)
into safe storage, and then uncompute f(x) to get rid of the scratch work [2]. However,
in the case that f is computed by a BQP machine, the situation is more complicated.
This is because only some of the computational paths of the machine lead to the correct
answer f(x), and therefore if we copy f(x) into safe storage and then uncompute f(x),
computational paths with different values of f(x) will no longer interfere with each other,
and we will not reverse the first phase of the computation. We show, nonetheless, that if
we boost the success probability of the BQP machine before copying f(x) into safe storage
and uncomputing f(x), then most of the weight of the final superposition has a clean tape
with only the input x and the answer f(x). Since such tidy BQP machines can be safely
used as subroutines, this allows us to show that BQP BQP. The result also justifies
our definition of oracle quantum machines.
The correctness of the boosting procedure is proved in Theorems 4.13 and 4.14. The
proof follows the same outline as in the classical case, except that we have to be much
more careful in simple programming constructs such as looping, etc. We therefore borrow
the machinery developed in [4] for this purpose, and present the statements of the relevant
lemmas and theorems in the first part of this section. The main new contribution in this
section is in the proofs of Theorems 4.13 and 4.14. The reader may therefore wish to skip
directly ahead to these proofs.
4.1 Some Programming Primitives for QTMs
In this subsection, we present several definitions, lemmas and theorems from [4].
Recall that a QTM M is defined by a triplet (\Sigma; Q; ffi) where: \Sigma is a finite alphabet with
an identified blank symbol #, Q is a finite set of states with an identified initial state q 0
and final state q f 6= q 0 , and ffi , the quantum transition function, is a function
where ~
C is the set of complex numbers whose real and imaginary parts can be approximated
to within 2 \Gamman in time polynomial in n.
Definition 4.1 A final configuration of a QTM is any configuration in state q f . If when
QTM M is run with input x, at time T the superposition contains only final configurations
and at any time less than T the superposition contains no final configuration, then M halts
with running time T on input x. The superposition of M at time T is called the final
superposition of M run on input x. A polynomial-time QTM is a well-formed QTM which
on every input x halts in time polynomial in the length of x.
Definition 4.2 A QTM M is called well-behaved if it halts on all input strings in a final
superposition where each configuration has the tape head in the same cell. If this cell is
always the start cell, we call the QTM stationary.
We will say that a QTM M is in normal form if all transitions from the distinguished
state q f lead to the distinguished state q 0 , the symbol in the scanned cell is left unchanged,
and the head moves right, say. Formally:
Definition 4.3 A QTM is in normal form if
Theorem 4.4 If f is a function mapping strings to strings which can be computed in
deterministic polynomial time and such that the length of f(x) depends only on the length
of x, then there is a polynomial-time, stationary, normal form QTM which given input x,
produces output x; f(x), and whose running time depends only on the length of x.
If f is a one-to-one function from strings to strings that such that both f and f \Gamma1 can be
computed in deterministic polynomial time, and such that the length of f(x) depends only on
the length of x, then there is a polynomial-time, stationary, normal form QTM which given
input x, produces output f(x), and whose running time depends only on the length of x.
Definition 4.5 A multi-track Turing machine with k tracks is a Turing machine whose
alphabet \Sigma is of the form \Sigma 1 \Theta \Sigma 2 \Theta \Delta \Delta \Delta \Theta \Sigma k with a special blank symbol # in each \Sigma i so that
the blank in \Sigma is (#). We specify the input by specifying the string on each "track"
(separated by ';'), and optionally by specifying the alignment of the contents of the tracks.
Lemma 4.6 Given any QTM and any set \Sigma 0 , there is a QTM
behaves exactly as M while leaving its second track unchanged

Lemma 4.7 Given any QTM
there is a QTM M such that the M 0 behaves exactly as M
except that its tracks are permuted according to -.
Lemma 4.8 If M 1 and M 2 are well-behaved, normal form QTMs with the same alphabet,
then there is a normal form QTM M which carries out the computation of M 1 followed by
the computation of M 2 .
Lemma 4.9 Suppose that M is a well-behaved, normal form QTM. Then there is a normal
such that on input x; k with k ? 0, the machine M 0 runs M for k iterations
on its first track.
Definition 4.10 If QTMs M 1 and M 2 have the same alphabet, then we say that
the computation of M 1 if the following holds: for any input x on which M 1 halts, let c x and
OE x be the initial configuration and final superposition of M 1 on input x. Then M 2 on input
the superposition OE x , halts with final superposition consisting entirely of configuration c x .
Note that for M 2 to reverse M 1 , the final state of M 2 must be equal to the initial state of
1 and vice versa.
Lemma 4.11 If M is a normal form QTM which halts on all inputs, then there is a normal
that reverses the computation of M with slowdown by a factor of 5.
Finally, recall the definition of the class BQP.
Definition 4.12 Let M be a stationary, normal form, multi-track QTM M whose last track
has alphabet f#; 0; 1g. We say that M accepts x if it halts with a 1 in the last track of the
start cell. Otherwise we say that M rejects x.
A QTM accepts the language L ' (\Sigma \Gamma #)   with probability accepts with probability
at least p every string x 2 L and rejects with probability at least p every string
We define the class BQP (bounded-error quantum polynomial time)
as the set of languages which are accepted with probability 2=3 by some polynomial-time
QTM. More generally, we define the class BQTime(T (n)) as the set of languages which
are accepted with probability 2=3 by some QTM whose running time on any input of length
n is bounded by T (n).
4.2 Boosting and Subroutine Calls
Theorem 4.13 If QTM M accepts language L with probability 2=3 in time T (n) ? n,
with T (n) time-constructible, then for any " ? 0, there is a QTM M 0 which accepts L with
is polynomial in log 1=" but independent of n.
Proof. Let M be a stationary QTM which accepts the language L in time T (n).
We will build a machine that runs k independent copies of M and then takes the
majority vote of the k answers. On any input x, M will have some final superposition
of strings
If we call A the set of i for which x i has the correct answer M(x) then
running M on separate copies of its input k times will produce
i. Then the probability of seeing jx
i such that the
majority have the correct answer M(x) is the sum of jff i 1
2 such that the majority
of lie in A. But this is just like taking the majority of k independent coin flips
each with probability at least 2=3 of heads. Therefore there is some constant b such that
log 1=", the probability of seeing the correct answer will be at least 1 \Gamma ".
So, we will build a machine to carry out the following steps.
1. Compute
2. Write out k copies of the input x spaced out with 2n blank cells in between, and write
down k and n on other tracks.
3. Loop k times on a machine that runs M and then steps n times to the right.
4. Calculate the majority of the k answers and write it back in the start cell.
We construct the desired QTM by building a QTM for each of these four steps and then
dovetailing them together.
Since Steps 1, 2, and 4 require easily computable functions whose output length depend
only on k and the length of x, we can carry them out using well-behaved, normal form
QTMs, constructed using Theorem 4.4, whose running times also depend only on k and the
length of x.
So, we complete the proof by constructing a QTM to run the given machine k times.
First, using Theorem 4.4 we can construct a stationary, normal form QTM which drags the
integers k and n one square to the right on its work track. If we add a single step right
to the end of this QTM and apply Lemma 4.9, we can build a well-behaved, normal form
QTM moves which n squares to the right, dragging k and n along with it. Dovetailing this
machine after M , and then applying Lemma 4.9 gives a normal form QTM that runs M on
each of the k copies of the input. Finally, we can dovetail with a machine to return with k
and n to the start cell by using Lemma 4.9 two more times around a QTM which carries k
and n one step to the left. 2
The extra information on the output tape of a QTM can be erased by copying the desired
output to another track, and then running the reverse of the QTM. If the output is the
same in every configuration in the final superposition, then this reversal will exactly recover
the input. Unfortunately, if the output differs in different configurations, then saving the
output will prevent these configurations from interfering when the machine is reversed, and
the input will not be recovered. We show is the same in most of the final superposition,
then the reversal must lead us close to the input.
Theorem 4.14 If the language L is contained in the class BQTime(T (n)), with T (n) ? n
and T (n) time-constructible, then for any " ? 0, there is a QTM M 0 which accepts L with
" and has the following property. When run on input x of length n,
runs for time bounded by cT (n), where c is a polynomial in log 1=", and produces a final
superposition in which jxijL(x)i, with otherwise, has squared
magnitude at least 1 \Gamma ".
Proof. Let be a stationary, normal form QTM which accepts language L in
time bounded by T (n).
According to Theorem 4.13, at the expense of a slowdown by factor which is polynomial
in log 1=" but independent of n, we can assume that M accepts L with probability
on every input.
Then we can construct the desired M 0 by running M , copying the answer to another
track, and then running the reverse of M . The copy is easily accomplished with a simple
two-step machine that steps left and back right while writing the answer on a clean track.
Using Lemma 4.11, we can construct a normal form QTM M R which reverses M . Finally,
with appropriate use of Lemmas 4.6 and 4.7, we can construct the desired stationary QTM
by dovetailing machines M and M R around the copying machine.
To see that this M 0 has the desired properties, consider running M 0 on input x of
length n. M 0 will first run M on x producing some final superposition of configurations
y ff y jyi of M on input x. Then it will write a 0 or 1 in the extra track of the start cell
of each configuration, and run M R on this superposition
y ff y jyijb y i. If we were
to instead run M R on the superposition jOE
y ff y jyijM(x)i we would after T (n) steps
have the superposition consisting entirely of the final configuration with output x; M(x).
Clearly, hOEjOE 0 i is real, and since M has success probability at least
Therefore, since the time evolution of M R is unitary and hence preserves the inner product,
the final superposition of M 0 must have an inner product with jxijM(x)i which is real and
at least 1 \Gamma "=2. Therefore, the squared magnitude in the final superposition of M 0 of the
final configuration with output x; M(x) must be at least (1 \Gamma
Corollary 4.15 BQP

Acknowledgement

We wish to thank Bob Solovay for several useful discussions.



--R

"Arthur - Merlin games: A randomized proof system, and a hierarchy of complexity classes"
"Logical reversibility of computation"
"Relative to a random oracle A, P A 6= NP A 6= co-NP A with probability 1"
"Quantum complexity theory"
"The quantum challenge to structural complexity theory"
"Oracle quantum computing"
"Tight bounds on quantum searching"
"Learning DNF over uniform distribution using a quantum example oracle"
"Quantum theory, the Church-Turing principle and the universal quantum computer"
"Quantum computational networks"
"Rapid solution of problems by quantum computation"
"Simulating physics with computers"
"A fast quantum mechanical algorithm for database search"
"Phase information in quantum oracle computing"
"Algorithms for quantum computation: Discrete logarithms and factoring"
"On the power of quantum computation"
"Quantum circuit complexity"
--TR

--CTR
Feng Lu , Dan C. Marinescu, An R || Cmax Quantum Scheduling Algorithm, Quantum Information Processing, v.6 n.3, p.159-178, June      2007
Peter W. Shor, Why haven't more quantum algorithms been found?, Journal of the ACM (JACM), v.50 n.1, p.87-90, January
Marcello Frixione, Tractable Competence, Minds and Machines, v.11 n.3, p.379-397, August 2001
Alp Atici , Rocco A. Servedio, Improved Bounds on Quantum Learning Algorithms, Quantum Information Processing, v.4 n.5, p.355-386, November  2005
Lov K. Grover , Jaikumar Radhakrishnan, Is partial quantum search of a database any easier?, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
Alex Fabrikant , Tad Hogg, Graph coloring with quantum heuristics, Eighteenth national conference on Artificial intelligence, p.22-27, July 28-August 01, 2002, Edmonton, Alberta, Canada
George F. Viamontes , Igor L. Markov , John P. Hayes, Is Quantum Search Practical?, Computing in Science and Engineering, v.7 n.3, p.62-70, May 2005
Mika Hirvensalo, Quantum computing  Facts and folklore, Natural Computing: an international journal, v.1 n.1, p.135-155, May 2002
Mark Adcock , Richard Cleve , Kazuo Iwama , Raymond Putra , Shigeru Yamashita, Quantum lower bounds for the Goldreich-Levin problem, Information Processing Letters, v.97 n.5, p.208-211, March 2006
Akinori Kawachi , Hirotada Kobayashi , Takeshi Koshiba , Raymond H. Putra, Universal test for quantum one-way permutations, Theoretical Computer Science, v.345 n.2-3, p.370-385, 22 November 2005
Maciej Gowin, On the Complexity of Searching for a Maximum of a Function on a Quantum Computer, Quantum Information Processing, v.5 n.1, p.31-41, February  2006
Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States
Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States
Damien Woods , Thomas J. Naughton, An optical model of computation, Theoretical Computer Science, v.334 n.1-3, p.227-258, 11 April 2005
Ashwin Nayak , Felix Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.384-393, May 01-04, 1999, Atlanta, Georgia, United States
Stephen Fenner , Lance Fortnow , Stuart A. Kurtz , Lide Li, An oracle builder's toolkit, Information and Computation, v.182 n.2, p.95-136, 01 May
Andris Ambainis , Ashwin Nayak , Ammon Ta-Shma , Umesh Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.376-383, May 01-04, 1999, Atlanta, Georgia, United States
Michele Mosca, Counting by quantum eigenvalue estimation, Theoretical Computer Science, v.264 n.1, p.139-153, 08/06/2001
A. Papageorgiou , H. Woniakowski, The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries, Quantum Information Processing, v.6 n.2, p.101-120, April     2007
Tetsuro Nishino, Mathematical models of quantum computation, New Generation Computing, v.20 n.4, p.317-337, October 2002
An introduction to quantum computing for non-physicists, ACM Computing Surveys (CSUR), v.32 n.3, p.300-335, Sept. 2000
Andris Ambainis, Quantum lower bounds by quantum arguments, Journal of Computer and System Sciences, v.64 n.4, p.750-767, June 2002
Andris Ambainis, Quantum lower bounds by quantum arguments, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.636-643, May 21-23, 2000, Portland, Oregon, United States
Lov K. Grover, A framework for fast quantum mechanical algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.53-62, May 24-26, 1998, Dallas, Texas, United States
Howard Barnum , Michael Saks, A lower bound on the quantum query complexity of read-once functions, Journal of Computer and System Sciences, v.69 n.2, p.244-258, September 2004
Markus Hunziker , David A. Meyer, Quantum Algorithms for Highly Structured Search Problems, Quantum Information Processing, v.1 n.3, p.145-154, June 2002
Scott Aaronson, Quantum lower bound for the collision problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Umesh Vazirani, Fourier transforms and quantum computation, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
Tarsem S. Purewal, Jr., Revisiting a limit on efficient quantum computation, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
van Dam , Sean Hallgren , Lawrence Ip, Quantum algorithms for some hidden shift problems, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Sean Hallgren , Cristopher Moore , Martin Rtteler , Alexander Russell , Pranab Sen, Limitations of quantum coset states for graph isomorphism, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Andrew Chi-Chih Yao, Graph entropy and quantum sorting problems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Hartmut Klauck, Quantum time-space tradeoffs for sorting, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Yaoyun Shi, Quantum and classical tradeoffs, Theoretical Computer Science, v.344 n.2-3, p.335-345, 17 November 2005
Mika Hirvensalo, Computing with quanta-impacts of quantum theory on computation, Theoretical Computer Science, v.287 n.1, p.267-298, 25 September 2002
Marco Carpentieri, On the simulation of quantum Turing machines, Theoretical Computer Science, v.304 n.1-3, p.103-128, 28 July
Harry Buhrman , Lance Fortnow , Ilan Newman , Hein Rhrig, Quantum property testing, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Harumichi Nishimura , Masanao Ozawa, Computational complexity of uniform quantum circuit families and quantum Turing machines, Theoretical Computer Science, v.276 n.1-2, p.147-181, April 6, 2002
Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM), v.48 n.4, p.778-797, July 2001
Holger Spakowski , Mayur Thakur , Rahul Tripathi, Quantum and classical complexity classes: separations, collapses, and closure properties, Information and Computation, v.200 n.1, p.1-34, 1 July 2005
Scott Aaronson , Yaoyun Shi, Quantum lower bounds for the collision and the element distinctness problems, Journal of the ACM (JACM), v.51 n.4, p.595-605, July 2004
Colin P. Williams, Quantum Search Algorithms in Science and Engineering, IEEE MultiMedia, v.3 n.2, p.44-51, March 1996
Hirotada Kobayashi , Keiji Matsumoto, Quantum multi-prover interactive proof systems with limited prior entanglement, Journal of Computer and System Sciences, v.66 n.3, p.429-450, May
Miklos Santha , Mario Szegedy, Quantum and classical query complexities of local search are polynomially related, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Scott Aaronson, Lower bounds for local search by quantum arguments, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.465-474, June 13-16, 2004, Chicago, IL, USA
A. Ambainis, Quantum search algorithms, ACM SIGACT News, v.35 n.2, June 2004
Frederic Magniez , Ashwin Nayak , Jeremie Roland , Miklos Santha, Search via quantum walk, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Andris Ambainis, Polynomial degree vs. quantum query complexity, Journal of Computer and System Sciences, v.72 n.2, p.220-238, March 2006
Lance Fortnow, One complexity theorist's view of quantum computing, Theoretical Computer Science, v.292 n.3, p.597-610, 31 January
Ronald de Wolf, Quantum communication and complexity, Theoretical Computer Science, v.287 n.1, p.337-353, 25 September 2002
Peter W. Shor, Progress in Quantum Algorithms, Quantum Information Processing, v.3 n.1-5, p.5-13, October 2004
Marco Lanzagorta , Jeffrey K. Uhlmann, Hybrid quantum-classical computing with applications to computer graphics, ACM SIGGRAPH 2005 Courses, July 31-August
Scott Aaronson, Guest Column: NP-complete problems and physical reality, ACM SIGACT News, v.36 n.1, March 2005
quantum Turing machines;quantum polynomial time;oracle quantum Turing machines