Towards a Complexity Theory of Quantum States and State Transformations
Abstract
This research proposal aims to develop new paradigms and techniques for studying the computational complexity of quantum states and state transformations. An important motivation comes from the following- in quantum information processing there are many natural tasks that are “inherently quantum�, meaning that they have quantum inputs and-or quantum outputs. Examples of such tasks include preparing the ground state of a many-body quantum system, decoding the Hawking radiation of a black hole, or breaking the security of a quantum bit commitment scheme. The traditional frameworks of computational complexity theory are focused on tasks with classical inputs and classical outputs (such as computing a Boolean function). Although this framework has been extremely successful in both classical and quantum computer science, it does not provide a natural way to reason about the computational resources needed to solve the “inherently quantum� tasks listed above. This calls for a new complexity theory for quantum computational problems. Along the way, this research will shed light on fundamental questions about quantum information, quantum complexity theory, and quantum cryptography.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 06, 2024
- Source ID
- FA95502310363
Entities
People
- Henry Yuen
Organizations
- Air Force Office of Scientific Research
- Trustees of Columbia University in the City of New York
- United States Air Force