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

**A BRICS Mini-Course**

**January 22, 24 and 26, 1996**

**Lectures by
André Berthiaume
**

**
**

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.

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

**Introduction**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

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

- http://www.cwi.nl/~berthiau/
- http://eve.physics.ox.ac.uk/QChome.html
- http://vesta.physics.ucla.edu/~smolin/