Quantum Computing

Research Review

 

December 15, 2000

 

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 useful that quantum computers could do.

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 unordered database and find a specified value with an average of sqrt(n) accesses instead of today’s best method which requires n/2 average accesses.

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.