(by Geza Giedke, 12/2000)

Quantum Information

It was observed already in the 1960s by Rolf Landauer, that information is physical, i.e. information cannot be separated from its physical representation: it is always stored in some physical system, manipulated by some physical process. This observation has a number of consequences for information theory. Perhaps, the most striking one is, that it makes a big difference whether the information is stored and processed in classical or quantum mechanical systems.

Until now this has always been done using systems governed by classical physics, e.g., one bit of information in a system that could take either of two states, for example a piece of magnetic tape being magnetized "up" or "down" representing the numbers "0" and "1", respectively.

But in the 1980s it was observed by P. Benioff, C. Bennet, G. Brassard, R. Feynman, and others, that quantum mechanics might provide new and possibly very powerful ways of information processing. Moreover, at the current pace, the ongoing miniaturization in chip design will in the next decade lead to chip components so small that quantum mechanics becomes important.

In a quantum computer information would be stored in quantum-mechanical two-state systems, so called qubits. The most peculiar feature of a qubit (and all quantum systems) is the existence of superpositions: according to the (experimentally well established) superposition principle, a qubit, which can be in two distinct physical states (say "0" and "1") can also be in an arbitrary coherent superposition of these states, representing in a certain sense both numbers at the same time. Similarly, two qubits can be in a superposition of the four states 00, 01, 10, and 11, and n qubits can be in a superposition of 2n numbers. With suitable algorithms a quantum computer can make use of this: it can process all those numbers at the same time. This exponential (n qubits provide for 2n numbers) quantum parallelism is the basis for the quantum speed-up in Shor's or Grover's algorithms. Moreover, the superposition principle is the basis for the quantum phenomenon of entanglement which is of particular importance for quantum communication. The study of entanglement has turned into a very fruitful field of research, revealing many strange features of quantum mechanics. Various types of entanglement have been discovered. We are still only beginning to understand their classification, quantification, and application.

The other fundamental principle of quantum mechanics is Heisenberg's uncertainty principle, which states that the observation of a quantum system unavoidably disturbs this system. This effect can be used to guarantee secret key distribution in quantum cryptography.

On the downside, these principles severely restrict the access to information in a quantum computer. In particular they prevent two things that are taken for granted in classical computers: it is neither possible to determine the state of an unknown quantum system exactly nor to make a perfect copy of it. From these properties arise the particular challenges of quantum computation.

A good and brief overview of the Basic Concepts in Quantum Information Theory is given by R. Werner. Further information on quantum mechanics can be found online, e.g. in Some basic explanations about Quantum Mechanics or this Scientific American article (Feb. 2001) or this New Scientist's Guide to the Quantum World*; for more detailed information on this subject refer to any textbook of quantum mechanics, e.g. A. Peres, Quantum Theory: Concepts and Methods, Kluwer Academic.

Quantum Computing

A central issue of quantum computing is to devise algorithms that take advantage of quantum mechanical properties to process information faster than even the best classical computers can. In order to determine which one of two algorithms (acting on an input x) is "faster" one compares the number of computational steps needed to solve the problem as a function of the size of the input, i.e. the number s( x) of bits needed to specify x. The algorithm for which the number of computational steps grows more slowly is the faster one. In fact, it is usually only the functional form of this growth for large values of s(x) (its "asymptotic behaviour") that matters: is it polynomially (like s(x)k) or exponentially (like es(x))? Exponential problems are considered intractable, since even a modest increase in the size of the input leads to an enormous increase in the computational time needed to find the answer, which cannot be compensated by improved hardware.

The holy grail of quantum computing is the exponential speed-up, i.e. a quantum algorithm that solves a problem in polynomial time which needs exponential time with classical computers. Closest to this goal to date is Shor's Algorithm: it would allow a quantum computer to find the prime factors of a large number in polynomial time. For classical computers no such algorithm is known: finding the factors of, e.g., a thousand-digit number would take much longer than the age of the universe using today's classical computers, while a quantum computer might find them within seconds. Why would anyone like to find the factors of large numbers? They are of great practical relevance, since many of the most commonly used cryptographic algorithms (RSA, PGP, etc.) are based on the virtual impossibility of finding those factors. Thus the availability of a quantum computer would invalidate current security schemes (see this article on quantum cryptanalysis by A. Ekert). But if you fear for your privacy now: there is quantum cryptography to help you out.

It is, however, not proven that one cannot find a classical polynomial algorithm for factoring, and thus the question whether quantum mechanics does indeed provide an exponential speed-up is still open. Nevertheless, Shor's Algorithm, invented in 1994, for the first time demonstrated the power of quantum computers in a problem of practical interest.

The second major quantum algorithm is Grover's Algorithm, which was invented in 1997. It finds a marked item in an unsorted database containing N entries with about square root of N queries to the database. On a classical computer the best algorithm needs on the order of N queries. This is an example where quantum computing definitely provides a speed-up (though not an exponential one).

For a long time, many scientists believed that large-scale experimental quantum computing would be impossible because of the fragile nature of quantum information. This concern has been largely resolved by the development of quantum error correction and fault-tolerant quantum computation, about which more will be said below.

A collection of introductory articles to the field of quantum information by various authors is provided by the Centre for Quantum Computation in Oxford, UK. Sam Braunstein provides a nice online tutorial on quantum computation, too. The enthusiastic first chapter of J. Brown's popular science book on The Quest for the Quantum Computer* is also available.

Quantum Communication

This subfield of quantum information processing is concerned with the exchange of information between distant parties. Several applications of quantum mechanics to communication problems have been proposed, ranging from more efficient ways of sending classical information (dense coding) over algorithms that reduce the complexity of communication problems to novel ways to achieve secret communication. Here is a brief introduction to quantum communication, and here's an entertaining account on How to use quantum mechanics to win in a game show (Physics Today, February 2000, 35-39) *.

An important tool for many quantum communication tasks is quantum teleportation [5]. By this process, the quantum information (i.e. the state of a quantum system) can be sent to a distant location without ever transporting the actual system. The crucial resource needed for teleportation is a pair of quantum mechanically correlated (entangled) quantum systems shared by the communicating parties. When this is available, local quantum operations and classical communication are sufficient to send quantum information. For more details see this brief description of quantum teleportation* (by the inventors) or this slightly longer article*. If you have no clue what "teleportation" is about, this short fun talk* is worth a look. Quantum teleportation has been experimentally realized in Innsbruck (Austria), in Rome, and at Caltech [5]

How to Build a Quantum Computer

Till now no full-fledged quantum computer has been built and most researchers in the field agree that such a device lies still many years or decades in the future.

Recently much progress has been made in identifying systems that appear to be promising for the implementation of a quantum computer. A quite general set of conditions that such a system has to fulfill has been identified:

1.It has to consist of a collection of well-defined distinct qubits.
2.The qubits must on the one hand be very well isolated from their surroundings as to protect the fragile superpositions.
3.On the other hand, the experimentalist (or, eventually, the user) needs to have complete control of them, i.e. he must be able to interact strongly with them, to bring them into any desired state and to perform any quantum operation on them. It has been shown that there is a small universal set of operations involving at most two qubits at the same time that suffices to construct arbitrary operations by concatenation.
4.In particular, it must be possible to initialize the quantum computer, e.g. to bring all qubits into the state "0".
5.Lastly, the system should be scalable, i.e., it must be possible to increase the number of qubits without sacrificing isolation or control.

See The Physical Implementation of Quantum Computation by D.P. DiVincenzo or [4] for a detailed discussion.

Experimentally the most daunting requirements are 2. and 3. In practice it is not possible to isolate the qubits completely. Thus there will always be unwanted interactions with the environment, leading to errors in the quantum register. If the time within which these errors become appreciable (decoherence time) is much longer than the time needed to perform a typical computational step in the quantum computer (gate operation time), it would at least be possible despite these errors to perform fairly accurate quantum calculations that are not longer than the decoherence time. Longer calculations, however, could not be done, and for some time it was therefore thought, that even the smallest sort of error would cancel the asymptotic advantage of the quantum computer, since the errors would accumulate during a long computation. But later it was shown that quantum error correction is possible, i.e. that quantum information can be encoded in such a way, that potential errors can be detected and corrected. Moreover it was proven that if the errors occurring per computational step are small enough, then suitable quantum error correcting codes can keep the error at that level throughout a computation of arbitrary length. Thanks to this result there is indeed hope that realistic (i.e. imperfect) quantum computers could be useful.

By now a large number of systems have been proposed to implement a quantum computers: ions or atoms in electromagnetic or optical traps, photons in cavities, nuclear spins on molecules, quantum dots, superconductors. A comprehensive overview is provided in the special issue "Experimental proposals for quantum computation", Fortschr. Phys. 48 (2000), S. L. Braunstein and H.-K. Lo (special issue editors), P. Kok (assist. ed.), also available as a book "Scalable quantum computers: paving the way to realization".

First steps on the road towards a quantum computer have also been taken experimentally, demonstrating complete coherent control over few qubits represented by trapped ions.

On the side of quantum communication the system of choice is light for its speed and the relative ease with which it can be transmitted. One approach uses single photons as the carrier of one qubit of quantum information, recently more intense light fields comprising many photons (continuous variable quantum communication) have been considered, which have the capacity to hold much more quantum information than a single photon (see Quantum Information Theory with Continuous Variables, S. L. Braunstein and A. K. Pati (eds.), Kluwer Academic, to appear).

Quantum Networks

The full power of quantum information processing is attained when quantum computing devices and quantum communication lines are connected to form a quantum network. Therefore it is important to have a good interface between quantum computers and quantum channels.

Until now, most work in this area considers the nodes of the network to be realized by quantum computers based on trapped ions (or atoms) that were first proposed in 1995. One reason why these systems have been favored in this context is that they interact in a well-understood and controllable fashion with photons, which are the best carriers of quantum information. To design a quantum interface it is required to find a physical process that maps the internal quantum state of, e.g., an ion onto the state of the light field and vice versa.

The interaction between ions and single photons is quite weak; therefore it has to be enhanced by placing the trapped ions inside an optical resonator (i.e. between two very good, suitably arranged mirrors). This leads to a strong coupling between the light field in the resonator and the ions. Shining appropriate laser pulses on the ion in question, its state can then be mapped to the state of the resonator field (see, e.g. [6]. Similarly the state of the resonator field can be mapped on the state of an ion. To complete the interface, the resonator field must be coupled to a traveling light field, e.g. in an optical fiber. For the output, one can just wait for the photons in the resonator to leak out into the transmission line. For the input, more care is needed to circumvent the reflection of most incoming photons at the mirrors, but carefully designed laser pulses may "open up" the resonator to incoming photons. These proposals are quite close to what can currently be done in the lab, and their realization should be achieved in the coming years.

Quantum Cryptography

Even in classical cryptography there exists an unbreakable code, the Vernam code or one-time pad. The drawback of this code is, that the communicating parties need to share a secret sequence of random numbers of the same length as the text to be encoded and can use it only once. So the problem of secrecy is just deferred from the message to the key, leading to the key distribution problem. Since often there is no practical way to distribute such large secret keys, most of today's cryptographic protocols rely on public key distribution and the assumed difficulty of certain computational problems instead.

It was G. Brassard, C. Bennett, and colleagues [7] who first suggested how to use quantum mechanics to achieve provably secure key distribution in their seminal paper (known as “BB84”). They demonstrated how two communicating parties may agree on a random key by exchanging and manipulating quantum systems in such a way that the laws of physics guarantee that an eavesdropper will either reveal themselves with near certainty or gain nearly no information about the key. The probability that an eavesdropper is not detected and nevertheless gains a substantial amount of information can be made as small as desired.

C. Bennet, G. Brassard, and colleagues also demonstrated privacy amplification, a means of improving the secrecy of the shared information. In privacy amplification, two communicating parties use a public discussion to cull secret information from the originally exchanged information from which an eavesdropper has gathered partial contents, thus ensuring that only they have copies of the secret information. Privacy amplification is a means by which cryptographic keys that are exchanged using QKD are made more secure.

Given secure key distribution, one then can use the (provably secure) Vernam cipher. This has the great advantage that it removes the risk (inherent in schemes that rely on the conjectured difficulty of some computational problem) of retroactive security loss due to unanticipated advances in hardware and algorithms, thus guaranteeing long-time security of the coded data.

Ultimately, the security of quantum key distribution arises from Heisenberg's uncertainty relation: anybody listening in on the channel, via which the key is distributed, will necessarily leave traces - and the more information he obtains, the more detectable disturbances will be caused. Consequently, Alice and Bob can use part of their key (sequence of zeros and ones) to measure how much an eavesdropper could possibly know about the key and only use it, when this knowledge is sufficiently small for their purposes. The actual mathematical proof of the security of quantum key distribution is a very hard problem, which has only recently been solved (see references in the survey articles.[7]

Quantum key distribution is the most advanced application of quantum information theory. There have been many successful experiments in realistic circumstances. In all these experiments the two-state quantum systems exchanged by the communicating parties are realized by photons, the qubit being for example encoded in the polarization of the photon. Most experiments to date use optical fibers to transmit the photons. Currently, distances over tens of kilometers have been achieved at many places, for example, at Los Alamos (USA), BT Labs (UK), the University of Geneva (CH), and the University of Vienna. Another approach sends the photons through the air (see e.g. the Los Alamos Free-Space experiment, the ultimate goal being secure ground-to-satellite communication.

Today's implementations of quantum cryptography still have some technical problems, mostly related to imperfections of the photon sources. The impact of imperfect sources and noisy channels on security has been extensively studied, in particular by N. Lütkenhaus (MagiQ Tech.). Nevertheless, quantum cryptography is feasible with current technology, though at still rather low data rates (a few hundred bits per second).

Not all hopes in quantum information have come to fruition. For example, quantum cryptography had long been claimed to provide unconditional security for the Age Problem, in which two ladies would like to find out who is younger without revealing their ages to each other. Any conventional (classical) solution would require either a trusted third party (or channel) or computational assumptions. The hope that with quantum mechanics they might fare better was dashed, when some basic cryptographic protocol including the so-called (non-relativistic) bit commitment were shown to be necessarily insecure.[8]

A comprehensive up-to-date bibliography of quantum cryptography is maintained by G. Brassard. An additional survey of quantum cryptography can be found at Gottesman and Lo, Physics Today, November 2000*. Briefer accounts are provided by the Los Alamos group* and by the Oxford Centre of Quantum Computation, and a popular science article* by the New Scientist (1999).

The still young field of quantum information has already achieved a multitude of exciting and surprising insights - both in the foundations of quantum mechanics and its applications to problems of communication and computation. With many dedicated groups now working in this area, more surprises and breakthroughs are to be expected. A new journal, "Quantum Information and Computation", dedicated to quantum information processing has been formed to report on these developments.

Some References

Geza Giedke is a postdoc in the Quantum Photonics Group (Prof. A. Imamoglu) at the Institute for Quantum Electronics , ETH Zürich, Switzerland.