Research work · 2025

Quantum advantage

Quantum Computing

Abstract

Abstract There is one question that, more than any other, pervades quantum computing: Is there a quantum advantage? This question may be asked either in general – of quantum mechanics as a model of computation – or for specified individual algorithms. In both cases, to even pose this question in a rigorous and meaningful way, a number of non-trivial prerequisites are required. These prerequisites mainly belong in the domain of computational complexity theory. This chapter defines the relevant classical and quantum computational complexity classes and includes classes of quantum circuits, such as instantaneous quantum polynomial (IQP) circuits, that provide compelling evidence that quantum mechanics indeed offers an exponential computational advantage. Also included are classes of circuits that are known not to enjoy a quantum advantage, most notably stabiliser circuits, that are extremely non-classical from a physics perspective, but can nevertheless be efficiently simulated on a classical computer, as proven in the famous Gottesman–Knill theorem.

DOI: 10.1093/9780191964381.003.0006