Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and which have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored.
Introduction
One of the first results in the mathematics of computation, which underlies the subsequent
development of much of theoretical computer science, was the distinction between
computable and non-computable functions shown in papers of Church [1936], Turing
[1936], and Post [1936]. Central to this result is Church's thesis, which says that all
computing devices can be simulated by a Turing machine. This thesis greatly simplifies
the study of computation, since it reduces the potential field of study from any of
an infinite number of potential computing devices to Turing machines. Church's thesis
is not a mathematical theorem; to make it one would require a precise mathematical
description of a computing device. Such a description, however, would leave open the
possibility of some practical computing device which did not satisfy this precise mathematical
description, and thus would make the resulting mathematical theorem weaker
than Church's original thesis.
With the development of practical computers, it has become apparent that the distinction
between computable and non-computable functions is much too coarse; computer
scientists are now interested in the exact efficiency with which specific functions
can be computed. This exact efficiency, on the other hand, is too precise a quantity to
work with easily. The generally accepted compromise between coarseness and precision
distinguishes efficiently and inefficiently computable functions by whether the length of
the computation scales polynomially or superpolynomially with the input size. The class
of problems which can be solved by algorithms having a number of steps polynomial in
the input size is known as P.
For this classification to make sense, we need it to be machine-independent. That is,
we need to know that whether a function is computable in polynomial time is independent
of the kind of computing device used. This corresponds to the following quantitative
version of Church's thesis, which Vergis et al. [1986] have called the ``Strong Church's
Thesis" and which makes up half of the "Invariance Thesis" of van Emde Boas [1990].
Thesis (Quantitative Church's thesis). Any physical computing device can be simulated
by a Turing machine in a number of steps polynomial in the resources used by the
computing device.
In statements of this thesis, the Turing machine is sometimes augmented with a random
number generator, as it has not yet been determined whether there are pseudorandom
number generators which can efficiently simulate truly random number generators
for all purposes. Readers who are not comfortable with Turing machines may think
instead of digital computers having an amount of memory that grows linearly with the
length of the computation, as these two classes of computing machines can efficiently
simulate each other.
There are two escape clauses in the above thesis. One of these is the word "physical."
Researchers have produced machine models that violate the above quantitative Church's
thesis, but most of these have been ruled out by some reason for why they are not "phys-
ical," that is, why they could not be built and made to work. The other escape clause in
the above thesis is the word "resources," the meaning of which is not completely specified
above. There are generally two resources which limit the ability of digital computers
to solve large problems: time (computation steps) and space (memory). There are more
resources pertinent to analog computation; some proposed analog machines that seem
able to solve NP-complete problems in polynomial time have required the machining of
FACTORING WITH A QUANTUM COMPUTER 3
exponentially precise parts, or an exponential amount of energy. (See Vergis et al. [1986]
and Steiglitz [1988]; this issue is also implicit in the papers of Canny and Reif [1987]
and Choi et al. [1995] on three-dimensional shortest paths.)
For quantum computation, in addition to space and time, there is also a third potentially
important resource, precision. For a quantum computer to work, at least in any
currently envisioned implementation, it must be able to make changes in the quantum
states of objects (e.g., atoms, photons, or nuclear spins). These changes can clearly
not be perfectly accurate, but must contain some small amount of inherent impreci-
sion. If this imprecision is constant (i.e., it does not depend on the size of the input),
then it is not known how to compute any functions in polynomial time on a quantum
computer that cannot also be computed in polynomial time on a classical computer
with a random number generator. However, if we let the precision grow polynomially
in the input size (that is, we let the number of bits of precision grow logarithmically
in the input size), we appear to obtain a more powerful type of computer. Allowing
the same polynomial growth in precision does not appear to confer extra computing
power to classical mechanics, although allowing exponential growth in precision does
[Hartmanis and Simon 1974, Vergis et al. 1986].
As far as we know, what precision is possible in quantum state manipulation is dictated
not by fundamental physical laws but by the properties of the materials and the
architecture with which a quantum computer is built. It is currently not clear which
architectures, if any, will give high precision, and what this precision will be. If the precision
of a quantum computer is large enough to make it more powerful than a classical
computer, then in order to understand its potential it is important to think of precision
as a resource that can vary. Treating the precision as a large constant (even though it is
almost certain to be constant for any given machine) would be comparable to treating
a classical digital computer as a finite automaton - since any given computer has a
fixed amount of memory, this view is technically correct; however, it is not particularly
useful.
Because of the remarkable effectiveness of our mathematical models of computation,
computer scientists have tended to forget that computation is dependent on the laws of
physics. This can be seen in the statement of the quantitative Church's thesis in van
Emde Boas [1990], where the word "physical" in the above phrasing is replaced with
the word "reasonable." It is difficult to imagine any definition of "reasonable" in this
context which does not mean "physically realizable," i.e., that this computing machine
could actually be built and would work.
Computer scientists have become convinced of the truth of the quantitative Church's
thesis through the failure of all proposed counter-examples. Most of these proposed
counter-examples have been based on the laws of classical mechanics; however, the universe
is in reality quantum mechanical. Quantum mechanical objects often behave quite
differently from how our intuition, based on classical mechanics, tells us they should.
It thus seems plausible that the natural computing power of classical mechanics corresponds
to Turing machines, 1 while the natural computing power of quantum mechanics
might be greater.
I believe that this question has not yet been settled and is worthy of further investigation. See
Vergis et al. [1986], Steiglitz [1988], and Rubel [1989]. In particular, turbulence seems a good candidate
for a counterexample to the quantitative Church's thesis because the non-trivial dynamics on many
length scales may make it difficult to simulate on a classical computer.
4 P. W. SHOR
The first person to look at the interaction between computation and quantum mechanics
appears to have been Benioff [1980, 1982a, 1982b]. Although he did not ask
whether quantum mechanics conferred extra power to computation, he showed that reversible
unitary evolution was sufficient to realize the computational power of a Turing
machine, thus showing that quantum mechanics is at least as powerful computationally
as a classical computer. This work was fundamental in making later investigation of
quantum computers possible.
Feynman [1982,1986] seems to have been the first to suggest that quantum mechanics
might be more powerful computationally than a Turing machine. He gave arguments as
to why quantum mechanics might be intrinsically expensive computationally to simulate
on a classical computer. He also raised the possibility of using a computer based on
quantum mechanical principles to avoid this problem, thus implicitly asking the converse
question: by using quantum mechanics in a computer can you compute more efficiently
than on a classical computer? Deutsch [1985, 1989] was the first to ask this question
explicitly. In order to study this question, he defined both quantum Turing machines
and quantum circuits and investigated some of their properties.
The question of whether using quantum mechanics in a computer allows one to
obtain more computational power was more recently addressed by Deutsch and Jozsa
[1992] and Berthiaume and Brassard [1992a, 1992b]. These papers showed that there
are problems which quantum computers can quickly solve exactly, but that classical
computers can only solve quickly with high probability and the aid of a random number
generator. However, these papers did not show how to solve any problem in quantum
polynomial time that was not already known to be solvable in polynomial time with
the aid of a random number generator, allowing a small probability of error; this is
the characterization of the complexity class BPP, which is widely viewed as the class of
efficiently solvable problems.
Further work on this problem was stimulated by Bernstein and Vazirani [1993]. One
of the results contained in their paper was an oracle problem (that is, a problem involving
a "black box" subroutine that the computer is allowed to perform, but for which no code
is accessible) which can be done in polynomial time on a quantum Turing machine but
which requires super-polynomial time on a classical computer. This result was improved
by Simon [1994], who gave a much simpler construction of an oracle problem which takes
polynomial time on a quantum computer but requires exponential time on a classical
computer. Indeed, while Bernstein and Vaziarni's problem appears contrived, Simon's
problem looks quite natural. Simon's algorithm inspired the work presented in this
paper.
Two number theory problems which have been studied extensively but for which no
polynomial-time algorithms have yet been discovered are finding discrete logarithms and
factoring integers [Pomerance 1987, Gordon 1993, Lenstra and Lenstra 1993, Adleman
and McCurley 1995]. These problems are so widely believed to be hard that several
cryptosystems based on their difficulty have been proposed, including the widely used
RSA public key cryptosystem developed by Rivest, Shamir, and Adleman [1978]. We
show that these problems can be solved in polynomial time on a quantum computer
with a small probability of error.
Currently, nobody knows how to build a quantum computer, although it seems as
though it might be possible within the laws of quantum mechanics. Some suggestions
have been made as to possible designs for such computers [Teich et al. 1988, Lloyd 1993,
FACTORING WITH A QUANTUM COMPUTER 5
1994, Cirac and Zoller 1995, DiVincenzo 1995, Sleator and Weinfurter 1995, Barenco et
al. 1995b, Chuang and Yamomoto 1995], but there will be substantial difficulty in building
any of these [Landauer 1995a, Landauer 1995b, Unruh 1995, Chuang et al. 1995,
Palma et al. 1995]. The most difficult obstacles appear to involve the decoherence of
quantum superpositions through the interaction of the computer with the environment,
and the implementation of quantum state transformations with enough precision to give
accurate results after many computation steps. Both of these obstacles become more
difficult as the size of the computer grows, so it may turn out to be possible to build
small quantum computers, while scaling up to machines large enough to do interesting
computations may present fundamental difficulties.
Even if no useful quantum computer is ever built, this research does illuminate
the problem of simulating quantum mechanics on a classical computer. Any method of
doing this for an arbitrary Hamiltonian would necessarily be able to simulate a quantum
computer. Thus, any general method for simulating quantum mechanics with at most
a polynomial slowdown would lead to a polynomial-time algorithm for factoring.
The rest of this paper is organized as follows. In x2, we introduce the model of
quantum computation, the quantum gate array, that we use in the rest of the paper.
In xx3 and 4, we explain two subroutines that are used in our algorithms: reversible
modular exponentiation in x3 and quantum Fourier transforms in x4. In x5, we give
our algorithm for prime factorization, and in x6, we give our algorithm for extracting
discrete logarithms. In x7, we give a brief discussion of the practicality of quantum
computation and suggest possible directions for further work.
Quantum computation
In this section we give a brief introduction to quantum computation, emphasizing the
properties that we will use. We will describe only quantum gate arrays, or quantum
acyclic circuits, which are analogous to acyclic circuits in classical computer science.
For other models of quantum computers, see references on quantum Turing machines
[Deutsch 1989, Bernstein and Vazirani 1993, Yao 1993] and quantum cellular automata
[Feynman 1986, Margolus 1986, 1990, Lloyd 1993, Biafore 1994]. If they are allowed
a small probability of error, quantum Turing machines and quantum gate arrays can
compute the same functions in polynomial time [Yao 1993]. This may also be true for
the various models of quantum cellular automata, but it has not yet been proved. This
gives evidence that the class of functions computable in quantum polynomial time with
a small probability of error is robust, in that it does not depend on the exact architecture
of a quantum computer. By analogy with the classical class BPP, this class is called
BQP.
Consider a system with n components, each of which can have two states. Whereas
in classical physics, a complete description of the state of this system requires only n
bits, in quantum physics, a complete description of the state of this system requires
To be more precise, the state of the quantum system is a
point in a 2 n -dimensional vector space. For each of the 2 n possible classical positions
of the components, there is a basis state of this vector space which we represent, for
example, by j011 meaning that the first bit is 0, the second bit is 1, and so on.
Here, the ket notation jxi means that x is a (pure) quantum state. (Mixed states will
6 P. W. SHOR
not be discussed in this paper, and thus we do not define them; see a quantum theory
book such as Peres [1993] for this definition.) The Hilbert space associated with this
quantum system is the complex vector space with these 2 n states as basis vectors, and
the state of the system at any time is represented by a unit-length vector in this Hilbert
space. As multiplying this state vector by a unit-length complex phase does not change
any behavior of the state, we need only numbers to completely describe
the state. We represent this superposition of states as
a
where the amplitudes a i are complex numbers such that
each jS i i
is a basis vector of the Hilbert space. If the machine is measured (with respect to
this basis) at any particular step, the probability of seeing basis state jS i i is ja
however, measuring the state of the machine projects this state to the observed basis
vector jS i i. Thus, looking at the machine during the computation will invalidate the
rest of the computation. In this paper, we only consider measurements with respect
to the canonical basis. This does not greatly restrict our model of computation, since
measurements in other reasonable bases could be simulated by first using quantum
computation to perform a change of basis and then performing a measurement in the
canonical basis.
In order to use a physical system for computation, we must be able to change the
state of the system. The laws of quantum mechanics permit only unitary transformations
of state vectors. A unitary matrix is one whose conjugate transpose is equal to
its inverse, and requiring state transformations to be represented by unitary matrices
ensures that summing the probabilities of obtaining every possible outcome will result
in 1. The definition of quantum circuits (and quantum Turing machines) only allows
local unitary transformations; that is, unitary transformations on a fixed number of
bits. This is physically justified because, given a general unitary transformation on n
bits, it is not at all clear how one would efficiently implement it physically, whereas
two-bit transformations can at least in theory be implemented by relatively simple
physical systems [Cirac and Zoller 1995, DiVincenzo 1995, Sleator and Weinfurter 1995,
Chuang and Yamomoto 1995]. While general n-bit transformations can always be
built out of two-bit transformations [DiVincenzo 1995, Sleator and Weinfurter 1995,
Lloyd 1995, Deutsch et al. 1995], the number required will often be exponential in n
[Barenco et al. 1995a]. Thus, the set of two-bit transformations form a set of building
blocks for quantum circuits in a manner analogous to the way a universal set of classical
gates (such as the AND, OR and NOT gates) form a set of building blocks for classical
circuits. In fact, for a universal set of quantum gates, it is sufficient to take all one-bit
gates and a single type of two-bit gate, the controlled NOT, which negates the second
bit if and only if the first bit is 1.
Perhaps an example will be informative at this point. A quantum gate can be
expressed as a truth table: for each input basis vector we need to give the output of the
gate. One such gate is:
FACTORING WITH A QUANTUM COMPUTER 7
Not all truth tables correspond to physically feasible quantum gates, as many truth
tables will not give rise to unitary transformations.
The same gate can also be represented as a matrix. The rows correspond to input
basis vectors. The columns correspond to output basis vectors. The (i;
when the ith basis vector is input to the gate, the coefficient of the jth basis vector in
the corresponding output of the gate. The truth table above would then correspond to
the following matrix:
p:
A quantum gate is feasible if and only if the corresponding matrix is unitary, i.e., its
inverse is its conjugate transpose.
Suppose our machine is in the superposition of statespj10i
and we apply the unitary transformation represented by (2.2) and (2.3) to this state.
The resulting output will be the result of multiplying the vector (2.4) by the matrix
(2.3). The machine will thus go to the superposition of states2
This example shows the potential effects of interference on quantum computation. Had
we started with either the state j10i or the state j11i, there would have been a chance of
observing the state j10i after the application of the gate (2.3). However, when we start
with a superposition of these two states, the probability amplitudes for the state j10i
cancel, and we have no possibility of observing j10i after the application of the gate.
Notice that the output of the gate would have been j10i instead of j11i had we started
with the superposition of statespj10i
which has the same probabilities of being in any particular configuration if it is observed
as does the superposition (2.4).
If we apply a gate to only two bits of a longer basis vector (now our circuit must have
more than two wires), we multiply the gate matrix by the two bits to which the gate is
8 P. W. SHOR
applied, and leave the other bits alone. This corresponds to multiplying the whole state
by the tensor product of the gate matrix on those two bits with the identity matrix on
the remaining bits.
A quantum gate array is a set of quantum gates with logical "wires" connecting their
inputs and outputs. The input to the gate array, possibly along with extra work bits
that are initially set to 0, is fed through a sequence of quantum gates. The values of
the bits are observed after the last quantum gate, and these values are the output. To
compare gate arrays with quantum Turing machines, we need to add conditions that
make gate arrays a uniform complexity class. In other words, because there is a different
gate array for each size of input, we need to keep the designer of the gate arrays from
hiding non-computable (or hard to compute) information in the arrangement of the
gates. To make quantum gate arrays uniform, we must add two things to the definition
of gate arrays. The first is the standard requirement that the design of the gate array
be produced by a polynomial-time (classical) computation. The second requirement
should be a standard part of the definition of analog complexity classes, although since
analog complexity classes have not been widely studied, this requirement is much less
widely known. This requirement is that the entries in the unitary matrices describing
the gates must be computable numbers. Specifically, the first log n bits of each entry
should be classically computable in time polynomial in n [Solovay 1995]. This keeps
non-computable (or hard to compute) information from being hidden in the bits of the
amplitudes of the quantum gates.
3 Reversible logic and modular exponentiation
The definition of quantum gate arrays gives rise to completely reversible computation.
That is, knowing the quantum state on the wires leading out of a gate tells uniquely
what the quantum state must have been on the wires leading into that gate. This is a
reflection of the fact that, despite the macroscopic arrow of time, the laws of physics appear
to be completely reversible. This would seem to imply that anything built with the
laws of physics must be completely reversible; however, classical computers get around
this fact by dissipating energy and thus making their computations thermodynamically
irreversible. This appears impossible to do for quantum computers because superpositions
of quantum states need to be maintained throughout the computation. Thus,
quantum computers necessarily have to use reversible computation. This imposes extra
costs when doing classical computations on a quantum computer, as is sometimes
necessary in subroutines of quantum computations.
Because of the reversibility of quantum computation, a deterministic computation
is performable on a quantum computer only if it is reversible. Luckily, it has already
been shown that any deterministic computation can be made reversible [Lecerf 1963,
Bennett 1973]. In fact, reversible classical gate arrays have been studied. Much like
the result that any classical computation can be done using NAND gates, there are also
universal gates for reversible computation. Two of these are Toffoli gates [Toffoli 1980]
and Fredkin gates [Fredkin and Toffoli 1982]; these are illustrated in Table 3.1.
The Toffoli gate is just a controlled controlled NOT, i.e., the last bit is negated if
and only if the first two bits are 1. In a Toffoli gate, if the third input bit is set to 1,
then the third output bit is the NAND of the first two input bits. Since NAND is a
FACTORING WITH A QUANTUM COMPUTER 9

Table

3.1: Truth tables for Toffoli and Fredkin gates.
Toffoli Gate
INPUT OUTPUT
Fredkin Gate
INPUT OUTPUT
universal gate for classical gate arrays, this shows that the Toffoli gate is universal. In
a Fredkin gate, the last two bits are swapped if the first bit is 0, and left untouched if
the first bit is 1. For a Fredkin gate, if the third input bit is set to 0, the second output
bit is the AND of the first two input bits; and if the last two input bits are set to 0
and 1 respectively, the second output bit is the NOT of the first input bit. Thus, both
AND and NOT gates are realizable using Fredkin gates, showing that the Fredkin gate
is universal.
From results on reversible computation [Lecerf 1963, Bennett 1973], we can compute
any polynomialtime function F (x) as long as we keep the input x in the computer. We do
this by adapting the method for computing the function F non-reversibly. These results
can easily be extended to work for gate arrays [Toffoli 1980, Fredkin and Toffoli 1982].
When AND, OR or NOT gates are changed to Fredkin or Toffoli gates, one obtains
both additional input bits, which must be preset to specified values, and additional
output bits, which contain the information needed to reverse the computation. While
the additional input bits do not present difficulties in designing quantum computers,
the additional output bits do, because unless they are all reset to 0, they will affect the
interference patterns in quantum computation. Bennett's method for resetting these bits
to 0 is shown in the top half of Table 3.2. A non-reversible gate array may thus be turned
into a reversible gate array as follows. First, duplicate the input bits as many times as
necessary (since each input bit could be used more than once by the gate array). Next,
keeping one copy of the input around, use Toffoli and Fredkin gates to simulate non-reversible
gates, putting the extra output bits into the RECORD register. These extra
output bits preserve enough of a record of the operations to enable the computation of
the gate array to be reversed. Once the output F (x) has been computed, copy it into a
register that has been preset to zero, and then undo the computation to erase both the
first OUTPUT register and the RECORD register.
To erase x and replace it with F (x), in addition to a polynomial-time algorithm for F ,
we also need a polynomial-time algorithm for computing x from F (x); i.e., we need that
F is one-to-one and that both F and F \Gamma1 are polynomial-time computable. The method
for this computation is given in the whole of Table 3.2. There are two stages to this
computation. The first is the same as before, taking x to (x; F (x)). For the second
stage, shown in the bottom half of Table 3.2, note that if we have a method to compute
non-reversibly in polynomial time, we can use the same technique to reversibly map
F (x) to However, since this is a reversible computation,
P. W. SHOR

Table

3.2: Bennett's method for making a computation reversible.
we can reverse it to go from (x; F (x)) to F (x). Put together, these two pieces take x to
F (x).
The above discussion shows that computations can be made reversible for only a
constant factor cost in time, but the above method uses as much space as it does time.
If the classical computation requires much less space than time, then making it reversible
in this manner will result in a large increase in the space required. There are methods
that do not use as much space, but use more time, to make computations reversible
[Bennett 1989, Levine and Sherman 1990]. While there is no general method that does
not cause an increase in either space or time, specific algorithms can sometimes be
made reversible without paying a large penalty in either space or time; at the end of this
section we will show how to do this for modular exponentiation, which is a subroutine
necessary for quantum factoring.
The bottleneck in the quantum factoring algorithm; i.e., the piece of the factoring
algorithm that consumes the most time and space, is modular exponentia-
tion. The modular exponentiation problem is, given n, x, and r, find x r (mod n).
The best classical method for doing this is to repeatedly square of x (mod n) to
(mod n) for i - log 2 r, and then multiply a subset of these powers (mod n)
to get x r (mod n). If we are working with l-bit numbers, this requires O(l) squar-
ings and multiplications of l-bit numbers (mod n). Asymptotically, the best classical
result for gate arrays for multiplication is the Sch-onhage-Strassen algorithm
[Sch-onhage and Strassen 1971, Knuth 1981, Sch-onhage 1982]. This gives a gate array
for integer multiplication that uses O(l log l log log l) gates to multiply two l-bit numbers.
Thus, asymptotically, modular exponentiation requires O(l 2 log l log log l) time. Making
this reversible would na-ively cost the same amount in space; however, one can reuse the
space used in the repeated squaring part of the algorithm, and thus reduce the amount
of space needed to essentially that required for multiplying two l-bit numbers; one simple
method for reducing this space (although not the most versatile one) will be given later
in this section. Thus, modular exponentiation can be done in O(l 2 log l log log l) time
and O(l log l log log l) space.
While the Sch-onhage-Strassen algorithm is the best multiplication algorithm discovered
to date for large l, it does not scale well for small l. For small numbers, the best
gate arrays for multiplication essentially use elementary-school longhand multiplication
in binary. This method requires O(l 2 ) time to multiply two l-bit numbers, and thus
modular exponentiation requires O(l 3 time with this method. These gate arrays can
be made reversible, however, using only O(l) space.
We will now give the method for constructing a reversible gate array that takes only
FACTORING WITH A QUANTUM COMPUTER 11
O(l) space and O(l 3 ) time to compute (a; x a (mod n)) from a, where a, x, and n are
l-bit numbers. The basic building block used is a gate array that takes b as input and
outputs n). Note that here b is the gate array's input but c and n are built
into the structure of the gate array. Since addition (mod n) is computable in O(log n)
time classically, this reversible gate array can be made with only O(logn) gates and
O(logn) work bits using the techniques explained earlier in this section.
The technique we use for computing x a (mod n) is essentially the same as the classical
method. First, by repeated squaring we compute x 2 i
(mod n) for all i ! l. Then, to
obtain x a (mod n) we multiply the powers x 2 i
(mod n) where 2 i appears in the binary
expansion of a. In our algorithm for factoring n, we only need to compute x a (mod n)
where a is in a superposition of states, but x is some fixed integer. This makes things
much easier, because we can use a reversible gate array where a is treated as input,
but where x and n are built into the structure of the gate array. Thus, we can use the
algorithm described by the following pseudocode; here, a i represents the ith bit of a in
binary, where the bits are indexed from right to left and the rightmost bit of a is a 0 .
power
power := power   x 2 i
(mod n)
endif
endfor
The variable a is left unchanged by the code and x a (mod n) is output as the variable
power . Thus, this code takes the pair of values (a; 1) to (a; x a (mod n)).
This pseudocode can easily be turned into a gate array; the only hard part of this
is the fourth line, where we multiply the variable power by x 2 i
(mod n); to do this we
need to use a fairly complicated gate array as a subroutine. Recall that x 2 i
(mod n)
can be computed classically and then built into the structure of the gate array. Thus,
to implement this line, we need a reversible gate array that takes b as input and gives
bc (mod n) as output, where the structure of the gate array can depend on c and n.
Of course, this step can only be reversible if gcd(c; n) = 1, i.e., if c and n have no
common factors, as otherwise two distinct values of b will be mapped to the same value
of bc (mod n); this case is fortunately all we need for the factoring algorithm. We will
show how to build this gate array in two stages. The first stage is directly analogous
to exponentiation by repeated multiplication; we obtain multiplication from repeated
addition (mod n). Pseudocode for this stage is as follows.
result := 0
result
endif
endfor
n) can be precomputed and built into the structure of the gate array.
P. W. SHOR
The above pseudocode takes b as input, and gives (b; bc (mod n)) as output. To
get the desired result, we now need to erase b. Recall that gcd(c; n) = 1, so there is
n). Multiplication by this c \Gamma1 could be used to
reversibly take bc (mod n) to (bc (mod n); bcc \Gamma1 (mod b). This is
just the reverse of the operation we want, and since we are working with reversible
computing, we can turn this operation around to erase b. The pseudocode for this
follows.
endif
endfor
As before, result i is the ith bit of result.
Note that at this stage of the computation, b should be 0. However, we did not set b
directly to zero, as this would not have been a reversible operation and thus impossible on
a quantum computer, but instead we did a relatively complicated sequence of operations
which ended with which in fact depended on multiplication being a group
(mod n). At this point, then, we could do something somewhat sneaky: we could
measure b to see if it actually is 0. If it is not, we know that there has been an error
somewhere in the quantum computation, i.e., that the results are worthless and we
should stop the computer and start over again. However, if we do find that b is 0,
then we know (because we just observed it) that it is now exactly 0. This measurement
thus may bring the quantum computation back on track in that any amplitude that b
had for being non-zero has been eliminated. Further, because the probability that we
observe a state is proportional to the square of the amplitude of that state, depending
on the error model, doing the modular exponentiation and measuring b every time that
we know that it should be 0 may have a higher probability of overall success than the
same computation done without the repeated measurements of b; this is the quantum
watchdog (or quantum Zeno) effect [Peres 1993]. The argument above does not actually
show that repeated measurement of b is indeed beneficial, because there is a cost (in time,
if nothing else) of measuring b. Before this is implemented, then, it should be checked
with analysis or experiment that the benefit of such measurements exceeds their cost.
However, I believe that partial measurements such as this one are a promising way of
trying to stabilize quantum computations.
Currently, Sch-onhage-Strassen is the algorithm of choice for multiplying very large
numbers, and longhand multiplication is the algorithm of choice for small numbers.
There are also multiplication algorithms which have efficiencies between these two al-
gorithms, and which are the best algorithms to use for intermediate length numbers
[Karatsuba and Ofman 1962, Knuth 1981, Sch-onhage et al. 1994]. It is not clear which
algorithms are best for which size numbers. While this may be known to some extent
for classical computation [Sch-onhage et al. 1994], using data on which algorithms work
better on classical computers could be misleading for two reasons: First, classical computers
need not be reversible, and the cost of making an algorithm reversible depends
on the algorithm. Second, existing computers generally have multiplication for 32- or
64-bit numbers built into their hardware, and this will increase the optimal changeover
FACTORING WITH A QUANTUM COMPUTER 13
points to asymptotically faster algorithms; further, some multiplication algorithms can
take better advantage of this hardwired multiplication than others. Thus, in order to
program quantum computers most efficiently, work needs to be done on the best way of
implementing elementary arithmetic operations on quantum computers. One tantalizing
fact is that the Sch-onhage-Strassen fast multiplication algorithm uses the fast Fourier
transform, which is also the basis for all the fast algorithms on quantum computers
discovered to date; it is tempting to speculate that integer multiplication itself might be
speeded up by a quantum algorithm; if possible, this would result in a somewhat faster
asymptotic bound for factoring on a quantum computer, and indeed could even make
breaking RSA on a quantum computer asymptotically faster than encrypting with RSA
on a classical computer.
4 Quantum Fourier transforms
Since quantum computation deals with unitary transformations, it is helpful to be able
to build certain useful unitary transformations. In this section we give a technique for
constructing in polynomial time on quantum computers one particular unitary transfor-
mation, which is essentially a discrete Fourier transform. This transformation will be
given as a matrix, with both rows and columns indexed by states. These states correspond
to binary representations of integers on the computer; in particular, the rows and
columns will be indexed beginning with 0 unless otherwise specified.
This transformations is as follows. Consider a number a with 0 - a ! q for some q
where the number of bits of q is polynomial. We will perform the transformation that
takes the state jai to the stateq 1=2
That is, we apply the unitary matrix whose (a; c) entry is 1
exp(2-iac=q). This Fourier
transform is at the heart of our algorithms, and we call this matrix A q .
Since we will use A q for q of exponential size, we must show how this transformation
can be done in polynomial time. In this paper, we will give a simple construction for A q
when q is a power of 2 that was discovered independently by Coppersmith [1994] and
Deutsch [see Ekert and Jozsa 1995]. This construction is essentially the standard fast
Fourier transform (FFT) algorithm [Knuth 1981] adapted for a quantum computer; the
following description of it follows that of Ekert and Jozsa [1995]. In the earlier version
of this paper [Shor 1994], we gave a construction for A q when q was in the special class
of smooth numbers with small prime power factors. In fact, Cleve [1994] has shown how
to construct A q for all smooth numbers q whose prime factors are at most O(logn).
us represent an integer a in binary as ja l\Gamma1 a For the
quantum Fourier transform A q , we only need to use two types of quantum gates. These
gates are R j , which operates on the jth bit of the quantum computer:
14 P. W. SHOR
and S j;k , which operates on the bits in positions j and k with
To perform a quantum Fourier transform, we apply the matrices
in the order (from left to right)
R
that is, we apply the gates R j in reverse order from R l\Gamma1 to R 0 , and between R j+1 and
R j we apply all the gates S j;k where k ? j. For example, on 3 bits, the matrices would
be applied in the order R 2 S 1;2 R 1 S 0;2 S 0;1 R 0 . To take the Fourier transform A q when
thus need to use l(l \Gamma 1)=2 quantum gates.
Applying this sequence of transformations will result in a quantum stateq 1=2
b exp(2-iac=q) jbi, where b is the bit-reversal of c, i.e., the binary number obtained
by reading the bits of c from right to left. Thus, to obtain the actual quantum
Fourier transform, we need either to do further computation to reverse the bits of jbi
to obtain jci, or to leave these bits in place and read them in reverse order; either
alternative is easy to implement.
To show that this operation actually performs a quantum Fourier transform, consider
the amplitude of going from First, the factors
of 1=
2 in the R matrices multiply to produce a factor of 1=q 1=2 overall; thus we need
only worry about the exp(2-iac=q) phase factor in the expression (4.1). The matrices
S j;k do not change the values of any bits, but merely change their phases. There is thus
only one way to switch the jth bit from a j to b j , and that is to use the appropriate entry
in the matrix R j . This entry adds - to the phase if the bits a j and b j are both 1, and
leaves it unchanged otherwise. Further, the matrix S j;k adds -=2 k\Gammaj to the phase if a j
and b k are both 1 and leaves it unchanged otherwise. Thus, the phase on the path from
jai to jbi is X
0-j!l
0-j!k!l
This expression can be rewritten as
0-j-k!l
Since c is the bit-reversal of b, this expression can be further rewritten as
0-j-k!l
Making the substitution l in this sum, we get
0-j+k!l
l a j c k (4.8)
FACTORING WITH A QUANTUM COMPUTER 15
Now, since adding multiples of 2- do not affect the phase, we obtain the same phase if
we sum over all j and k less than l, obtaining
where the last equality follows from the distributive law of multiplication. Now,
so the above expression is equal to 2-ac=q, which is
the phase for the amplitude of jai ! jci in the transformation (4.1).
large in the gate S j;k in (4.3), we are multiplying by a very small
phase factor. This would be very difficult to do accurately physically, and thus it would
be somewhat disturbing if this were necessary for quantum computation. Luckily, Coppersmith
[1994] has shown that one can define an approximate Fourier transform that
ignores these tiny phase factors, but which approximates the Fourier transform closely
enough that it can also be used for factoring. In fact, this technique reduces the number
of quantum gates needed for the (approximate) Fourier transform considerably, as it
leaves out most of the gates S j;k .
5 Prime factorization
It has been known since before Euclid that every integer n is uniquely decomposable
into a product of primes. Mathematicians have been interested in the question of how
to factor a number into this product of primes for nearly as long. It was only in the
1970's, however, that researchers applied the paradigms of theoretical computer science
to number theory, and looked at the asymptotic running times of factoring algorithms
[Adleman 1994]. This has resulted in a great improvement in the efficiency of factoring
algorithms. The best factoring algorithm asymptotically is currently the number field
sieve [Lenstra et al. 1990, Lenstra and Lenstra 1993], which in order to factor an integer
takes asymptotic running time exp(c(log n) 1=3 (log log n) 2=3 ) for some constant c.
Since the input, n, is only log n bits in length, this algorithm is an exponential-time
algorithm. Our quantum factoring algorithm takes asymptotically O((log n) 2 (log log n)
(log log log n)) steps on a quantum computer, along with a polynomial (in log n) amount
of post-processing time on a classical computer that is used to convert the output of
the quantum computer to factors of n. While this post-processing could in principle be
done on a quantum computer, there is no reason not to use a classical computer if they
are more efficient in practice.
Instead of giving a quantum computer algorithm for factoring n directly, we give a
quantum computer algorithm for finding the order of an element x in the multiplicative
group (mod n); that is, the least integer r such that x r j 1 (mod n). It is known that
using randomization, factorization can be reduced to finding the order of an element
[Miller 1976]; we now briefly give this reduction.
To find a factor of an odd number n, given a method for computing the order r
of x, choose a random x (mod n), find its order r, and compute gcd(x
gcd(a; b) is the greatest common divisor of a and b, i.e., the largest integer that divides
both a and b. The Euclidean algorithm [Knuth 1981] can be used to compute gcd(a; b)
in polynomial time. Since n), the gcd(x
P. W. SHOR
fails to be a non-trivial divisor of n only if r is odd or if x n). Using this
criterion, it can be shown that this procedure, when applied to a random x (mod n),
yields a factor of n with probability at least 1 \Gamma 1=2 is the number of distinct
odd prime factors of n. A brief sketch of the proof of this result follows. Suppose that
be the order of x (mod p a i
r is the least common multiple
of all the r i . Consider the largest power of 2 dividing each r i . The algorithm only fails
if all of these powers of 2 agree: if they are all 1, then r is odd and r=2 does not exist; if
they are all equal and larger than 1, then x
for every i. By the Chinese remainder theorem [Knuth 1981, Hardy and Wright 1979,
Theorem 121], choosing an x (mod n) at random is the same as choosing for each i a
number x i (mod p a i
i ) at random, where p a i
i is the ith prime power factor of n. The
multiplicative group (mod p ff ) for any odd prime power p ff is cyclic [Knuth 1981], so for
any odd prime power p a i
i , the probability is at most 1=2 of choosing an x i having any
particular power of two as the largest divisor of its order r i . Thus each of these powers
of 2 has at most a 50% probability of agreeing with the previous ones, so all k of them
agree with probability at most 1=2 k\Gamma1 , and there is at least a chance that
the x we choose is good. This scheme will thus work as long as n is odd and not a prime
finding factors of prime powers can be done efficiently with classical methods.
We now describe the algorithm for finding the order of x (mod n) on a quantum
computer. This algorithm will use two quantum registers which hold integers represented
in binary. There will also be some amount of workspace. This workspace gets reset to
after each subroutine of our algorithm, so we will not include it when we write down
the state of our machine.
Given x and n, to find the order of x, i.e., the least r such that x r j 1 (mod n), we
do the following. First, we find q, the power of 2 with We will not include
when we write down the state of our machine, because we never change these
values. In a quantum gate array we need not even keep these values in memory, as they
can be built into the structure of the gate array.
Next, we put the first register in the uniform superposition of states representing
numbers a (mod q). This leaves our machine in stateq 1=2
This step is relatively easy, since all it entails is putting each bit in the first register into
the superposition 1
Next, we compute x a (mod n) in the second register as described in x3. Since we
keep a in the first register this can be done reversibly. This leaves our machine in the
stateq 1=2
jai jx a (mod n)i : (5.2)
We then perform our Fourier transform A q on the first register, as described in x4,
mapping jai toq 1=2
FACTORING WITH A QUANTUM COMPUTER 17
That is, we apply the unitary matrix with the (a; c) entry equal to 1
exp(2-iac=q).
This leaves our machine in stateq
Finally, we observe the machine. It would be sufficient to observe solely the value
of jci in the first register, but for clarity we will assume that we observe both jci and
jx a (mod n)i. We now compute the probability that our machine ends in a particular
state
ff , where we may assume Summing over all possible ways
to reach the state
ff , we find that this probability is
a: x a jx k
where the sum is over all a, 0 - a ! q, such that x a j x k (mod n). Because the order
of x is r, this sum is over all a satisfying a j k (mod r). Writing a
that the above probability is
We can ignore the term of exp(2-ikc=q), as it can be factored out of the sum and has
magnitude 1. We can also replace rc with frcg q , where frcg q is the residue which is
congruent to rc (mod q) and is in the range \Gammaq=2 ! frcg q - q=2. This leaves us with
the expression fi fi fi fi fi fiq
exp(2-ibfrcg q =q)
We will now show that if frcg q is small enough, all the amplitudes in this sum will be
in nearly the same direction (i.e., have close to the same phase), and thus make the sum
large. Turning the sum into an integral, we obtainq
r cexp(2-ibfrcg q =q)db
If jfrcg q j - r=2, the error term in the above expression is easily seen to be bounded by
O(1=q). We now show that if jfrcg q j - r=2, the above integral is large, so the probability
of obtaining a state
ff is large. Note that this condition depends only on
c and is independent of k. Substituting in the above integral, we getr
Z r
r cexp
r u
du:
approximating the upper limit of integration by 1 results in only a O(1=q)
error in the above expression. If we do this, we obtain the integralr
Z 1exp
r u
du: (5.10)
P. W. SHOR0.020.060.100
c

Figure

5.1: The probability P of observing values of c between 0 and 255, given
and
Letting frcg q =r vary between \Gamma 1and 1, the absolute magnitude of the integral (5.10)
is easily seen to be minimized when frcg q which case the absolute value
of expression (5.10) is 2=(-r). The square of this quantity is a lower bound on the
probability that we see any particular state
ff with frcg q - r=2; this
probability is thus asymptotically bounded below by 4=(- 2 r 2 ), and so is at least 1=3r 2
for sufficiently large n.
The probability of seeing a given state
ff will thus be at least 1=3r 2 if
\Gammar
i.e., if there is a d such that
\Gammar
Dividing by rq and rearranging the terms gives
r
We know c and q. Because q ? n 2 , there is at most one fraction d=r with r ! n that
satisfies the above inequality. Thus, we can obtain the fraction d=r in lowest terms by
rounding c=q to the nearest fraction having a denominator smaller than n. This fraction
can be found in polynomial time by using a continued fraction expansion of c=q, which
FACTORING WITH A QUANTUM COMPUTER 19
finds all the best approximations of c=q by fractions [Hardy and Wright 1979, Chapter
X, Knuth 1981].
The exact probabilities as given by equation (5.7) for an example case with
and are plotted in Figure 5.1. The value could occur when factoring 33
if x were chosen to be 5, for example. Here q is taken smaller than 33 2 so as to make the
values of c in the plot distinguishable; this does not change the functional structure of
P(c). Note that with high probability the observed value of c is near an integral multiple
of
If we have the fraction d=r in lowest terms, and if d happens to be relatively prime
to r, this will give us r. We will now count the number of states
ff which
enable us to compute r in this way. There are OE(r) possible values of d relatively prime
to r, where OE is Euler's totient function [Knuth 1981, Hardy and Wright 1979, x5.5].
Each of these fractions d=r is close to one fraction c=q with There
are also r possible values for x k , since r is the order of x. Thus, there are rOE(r) states
ff which would enable us to obtain r. Since each of these states occurs
with probability at least 1=3r 2 , we obtain r with probability at least OE(r)=3r. Using
the theorem that OE(r)=r ? log r for some constant ffi [Hardy and Wright 1979,
Theorem 328], this shows that we find r at least a fraction of the time, so by
repeating this experiment only O(log log r) times, we are assured of a high probability
of success.
In practice, assuming that quantum computation is more expensive than classical
computation, it would be worthwhile to alter the above algorithm so as to perform less
quantum computation and more postprocessing. First, if the observed state is jci, it
would be wise to also try numbers close to c such as c \Sigma 1, c \Sigma since these also
have a reasonable chance of being close to a fraction qd=r. Second, if c=q - d=r, and
d and r have a common factor, it is likely to be small. Thus, if the observed value of
c=q is rounded off to d 0 =r 0 in lowest terms, for a candidate r one should consider not
only r 0 but also its small multiples 2r 0 , 3r 0 , . , to see if these are the actual order of x.
Although the first technique will only reduce the expected number of trials required to
find r by a constant factor, the second technique will reduce the expected number of
trials for the hardest n from O(log log n) to O(1) if the first (log n) 1+ffl multiples of r 0 are
considered [Odylzko 1995]. A third technique is, if two candidate r's have been found,
say r 1 and r 2 , to test the least common multiple of r 1 and r 2 as a candidate r. This third
technique is also able to reduce the expected number of trials to a constant [Knill 1995],
and will also work in some cases where the first two techniques fail.
Note that in this algorithm for determining the order of an element, we did not use
many of the properties of multiplication (mod n). In fact, if we have a permutation
f mapping the set f0; itself such that its kth iterate, f (k) (a), is
computable in time polynomial in log n and log k, the same algorithm will be able to
find the order of an element a under f , i.e., the minimum r such that f (r) (a) = a.
6 Discrete logarithms
For every prime p, the multiplicative group (mod p) is cyclic, that is, there are generators
g such that 1, g, g 2 , . , g p\Gamma2 comprise all the non-zero residues (mod p) [Hardy and
Wright 1979, Theorem 111, Knuth 1981]. Suppose we are given a prime p and such
P. W. SHOR
a generator g. The discrete logarithm of a number x with respect to p and g is the
integer r with p). The fastest algorithm known for
finding discrete logarithms modulo arbitrary primes p is Gordon's [1993] adaptation of
the number field sieve, which runs in time exp(O(log p) 1=3 (log log p) 2=3 )). We show how
to find discrete logarithms on a quantum computer with two modular exponentiations
and two quantum Fourier transforms.
This algorithm will use three quantum registers. We first find q a power of 2 such
that q is close to p, i.e., with Next, we put the first two registers in our
quantum computer in the uniform superposition of all jai and jbi (mod
compute g a x \Gammab (mod p) in the third register. This leaves our machine in the statep \Gamma 1
a x \Gammab (mod p)
As before, we use the Fourier transform A q to send jai ! jci and jbi ! jdi with
probability amplitude 1
q exp(2-i(ac+bd)=q). This is, we take the state ja; bi to the stateq
exp
This leaves our quantum computer in the state(p \Gamma 1)q
c;d=0
exp
a x \Gammab (mod p)
Finally, we observe the state of the quantum computer.
The probability of observing a state jc; d; yi with y j g k (mod p) is
a;b
a\Gammarbjk
exp
where the sum is over all (a; b) such that a \Gamma rb 1). Note that we now
have two moduli to deal with, q. While this makes keeping track of things
more confusing, it does not pose serious problems. We now use the relation
and substitute (6.5) in the expression (6.4) to obtain the amplitude on
ff ,
which
exp
The absolute value of the square of this amplitude is the probability of observing the
state
ff . We will now analyze the expression (6.6). First, a factor of
FACTORING WITH A QUANTUM COMPUTER 21
exp(2-ikc=q) can be taken out of all the terms and ignored, because it does not change
the probability. Next, we split the exponent into two parts and factor out b to obtain(p \Gamma 1)q
exp
exp
where
and
Here by fzg q we mean the residue of z (mod q) with \Gammaq=2 ! fzg q - q=2, as in equation
(5.7).
We next classify possible outputs (observed states) of the quantum computer into
"good" and "bad." We will show that if we get enough "good" outputs, then we will
likely be able to deduce r, and that furthermore, the chance of getting a "good" output
is constant. The idea is that if
where j is the closest integer to T=q, then as b varies between 0 and 2, the phase
of the first exponential term in equation (6.7) only varies over at most half of the unit
circle. Further, if
then jV j is always at most q=12, so the phase of the second exponential term in equation
(6.7) never is farther than exp(-i=6) from 1. If conditions (6.10) and (6.11) both hold,
we will say that an output is "good." We will show that if both conditions hold, then the
contribution to the probability from the corresponding term is significant. Furthermore,
both conditions will hold with constant probability, and a reasonable sample of c's for
which condition (6.10) holds will allow us to deduce r.
We now give a lower bound on the probability of each good output, i.e., an output
that satisfies conditions (6.10) and (6.11). We know that as b ranges from 0 to
the phase of exp(2-ibT=q) ranges from 0 to 2-iW where
and j is as in equation (6.10). Thus, the component of the amplitude of the first
exponential in the summand of (6.7) in the direction
is at least cos(2- jW=2 \Gamma W b=(p \Gamma 2)j). By condition (6.11), the phase can vary by at
most -i=6 due to the second exponential exp(2-iV=q). Applying this variation in the
manner that minimizes the component in the direction (6.13), we get that the component
in this direction is at least
22 P. W. SHOR
Thus we get that the absolute value of the amplitude (6.7) is at least(p \Gamma 1)q
cos
Replacing this sum with an integral, we get that the absolute value of this amplitude is
at leastq
From condition (6.10), jW j - 1, so the error term is O( 1
pq ). As W varies between \Gamma 1and 1, the integral (6.16) is minimized when jW 1. Thus, the probability of arriving
at a state jc; d; yi that satisfies both conditions (6.10) and (6.11) is at least
Z 2-=3
cos u du
or at least :054=q 2 ? 1=(20q 2 ).
We will now count the number of pairs (c; d) satisfying conditions (6.10) and (6.11).
The number of pairs (c; d) such that (6.10) holds is exactly the number of possible c's,
since for every c there is exactly one d such that (6.10) holds. Unless gcd(p \Gamma 1; q) is large,
the number of c's for which (6.11) holds is approximately q=6, and even if it is large,
this number is at least q=12. Thus, there are at least q=12 pairs (c; d) satisfying both
conditions. Multiplying by which is the number of possible y's, gives approximately
pq=12 good states jc; d; yi. Combining this calculation with the lower bound 1=(20q 2 ) on
the probability of observing each good state gives us that the probability of observing
some good state is at least p=(240q), or at least 1=480 (since q ! 2p). Note that each
good c has a probability of at least (p of being observed, since
there of y and one value of d with which c can make a good state jc; d; yi.
We now want to recover r from a pair c; d such that
(mod 1); (6.18)
where this equation was obtained from condition (6.10) by dividing by q. The first thing
to notice is that the multiplier on r is a fraction with denominator evenly
divides . Thus, we need only round d=q off to the nearest multiple
of by the integer
to find a candidate r. To show that the quantum calculation need only be repeated a
polynomial number of times to find the correct r requires only a few more details. The
problem is that we cannot divide by a number c 0 which is not relatively prime to p \Gamma 1.
For the discrete log algorithm, we do not know that all possible values of c 0 are
generated with reasonable likelihood; we only know this about one-twelfth of them.
This additional difficulty makes the next step harder than the corresponding step in the
FACTORING WITH A QUANTUM COMPUTER 23
algorithm for factoring. If we knew the remainder of r modulo all prime powers dividing
could use the Chinese remainder theorem to recover r in polynomial time. We
will only be able to prove that we can find this remainder for primes larger than 18, but
with a little extra work we will still be able to recover r.
Recall that each good (c; d) pair is generated with probability at least 1=(20q 2 ), and
that at least a twelfth of the possible c's are in a good (c; d) pair. From equation (6.19),
it follows that these c's are mapped from c=q to c 0 by rounding to the nearest
integral multiple of 1=(p \Gamma 1). Further, the good c's are exactly those in which c=q is
close to c 0 =(p \Gamma 1). Thus, each good c corresponds with exactly one c 0 . We would like
to show that for any prime power p ff i
dividing is unlikely to
contain p i . If we are willing to accept a large constant for our algorithm, we can just
ignore the prime powers under 18; if we know r modulo all prime powers over 18, we can
try all possible residues for primes under with only a (large) constant factor increase
in running time. Because at least one twelfth of the c's were in a good (c; d) pair, at
least one twelfth of the c 0 's are good. Thus, for a prime power p ff i
i , a random good c 0 is
divisible by p ff i
with probability at most 12=p ff i
. If we have t good c 0 's, the probability
of having a prime power over that divides all of them is therefore at most
where ajb means that a evenly divides b, so the sum is over all prime powers greater
than
goes down by at least a factor of 2=3 for each further increase of t by 1; thus for some
constant t it is less than 1=2.
Recall that each good c 0 is obtained with probability at least 1=(40q) from any
experiment. Since there are q=12 good c 0 's, after 480t experiments, we are likely to
obtain a sample of t good c 0 's chosen equally likely from all good c 0 's. Thus, we will be
able to find a set of c 0 's such that all prime powers p ff i
are relatively
prime to at least one of these c 0 's. To obtain a polynomial time algorithm, all one need
do is try all possible sets of c 0 's of size t; in practice, one would use an algorithm to
find sets of c 0 's with large common factors. This set gives the residue of r for all primes
larger than 18. For each prime p i less than 18, we have at most possibilities for the
residue modulo p ff i
is the exponent on prime p i in the prime factorization of
1. We can thus try all possibilities for residues modulo powers of primes less than 18:
for each possibility we can calculate the corresponding r using the Chinese remainder
theorem and then check to see whether it is the desired discrete logarithm.
If one were to actually program this algorithm there are many ways in which the
efficiency could be increased over the efficiency shown in this paper. For example, the
estimate for the number of good c 0 's is likely too low, especially since weaker conditions
than (6.10) and (6.11) should suffice. This means that the number of times the experiment
need be run could be reduced. It also seems improbable that the distribution of
bad values of c 0 would have any relationship to primes under 18; if this is true, we need
not treat small prime powers separately.
This algorithm does not use very many properties of Z p , so we can use the same
algorithm to find discrete logarithms over other fields such as Z p ff , as long as the field
P. W. SHOR
has a cyclic multiplicative group. All we need is that we know the order of the generator,
and that we can multiply and take inverses of elements in polynomial time. The order
of the generator could in fact be computed using the quantum order-finding algorithm
given in x5 of this paper. Boneh and Lipton [1995] have generalized the algorithm so as
to be able to find discrete logarithms when the group is abelian but not cyclic.
7 Comments and open problems
It is currently believed that the most difficult aspect of building an actual quantum
computer will be dealing with the problems of imprecision and decoherence. It was
shown by Bennett et al. [1994] that the quantum gates need only have precision O(1=t)
in order to have a reasonable probability of completing t steps of quantum computation;
that is, there is a c such that if the amplitudes in the unitary matrices representing the
quantum gates are all perturbed by at most c=t, the quantum computer will still have a
reasonable chance of producing the desired output. Similarly, the decoherence needs to
be only polynomially small in t in order to have a reasonable probability of completing t
steps of computation successfully. This holds not only for the simple model of decoherence
where each bit has a fixed probability of decohering at each time step, but also for
more complicated models of decoherence which are derived from fundamental quantum
mechanical considerations [Unruh 1995, Palma et al. 1995, Chuang et al. 1995]. How-
ever, building quantum computers with high enough precision and low enough decoherence
to accurately perform long computations may present formidable difficulties to
experimental physicists. In classical computers, error probabilities can be reduced not
only though hardware but also through software, by the use of redundancy and error-correcting
codes. The most obvious method of using redundancy in quantum computers
is ruled out by the theorem that quantum bits cannot be cloned [Peres 1993, x9-4],
but this argument does not rule out more complicated ways of reducing inaccuracy or
decoherence using software. In fact, some progress in the direction of reducing inaccuracy
[Berthiaume et al. 1994] and decoherence [Shor 1995] has already been made. The
result of Bennett et al. [1995] that quantum bits can be faithfully transmitted over a
noisy quantum channel gives further hope that quantum computations can similarly be
faithfully carried out using noisy quantum bits and noisy quantum gates.
Discrete logarithms and factoring are not in themselves widely useful problems. They
have only become useful because they have been found to be crucial for public-key cryp-
tography, and this application is in turn possible only because they have been presumed
to be difficult. This is also true of the generalizations of Boneh and Lipton [1995] of
these algorithms. If the only uses of quantum computation remain discrete logarithms
and factoring, it will likely become a special-purpose technique whose only raison d'-etre
is to thwart public key cryptosystems. However, there may be other hard problems
which could be solved asymptotically faster with quantum computers. In particular,
of interesting problems not known to be NP-complete, the problem of finding a short
vector in a lattice [Adleman 1994, Adleman and McCurley 1995] seems as if it might
potentially be amenable to solution by a quantum computer.
In the history of computer science, however, most important problems have turned
out to be either polynomial-time or NP-complete. Thus quantum computers will likely
not become widely useful unless they can solve NP-complete problems. Solving NP-
FACTORING WITH A QUANTUM COMPUTER 25
complete problems efficiently is a Holy Grail of theoretical computer science which very
few people expect to be possible on a classical computer. Finding polynomial-time
algorithms for solving these problems on a quantum computer would be a momentous
discovery. There are some weak indications that quantum computers are not powerful
enough to solve NP-complete problems [Bennett et al. 1994], but I do not believe that
this potentiality should be ruled out as yet.

Acknowledgements

I would like to thank Jeff Lagarias for finding and fixing a critical error in the first version
of the discrete log algorithm. I would also like to thank him, David Applegate, Charles
Bennett, Gilles Brassard, Andrew Odlyzko, Dan Simon, Bob Solovay, Umesh Vazirani,
and correspondents too numerous to list, for productive discussions, for corrections to
and improvements of early drafts of this paper, and for pointers to the literature.



--R

Algorithmic number theory-The complexity contribution
Open problems in number-theoretic complexity II


The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines


Logical reversibility of computation
Time/space trade-offs for reversible computation
Strengths and weaknesses of quantum computing
Purification of noisy entanglement
Quantum complexity theory


The stabilisation of quantum computations
Can quantum computers have simple Hamiltonians
Quantum cryptanalysis of hidden linear functions
New lower bound techniques for robot motion planning problems

Quantum computers
A simple quantum computer
An unsolvable problem of elementary number theory
Quantum computations with cold trapped ions
A note on computing Fourier transforms by quantum programs
An approximate Fourier transform useful in quantum factoring
Quantum theory
Quantum computational networks
Universality of quantum computation

Rapid solution of problems by quantum computation


Shor's quantum algorithm for factorising numbers
Simulating physics with computers

Conservative logic
Discrete logarithms in GF(p) using the number field sieve
An Introduction to the Theory of Numbers
On the power of multiplication in random access machines
Multiplication of multidigit numbers on automata

The Art of Computer Programming
personal communication.


Machines de Turing r'eversibles.


A note on Bennett's time-space tradeoff for reversible computation
A potentially realizable quantum computer
Envisioning a quantum supercomputer
Almost any quantum logic gate is universal
Quantum computation
Parallel quantum computation
Riemann's hypothesis and tests for primality
personal communication.
Quantum computers and dissipation



Academic Press
Finite combinatory processes.
A method of obtaining digital signatures and public-key cryptosystems
Digital simulation of analog computation and Church's thesis



Algorithms for quantum computation: Discrete logarithms and factoring
Scheme for reducing decoherence in quantum memory
On the power of quantum computation
Realizable universal quantum logic gates
personal communication.
Two non-standard paradigms for computation: Analog machines and cellular automata

Structural basis of multistationary quantum systems II: Effective few-particle dynamics
Reversible computing
On computable numbers

Maintaining coherence in quantum computers

The complexity of analog computation

Quantum circuit complexity
--TR

--CTR
Lihua Liu , Zhengjun Cao, On computing ord
S.-J. Park , A. Persaud , J. A. Liddle , J. Nilsson , J. Bokor , D. H. Schneider , I. W. Rangelow , T. Schenkel, Processing issues in top-down approaches to quantum computer development in Silicon, Microelectronic Engineering, v.73-74 n.1, p.695-700, June 2004
Richard Jozsa, Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem, IEEE MultiMedia, v.3 n.2, p.34-43, March 1996
Andrew M. Steane , Eleanor G. Rieffel, Beyond Bits: The Future of Quantum Information Processing, Computer, v.33 n.1, p.38-45, January 2000
B. M. Terhal, Is entanglement monogamous?, IBM Journal of Research and Development, v.48 n.1, p.71-78, January 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
Mark Ettinger , Peter Hyer , Emanuel Knill, The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters, v.91 n.1, p.43-48, July 2004
Christopher Wolf , An Braeken , Bart Preneel, On the security of stepwise triangular systems, Designs, Codes and Cryptography, v.40 n.3, p.285-302, September 2006
Richard J. Hughes , Colin P. Williams, Quantum Computing: The Final Frontier?, IEEE Intelligent Systems, v.15 n.5, p.10-18, September 2000
Byung-Soo Choi , Thomas A. Walker , Samuel L. Braunstein, Sure Success Partial Search, Quantum Information Processing, v.6 n.1, p.1-8, February  2007
Siddhartha Kasivajhula, Quantum computing: a survey, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
communications with an asymptotic secrecy model, Knowledge-Based Systems, v.20 n.5, p.478-484, June, 2007
IEEE Computer Graphics and Applications Staff, Quantum Computing, Part 3, IEEE Computer Graphics and Applications, v.21 n.6, p.72-82, November 2001
Leslie G. Valiant, Expressiveness of matchgates, Theoretical Computer Science, v.289 n.1, p.457-471, 23 October 2002
Takayuki Miyadera , Masanori Ohya, On Halting Process of Quantum Turing Machine, Open Systems & Information Dynamics, v.12 n.3, p.261-264, June      2005
George F. Viamontes , Igor L. Markov , John P. Hayes, High-Performance QuIDD-Based Simulation of Quantum Circuits, Proceedings of the conference on Design, automation and test in Europe, p.21354, February 16-20, 2004
Kazuo Ohta , Tetsuro Nishino , Seiya Okubo , Noboru Kunihiro, A quantum algorithm using NMR computers to break secret-key cryptosystems, New Generation Computing, v.21 n.4, p.347-361, April
Umesh Vazirani, Fourier transforms and quantum computation, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
Dorit Aharonov , Andris Ambainis , Julia Kempe , Umesh Vazirani, Quantum walks on graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.50-59, July 2001, Hersonissos, Greece
Andrew M. Steane , Eleanor G. Rieffel, Beyond Bits: The Future of Quantum Information Processing, Computer, v.33 n.1, p.38-45, January 2000
Sean Hallgren, Fast quantum algorithms for computing the unit group and class group of a number field, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Richard Cleve, The query complexity of order-finding, Information and Computation, v.192 n.2, p.162-171, August 1, 2004
Hales , Sean Hallgren, Quantum Fourier sampling simplified, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.330-338, May 01-04, 1999, Atlanta, Georgia, United States
Peter W. Shor, Why haven't more quantum algorithms been found?, Journal of the ACM (JACM), v.50 n.1, p.87-90, January
Takashi Mihara , Shao Chin Sung, Deterministic polynomial-time quantum algorithms for Simon's problem, Computational Complexity, v.12 n.3-4, p.162-175, September 2004
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
Andrew Chi-Chih Yao, Classical physics and the Church--Turing Thesis, Journal of the ACM (JACM), v.50 n.1, p.100-105, January
Michelangelo Grigni , Leonard Schulman , Monica Vazirani , Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.68-74, July 2001, Hersonissos, Greece
Qian-Hong Wu , Bo Qin , Yu-Min Wang, Extended methodology of RS design and instances based on GIP, Journal of Computer Science and Technology, v.20 n.2, p.270-275, March 2005
Arthur Schmidt , Ulrich Vollmer, Polynomial time quantum algorithm for the computation of the unit group of a number field, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Kareem S. Aggour , Renee Guhde , Melvin K. Simmons , Michael J. Simon, Simulation and verification II: simulating quantum computing: quantum express, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
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
Daniel N. Rockmore, The FFT: An Algorithm the Whole Family Can Use, Computing in Science and Engineering, v.2 n.1, p.60-64, January 2000
Simon Perdrix, Quantum Patterns and Types for Entanglement and Separability, Electronic Notes in Theoretical Computer Science (ENTCS), 170, p.125-138, March, 2007
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
Jens-Matthias Bohli , Rainer Steinwandt , Mara Isabel Vasco , Consuelo Martnez, Weak Keys in MST1, Designs, Codes and Cryptography, v.37 n.3, p.509-524, December  2005
Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Paul Massey , John A. Clark , Susan A. Stepney, Human-Competitive Evolution of Quantum Computing Artefacts by Genetic Programming, Evolutionary Computation, v.14 n.1, p.21-40, March 2006
Paul Massey , John A. Clark , Susan Stepney, Evolution of a human-competitive quantum fourier transform algorithm using genetic programming, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
George F. Viamontes , Manoj Rajagopalan , Igor L. Markov , John P. Hayes, Gate-level simulation of quantum circuits, Proceedings of the conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
Sean Hallgren , Alexander Russell , Amnon Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.627-635, May 21-23, 2000, Portland, Oregon, United States
Juan A. Acebrn , Renato Spigler, Supercomputing applications to the numerical modeling of industrial and applied mathematics problems, The Journal of Supercomputing, v.40 n.1, p.67-80, April     2007
George F. Viamontes , Igor L. Markov , John P. Hayes, Improving Gate-Level Simulation of Quantum Circuits, Quantum Information Processing, v.2 n.5, p.347-380, October
Edith Hemaspaandra , Lane A. Hemaspaandra , Marius Zimand, Almost-everywhere superiority for Quantum polynomial time, Information and Computation, v.175 n.2, p.171-181, June 15, 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
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
Ziv Bar-Yossef , T. S. Jayram , Iordanis Kerenidis, Exponential separation of quantum and classical one-way communication complexity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
A. T. Vakhitov , O. N. Granichin , S. S. Sysoev, A randomized stochastic optimization algorithm: Its estimation accuracy, Automation and Remote Control, v.67 n.4, p.589-597, April     2006
Stephan Mertens, Computational Complexity for Physicists, Computing in Science and Engineering, v.4 n.3, p.31-47, May 2002
Vivek V. Shende , Stephen S. Bullock , Igor L. Markov, Synthesis of quantum logic circuits, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
Hea Joung Kim , William H. Mangione-Smith, Factoring large numbers with programmable hardware, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.41-48, February 10-11, 2000, Monterey, California, United States
Farid Ablayev , Aida Gainutdinova , Marek Karpinski , Cristopher Moore , Christopher Pollett, On the computational power of probabilistic and quantum branching program, Information and Computation, v.203 n.2, p.145-162, December 15, 2005
Pascal Koiran , Vincent Nesme , Natacha Portier, The quantum query complexity of the abelian hidden subgroup problem, Theoretical Computer Science, v.380 n.1-2, p.115-126, June, 2007
Katalin Friedl , Gbor Ivanyos , Miklos Santha, Efficient testing of groups, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Igor E. Shparlinski , Arne Winterhof, Quantum period reconstruction of approximate sequences, Information Processing Letters, v.103 n.6, p.211-215, September, 2007
Ran Raz, Exponential separation of quantum and classical communication complexity, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.358-367, May 01-04, 1999, Atlanta, Georgia, United States
Paul Vitnyi, Time, space, and energy in reversible computing, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
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
Eli Biham , Gilles Brassard , Dan Kenigsberg , Tal Mor, Quantum computing without entanglement, Theoretical Computer Science, v.320 n.1, p.15-33, 12 June 2004
Katalin Friedl , Gbor Ivanyos , Frdric Magniez , Miklos Santha , Pranab Sen, Hidden translation and orbit coset in quantum computing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
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
Andris Ambainis , John Watrous, Two-way finite automata with quantum and classical states, Theoretical Computer Science, v.287 n.1, p.299-311, 25 September 2002
Takashi Mihara, Splitting information securely with entanglement, Information and Computation, v.187 n.1, p.110-122, November 25,
Cristopher Moore , Daniel Rockmore , Alexander Russell , Leonard J. Schulman, The power of basis selection in fourier sampling: hidden subgroup problems in affine groups, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Nick Papanikolaou, An introduction to quantum cryptography, Crossroads, v.11 n.3, p.3-3, Spring 2005
Takashi Mihara, Quantum protocols for untrusted computations, Journal of Discrete Algorithms, v.5 n.1, p.65-72, March, 2007
Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Journal of the ACM (JACM), v.54 n.1, p.1-es, March 2007
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
Debajyoti Bera , Frederic Green , Steven Homer, Small depth quantum circuits, ACM SIGACT News, v.38 n.2, June 2007
Andris Ambainis, Quantum lower bounds by quantum arguments, Journal of Computer and System Sciences, v.64 n.4, p.750-767, June 2002
Eli Biham , Michel Boyer , P. Oscar Boykin , Tal Mor , Vwani Roychowdhury, A proof of the security of quantum key distribution (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.715-724, May 21-23, 2000, Portland, Oregon, United States
Peter Hoyer , Troy Lee , Robert Spalek, Negative weights make adversaries stronger, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Michele Mosca, Counting by quantum eigenvalue estimation, Theoretical Computer Science, v.264 n.1, p.139-153, 08/06/2001
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
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
Evgeny Dantsin , Vladik Kreinovich , Alexander Wolpert, On quantum versions of record-breaking algorithms for SAT, ACM SIGACT News, v.36 n.4, p.103-108, December 2005
Esma Ameur , Gilles Brassard , Sbastien Gambs, Quantum clustering algorithms, Proceedings of the 24th international conference on Machine learning, p.1-8, June 20-24, 2007, Corvalis, Oregon
A. Papageorgiou , H. Woniakowski, Classical and Quantum Complexity of the Sturm--Liouville Eigenvalue Problem, Quantum Information Processing, v.4 n.2, p.87-127, June      2005
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
Andris Ambainis, A new protocol and lower bounds for quantum coin flipping, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.134-142, July 2001, Hersonissos, Greece
Cristopher Moore , Daniel Rockmore , Alexander Russell, Generic quantum Fourier transforms, ACM Transactions on Algorithms (TALG), v.2 n.4, p.707-723, October 2006
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
Andrew M. Childs , Richard Cleve , Enrico Deotto , Edward Farhi , Sam Gutmann , Daniel A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Cristopher Moore , Daniel Rockmore , Alexander Russell, Generic quantum Fourier transforms, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Amr Sabry, Modeling quantum computing in Haskell, Proceedings of the ACM SIGPLAN workshop on Haskell, p.39-49, August 28-28, 2003, Uppsala, Sweden
A. Lyon , Margaret Martonosi, Tailoring quantum architectures to implementation style: a quantum computer for mobile and persistent qubits, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
Shengyu Zhang, On the power of Ambainis lower bounds, Theoretical Computer Science, v.339 n.2, p.241-256, 12 June 2005
Gbor Ivanyos , Frdric Magniez , Miklos Santha, Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.263-270, July 2001, Crete Island, Greece
Licheng Wang , Zhenfu Cao , Peng Zeng , Xiangxue Li, One-more matching conjugate problem and security of braid-based signatures, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore
Leslie G. Valiant, Quantum computers that can be simulated classically in polynomial time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.114-123, July 2001, Hersonissos, Greece
Evgeny Dantsin , Alexander Wolpert , Vladik Kreinovich, Quantum versions of k-CSP algorithms: a first step towards quantum algorithms for interval-related constraint satisfaction problems, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
John Watrous, Zero-knowledge against quantum attacks, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Alberto Bertoni , Carlo Mereghetti , Beatrice Palano, Some formal tools for analyzing quantum automata, Theoretical Computer Science, v.356 n.1, p.14-25, 5 May 2006
Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004
Harumichi Nishimura , Masanao Ozawa, Uniformity of quantum circuit families for error-free algorithms, Theoretical Computer Science, v.332 n.1-3, p.487-496, 28 February 2005
Lance Fortnow, One complexity theorist's view of quantum computing, Theoretical Computer Science, v.292 n.3, p.597-610, 31 January
Reihaneh Safavi-Naini , Shuhong Wang , Yvo Desmedt, Unconditionally secure ring authentication, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore
Alexei Kitaev , John Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.608-617, May 21-23, 2000, Portland, Oregon, United States
Andris Ambainis, Polynomial degree vs. quantum query complexity, Journal of Computer and System Sciences, v.72 n.2, p.220-238, March 2006
John Watrous, PSPACE has constant-round quantum interactive proof systems, Theoretical Computer Science, v.292 n.3, p.575-588, 31 January
Marcello Frixione, Tractable Competence, Minds and Machines, v.11 n.3, p.379-397, August 2001
Andris Ambainis, A new protocol and lower bounds for quantum coin flipping, Journal of Computer and System Sciences, v.68 n.2, p.398-416, March 2004
H. Woniakowski, The Quantum Setting with Randomized Queries for Continuous Problems, Quantum Information Processing, v.5 n.2, p.83-130, April     2006
Dmitry Gavinsky , Julia Kempe , Iordanis Kerenidis , Ran Raz , Ronald de Wolf, Exponential separations for one-way quantum communication complexity, with applications to cryptography, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
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
V. Arvind , Piyush P. Kurur, Graph isomorphism is in SPP, Information and Computation, v.204 n.5, p.835-852, May 2006
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
Nemanja Isailovic , Mark Whitney , Yatish Patel , John Kubiatowicz , Dean Copsey , Frederic T. Chong , Isaac L. Chuang , Mark Oskin, Datapath and control for quantum wires, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.1, p.34-61, March 2004
Dorit Aharonov , Vaughan Jones , Zeph Landau, A polynomial quantum algorithm for approximating the Jones polynomial, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
van Dam , Frdic Magniez , Michele Mosca , Miklos Santha, Self-testing of universal and fault-tolerant sets of quantum gates, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.688-696, May 21-23, 2000, Portland, Oregon, United States
Tien D. Kieu, Quantum Hypercomputation, Minds and Machines, v.12 n.4, p.541-561, November 2002
Hartmut Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.644-651, May 21-23, 2000, Portland, Oregon, United States
Martin Sauerhoff , Detlef Sieling, Quantum branching programs and space-bounded nonuniform quantum complexity, Theoretical Computer Science, v.334 n.1-3, p.177-225, 11 April 2005
A. Ambainis, Quantum search algorithms, ACM SIGACT News, v.35 n.2, June 2004
Tatjana Curcic , Mark E. Filipkowski , Almadena Chtchelkanova , Philip A. D'Ambrosio , Stuart A. Wolf , Michael Foster , Douglas Cochran, Quantum networks: from quantum cryptography to quantum architecture, ACM SIGCOMM Computer Communication Review, v.34 n.5, October 2004
John Watrous, Quantum algorithms for solvable groups, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.60-67, July 2001, Hersonissos, Greece
Scott Aaronson, Multilinear formulas and skepticism of quantum computing, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Yaoyun Shi, Tensor norms and the classical communication complexity of nonlocal quantum measurement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
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
Dorit Aharonov , Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Mark Oskin , Frederic T. Chong , Isaac L. Chuang , John Kubiatowicz, Building quantum wires: the long and the short of it, ACM SIGARCH Computer Architecture News, v.31 n.2, May
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
An introduction to quantum computing for non-physicists, ACM Computing Surveys (CSUR), v.32 n.3, p.300-335, Sept. 2000
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
R. Srikanth, A Computational Model for Quantum Measurement, Quantum Information Processing, v.2 n.3, p.153-199, June
Dagmar Bruss , Gbor Erdlyi , Tim Meyer , Tobias Riege , Jrg Rothe, Quantum cryptography: A survey, ACM Computing Surveys (CSUR), v.39 n.2, p.6-es, 2007
Scott Aaronson, Guest Column: NP-complete problems and physical reality, ACM SIGACT News, v.36 n.1, March 2005
Andrew Odlyzko, Discrete Logarithms: The Past and the Future, Designs, Codes and Cryptography, v.19 n.2-3, p.129-145, March 2000
David S. Johnson, The NP-completeness column, ACM Transactions on Algorithms (TALG), v.1 n.1, p.160-176, July 2005
Jrg Rothe, Some facets of complexity theory and cryptography: A five-lecture tutorial, ACM Computing Surveys (CSUR), v.34 n.4, p.504-549, December 2002
Rodney Van Meter , Mark Oskin, Architectural implications of quantum computing technologies, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.2 n.1, p.31-63, January 2006
spin systems;quantum computers;algorithmic number theory;church's thesis;fourier transforms;foundations of quantum mechanics;prime factorization;discrete logarithms