Grant: Discovery Grants Program - Individual
The University of British Columbia
$36,000.00
Quantum speedups: structure, design, and application
FY 2024-25
Summary
Quantum computation is computation using quantum mechanical laws. While its conception dates back to the 1980s, it has taken recent experiments to show that its promise can be physically fulfilled. The promise of quantum computation lies in the existence of quantum speedups. A quantum speedup occurs when a quantum algorithm can solve a computational problem faster than any classical counterpart.
There are a variety of low-value, artificial problems that admit large quantum speedups. There are also many high-value problems that admit small quantum speedups. However, not many problems are known to have both high value and large speedup. In 1994, Shor showed that the problem of factoring integers belongs to this category. Shor's discovery made traditional cryptographic schemes obsolete and led to a huge surge of interest in quantum computation. The long-term objective of my research is to expand the pool of high-value problems with large speedup.
To systematically achieve the long-term objective, this proposal is split into three components: structure, design, and application. The structure component will better characterize how the structure of a problem relates to its speedup. The design component will develop new tools for designing quantum algorithms that capture speedups. The application component will focus on analyzing speedups in three key application areas: cryptanalysis, reinforcement learning, and the natural sciences. If getting quantum speedups is like getting water, the structure component locates the water, the design component builds the well, and the application component pulls the water out in a bucket.
Structure. The guiding question of the structure component is whether there exists a fundamental tradeoff between a problem's structure and speedup. The short-term objective is to study this tradeoff for two particular structures: graph and periodicity. For the former, a tradeoff is known to exist and the goal is to find an explicit family of problems that witnesses it. For the latter, we know two points on a possible tradeoff curve and the goal is to understand the full curve, including its existence.
Design. Historically, quantum algorithm design has been driven by the development of frameworks that reduce the task to solving purely classical problems. The short-term objective of the design component is to develop new frameworks in non-traditional settings where the algorithm is online (i.e., receives inputs and produces outputs in stages) or has its performance measured on average over random inputs.
Application. The short-term objectives are (i) evaluate the security of new cryptographic schemes that have been proposed for securing online financial transactions by first understanding their underlying structures and (ii) explore the possibility of super-quadratic speedups in reinforcement learning and the natural sciences by working in the non-traditional settings described in the design component.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2024-06493
Name nom
Wang, Daochen
Department département
Computer Science
Organization id
2
Institution établissement
The University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
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 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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Quantum speedups: structure, design, and application
Keywords
quantum computing; quantum speedups; quantum algorithms; quantum information; quantum cryptanalysis; quantum machine learning; quantum simulation
Application summary
Quantum computation is computation using quantum mechanical laws. While its conception dates back to the 1980s, it has taken recent experiments to show that its promise can be physically fulfilled. The promise of quantum computation lies in the existence of quantum speedups. A quantum speedup occurs when a quantum algorithm can solve a computational problem faster than any classical counterpart.
There are a variety of low-value, artificial problems that admit large quantum speedups. There are also many high-value problems that admit small quantum speedups. However, not many problems are known to have both high value and large speedup. In 1994, Shor showed that the problem of factoring integers belongs to this category. Shor's discovery made traditional cryptographic schemes obsolete and led to a huge surge of interest in quantum computation. The long-term objective of my research is to expand the pool of high-value problems with large speedup.
To systematically achieve the long-term objective, this proposal is split into three components: structure, design, and application. The structure component will better characterize how the structure of a problem relates to its speedup. The design component will develop new tools for designing quantum algorithms that capture speedups. The application component will focus on analyzing speedups in three key application areas: cryptanalysis, reinforcement learning, and the natural sciences. If getting quantum speedups is like getting water, the structure component locates the water, the design component builds the well, and the application component pulls the water out in a bucket.
Structure. The guiding question of the structure component is whether there exists a fundamental tradeoff between a problem's structure and speedup. The short-term objective is to study this tradeoff for two particular structures: graph and periodicity. For the former, a tradeoff is known to exist and the goal is to find an explicit family of problems that witnesses it. For the latter, we know two points on a possible tradeoff curve and the goal is to understand the full curve, including its existence.
Design. Historically, quantum algorithm design has been driven by the development of frameworks that reduce the task to solving purely classical problems. The short-term objective of the design component is to develop new frameworks in non-traditional settings where the algorithm is online (i.e., receives inputs and produces outputs in stages) or has its performance measured on average over random inputs.
Application. The short-term objectives are (i) evaluate the security of new cryptographic schemes that have been proposed for securing online financial transactions by first understanding their underlying structures and (ii) explore the possibility of super-quadratic speedups in reinforcement learning and the natural sciences by working in the non-traditional settings described in the design component.