Formal Framework for Quantum Advantage

Motivated by notions of quantum heuristics and by average-case rather than worst-case algorithmic analysis, we define quantum computational advantage in terms of individual problem instances. Inspired by the classical notions of Kolmogorov complexity and instance complexity, we define their quantum versions. This allows us to define queasy instances of computational problems, like e.g. Satisfiability and Factoring, as those whose quantum instance complexity is significantly smaller than their classical instance complexity. These instances indicate quantum advantage: they are easy to solve on a quantum computer, but classical algorithms struggle (they feel queasy). Via a reduction from Factoring, we prove the existence of queasy Satisfiability instances; specifically, these instances are maximally queasy (under reasonable complexity-theoretic assumptions). Further, we show that there is exponential algorithmic utility in the queasiness of a quantum algorithm. This formal framework serves as a beacon that guides the hunt for quantum advantage in practice, and moreover, because its focus lies on single instances, it can lead to new ways of designing quantum algorithms.