Mathematics of Quantum Computing

A brief history of the subject:

Existing computers and the corresponding mathematical theory of computing are based on laws of classical physics, as opposed to quantum physics. In 1981, Richard Feynman made a simple yet deep observation: while classical computers seem to be inefficient in tackling computations in quantum mechanics (e.g. solutions of Schrödinger equation), (hypothetical) computers working based on principles of quantum mechanics should be extremely efficient at least for classical problems!

A few years later, in 1985, foundations of quantum computer science were laid down in a paper by D. Deutsch. This theory subsumes the classical theory of Church-Turing (and others) at a classical limit. From a mathematical view, the passage from classical computer science to quantum computer science is quite similar to passage from classical geometry (of any sort) to quantum (or noncommutative) geometry and is also very similar to passage from classical mechanics to quantum mechanics.

In 1994 Peter Shor showed that two very important problems of "prime factorization of numbers" and the so-called "discrete logarithm problem" can be efficiently solved in a quantum computer. The existence of these algorithms and their enormous potentials give weight to the above mentioned idea of Feynman. A main idea in quantum computation is to replace classical "bits" and "gates" by "quantum bits" ("qubits") which are vectors in a Hilbert space (up to phase) and "quantum gates" which are unitary operators acting on qubits.

This is a self-contained introduction to issues in quantum computing theory. I will cover all the necessary background material needed from quantum mechanics, (classical) computer science, and mathematics (finite dimensional Hilbert spaces and operators on them). One goal is to explain Shor's algorithms. I will also emphasize emerging relations with noncommutative geometry. Graduate (and enthusiastic undergraduate) students and faculty members in mathematics, applied mathematics, computer science, physics, engineering and philosophy are encouraged to participate.

Outlines and Lecture notes:

• Qubits and quantum gates: Hilbert spaces and operators on them.
• A short introduction to quantum mechanics and computer science.
• Quantum Fourier transform and its applications (factoring and discrete logarithm).
• Quantum information (quantum entropy).

Marking Policy:  Students are expected to prepare and present reports on selected topics of current interest. I will choose these topics in consultation with each student.

Textbook:

 Quantum computation and quantum information by Nielsen and Chuang, published by Cambridge University Press.

References:

[1] Feynman lectures on computation by R. Feynman, edited by Hey and Allen, published by Perseus Publishing.

[2] Simulating physics with computers by R. Feynman , International Journal of Theoretical Physics, Volume 21(1982), 467-488.

[3] Quantum theory, the Church-Turing principle, and the universal quantum computer by D. Deutsch, Proc. Roy. Soc. London. A400(1985), 97-117.

[4] Algorithm for quantum computations: discrete logarithms and factoring by P. Shor, Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, IEEE Comput. Soc. Press, 124-134.