Fetching the paper…
Reading the bibliography…
I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022.
Quantum field theory and the Jones polynomial
E. Witten · 1989
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Earlier work this paper cites.
On the power of quantum computation
D. Simon · 1994
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
Quantum algorithm for the collision problem
G. Brassard, P. Høyer, and A. Tapp · 1997
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 1998
Earlier work this paper cites.
Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen · 2001
Earlier work this paper cites.
Simulation of topological quantum field theories by quantum computers
M. Freedman, A. Kitaev, and Z. Wang · 2002
Earlier work this paper cites.
Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem
S. Hallgren · 2002
Earlier work this paper cites.
Exponential algorithmic speedup by a quantum walk
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman · 2003
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Earlier work this paper cites.
The quantum query complexity of the hidden subgroup problem is polynomial
M. Ettinger, P. Høyer, and E. Knill · 2004
Earlier work this paper cites.
The power of adiabatic quantum computation with no sign problem
M. B. Hastings · 2005
Earlier work this paper cites.
A polynomial quantum algorithm for approximating the Jones polynomial
D. Aharonov, V. Jones, and Z. Landau · 2006
Earlier work this paper cites.
Symmetries, graph properties, and quantum speedups
S. Ben-David, A. M. Childs, A. Gilyén, W. Kretschmer, S. Podder, and D. Wang · 2006
Cited alongside, same era.
Limitations of quantum coset states for graph isomorphism
S. Hallgren, C. Moore, M. Rötteler, A. Russell, and P. Sen · 2006
Cited alongside, same era.
k k -forrelation optimally separates quantum and classical query complexity
N. Bansal and M. Sinha · 2008
Cited alongside, same era.
An optimal separation of randomized and quantum query complexity
A. A. Sherstov, A. A. Storozhenko, and P. Wu · 2008
Cited alongside, same era.
Quantum algorithm for solving linear systems of equations
A. Harrow, A. Hassidim, and S. Lloyd · 2009
Near invariance of the hypercube
S. Aaronson and H. Nguyen · 2016
Later among the works it cites.
Separations in query complexity based on pointer functions
A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrovs · 2016
Later among the works it cites.
Complexity-theoretic foundations of quantum supremacy experiments
S. Aaronson and L. Chen · 2017
Later among the works it cites.
A stability result using the matrix norm to bound the permanent
R. Berkowitz and P. Devlin · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
BQP and the polynomial hierarchy
S. Aaronson · 2010
Cited alongside, same era.
Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem
S. Aaronson, S. Ben-David, R. Kothari, S. Rao, and A. Tal · 2010
Cited alongside, same era.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
M. Bremner, R. Jozsa, and D. Shepherd · 2010
Cited alongside, same era.
The need for structure in quantum speedups
S. Aaronson and A. Ambainis · 2011
Cited alongside, same era.
The computational complexity of linear optics
S. Aaronson and A. Arkhipov · 2011
Cited alongside, same era.
Focus beyond quadratic speedups for error-corrected quantum advantage
R. Babbush, J. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven · 2011
Cited alongside, same era.
(sub)exponential advantage of adiabatic quantum computation with no sign problem
A. Gilyén, M. B. Hastings, and U. V. Vazirani · 2011
Cited alongside, same era.
U. Mahadev · 2018
Later among the works it cites.
A note on the quantum query complexity of permutation symmetric functions
A. Chailloux · 2019
Later among the works it cites.
Quantum supremacy using a programmable superconducting processor
F. Arute et al · 2019
Later among the works it cites.
Oracle separation of BQP and PH
R. Raz and A. Tal · 2019
Later among the works it cites.
A quantum-inspired classical algorithm for recommendation systems
E. Tang · 2019
Later among the works it cites.
N. Bansal, M. Sinha, and R. de Wolf · 2022
Closest in time.
Classically-verifiable quantum advantage from a computational bell test
G. D. Kahanamoku-Meyer, S. Choi, U. V. Vazirani, and N. Y. Yao · 2022
Closest in time.
Quantum computational advantage using photons
L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, A. E. Lita, T. Gerrits, S. W. Nam, V. D. Vaidya, M. Menotti, I. Dhand, Z. Vernon, N. Quesada, and J. Lavoie · 2022
Closest in time.
The physics of quantum information
J. Preskill · 2022
Closest in time.
The early days of quantum computation
P. W. Shor · 2022
Closest in time.
Verifiable quantum advantage without structure
T. Yamakawa and M. Zhandry · 2022
Closest in time.