What gives quantum computers their extra power?

点击翻译按钮获取中文摘要

Quantum computation holds the promise to vastly expand the realm of the efficiently computable, and as such can become a major driving force for the information-based industries of modern society. Shor's factoring algorithm is a prime example to demonstrate this potential. Currently, a wide variety of approaches to quantum algorithms is being pursued, drawing intuition from various areas of computer science and physics. Yet, so far, breakthroughs of the magnitude of Shor's and Grover's discoveries have proven to be extremely rare. Therefore, to tap into the full potential of quantum computation, we need to better understand its foundations. That is, we need to ask which fundamental properties of quantum mechanics have computational value, and how this value can be utilized. This proposal points to two such resources, and describes a path towards understanding how to best apply them. If this research is successful in the long term, it will become a foundation for future high-level quantum algorithm design.