Quantum information formulates the notion of information in a manner
that accounts for the quantum mechanical behavior of our world.
In this framework, models of computation and communication that
harness the strange power of quantum mechanics have been proposed and
investigated.
In particular, quantum computers are computing devices can exist in
several states simultaneously and their computation paths can
interfere with each other.
They can perform some tasks exponentially faster than any classical
computer (restricted to the laws of classical physics).
For example, a quantum computer can factor an *n*-bit integer in time
polynomial in *n*, whereas all known classical algorithms require
exponential time to do this.
It follows that a quantum computer can easily break many public-key
cryptosystems, such as RSA.
There are, however, quantum public-key cryptosystems based on the
uncertainty principle, that are provably secure against any (classical
or quantum) attack.

Quantum computing in the School of Computer Science is focused on the
theoretical aspects of quantum computing, including
the design and analysis of quantum algorithms, cryptographic
protocols, and various issues in information and complexity theory.
We are part of the University of Waterloo's
**Institute for Quantum
Computing**—please see the institute's web page and our individual
web pages for further details of our research and activities.