CAREER: Fundamental principles of computation and physics

计算的基本原理是什么？任何计算机，无论多么先进，最终都受到量子力学的限制，因此计算定律和物理定律交织在一起。充分利用量子物理的量子计算机目前还不存在，但正在积极发展。该奖项旨在发现未来量子计算机的新算法和算法框架，以及在当前量子加密设备上证明更强安全保证的新技术。该奖项还将用于为学生提供建议和支持，与PI合作并参与这项研究。量子算法可以以与经典算法非常不同的方式工作。开发量子算法的两种最成功的方法——跨度程序和学习图——是最近才开发出来的，但已经导致了许多具体的算法和一般的计算规则，例如，用于组合算法。这项研究将扩展和结合这些方法与物理启发算法技术。此外，该研究将考虑量子计算可以教给我们关于物理原理的东西。作为经典生物，我们对量子系统的描述是否存在内在的限制？这个问题的答案与密码学密切相关，并且应该允许高度安全的密钥分发方案。通过研究量子计算机的终极能力，这项研究将加深我们对计算和物理基本原理的理解。

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.