Quantum Algorithms


11.05 - 15.05.1998

organized by


Thomas Beth and Gilles Brassard

Quantum algorithms - a new topic in both informatics and physics has become a central theme of one of the most challenging areas of interdisciplinary research of modern science. This seemingly esoteric area of research which has been stimulated by Feynman in 1980 and Benioff, who was the first to suggest quantum-mechanical evolution for computation in 1982, has become a serious challenge after Shor's publication of the ``Algorithms for quantum computation: Discrete logarithms and factoring'' in 1994. This breakthrough in theoretical computer science has stimulated a new field of physics, especially on the experimental side, namely the investigation of controlled quantum systems which is motivated by the promise that algorithmic processing of quantum information may provide an exponential gain in speed and space over classical computers. As a consequence of this joint research there has been a surprising progress during the last years towards new algorithms and especially complexity bounds for certain problems. However, up to today there are no exact theorems available on the relation between quantum complexity classes and classical complexity classes.

Quantum algorithms rely on three effects:

• superposition,
• entanglement,
• interference.

If several qubits are combined in a quantum register by the laws of quantum mechanics, the state space of such a processor allows the handling of exponentially many data by superposition of entangled states. Owing to the linearity of quantum mechanics each operation of so-called quantum gates will act on all states simultaneously which have non-zero population in the superposition. This phenomenon is the basis for quantum parallelism which leads to a completely new model of computation: While a classical probabilistic algorithm can be well described through the tree of all possible computations weighed with the respective probabilities, the sum of probabilities of all positive results are added to give the total probability of a successful computation, the use of quantum states based on complex amplitudes instead of probabilistic weights will allow the enhancement or deletion of amplitudes. This, in a nutshell, is the essential advantage of quantum algorithms. Each desirable computational path can be designed to ``absorbe'' the probability amplitude on the account of the amplitudes of other paths. This principle is known from physics as constructive and destructive interference.

Physical realizations of quantum computers are envisaged as hybrid systems consisting of a classical computer and a quantum register controlled by classical electromagnetic fields, see e.g. the figure. The control of this system at runtime especially and the design of program loops are performed by classical computers on the basis of measurements carried out on the quantum register. For obvious physical reasons such programming languages are rather restricted even though it has been proved by Deutsch in 1985 that the class of quantum Turing machines encompasses the class of classical Turing machines, following a proposal by Benioff who was the first to think that computation can be done entirely in a quantum mechanical unitary manner.

The Dagstuhl seminar 98191 has brought together scientists from computer science, mathematics, theoretical physics, and experimental physics to discuss the most recent developments of this very new and possibly revolutionizing concept of modern computing.

As opposed to most ``classical'' computer science conferences, the unusual concept of this conference can be described by the fact that the theoretical aspects of algorithm design are, at least at the present state of the field, not to be seen device-independent: In other words, in contrast to classical computer science approaches to algorithms and their application, where the actual physical realization on the bit level is not taken into account, it is the feature of this field that in quantum algorithms the physical realization is intrinsically connected with the design of algorithms: Thus, everyone working in the area has to be relatively well acquainted with both, the computer science sides and the physics sides where the modeling of both physics and computer science on the basis of quantum theory and their applications relies on rather strong mathematical foundations such as Hilbert space theory, group theory, combinatorics, information theory, coding theory, and signal processing.

The organizers have judiciously combined the topics to be addressed at this conference to bring together those experts in the fields which can contribute to each of the questions from the mentioned side, ranging from pure theory to actual experiment. Owing to the relative youth of the field and the demanding requirements for a successful work in this area, this Dagstuhl seminar did not only bring together a considerable set of the world experts in the area but also a relatively dominating majority of young scientists which have been attracted by this area. The success of this workshop was not only noted by the computer scientists who have been able to learn from fundamental physical developments of the last years, but also especially physicists have been attracted by the methods of algorithm design and theoretical computer science to be applied to design new physical processes.

So, all in all, we had a successful workshop of mostly three sessions a day lasting late into the night. The interruption of the intensive discussions were only due to the fine food during the day and the expectancy of good spirits at night. This was made possible by the wonderful surroundings of Schloß Dagstuhl accompanied by an exceptionally good weather and the hospitality of the Dagstuhl staff.