Please continue to follow the general
advice on reading assignments from the
first week's assignment. Note: This section's lecture slides
should be available on reserve.
Reading assignment:
For these two weeks we will be covering Quantum Computing, meaning computation
that leverages the effects of large-scale coherent quantum superposititions,
entanglement, and interference - "Many Universes" computing, as David
Deutsch might call it.
Introduction to quantum computing (Lec. 24) slides
in .pdf another version
Introductory Articles for General Readers:
If you find that you can't make heads or tails of any of the more technical
articles in the list, then read some of this fluff instead. But,
please do try to read some more technical articles, if you possibly can.
-
Seth Lloyd, "Quantum-Mechanical Computers," Scientific American,
October 1995, pp. 140-145. Will be on reserve.
-
Charles Bennett et al., "Quantum Cryptography," Scientific American,
October 1992, pp. 50-57. Will be on reserve.
-
Neil Gershenfeld & Isaac Chuang, "Quantum Computing with Molecules,"
Scientific
American, June 1998, pp. 66-71. Will be on reserve.
-
Andrew Steane & Eleanor Rieffel, "Beyond Bits: The Future of Quantum
Information Processing," IEEE Computer, January 2000, pp. 38-45.
Will be on reserve.
"Introductory" Technical Reviews/Tutorials:
My own rather abbreviated summary of the field:
-
Chapter 4, "Quantum computation," pp. 91-105 of Michael Frank, "Reversibility
for Efficient Computing," green course manuscript available in UF bookstore
or at http://www.cise.ufl.edu/~mpf/manuscript/.
After looking through these Williams-Clearwater books, I feel they are
a little bit lacking in terms of technical thoroughness and clarity of
explication. However, they do gather a lot of moderately technical
information in one place. The Mathematica programs look fun to play
with, but I haven't been able to try them yet.
-
Colin Williams and Scott Clearwater, Explorations in Quantum Computing,
Springer-Verlag, 1998. Recommended book, available in UF bookstore.
Includes CD-ROM.
-
Colin Williams and Scott Clearwater, Ultimate Zero and One: Computing
at the Quantum Frontier, Springer-Verlag, 2000. Will be on physical
reserve at Marston science library.
Some pretty good technical overview articles.
-
Richard J. Hughes, "Quantum Computation," chapter 14 (pp. 191-221) of Anthony
Hey, ed., Feynman and Computation, Perseus, 1999. (Recommended
book, available in UF bookstore.)
-
Samuel Braunstein, "Quantum computation: A tutorial," http://www.sees.bangor.ac.uk/~schmuel/home.html.
-
Artur Ekert & Chiara Macchiavello, "An Overview of Quantum Computing,"
in Calude et al. (eds.), Unconventional Models of Computation,
Springer, 1998. Will be on reserve.
-
Eleanor Rieffel and Wolfgang Polak, "An Introduction to Quantum Computing
for Non-Physicists," ACM Computing Surveys, http://arxiv.org/abs/quant-ph/9809016.
Historic articles, if you're interested:
First theoretical construction of a computer based solely on quantum
mechanical principles. This one only had the power of a classical
computer, however.
-
Paul Benioff, "The Computer as a Physical System: A Microscopic Quantum
Mechanical Hamiltonian Model of Computers as Represented by Turing Machines,"
Journal
of Statistical Physics, 22(5):563-591, 1980.
Points out that classical computers seem unable to efficiently simulate
physics. First suggestion that a quantum-based computer might be
exponentially faster.
-
Richard Feynman, "Simulating physics with computers," International
Journal of Theoretical Physics, 21(6&7):467-488, 1982.
Reprinted as chapter 11 (pp. 133-153) of Feynman and Computation,
one of our recommended books in the UF bookstore.
Feynman's quantum computer construction, similar to but independent of
Benioff's.
-
Richard Feynman, "Quantum Mechanical Computers," Foundations of Physics
16(6):507-531,
1986. Reprinted as chapter 6 (pp. 185-211) of Feynman Lectures
on Computation, one of our recommended books in the UF bookstore.
First demonstration of a theoretical computational advantage from a quantum
computer. (But only a small advantage on a contrived problem.)
Quantum Logic Gates & Circuits (Lec. 25): Lec25-qcgates.pdf
-
David Deutsch, "Quantum computational networks," Proceedings of the
Royal Society of London A 425:73-90, 1989. Will be on
reserve.
-
Adriano Barenco et al., "Elementary gates for quantum computation,"
Physical
Review A 52:3457-3467, 1995. http://arxiv.org/abs/quant-ph/9503016
Shor's Quantum Factoring Algorithm (Lec. 26): Lec26-shoralg.pdf
The original paper that turned quantum computing into an academic mega-industry:
-
Peter Shor, "Algorithms for Quantum Computation: Discrete Log and Factoring,"
Proceedings
35th Annual Symposium on Foundations of Computer Science, 1994, pp.
124-134. http://arxiv.org/abs/quant-ph/9508027.
A nice re-explication of it.
-
Artur Ekert & Richard Jozsa, "Notes on Shor's Efficient Algorithm for
Factoring on a Quantum Computer," NIST Workshop on Quantum Computing and
Communication, August 1994. http://www.cise.ufl.edu/~mpf/Ekert-Jozsa.ps.
Quantum Unstructured Search & Physics Simulations (Lec. 27):
Lec27-qcapps.pdf
Unstructured search:
Physics simulations:
Decoherence, Error Correction & Quantum Cryptography (Lec. 28):
Lec28-qcmisc.pdf
-
A. R. Calderbank & Peter W. Shor, "Good quantum error-correcting codes
exist," Dec. 1995, http://arxiv.org/abs/quant-ph/9512032.
-
See Bennett's crypto article in the Intro section at the top of this page.
Physical Implementations:
This is a very nice overview of the requirements for physical implementations:
Lloyd's early paper which foresaw the common features of many schemes:
Examples of some early, concrete but difficult-to-scale schemes:
-
J. I. Cirac and P. Zoller, "Quantum Computations with Cold Trapped Ions,"
Physical
Review Letters 74(20):4091-4094, May 1995. Reserve.
-
Q. A. Turchette et al., "Measurement of conditional phase shifts
for quantum logic," Phys. Rev. Lett. 75:4710-4713, 1995.
http://arxiv.org/abs/quant-ph/9511008.
Liquid-state NMR quantum computing:
-
David Cory et al., "Ensemble Quantum Computing by Nuclear Magnetic
Resonance Spectroscopy," Proc. Nat. Acad. Sci. 94(5):1634,
1997. Reserve.
A promising idea for quantum computing in microlithographed superconducting
circuits.
-
J. E. Mooij et al., "Josephson Persistent-Current Qubit," Science
285:1036-1039,
13 August 1999. Will be on reserve.
Quantum computing using spins in doped semiconductors:
Some Relevant Web Sites:
Other Recommended Readings:
-
Julian Brown, Minds, Machines, and the Multiverse: The Quest for the
Quantum Computer, Simon & Schuster, 2000. Not a whole lot
of technical depth, but it's the most complete layperson's survey of the
field that I've seen so far.
Written assignment #7: (due Mon. 3/27)
This is our standing written assignment. It should be on the subject
of the above lectures and reading material.