Grant: Discovery Grants Program - Individual
University of Waterloo
$22,000.00
Algorithms for quantum computers
EF 2009-10
Résumé
The computers in use today are based on a notion of information rooted in classical physics. They represent data using bits, each bit taking the value 0 or 1. But quantum mechanics, the physical theory describing the behavior of atoms at a fundamental level, offers a more general notion of information. In quantum mechanics, data can take on a superposition of its possible classical values. To take advantage of this new kind of information, we can envision constructing a quantum mechanical computer, an information processing machine that operates according to the laws of quantum mechanics.
It turns out that quantum computers can quickly perform certain tasks that seem to be intractable for classical computers. For example, there is an efficient quantum algorithm for decomposing an integer into its prime factors. No such algorithm is known for classical computers, and indeed, many of the cryptosystems in use today (for example, to encrypt financial transactions carried out over the internet) are based on the widely-held assumption that this problem is hard. Thus, quantum computers overturn established notions of what can be computed efficiently, with potentially dramatic implications for technology. However, only a few examples of quantum speedup are known, and the nature of the computational advantage provided by quantum mechanics is currently poorly understood.
My research program is focused on better understanding the power of quantum computers. Specifically, I work to develop new quantum algorithms that achieve dramatic speedup over classical computation. This research serves both to illuminate the differences between classical and quantum computers and to find quantum solutions for problems of practical importance, such as search problems and cryptographic tasks. I am especially interested in developing novel algorithmic techniques for quantum computation, expanding the toolbox of methods that can be used to design and analyze new quantum algorithms.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
356068-2008
Name nom
Childs, Andrew
Department département
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
2009
Competition year année de concours
2008
Award amount
22000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
Partie
2
Nb partie
5
Application title
Algorithms for quantum computers
Keyword
NA
Application summary
The computers in use today are based on a notion of information rooted in classical physics. They represent data using bits, each bit taking the value 0 or 1. But quantum mechanics, the physical theory describing the behavior of atoms at a fundamental level, offers a more general notion of information. In quantum mechanics, data can take on a superposition of its possible classical values. To take advantage of this new kind of information, we can envision constructing a quantum mechanical computer, an information processing machine that operates according to the laws of quantum mechanics.
It turns out that quantum computers can quickly perform certain tasks that seem to be intractable for classical computers. For example, there is an efficient quantum algorithm for decomposing an integer into its prime factors. No such algorithm is known for classical computers, and indeed, many of the cryptosystems in use today (for example, to encrypt financial transactions carried out over the internet) are based on the widely-held assumption that this problem is hard. Thus, quantum computers overturn established notions of what can be computed efficiently, with potentially dramatic implications for technology. However, only a few examples of quantum speedup are known, and the nature of the computational advantage provided by quantum mechanics is currently poorly understood.
My research program is focused on better understanding the power of quantum computers. Specifically, I work to develop new quantum algorithms that achieve dramatic speedup over classical computation. This research serves both to illuminate the differences between classical and quantum computers and to find quantum solutions for problems of practical importance, such as search problems and cryptographic tasks. I am especially interested in developing novel algorithmic techniques for quantum computation, expanding the toolbox of methods that can be used to design and analyze new quantum algorithms.