Quantum Computation. Mini-Course

André Berthiaume

January 1996


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?

This mini-course introduces the quantum computer and presents 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 are introduced when needed. A fascinating aspect of quantum computation is the possibility of building such devices. Some of the problems still to be overcome will briefly addressed, 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.

Available as PostScript (7.7Mb -> 130.2Mb), PDF (3.5Mb).


Pages 1-32: Quantum Computation. (ps.gz, pdf)
Introductory paper reprinted with kind permission from Complexity Theory Retrospective II, Springer Verlag, 1996.

Page 35: Course Abstract. (ps.gz, pdf)


Pages 37-66: Session I: Introduction. (ps.gz 4.9Mb -> 47.7Mb, pdf 0.8Mb)

Pages 67-86: Session II: Quantum Complexity, Part I. (ps.gz 3.4Mb -> 28.8Mb, pdf 0.5Mb)

Pages 87-98: Session III: Quantum Complexity, Part II. (ps.gz 1.6Mb -> 17.7Mb, pdf 0.3Mb)

Pages 99-126: Session IV: Factoring. (ps.gz 5.3Mb -> 46.9Mb, pdf 0.8Mb)


Last modified: 2003-06-04 by webmaster.