Quantum Computing or: "Quantum Chat Room"
Introduction - Quantum Computers and Quantum Information Science
Piet Brouwer, Free University of Berlin, Germany
Quantum mechanics, which was developed in the first half of the 20th century, is the fundamental microscopic theory underlying all physical phenomena. While quantum mechanics is essential for a description of the microscopic scale, Newtonian or "classical" mechanics still provides an excellent description of the macroscopic world.
One of the profound differences between quantum mechanics and classical mechanics is that in classical mechanics the state of a system can be known (measured) with arbitrary precision, whereas the quantum mechanical description harbors innate uncertainties, which can not be resolved by any measurement. Also, quantum mechanics allows the principle of "superposition", known from the theory of waves, which is foreign to classical mechanics.
Since the macroscopic world in which we live is governed by classical mechanics, classical mechanics has shaped the way we think about information and information processing. Indeed, in spite of the fact that computers are governed by quantum mechanics - after all, quantum mechanics governs all phenomena -, our thinking of the information stored in the computer is still guided by classical mechanics. Thus, the fundamental unit of information is a "bit", which at all times can take the values "0" or "1" only. It is essential for the proper processing of information that the information content of the bits is known at all times.
A "quantum computer" is a computer in which the processing of information itself makes essential use of the laws of quantum mechanics. In a quantum computer, information is stored in "quantum bits" or "qubits". In such qubits, information is not stored as "0" or "1", but as a full quantum mechanical state, including its fundamental uncertainties and the possibility of superposition. Operations on these bits are such that they preserve any uncertainties and superpositions. Hence, a quantum computer is not simply a different physical device. It is also a device that calls for a radically new way of information processing, called "quantum information science".
The (so far purely theoretical) discipline of quantum information science has shown that there are important information processing tasks for which a hypothetical quantum computer outperforms a "classical computer". An example of such a task is the factoring of the product of two large prime numbers. The so-called RSA encryption method (called after its inventors, Rivest, Shamir, and Adleman) makes essential use of the fact that this task is extremely time-consuming for a standard computer. In 1994, Shor showed that the factoring of the product of two large prime numbers is a solvable problem if information can be processed in the quantum mechanical way. Hence, if a quantum computer would ever be built, it would break the RSA encryption.
This introduction describes the basics of quantum information science and discusses a few key ideas why it is that quantum computers can outperform their classical counterparts for certain tasks.
A broadly accessible introduction to quantum information science is the recent book “Quantum Computer Science, An Introduction” by N. David Mermin, (Cambridge University Press, 2007).
Many universities have institutes devoted exclusively to quantum information science. An example is the Perimeter Institute in Waterloo, Ontario, Canada. Its quantum-information website:
perimeterinstitute.ca/Outreach/What_We_Research/Quantum_Information/, contains a lot of interesting information as well as links to other quantum information resources at all levels.