Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$28,000.00

The Nature of Quantum Speedups

FY 2019-20

Summary
Quantum computers are devices that can harness the quantum nature of physical reality for computational power. These machines, if built to scale, would potentially lead to breakthroughs in material design by allowing the simulation of quantum physics, and would also render many cryptographic schemes insecure.******On the other hand, it is important to realize that quantum computers are not simply faster versions of regular computers. Instead, they support a new class of algorithms - quantum algorithms - and for some select problems, such algorithms are known to be much more efficient than the best known non-quantum approach. A crucial question, then, is to understand for which types of problems quantum algorithms can provide a substantial speedup, and for which types of problems they cannot.******For example, we know of fast quantum algorithms for problems such as factoring and taking discrete logarithms, on which much of modern cryptography is based. These quantum algorithms are exponentially faster than the best known classical algorithm. On the other hand, for a large class of problems known as the NP-complete problems, such an exponential quantum speedup is not known, and generally not believed to exist. The intuition is that factoring and discrete log are highly ""structured"" problems, whereas NP-complete problems are unstructured and just involve a search over an exponentially large, unordered solution space.******What structure allows quantum algorithms to yield an exponential speedup? For which tasks should we expect a quantum computer to help, and for which should we not? I propose to study these questions to help shed light on the utility of quantum devices. Specifically, I propose to study them in two primary models called query complexity and communication complexity. These mathematical models of computation capture most of the design space of known quantum algorithms: for example, both Shor's algorithm and Grover's algorithm have a natural conceptualization in the query complexity model.******Characterizing the structure necessary for exponential quantum speedups will require not only a better understanding of how to use quantum resources to provide speedups, but also better tools for ruling out certain approaches. Showing that a fast algorithm does not exist for a problem can be a mathematically challenging task. While we have some tools to do so, many open problems remain. I propose to also work on lower bound techniques in query and communication complexity to allow us to more easily show that a given problem has no fast algorithm.******Quantum computers may become a reality over the next few decades, bringing with them drastic changes to the capabilities of computing devices and rendering many cryptographic protocols insecure. To prepare for a post-quantum world, it is crucial that we understand what quantum computers can and cannot do. The applications of such an understanding to algorithms and cryptography will ultimately benefit all Canadians.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2019-04804
Name nom
BenDavid, Shalev
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
2019
Competition year année de concours
2019
Award amount
28000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
The Nature of Quantum Speedups
Keyword
NSERC
Application summary
Quantum computers are devices that can harness the quantum nature of physical reality for computational power. These machines, if built to scale, would potentially lead to breakthroughs in material design by allowing the simulation of quantum physics, and would also render many cryptographic schemes insecure.******On the other hand, it is important to realize that quantum computers are not simply faster versions of regular computers. Instead, they support a new class of algorithms - quantum algorithms - and for some select problems, such algorithms are known to be much more efficient than the best known non-quantum approach. A crucial question, then, is to understand for which types of problems quantum algorithms can provide a substantial speedup, and for which types of problems they cannot.******For example, we know of fast quantum algorithms for problems such as factoring and taking discrete logarithms, on which much of modern cryptography is based. These quantum algorithms are exponentially faster than the best known classical algorithm. On the other hand, for a large class of problems known as the NP-complete problems, such an exponential quantum speedup is not known, and generally not believed to exist. The intuition is that factoring and discrete log are highly ""structured"" problems, whereas NP-complete problems are unstructured and just involve a search over an exponentially large, unordered solution space.******What structure allows quantum algorithms to yield an exponential speedup? For which tasks should we expect a quantum computer to help, and for which should we not? I propose to study these questions to help shed light on the utility of quantum devices. Specifically, I propose to study them in two primary models called query complexity and communication complexity. These mathematical models of computation capture most of the design space of known quantum algorithms: for example, both Shor's algorithm and Grover's algorithm have a natural conceptualization in the query complexity model.******Characterizing the structure necessary for exponential quantum speedups will require not only a better understanding of how to use quantum resources to provide speedups, but also better tools for ruling out certain approaches. Showing that a fast algorithm does not exist for a problem can be a mathematically challenging task. While we have some tools to do so, many open problems remain. I propose to also work on lower bound techniques in query and communication complexity to allow us to more easily show that a given problem has no fast algorithm.******Quantum computers may become a reality over the next few decades, bringing with them drastic changes to the capabilities of computing devices and rendering many cryptographic protocols insecure. To prepare for a post-quantum world, it is crucial that we understand what quantum computers can and cannot do. The applications of such an understanding to algorithms and cryptography will ultimately benefit all Canadians.