The purpose of this cluster is to further develop the theory of
quantum algorithms, quantum complexity theory, quantum cryptography, and
quantum information theory, and to facilitate the building of devices
that perform quantum information processing tasks.
The cluster consists of three projects, which are described below.
- Project #1: Quantum Algorithms and Complexity Theory
Project Leader: Richard Cleve
Other Project Investigators: Gilles Brassard, Peter Høyer,
Michele Mosca, Ashwin Nayak, Alain Tapp, Barry Sanders, William Unruh,
John Watrous
The purpose of this project is to explore the boundary between what is
efficiently computable by quantum algorithms and what is not.
A major goal of this project is to develop new quantum algorithms,
new insights into how quantum algorithms work, and new insights about
what kinds of problems can be solved quickly by quantum algorithms.
Elements of this project include the quantum walk
algorithmic paradigm (which is a quantum analogue of a classical random
walk), properties of quantum Fourier transforms (such as the cost of
computing them with various resource measures and their algorithmic
applications), the amplitude amplification algorithmic paradigm, and
issues related to entanglement as a resource in quantum algorithms.
Two other elements of this project are the development of complexity
theories of quantum proof systems (such as quantum analogues of the
complexity classes NP and IP), and quantum communication complexity
(which considers the communication costs required to solve problems
in distributed systems).
One of the motivations for analyzing these elements is that their
classical counterparts have had profound consequences for classical
computational complexity.
- Project #2: Quantum Information Security
Project Leader: Gilles Brassard
Other Project Investigators: Claude Crépeau, Michele Mosca, Ashwin Nayak,
Barry Sanders, Alain Tapp, John Watrous, Richard Cleve
The main purpose of this project is to develop new cryptographic
protocols based on the laws of quantum mechanics.
Examples of cryptographic primitives that are under investigation
are encryption, authentication, verifiable secret sharing, and
secure multi-party computations. Furthermore, quantum versions of
the notion of "zero-knowledge" are under development.
Quantum teleportation can be viewed as the quantum equivalent of
the classical one-time pad with quantum secret keys, and recent
research has naturally led to the notion of a quantum one-time pad
that uses only a classical secret key to do perfect encryption of
quantum states.
A natural extension to this concept is the notion of public-key quantum
qryptography which uses a classical public-key crypto-system to transmit
the secret-key of a quantum one-time pad.
Similarly, the notion of quantum authentication has recently emerged
as the quantum analog with classical secret keys of the classical
notion of authentication codes to protect the integrity of quantum
data.
Other important notions such as quantum secret sharing,
and verifiable quantum secret sharing have been introduced to allow
a party to share a quantum state among several parties in such a way
that a small number of them have no information about the original state,
whereas sufficiently many of them can reconstruct the state accurately.
It is verifiable if honest parties can check ahead of time whether the
reconstruction process will work despite the presence of a few dishonest
participants.
This leads naturally to the development of multiparty quantum computations
where several distrustful parties accomplish a quantum computation
on data that they keep secret from each other.
Research on quantum versions of zero-knowledge is at a very preliminary
stage, since even a good (robust) definition seems difficult to obtain.
- Project #3: Theory of Quantum Information Processing
Implementations
Project Leader: Raymond Laflamme
Other Project Investigators: Gilles Brassard, Richard Cleve,
Peter Høyer, Michele Mosca, Ashwin Nayak, Barry Sanders,
William Unruh
The purpose of this project is to analyze methods for making quantum
computations resilient with respect to noise, decoherence, and various
inaccuracies that occur in realistic physical implementations of quantum
information processing systems.
Elements of this project include mathematical theories of quantum
error-correcting codes and fault tolerance, and well as theoretical
models of the behavior of specific physical systems.
At the fundamental level, quantum information processing is a physical
process, and the field will reach its full potential with the
development of quantum devices which will reach society.
The development of quantum information concepts has had a fundamental
impact on the overlap of the mathematics and physics community and has
lead to strong interactions between them.
Furthermore, it is already impacting the design and implementation
of quantum technologies, and this project addresses issues that arise
in this context.
|
