Grant: Discovery Grants Program - Individual
University of Waterloo
$39,000.00
Implications of quantum information for computational complexity
FY 2016-17
Summary
The area of quantum information and computation studies the consequences of storing and processing information in devices at the atomic scale. In this regime, nature follows laws of physics discovered early in the 20th century, the laws of quantum mechanics, which are fundamentally different from those we experience in our daily lives. These laws enable astonishing tasks, from algorithms more efficient than possible with current technology, to cryptography that would be provably impossible under the laws they replace (the laws of classical physics). Considerable progress has been made in understanding the power of quantum mechanical computers, and in the building of experimental prototypes. Commercial systems implementing quantum cryptography have long been deployed.
Within computer science, quantum computation has had a profound impact on traditional areas of research, especially in the last five years. For instance, it has led to the development of efficient parallel algorithms for certain semi-definite optimization problems, to unconditional proofs of impossibility of solving NP-hard problems using extended formulations of linear programs, and to the discovery of an efficient (classical) algorithm for a well-studied many-body system in quantum physics. Prominent themes in these developments are the use of convex optimization and quantum information-theoretic techniques. My current research is inspired by these developments, and focuses on the analysis of quantum information and its consequences for algorithms, communication, and cryptography.
Along with my research group and collaborators, I plan to: study entanglement as a resource, and quantify the amount of this resource needed in information processing tasks; use methods from convex optimization to study entropic quantities in non-asymptotic information theory, and their applications to communication and cryptography; study the information content properties of quantum states, and bring these to bear on the efficiency of algorithms and protocols; and analyze ground states of quantum physical systems, and their connection with the complexity of the associated computational problems. The projects draw from and connect to rich areas of study in mathematics and computer science. We expect that our research will have repercussions for these areas as well, while making strides in quantum computing.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-06332
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
2016
Competition year année de concours
2014
Award amount
39000
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
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
5
Application title
Implications of quantum information for computational complexity
Keyword
NSERC
Application summary
The area of quantum information and computation studies the consequences of storing and processing information in devices at the atomic scale. In this regime, nature follows laws of physics discovered early in the 20th century, the laws of quantum mechanics, which are fundamentally different from those we experience in our daily lives. These laws enable astonishing tasks, from algorithms more efficient than possible with current technology, to cryptography that would be provably impossible under the laws they replace (the laws of classical physics). Considerable progress has been made in understanding the power of quantum mechanical computers, and in the building of experimental prototypes. Commercial systems implementing quantum cryptography have long been deployed.
Within computer science, quantum computation has had a profound impact on traditional areas of research, especially in the last five years. For instance, it has led to the development of efficient parallel algorithms for certain semi-definite optimization problems, to unconditional proofs of impossibility of solving NP-hard problems using extended formulations of linear programs, and to the discovery of an efficient (classical) algorithm for a well-studied many-body system in quantum physics. Prominent themes in these developments are the use of convex optimization and quantum information-theoretic techniques. My current research is inspired by these developments, and focuses on the analysis of quantum information and its consequences for algorithms, communication, and cryptography.
Along with my research group and collaborators, I plan to: study entanglement as a resource, and quantify the amount of this resource needed in information processing tasks; use methods from convex optimization to study entropic quantities in non-asymptotic information theory, and their applications to communication and cryptography; study the information content properties of quantum states, and bring these to bear on the efficiency of algorithms and protocols; and analyze ground states of quantum physical systems, and their connection with the complexity of the associated computational problems. The projects draw from and connect to rich areas of study in mathematics and computer science. We expect that our research will have repercussions for these areas as well, while making strides in quantum computing.