**Background**

"Where a calculator on the Eniac is equipped with 18000 vacuum tubes and weighs 30 tons, computers in the future may have only 1000 tubes and weigh only 1 1/2 tons". Eleven years after Popular Mechanics made the above prediction in 1949, a prominent Intel executive Gordon Moore observed that the number of transistors that could be put on a silicon chip doubled every 18 months. So far the Moore's famous law is holding true, however, current methods of processing information are reaching their limits because die sizes are nearing atomic levels, at which the standard physics properties begin to follow the laws of quantum physics, rendering them useless.

Many avenues in nano-technology have yet to be explored, such as stacking silicon wafers to form cubes or spheres, the use of Single Electron Transistors (SET), and using molecules themselves as switching devices. These methods will sustain Moore’s law well into this century, but eventually, they are destined to be overtaken as well. The reason is simple. All of these methods merely reproduce the actions of a classical Turing Machine.

After quantum physics was born, the fields of mathematics, physics, information science, and computer science have mingled together to tackle the concept of quantum computing. Through the strange laws that affect particles at the atomic level, it has become conceivable that someday a complete physical computation device might be built that is not limited to standard 1s and 0s.

A direct consequence of using "partial" 1s and 0s and the principals of quantum entanglement is that some algorithms currently belonging to the NP-Complete class can be re-written to be performed on a quantum computer with a polynomial time complexity. Even if such a computer were only able to perform a few clock cycles per second, (compared to the gigahertz computers of today), the quantum computer would be far superior to any conventional Turing Machine. Certain problems that would take hundreds of millions of years to compute on today’s classical Turing Machines would, (and in some cases do), take merely seconds on a quantum computer.

Currently, most research in quantum computing is classified
as one of the following sub-topics: quantum algorithm design, communication/cryptography,
quantum entanglement, or physical quantum computer implementation.

**Criteria**

The materials presented are intended for persons who possess a background and interest in physics (atomic level), chemistry, computer science (algorithm time complexity), mathematics, matrix theory, or digital gate logic.

The following scientific papers were selected based on their relationship to quantum computation. A particular work might be selected because it was the first in its area of research, its experiments produced a noteworthy advance in the field, or it embodies the entire scope of its field of study.

**REVIEWS**

**Quantum Algorithm Design**

__Isaac L. Chuang, Michael A. Nielsen - Quantum Computation
and Quantum Information
__Nielsen and Chuang provide a general overview in textbook form of the
quest for creating a quantum computer. They cover a variety of topics such
as rotation of vectors in Hilbert Space via matrix multiplication, quantum
algorithms, quantum noise/error correction, quantum cryptography, and building
quantum logic gates.

__Peter W. Shor - Polynomial-time Algorithms for Prime Factorization
and Discrete Logarithms on a Quantum Computer
__In 1994 Shor of AT&T Labs astonished the Computer Science community
with his algorithm for factoring large integers on a quantum computer in polynomial
time. The algorithm as well as the formal proof is presented. Release of this
world famous algorithm sparked a frenzy of research into quantum computation.
For the first time, there was actually something

The first group to build a quantum computer will have the power to crack all RSA encryption systems used by banks, governments, and most Internet traffic. Unfortunately, Shor’s algorithm has never been implemented since it would require a 16+ qubit register, and current implementations top out at 5 qubits. According to Shor’s estimation, by the end of the decade 30 qubits computers will exist. For his work in the field, Shor received the 1999 Godel Prize and the 1998 Nevanlinna Award.

__L. K. Grover - A Fast Quantum Mechanical Algorithm for Database
Search.
__In this Paper, Grover from Bell Laboratories described an algorithm to
search through an

While Grover’s algorithm does not provide the speedup that is obtained by Shor’s algorithm, which breaks the co-NP barrier, his algorithm is important because it may mean that there are other similar "needle in the haystack" problems that could be reduced in time complexity as well. If a problem can by mapped onto or reduced to the problem of searching an unordered database, then it would follow that it can also be solved in sqrt(n) average accesses as well. Furthermore, Non-Polynomial problems (NP) that use sub-functions similar to searching an unordered database might be able to use an approach similar to Grover’s to knock them down a notch from NP or NP-Complete to polynomial.

Grover’s work is especially significant in today’s world because it has been proved by implementation. Since the procedure only requires a 3 qubit register, current quantum computers have been able to execute it and verify its accuracy.

**Quantum Communication/Cryptography**

__C.H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J.
Smolin - Experimental Quantum Cryptography
__Charles Bennett of the IBM Thomas J Watson Research Center used non-locality
to devise "a hypothetical quantum communication system in which the receiver
reads a two-bit message from two physical bits, but only one of those bits
- the transmitted bit - has physically come from the sender of the message."
An information network system that could receive an extra bit for free would
greatly enhance the compression and speed of current bandwidth bogged networks.
By measuring the polarization of photons, the eavesdropper can easily be detected
since the act of measurement is sure to introduce errors in the transmission
unless he/she knows the type of polarization of each photon in advance.

__A.K. Ekert, J.G. Rarity, P.R. Tapster, and G.M. Palma - Cryptosystems
with Encoding Built upon Quantum Entanglement and the Bell Theorem
__Ekert contrived a practical use for the Heisenberg uncertainty and quantum
entanglement principles by establishing a strategy where an entangled pair
of particles is initially generated so that each party measures one member
of each pair. Detection of one quantum particle destroys its quantum correlation
with the other, allowing intrusion to be detected immediately by verifying
measurement results over an open channel. Thus, the insecurity imbalance created
by Shor’s algorithm is restored by the very same properties of quantum mechanics
that caused the breakdown of previous encryption systems in the first place.

__The Quantum Cryptography Experiment at Los Alamos, (web site)
- http://p23.lanl.gov/Quantum/quantum.html
__Employees at the Quantum Cryptography Experiment in Los Alamos are working
to create a quantum cryptography network for use in the near future in commercial
systems. Current experiments have reliably transferred quantum-encrypted information
48km using advanced quantum error correction techniques. An ion trapping technique,
(see physical implementation reviews), is used for the quantum register.

**Quantum Entanglement**

__A. Einstein, B. Podolsky and N. Rosen - Can the Quantum-Mechanical
Description of Physical Reality be Considered Complete?
__The Einstein, Podolsky, and Rosen trio (EPR) first pointed out the strange
properties of the Bell State. In a heated debate, they used the random-like
properties of entangled particles as evidence against certain aspects of quantum
physics. They describe the strange phenomenon that occurs from measuring one
of two entangled photons, causing the state of the other to immediately become
fixed. This holds true, even if the two photons have traveled long distances
from each other by the time of measurement!

__A. Zeilinger, D. Bouwmeester, J. W. Pan, H. Weinfurter -
Experimental Quantum Teleportation and Entanglement Swapping.
__In 1998 Anton Zeilinger and his colleagues at the University of Innsbruck
in Austria performed a remarkable demonstration of quantum teleportation over
long distances using the principles of entanglement. Here, teleporting refers
to the transfer of information about the quantum pair, and not the actual
particle itself. The group does propose, however, that there are ways of reading
a particle and reconstructing it on the other side, (inevitably destroying
the original), that would constitute a complete teleportation similar to the
science fiction teleportation portrayed in Star Trek.

**Physical Implementation**

__Isaac L. Chuang and N. A. Gershenfeld - Nuclear Magnetic
Resonance (NMR) Spectroscopy
__Chuang and his research team describe how to "distill" an effectively
pure starting state from a complex mixture involving chloroform, which creates
stable isolated qubits on which to perform calculations. The technique, called
Nuclear Magnetic Resonance (NMR), utilizes radio frequency fields to stimulate
the rotation of the Hydrogen (1H) and Carbon (13C) atoms in a large body of
chloroform, thus simulating quantum gates. Using the NMR emanating from each
atom, the spins of individual atoms can be distinguished from the molecule.
The future of computing envisioned by Chuange and Gershenfeld involves computers
that look more like chemistry experiments in a bottle than today’s computer.

__Andrew Steane - The Ion Trap Quantum Information Processor
__The Ion Trap created by Steane’s research group is a tiny 3 cm metal device
that traps ions in an isolated state. A beam of fast moving electrons is fired
through a cloud of vaporized positively charged calcium metal in a vacuum,
which essentially "traps" a portion of the ions in the device. Lasers
are used to minimize the thermal kinetic energy of the ions by firing the
laser in the opposite direction as the motion of the atom, (detected with
Doppler Shift analysis techniques). Shining a laser light pulse for a brief
period on an ion causes it to vibrate at a specific frequency and flip the
states of its neighbors in the register to the opposite state – effectively
simulating a NOT gate. Other logic gates can be built using various combinations
and durations of laser exposure.

**Conclusion**

More than any previous moment in history, the physicist is dabbling with the theories of information science, the computer scientist is scribbling physics, the information/communication scientist is dabbling in computer science, mathematicians are calculating vectors in Hilbert Space, and all four are collaborating to bring quantum computers to life. We saw the four fields merge somewhat during the discovery of the transistor, however, at the time computer science was in its infancy, information science didn’t become involved until the computer/internet, and for the most part there was never an easily noticeable convergence.

There is no doubt that all three sciences are baffled by the complications of this invisible world. A computer scientist can’t help but wonder how an algorithm could run so much faster on a qubit register. An information/communication scientist finds him/herself pondering how information can travel without a medium. The physicist must contemplate parallel universes stemming from electrons that violate all known physics laws by existing in two locations at the same time. The mathematician wonders how one bit can represent two.

In a letter from Einstein to Schrödinger in 1950, Einstein comically stated our frustration with the backward principals of the quantum world when he said, "It is quite hard to accept that we still are in the stage of babies in their diapers"

All of the above works, (with the exception of Chuang and Nielsen’s textbook), are focused towards one of the four areas of research, but each item has unavoidable ties with the other three fields. It makes sense to base reading preferences upon which field of study the reader’s background is in and which quantum-computing sub-topic seems most interesting.

**Recommendations**

For those readers interested in a general overview of quantum computation techniques to date, Chuange and Nielsen’s textbook provides a thorough background on the subject. Beginning with basic building blocks, the reader can accomplish a complete understanding of the building blocks in the quantum computational field of study.

Shor’s remarkable algorithm will heat up the blood in any computer scientist. The mathematics involved are not for the faint of heart, so give yourself plenty of time, (at least a week), if you desire to understand it thoroughly. It is imperative that the reader be at least familiar with quantum computing notation and logic before diving in.

Readers interested in the cryptographic, error correcting, and
communication networking aspects of quantum computing would find it well worth
the time to read Bennett’s *Experimental Quantum Cryptography *papers.
Bennett is probably the most active researcher in the topic to date. The communication
aspects will particularly interest the information scientist since certain
instances of quantum networking clearly are in direct violation of the "no
information without a medium" rule, thanks to entanglement theory.

The A. Einstein, B. Podolsky and N. Rosen research paper is a fundamental founding force in the entanglement theory, however, its 1935 date makes some of its contents out of date. The reader seeking history will find it fascinating, but those pursuing knowledge of the workings of entanglement will not find it extremely helpful. Since entanglement is an intrinsic property involved in almost every aspect of quantum computing, one cannot help but pick up the details by simply reading or researching one of the many areas involved in quantum computation.

The enthusiastic physicist will find both the NMR research by Chuang & colleagues and the ion trapping research by Steane to be of great value. A non-physicist is likely to find both works heavy on the technical side.

**REFERENCE LIST**

Bennett, Charles H. Bessette, F. Brassard, G. Salvail, L. and
Smolin, J. . *Experimental Quantum Cryptography*. Journal of Cryptology
5, 3, 1992.

Chuang, Isaac. L. and Gershenfeld N. A. . *Nuclear Magnetic
Resonance (NMR) spectroscopy* Science 275, 350, 1997

Chuang, Isaac L. and Nielsen, Michael A. . *Quantum Computation
and Quantum Information*. Cambridge: University Press, 2000.

Einstein, A. Podolsky, B. and Rosen, N. *Can the Quantum-Mechanical
Description of Physical Reality be Considered Complete?* . Phys. Rev. 47
1935 pp. 777.

Ekert, A.K. Rarity, J.G. Tapster, P.R. and Palma, G.M. . *Cryptosystems
with Encoding Built upon Quantum Entanglement and the Bell Theorem*. Phys.
Rev. Lett. 69, 1293, 1992.

Grover, L. K . *A Fast Quantum Mechanical Algorithm for Database
Search. *Proceedings of the 28th Annual ACM Symposium on the Theory of
Computing, Philadelphia, 1996. pp. 212-219.

Przibram, K. . *Letter Einstein to Schrödinger* .
Letter 22.12.1950, from "Briefe zur Wellenmechanik" ("Letters on Wave Mechanics"),
Springer-Verlag: Vienna 1963 pp. 36-37

Shor, Peter W. . *Polynomial-time Algorithms for Prime Factorization
and Discrete Logarithms on a Quantum Computer*. Proceedings of the 35th
Annual Symposium on the Foundations of Computer Science. Los Alamitos, CA:
IEEE Computer Society, 1994.

Steane, Andrew. *The Ion Trap Quantum Information Processor*.
Clarendon Laboratory, Oxford University: Rept.Prog.Phys. : 61, 1998

*The Quantum Cryptography Experiment at Los Alamos*, (web
site), http://p23.lanl.gov/Quantum/quantum.html

Zeilinger, A. Bouwmeester, D. Pan, J.-W. Weinfurter, H. . *Experimental
Quantum Teleportation and Entanglement Swapping*. Technical Digest, Glasgow,
1998 pp. 98.