BRICS · Contents · Lecturer · Programme · References · Lecture Notes

Quantum Computation

A BRICS Mini-Course
January 22, 24 and 26, 1996

Lectures by
André Berthiaume

Course Contents

Computer science has a classical soul; many definitions implicitly contain ideas from the time we believed the world evolved according to newtonian physics. Ideas such as: an object's state is well defined, instantaneous actions at a distance are impossible, etc. Modern physics and more specifically quantum physics tells us that Nature is not as straightforward as Newton originally believed. One can prepare systems such that the state is completely undefined in any classical sense. Instantaneous actions at a distance have been observed and sometimes having less alternatives to produce a given outcome may improve the probability of getting this outcome! What would happen computing models are allowed to operate within the rules of quantum physics? What are the advantages offered by a quantum computer?

In this mini-course, I will introduce the quantum computer and present some of the milestone results in quantum complexity theory leading up to Shor's famous polynomial time quantum factoring algorithm. Foreknowledge of quantum physics is useful but not necessary as the relevant notions will be introduced when needed. A fascinating aspect of quantum computation is the possibility of building such devices. I will briefly address some of the problems still to be overcome, but it is worth mentioning that some ongoing experiments have shown some very positive results. Quantum computers may well be available sooner than we think.

About the Lecturer

Dr. Berthiaume is one of the pioneers in quantum computation and earned the 1996 doctoral prize from the Natural Sciences and Engineering Research Council of Canada for his thesis on the complexity and stabilisation of quantum computation.


Monday January 22, 1996, 10:15-12:00 in Auditorium D4


We present the basic elements of quantum physics and introduce the qubit, the quantum gate, the quantum register, quantum gate arrays and observables.

Wednesday January 24, 1996, 10:15-12:00 in Auditorium D2

Quantum Complexity, Part I

We define the Deutsch-Jozsa problem and show how a quantum gate array can solve it exponentially faster than a classical computer. Using this problem in a relativised setting, we extend the result to complexity classes.

Wednesday January 24, 1996, 13:15-15:00 in Auditorium D2

Quantum Complexity, Part II

We show how Bernstein & Vazirani (1993) and Simon (1994) seperated (relative to oracles) the classe BPP from its quantum version, BQP.

Friday January 26, 1996, 10:15-12:00 in Auditorium D2


We present Shor's factoring algorithm and review some issues concerning the construction of a quantum computer.


Various material relevant for the course exists in electronic form on the web. Useful URLs include:

Lecture Notes