soon encountered in such simulations
was that quantum systems appeared to
be harder to simulate than their classical counterparts. But, of course, somehow nature, which obeys quantum
theory, is already carrying out “the simulation” involved in quantum physics.
So, if nature is carrying out the simulation, then should we be able to design
a computer that also can perform this
simulation? This was in fact the seed of
the idea that led to the original notion of
quantum computing by Feynman. 11
To put this in perspective, consider
the problem of simulating classical
physics. The miracle of reproducing
classical physics on a classical computer is that you can use many ‘
particles’ with small state spaces (bits) to
mimic a few particles that have very
large state spaces. For this to be possible it is required that the number of
bit configurations, 2(number of bits), is at
least as big as the number of possible
states of the physical system (which
is the size of the particle’s state space
exponentiated with the number of
particles). As a result, we can simulate
the solar system on a laptop.
Quantum computing does the same
thing for quantum mechanical systems;
now 2(number of qubits) is the dimension of
the state space and it allows us to simulate other quantum physical systems
that consists of few particles with exponentially large state spaces. Here however, it appears essential that we rely
on quantum computing components
in order to simulate the truly quantum
mechanical components of a physical
system. A crucial question therefore is:
which physical systems are interesting
to simulate in such a manner?
While the complete answer to this
question is not known, a deeper look
at quantum algorithms for simulating
quantum physics is now being under-taken in several places. As an example, a
group of physical chemists have recently
compared how useful quantum computers would be for computing the energy
level structure of molecular systems. 5
This is a classical problem of physical
chemistry, and our inability to perform
these calculations robustly for large
molecules is a bottleneck in a variety
of chemical and biological applications. Could quantum computers help
for solving this problem and outperforming the best classical algorithms?
One of the exciting findings in studying
this problem was that a small quantum
computer, consisting of only a few hundred qubits, could already outperform
the best classical algorithms for this
problem. This small number makes it
likely that among the first applications
of a quantum computer will not be factoring numbers, but instead will be in
simulating quantum physics. Indeed,
we believe that a quantum computer will
be able to efficiently simulate my possible physical system and that it therefore
has the potential to have a huge impact
on everything from drug discovery to the
rapid development of new materials.
The discovery that quantum computers could efficiently factor is, even
today, difficult to really appreciate.
There are many ways to get out of the
conundrum posed by this discovery,
but all of these will require a fundamental rewriting of our understanding
of either physics or computer science.
One possibility is that quantum computers cannot be built because quantum theory does not really hold as a
universal theory. Although disappointing for quantum computer scientists,
such a conclusion would be a major
discovery about one of the best tested
physical theories—quantum theory.
Perhaps there is a classical algorithm
for efficiently factoring integers. This
would be a major computer science
discovery and would blow apart our
modern public key cryptography. Or
perhaps, just perhaps, quantum computers really are the true model of
computing in our universe, and the
rules of what is efficiently computable
have changed. These are the dreams
of quantum computer scientists looking for quantum algorithms on the
quantum machines they have yet to be
1. aharonov, D., ben-or, M. Fault-tolerant quantum
computation with constant error rate. in
Proceedings of the Twenty-Ninth Annual ACM
Symposium on Theory of Computing (1997). acM,
2. aharonov, y., Davidovich, L., zagury, N. Quantum
random walks. Phys. Rev. A 48, 167 (1993).
3. ambainis, a. Quantum walk algorithm for
element distinctness. SIAM J. Comput. 37
4. ambainis, a., kempe, J., rivosh, a. coins make
quantum walks faster. in Proceedings of the
16th Annual ACM SIAM Symposium on Discrete
Algorithms (2005), 1099.
5. aspuru-guzik, a., Dutoi, a., Love, P.J., head-gordon,
M. Simulated quantum computation of molecular
energies. Science 309, 5741 (2005).
6. bell, J.S. on the Einstein Podolsky rosen paradox.
Physics 1, (1964), 195.
7. buhrman, h. Špalek, r. Quantum verification of matrix
products. in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (2006), 880.
8. childs, a. M., cleve, r., Deotto, E., Farhi, E., gutmann,
S., Spielman, D.a. Exponential algorithmic speedup
by quantum walk. in Proceedings of the 35th ACM
Symposium on Theory of Computing (2003), 59–68.
9. Farhi, E., gutmann, S. Quantum computation and
decision trees. Phys. Rev. A 58 (1998), 915.
10. Farhi, E., goldstone, J., gutmann, S. a quantum
algorithm for the hamiltonian NaND tree. Eprint
11. Feynman, r. Simulating physics with computers. Intl.
J. Theor. Phys. 21 (1982), 467–488.
12. grover, L. a fast quantum mechanical algorithm for
database search. in Proceedings of the 28th Annual
ACM Symposium on the Theory of Computation
(New york, 1996). acM, 212–219.
13. häffner, h., hänsel, W., roos, c.F., benhelm, J., al kar,
D.c., chwalla, M., körber, t., rapol, U.D., riebe, M.,
Schmidt, P.o., becher, c., gühne, o., Dür, W., blatt,
r. Scalable multiparticle entanglement of trapped
ions. Nature 438 (2005), 643.
14. hallgren, S. Polynomial-time quantum algorithms
for pell’s equation and the principal ideal problem.
in Proceedings of the 34th Annual ACM Symposium
on the Theory of Computation (New york, 2002).
15. kedlaya, k.S. Quantum computation of zeta functions
of curves. Comput. Complex. 15, 1–19 (2006).
16. kitaev, a. Quantum error correction with imperfect
gates. in Quantum Communication, Computing and
Measurement (New york, 1997). Plenum, 181–188.
17. knill, E., Laflamme, r., zurek, W.h. resilent quantum
computation. Science 279 (1998), 342–345.
18. knill, E., Laflamme, r., zurek, W.h. resilient quantum
computation: error models and thresholds. Proc. Roy.
Soc. Lond. Ser. A 454 (1998), 365–384.
19. Leibfried, D., knill, E., Seidelin, S., britton, J.,
blakestad, r.b., chiaverini, J., hume, D.b., itano,
W.M., Jost, J.D., Langer, c., ozeri, r., reichle,
r., Wineland, D.J. creation of a six-atom
‘Schrödinger cat’ state. Nature 438 (2005), 639.
20. Magniez, F., Santha, M., Szegedy, M. Quantum
algorithms for the triangle problem. in Proceedings
of the 16th Annual ACM SIAM Symposium on
Discrete Algorithms (2005), 1109.
21. Nielsen, M.a. chuang, i.L. Quantum Computation
and Quantum Information. cambridge University
Press, New york, 2000.
22. regev, o. Quantum computation and lattice
problems. in 43rd Symposium on Foundations of
Computer Science (iEEE computer Society, 2002),
23. rivest, r.L., Shamir, a., adleman, L. a method
of obtaining digital signatures and public-key
cryptosystems. Commun. ACM 21 (1978), 120–126.
24. Shor, P. W. algorithms for quantum computation:
Discrete log and factoring. in Proceedings of the
35th Annual Symposium on the Foundations of
Computer Science. S. goldwasser, ed. (Los alamitos,
ca, 1994). iEEE computer Society, 124–134.
25. Shor, P. W. Fault tolerant quantum computation.
in Proceedings of the 37th Symposium on the
Foundations of Computer Science (Los alamitos, ca,
1996), iEEE, 56–65.
26. Woehr, J. online interview “a conversation with
christos Papadimitriou”. Dr. Dobb’s J. July Dave
bacon is an assistant research professor in the
Department of computer Science and Engineering,
Department of Physics, at the University of
Dave Bacon ( firstname.lastname@example.org) is an assistant
research professor in the Department of computer Science
& Engineering, Department of Physics, University of
Washington, Seattle, Wa.
Wim van Dam ( email@example.com) is an associate
professor in the Department of computer Science,
Department of Physics, University of california, Santa
barbara, Santa barbara, ca.