Quantum Computing Pioneers in Amsterdam

Quantum computing has become a hot topic in the past five years. Worldwide interest rapidly increased, for example from IBM, Caltech, Lucent, AT&T, and NSA, since existing techniques will soon reach their limits, and several computations could be done much faster on a quantum computer. The Fourth Workshop on Quantum Information Processing was organized by CWI 9-12 January 2001 in Amsterdam.

Remember that a cat is said to have nine lives? A Quantum Cat does even better: it can be dead and alive at the same time. This wizardry is at the heart of quantum computing, a novel way of computing based on certain characteristics of quantum mechanics. It emerged in the 1980s as a theoretical alternative to traditional computing, which will be faced with its physical limitations soon. The possibilities are very promising, but the field is still in its infancy, and realization of a working quantum computer is still an enormous challenge.

Quantum mechanics offers a novel way of computing, enabling computations out of reach for traditional computers, even if these could be miniaturized to the same level. A crucial notion is ‘superposition’. Quantum mechanics describes matter as a superposition of all of its possible states, each with a certain amplitude – a complex number whose modulus squared is interpreted as a probability. These amplitudes thus have addition properties different from ordinary probabilities – a feature that becomes apparent in ‘interference’. Precisely this feature together with the superposition principle gives quantum computing its power. The evolution of a system is described by a unitary operation on the superposition which preserves the probability interpretation of the amplitudes. In traditional computing the smallest unit is a ‘bit’ which can only take the values 0 or 1. Quantum computing is based on ‘qubits’ which consist of a superposition of the two classical states 0 and 1 each with its own amplitude. Several physical realizations of qubits have been proposed, for example an atom in the ground state (0) or excited state (1). A computation starts with a number of qubits in a well-determined state, on which a series of unitary operations is performed (the algorithm). Because of interference certain superpositions are intensified, whereas others cancel each other out. After a number of steps the final state (the result) is observed. During the intermediate evolution all possible computational paths are followed simultaneously (quantum parallelism), but they remain hidden in a box. In certain cases this form of computation may lead to a tremendous speed-up compared to traditional methods, but at the same time it poses equally tremendous problems: the smallest disturbance from the environment may ruin the delicate superposition and may render the computation meaningless.

Schrödinger’s Paradox
Nobel Prize winner Erwin Schrödinger invented in the 1930s a thought experiment to elucidate a seemingly absurd consequence of quantum mechanics. A cat sits in a closed box together with one radio-active atom. This atom will decay with a certain probability, according to the laws of quantum mechanics. Upon decaying, the emitted nuclear particle crushes a thin glass tube filled with cyanide and the cat dies instantly. Being outside the box, we don’t know whether the radio-active particle has decayed and thus whether the cat is dead or alive. Quantum mechanically the animal is in a superposition of both states with a certain probability. If we look inside the box, however, we see only one of the two states: the cat is either dead or alive. An observation of the ‘superposition’ of states makes it collapse to one of the states with a certain probability. (Drawing by Tobias Baanders, CWI.)

An important notion in quantum mechanics and quantum computing is ‘entanglement’: two (or more) qubits can be prepared in such a way that, although they are separated in space – one could be on Mars and the other here on earth – they have correlations that can not be explained by classical probability theory, for example two atomic nuclei having unknown but opposite spins. As soon as one qubit is measured, the content of the other is also known, no matter how far they are apart. This property can be used for error correction during the computation, as well as for more efficient transmission of information and for certain forms of distributed computations.

Quantum computing gained momentum after P.W. Shor showed in 1994 how to construct an efficient algorithm for factoring large numbers, which is of crucial importance for, eg, internet security, followed by an algorithm by L.K. Grover (1996) to search a database quadratically faster than any classical algorithm.

The Workshop in Amsterdam (http://www.cwi.nl/~qip) drew 150 participants from 24 countries, including several pioneers of the field, such as Charles Bennett and David DiVincenzo (IBM Yorktown Heights), Richard Jozsa (Bristol), Gilles Brassard (Montreal), Umesh Vazirani (Berkeley), as well as Nobel laureate Gerard ‘t Hooft (Utrecht).

CWI started the first quantum computing research group in The Netherlands (and one of the first in Europe) in 1995, and has contributed significant discoveries to the field. CWI has applied quantum computing notions to communication complexity, and found general limitations of quantum computers, as well as some new speed-ups. CWI also studies quantum information theory. The European Union has recognized the importance of this research and has given the group substantial support.

Please contact:
Harry Buhrman - CWI
Tel: +31 20 592 4076 / 4078
E-mail: Harry.Buhrman@cwi.nl