Grant: Discovery Grants Program - Accelerator Supplements
University of Waterloo
$40,000.00
Efficient quantum algorithms and protocols
EF 2009-10
Résumé
Quantum mechanical computers, when built, will considerably alter the information processing landscape. They offer provably efficient solutions to problems believed to be beyond the capability of current computers. At the same time, they compromise the security of widely deployed cryptographic schemes.
We plan to design new quantum algorithms for a variety of problems in combinatorial optimization and statistical physics. These algorithms, based on novel properties of quantum walks and quantum Fourier transforms, would be provably faster than those known today. We also plan to devise efficient protocols for fundamental cryptographic tasks that are secure in the strongest possible sense---even in the presence of quantum computers. In the process, we hope to discover new constructions of combinatorial objects akin to randomness extractors, as well as ways of analysing strategies of malicious parties in cryptographic scenarios with methods from convex optimization. Finally, we wish to develop techniques in quantum information theory to address important questions regarding quantum and classical communication.
The study of quantum information and computation has revealed powerful concepts whose consequences are percolating into classical computing as well as other areas of mathematics. We expect that our research will have further such impact.
Programme
Discovery Grants Program - Accelerator Supplements
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
364476-2008
Name nom
Nayak, Ashwin
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
40000
Program id
RGPAS
Program nane en
Discovery Grants Program - Accelerator Supplements
Program name fr
Programme de subventions à la découverte - supplément d'accélération
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1073
Committee name en
DAS - Math., Stats., Computer Sc. and Electrical Eng. Selection Committee
Committee name fr
SAD - Comité de sélection en Math., Stats., Informatique et Génie électrique
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
1
Nb partie
3
Application title
Efficient quantum algorithms and protocols
Keyword
NA
Application summary
Quantum mechanical computers, when built, will considerably alter the information processing landscape. They offer provably efficient solutions to problems believed to be beyond the capability of current computers. At the same time, they compromise the security of widely deployed cryptographic schemes.
We plan to design new quantum algorithms for a variety of problems in combinatorial optimization and statistical physics. These algorithms, based on novel properties of quantum walks and quantum Fourier transforms, would be provably faster than those known today. We also plan to devise efficient protocols for fundamental cryptographic tasks that are secure in the strongest possible sense---even in the presence of quantum computers. In the process, we hope to discover new constructions of combinatorial objects akin to randomness extractors, as well as ways of analysing strategies of malicious parties in cryptographic scenarios with methods from convex optimization. Finally, we wish to develop techniques in quantum information theory to address important questions regarding quantum and classical communication.
The study of quantum information and computation has revealed powerful concepts whose consequences are percolating into classical computing as well as other areas of mathematics. We expect that our research will have further such impact.