Grant: Discovery Grants Program - Individual
University of Waterloo
$36,000.00
Quantum information and complexity theory
FY 2014-15
Summary
The proposal is to investigate computational complexity issues that arise in the context of quantum information. ""Computational complexity"" is concerned with the inherent computational costs of performing computations. ""Quantum information"" is a model of information that captures the quantum mechanical behavior that arises in physical systems. It is natural to consider computational complexity in this model and this has resulted in several remarkable results during the past two decades (such as efficient ""quantum algorithms"", novel cryptographic protocols, reductions in communication complexity, and quantum ""proof systems""). The specific focus of the proposal is on the following two topics. One topic is the computational complexity of ""non-local games"", which are scenarios where two (or more) cooperating players who cannot communicate with each other respond to questions from a verifier. The scenario is particularly interesting when the cooperating players are allowed to possess quantum systems whose joint state is ""entangled"" (a quantum mechanical analogue of ""correlated""), which permits them to coordinate their answers in ways that are impossible with classical information. An interesting problem it to determine the optimal coordination possible. There are classes of these games where the computational complexity of this problem is well-understood, but the general problem is not currently even known to be decidable. The other topic concerns the computational complexity of Hamiltonian evolution: simulating the state that arises if an initial state evolves for a specified time-interval under SchrËdinger's equation. This is interesting in the context of simulating physical systems, and also because there are quantum algorithms for combinatorial problems that utilize such simulations. There are interesting open questions about the inherent computational costs arising in these processes. Finally, I speculate that some of the ideas arising in this topic might lead to more efficient Trotter-Suzuki type product formulas.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
105393-2013
Name nom
Cleve, Richard
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2013
Award amount
36000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2709
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Other computing methods
Research subject fr
Autres méthodes informatiques
Partie
2
Nb partie
5
Application title
Quantum information and complexity theory
Keyword
NSERC
Application summary
The proposal is to investigate computational complexity issues that arise in the context of quantum information. ""Computational complexity"" is concerned with the inherent computational costs of performing computations. ""Quantum information"" is a model of information that captures the quantum mechanical behavior that arises in physical systems. It is natural to consider computational complexity in this model and this has resulted in several remarkable results during the past two decades (such as efficient ""quantum algorithms"", novel cryptographic protocols, reductions in communication complexity, and quantum ""proof systems""). The specific focus of the proposal is on the following two topics. One topic is the computational complexity of ""non-local games"", which are scenarios where two (or more) cooperating players who cannot communicate with each other respond to questions from a verifier. The scenario is particularly interesting when the cooperating players are allowed to possess quantum systems whose joint state is ""entangled"" (a quantum mechanical analogue of ""correlated""), which permits them to coordinate their answers in ways that are impossible with classical information. An interesting problem it to determine the optimal coordination possible. There are classes of these games where the computational complexity of this problem is well-understood, but the general problem is not currently even known to be decidable. The other topic concerns the computational complexity of Hamiltonian evolution: simulating the state that arises if an initial state evolves for a specified time-interval under SchrËdinger's equation. This is interesting in the context of simulating physical systems, and also because there are quantum algorithms for combinatorial problems that utilize such simulations. There are interesting open questions about the inherent computational costs arising in these processes. Finally, I speculate that some of the ideas arising in this topic might lead to more efficient Trotter-Suzuki type product formulas.