Formal Framework for Quantum Advantage

The Bell System Technical Journal

Claude Elwood Shannon (1948): A Mathematical Theory of Communication · 1948

Earlier work this paper cites.

Information and Control

Leonid A. Levin (1984): Randomness conservation inequalities; information and independence in mathematical theories · 1984

Earlier work this paper cites.

Springer Berlin Heidelberg, doi: 10.1007/bfb0091534

(1993): The development of the number field sieve · 1993

Earlier work this paper cites.

Journal of the ACM

Pekka Orponen, Ker-I Ko, Uwe Schöning & Osamu Watanabe (1994): Instance Complexity · 1994

Earlier work this paper cites.

SIAM Journal on Computing

Peter W. Shor (1997): Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer · 1997

Earlier work this paper cites.

In Rüdiger Reischuk & Michel Morvan, editors: STACS 97

Harry Buhrman & Lance Fortnow (1997): Resource-bounded kolmogorov complexity revisited · 1997

Earlier work this paper cites.

Cambridge University Press

Michael Mitzenmacher & Eli Upfal (2005): Probability and Computing: Randomized Algorithms and Probabilistic Analysis · 2005

Cited alongside, same era.

eprint quant-ph/0511096

Dorit Aharonov, Vaughan Jones & Zeph Landau (2006): A Polynomial Quantum Algorithm for Approximating the Jones Polynomial · 2006

Cited alongside, same era.

Springer New York, doi: 10.1007/978-0-387-49820-1_1

Ming Li & Paul Vitányi (2008): Preliminaries , p. 1–99 · 2008

Cited alongside, same era.

In: 2008 23rd Annual IEEE Conference on Computational Complexity

Harry Buhrman & John M. Hitchcock (2008): NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly · 2008

Cited alongside, same era.

Cambridge University Press

Michael A. Nielsen & Isaac L. Chuang (2010): Quantum Computation and Quantum Information: 10th Anniversary Edition · 2010

Cited alongside, same era.

Course Technology, Boston, MA

Michael Sipser (2013): Introduction to the Theory of Computation , third edition · 2013

Later among the works it cites.

In Shubhangi Saraf, editor: 35th Computational Complexity Conference (CCC 2020)

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang & Ruizhe Zhang (2020): On the Quantum Complexity of Closest Pair and Related Problems · 2020

Later among the works it cites.

In Markus Bläser & Benjamin Monmege, editors: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Harry Buhrman, Subhasree Patro & Florian Speelman (2021): A Framework of Quantum Strong Exponential-Time Hypotheses · 2021

Later among the works it cites.

eprint 2508.05720

Hsin-Yuan Huang, Soonwon Choi, Jarrod R. McClean & John Preskill (2025): The vast world of quantum advantage · 2025

Closest in time.

eprint 2503.05625

Tuomas Laakkonen, Enrico Rinaldi, Chris N. Self, Eli Chertkov, Matthew DeCross, David Hayes, Brian Neyenhuis, Marcello Benedetti & Konstantinos Meichanetzidis (2025): Less Quantum, More Advantage: An End-to-End Quantum Algorithm for the Jones Polynomial · 2025

Closest in time.