8th Estonian Winter School in Computer Science (EWSCS)
VIII Eesti Arvutiteaduse Talvekool (EATTK)
Palmse, Estonia
March 2 - 7, 2003
Andris Ambainis
Department of Computer Science
University of Latvia
Quantum Algorithms and Quantum Cryptography
Quantum computing is a new, more powerful model of computing based on quantum mechanics. It relates to cryptography in two ways. First, polynomial time algorithms for factoring and discrete logarithm could make number-theory based cryptosystems insecure. Second, it is possible to build new cryptographic systems based on quantum effects which are secure with validity of quantum mechanics as the only assumption.
In this short course, I will give an introduction to quantum computing with emphasis on results related to cryptography. The first lecture will introduce the basics of quantum computing and describe a quantum protocol for key distribution. The second lecture will describe Shor's polynomial time quantum algorithm for factoring.
The short course will be self-contained. No background in quantum mechanics is assumed.
Course materials
A really simple explanation of quantum computing model:
S. Fenner. A physics-free introduction to the quantum computation model. Bulletin of EATCS. [ps]Survey article on quantum algorithms:
D. Aharonov. Quantum Computation. http://www.arxiv.org/abs/quant-ph/9812037Survey article on quantum cryptography:
D. Gottesman and H.-K. Lo, "From Quantum Cheating to Quantum Security," Physics Today 53, no. 11, 22-27. [html].
About the Speaker
Andris Ambainis received his MSc from University of Latvia in 1997 and Ph.D. from University of California, Berkeley in 2001. After that, he was a postdoc at Institute for Advanced Study, Princeton for one year and is now back to University of Latvia as Assistant Professor. He is working on many topics in quantum computing: quantum algorithms, quantum complexity theory, quantum communication, cryptography and information theory. He is also interested in non-quantum algorithms and complexity.
E-mail: ambainis@lanet.lv