Grant: Discovery Grants Program - Individual
University of Waterloo
$6,786.00
Fault-tolerant quantum computing and quantum algorithms
FY 2011-12
Summary
As transistors approach atomic-scale size limits, what will become of Moore's Law? A possible answer is that quantum computers, which take advantage of quantum effects at small scales, will take the baton and give further exponential increases in computational power. This proposal will address two important questions:
1. What are quantum computers good for? The best-known quantum algorithms are for factoring and simulating quantum systems. Although many other algorithms are known, the full power of quantum computers is still mysterious. We have developed a new framework for designing quantum algorithms based on a classical computational model known as ""span programs."" So far, we have found optimal algorithms for a large class of formula-evaluation problems. For example, the question of whether white or black has a winning strategy in chess is a special case of evaluating an AND-OR formula, a common problem whose quantum complexity our work has now characterized. A main research direction is to apply the framework to other problems for which optimal quantum algorithms are not yet known, e.g., many graph problems.
2. How can we build a quantum computer? Quantum computers have not yet been implemented. The major difficulty, common to all the different approaches, is overcoming noise in fragile quantum systems. Improved physical engineering can only eliminate some noise. Efficient fault-tolerance schemes, for computing reliably with noisy operations, are essential. I have worked on designing such schemes, and further progress is likely to come from tailoring the schemes more closely to the strengths and weaknesses of particular experimental systems. Beyond developing new fault-tolerance schemes, though, technical work is also required to develop methods to evaluate accurately proposed schemes; the schemes cannot be tested on quantum computers today, nor can they be easily simulated on classical computers.
If successful, then the proposed research should simplify experimental implementations of quantum computers by loosening noise requirements, and should broaden their applicability.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
371786-2009
Name nom
Reichardt, Ben
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
2011
Competition year année de concours
2009
Award amount
6786
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
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
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
3
Nb partie
3
Application title
Fault-tolerant quantum computing and quantum algorithms
Keyword
NSERC
Application summary
As transistors approach atomic-scale size limits, what will become of Moore's Law? A possible answer is that quantum computers, which take advantage of quantum effects at small scales, will take the baton and give further exponential increases in computational power. This proposal will address two important questions:
1. What are quantum computers good for? The best-known quantum algorithms are for factoring and simulating quantum systems. Although many other algorithms are known, the full power of quantum computers is still mysterious. We have developed a new framework for designing quantum algorithms based on a classical computational model known as ""span programs."" So far, we have found optimal algorithms for a large class of formula-evaluation problems. For example, the question of whether white or black has a winning strategy in chess is a special case of evaluating an AND-OR formula, a common problem whose quantum complexity our work has now characterized. A main research direction is to apply the framework to other problems for which optimal quantum algorithms are not yet known, e.g., many graph problems.
2. How can we build a quantum computer? Quantum computers have not yet been implemented. The major difficulty, common to all the different approaches, is overcoming noise in fragile quantum systems. Improved physical engineering can only eliminate some noise. Efficient fault-tolerance schemes, for computing reliably with noisy operations, are essential. I have worked on designing such schemes, and further progress is likely to come from tailoring the schemes more closely to the strengths and weaknesses of particular experimental systems. Beyond developing new fault-tolerance schemes, though, technical work is also required to develop methods to evaluate accurately proposed schemes; the schemes cannot be tested on quantum computers today, nor can they be easily simulated on classical computers.
If successful, then the proposed research should simplify experimental implementations of quantum computers by loosening noise requirements, and should broaden their applicability.