Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$33,000.00

Algorithms and complexity for quantum advantage

EF 2021-22

Résumé
A large quantum computer which is protected from its environment using quantum error correction is expected to be vastly more powerful than any classical computer. But before such a large quantum computer is available, there will be smaller quantum devices without quantum error correction. And as a result of enormous academic and commercial investment we are beginning to see the availability of these small and noisy quantum computers. Moreover, it is expected that there will soon be quantum devices that cannot be simulated by existing classical computers, opening the door to the possibility of demonstrating some kind of quantum advantage. While these developments are exciting, they also highlight a mismatch between the efforts to build a quantum computer and the existing state of quantum algorithms research. Indeed, a pressing question is: what should we do with a near-term quantum computer? Arguably we do not yet have a satisfactory answer. Interpreted narrowly in the context of the next-generation of devices, it translates as: what can be achieved without error correction, using short-depth circuits, over a gate set determined by architecture? Unfortunately these restrictions rule out most known quantum algorithmic primitives, and do not leave much room for creative algorithm design. In the next several years there is an opportunity (and need) for theoretical work to impact potential applications of quantum computers. Rather than commit ourselves to a particular architecture or device, we propose to contribute to this effort through fundamental research in quantum algorithms and complexity, guided by the basic questions: Which restricted quantum computations can be more powerful than classical computers? Which are classically simulable? These questions are central to the challenge of realizing the potential of near-term quantum computers. To succeed we must understand new ways that quantum computers can eke out an advantage over classical computers in the presence of restrictions on their operation (e.g., from limitations of existing hardware). In fact, several of the leading proposals for near-term demonstrations have their origins in early studies of restricted models of quantum computation such as constant-depth quantum circuits, BosonSampling, and Instantaneous Quantum Computation. We propose research in three areas centered around this theme. First, we will develop quantum algorithms that use fewer quantum resources and may demonstrate new forms of quantum advantage. Second, we will improve methods for classically simulating small or restricted quantum computations; in addition to their direct use in verifying small quantum computers, such methods help to identify the quantum resources necessary for quantum speedup. Finally, we will investigate the complexity of quantum many-body systems, and identify structural features of such systems which can be leveraged by efficient classical or quantum algorithms.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2019-04198
Name nom
Gosset, David
Department département
Department of Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2019
Award amount
33000
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
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Installment
inst:3
Partie
1
Nb partie
5
Application title
Algorithms and complexity for quantum advantage
Keyword
NSERC
Application summary
A large quantum computer which is protected from its environment using quantum error correction is expected to be vastly more powerful than any classical computer. But before such a large quantum computer is available, there will be smaller quantum devices without quantum error correction. And as a result of enormous academic and commercial investment we are beginning to see the availability of these small and noisy quantum computers. Moreover, it is expected that there will soon be quantum devices that cannot be simulated by existing classical computers, opening the door to the possibility of demonstrating some kind of quantum advantage. While these developments are exciting, they also highlight a mismatch between the efforts to build a quantum computer and the existing state of quantum algorithms research. Indeed, a pressing question is: what should we do with a near-term quantum computer? Arguably we do not yet have a satisfactory answer. Interpreted narrowly in the context of the next-generation of devices, it translates as: what can be achieved without error correction, using short-depth circuits, over a gate set determined by architecture? Unfortunately these restrictions rule out most known quantum algorithmic primitives, and do not leave much room for creative algorithm design. In the next several years there is an opportunity (and need) for theoretical work to impact potential applications of quantum computers. Rather than commit ourselves to a particular architecture or device, we propose to contribute to this effort through fundamental research in quantum algorithms and complexity, guided by the basic questions: Which restricted quantum computations can be more powerful than classical computers? Which are classically simulable? These questions are central to the challenge of realizing the potential of near-term quantum computers. To succeed we must understand new ways that quantum computers can eke out an advantage over classical computers in the presence of restrictions on their operation (e.g., from limitations of existing hardware). In fact, several of the leading proposals for near-term demonstrations have their origins in early studies of restricted models of quantum computation such as constant-depth quantum circuits, BosonSampling, and Instantaneous Quantum Computation. We propose research in three areas centered around this theme. First, we will develop quantum algorithms that use fewer quantum resources and may demonstrate new forms of quantum advantage. Second, we will improve methods for classically simulating small or restricted quantum computations; in addition to their direct use in verifying small quantum computers, such methods help to identify the quantum resources necessary for quantum speedup. Finally, we will investigate the complexity of quantum many-body systems, and identify structural features of such systems which can be leveraged by efficient classical or quantum algorithms.