What are the foundational principles of computation? Any computer, however advanced, is ultimately limited by quantum mechanics, so the laws of computation and physics intertwine. Quantum computers, that take full advantage of quantum physics, do not yet exist, but are under active development. This award seeks to discover new algorithms and algorithmic frameworks for future quantum computers, as well as new techniques for proving stronger security guarantees on present-day quantum cryptography devices. The award will also be used for advising and supporting students, working with the PI and taking part in this research.
Quantum algorithms can work in very different ways than classical algorithms. Two of the most successful approaches for developing quantum algorithms---span programs and learning graphs---were developed only recently, but have led both to many concrete algorithms and to general computational rules, e.g., for composing algorithms. This research will extend and combine these approaches with physically inspired algorithmic techniques. In addition, the research will consider what quantum computation can teach us about the principles of physics. Are there intrinsic limits to how well we, as classical beings, can characterize quantum systems? Answers to this question tie closely to cryptography, and should allow for highly secure key-distribution schemes. By investigating the ultimate capabilities of quantum computers, the research will deepen our understanding of the basic principles of computation and physics.
