Algorithms and complexity for quantum advantage

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

A large quantum computer which is protected from its environment using quantum error correction is expected to be vastly more powerful than any classical computer. But before such a large quantum computer is available, there will be smaller quantum devices without quantum error correction. And as a result of enormous academic and commercial investment we are beginning to see the availability of these small and noisy quantum computers. Moreover, it is expected that there will soon be quantum devices that cannot be simulated by existing classical computers, opening the door to the possibility of demonstrating some kind of quantum advantage.******While these developments are exciting, they also highlight a mismatch between the efforts to build a quantum computer and the existing state of quantum algorithms research. Indeed, a pressing question is: what should we do with a near-term quantum computer? Arguably we do not yet have a satisfactory answer. Interpreted narrowly in the context of the next-generation of devices, it translates as: what can be achieved without error correction, using short-depth circuits, over a gate set determined by architecture? Unfortunately these restrictions rule out most known quantum algorithmic primitives, and do not leave much room for creative algorithm design.******In the next several years there is an opportunity (and need) for theoretical work to impact potential applications of quantum computers. Rather than commit ourselves to a particular architecture or device, we propose to contribute to this effort through fundamental research in quantum algorithms and complexity, guided by the basic questions: Which restricted quantum computations can be more powerful than classical computers? Which are classically simulable?******These questions are central to the challenge of realizing the potential of near-term quantum computers. To succeed we must understand new ways that quantum computers can eke out an advantage over classical computers in the presence of restrictions on their operation (e.g., from limitations of existing hardware). In fact, several of the leading proposals for near-term demonstrations have their origins in early studies of restricted models of quantum computation such as constant-depth quantum circuits, BosonSampling, and Instantaneous Quantum Computation.******We propose research in three areas centered around this theme. First, we will develop quantum algorithms that use fewer quantum resources and may demonstrate new forms of quantum advantage. Second, we will improve methods for classically simulating small or restricted quantum computations; in addition to their direct use in verifying small quantum computers, such methods help to identify the quantum resources necessary for quantum speedup. Finally, we will investigate the complexity of quantum many-body systems, and identify structural features of such systems which can be leveraged by efficient classical or quantum algorithms.