Estonian Winter Schools in Computer Science    
Eesti arvutiteaduse talvekoolid
EWSCS 2003
EATTK 2003

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

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.


Modified Monday, Oct 12, 2015 at 17:19 EEST+0300 by