Fetching the paper…
Reading the bibliography…
We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely the quantum adiabatic algorithm for discrete optimization and quantum Hamiltonian descent for continuous optimization.
“Quantum algorithms for zero-sum games”, 2019
Joran van Apeldoorn and András Gilyén · 1904
Earlier work this paper cites.
“The characteristic roots of certain real symmetric matrices” https://trace.tennessee.edu/utk_gradthes/2384/ , 1953
Joseph Elliott · 1953
Earlier work this paper cites.
“The rotation of eigenvectors by a perturbation. III”
Chandler Davis and W.. Kahan · 1970
Earlier work this paper cites.
“Simulating physics with computers”
Richard. Feynman · 1982
Earlier work this paper cites.
“Inversion of Jacobi’s tridiagonal matrix”
R.A. Usmani · 1994
Earlier work this paper cites.
“Universal Quantum Simulators”
Seth Lloyd · 1996
Earlier work this paper cites.
“Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”
Peter. Shor · 1997
Earlier work this paper cites.
“On the power of quantum computation”
Daniel. Simon · 1997
Earlier work this paper cites.
“Quantum computation by adiabatic evolution”, 2000
Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Michael Sipser · 2000
Earlier work this paper cites.
“How powerful is adiabatic quantum computation?”
W. van Dam, M. Mosca and U. Vazirani · 2001
Earlier work this paper cites.
“A Quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem”
Edward Farhi et al · 2001
Earlier work this paper cites.
“Classical and Quantum Computation”
A. Kitaev, A. Shen and M. Vyalyi · 2002
Earlier work this paper cites.
“Quantum search by local adiabatic evolution”
Jérémie Roland and Nicolas. Cerf · 2002
Earlier work this paper cites.
“Adiabatic quantum state generation and statistical zero knowledge”
Dorit Aharonov and Amnon Ta-Shma · 2003
Earlier work this paper cites.
“Exponential algorithmic speedup by a quantum walk”
Andrew. Childs et al · 2003
Earlier work this paper cites.
“Adiabatic perturbation theory in quantum dynamics”
Stefan Teufel · 2003
Earlier work this paper cites.
“Fast quantum algorithm for numerical gradient estimation”
Stephen. Jordan · 2005
Earlier work this paper cites.
“An elementary proof of the quantum adiabatic theorem”, 2006
Andris Ambainis and Oded Regev · 2006
Earlier work this paper cites.
“The Complexity of the Local Hamiltonian Problem”
Julia Kempe, Alexei Kitaev and Oded Regev · 2006
Earlier work this paper cites.
“Adiabatic quantum computation is equivalent to standard quantum computation”
Dorit Aharonov et al · 2007
Earlier work this paper cites.
“Efficient quantum algorithms for simulating sparse Hamiltonians”
Dominic. Berry, Graeme Ahokas, Richard Cleve and Barry. Sanders · 2007
Earlier work this paper cites.
“Bounds for the adiabatic approximation with applications to quantum computation”
Sabine Jansen, Mary-Beth Ruskai and Ruedi Seiler · 2007
Earlier work this paper cites.
“The complexity of stoquastic local Hamiltonian problems” https://dl.acm.org/doi/abs/10.5555/2011772.2011773
Sergey Bravyi, David. Divincenzo, Roberto Oliveira and Barbara. Terhal · 2008
Earlier work this paper cites.
“The complexity of quantum spin systems on a two-dimensional square lattice”
R. Oliveira and B.M. Terhal · 2008
Earlier work this paper cites.
“Quantum algorithm for linear systems of equations”
Aram. Harrow, Avinatan Hassidim and Seth Lloyd · 2009
Earlier work this paper cites.
“Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer”
David Poulin and Pawel Wocjan · 2009
Earlier work this paper cites.
“Schrieffer–Wolff transformation for quantum many-body systems”
Sergey Bravyi, David. DiVincenzo and Daniel Loss · 2011
Cited alongside, same era.
“Unbounded self-adjoint operators on Hilbert space”
Konrad Schmüdgen · 2012
Cited alongside, same era.
“On complexity of the quantum Ising model”, 2014
Sergey Bravyi and Matthew Hastings · 2014
Cited alongside, same era.
“A Quantum Approximate Optimization Algorithm”, 2014
Edward Farhi, Jeffrey Goldstone and Sam Gutmann · 2014
Cited alongside, same era.
“A useful variant of the Davis–Kahan theorem for statisticians”
Y. Yu, T. Wang and R.. Samworth · 2014
Cited alongside, same era.
“Beating the random assignment on constraint satisfaction problems of bounded degree”
“How much structure is needed for huge quantum speedups?”, 2022
Scott Aaronson · 2022
Later among the works it cites.
“Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models”
Joao Basso, David Gamarnik, Song Mei and Leo Zhou · 2022
Later among the works it cites.
“Quantum simulation of real-space dynamics”
Andrew. Childs et al · 2022
Later among the works it cites.
“Quantum advantage for combinatorial optimization problems, simplified”, 2022
Mario Szegedy · 2022
Later among the works it cites.
“Quantum interior point methods for semidefinite optimization”
Brandon Augustino, Giacomo Nannicini, Tamás Terlaky and Luis. Zuluaga · 2023
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Boaz Barak et al · 2015
Cited alongside, same era.
Edward Farhi, Jeffrey Goldstone and Sam Gutmann · 2015
Cited alongside, same era.
“A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights” http://jmlr.org/papers/v17/15-084.html
Weijie Su, Stephen Boyd and Emmanuel. Candès · 2016
Cited alongside, same era.
“A variational perspective on accelerated methods in optimization”
Andre Wibisono, Ashia. Wilson and Michael. Jordan · 2016
Cited alongside, same era.
“On complexity of the quantum Ising model”
Sergey Bravyi and Matthew Hastings · 2017
Cited alongside, same era.
“Quantum speed-ups for solving semidefinite programs”
Fernando.S.L. Brandao and Krysta. Svore · 2017
Cited alongside, same era.
“Forrelation: A problem that optimally separates quantum from classical computing”
Scott Aaronson and Andris Ambainis · 2018
Cited alongside, same era.
Jiaqi Leng, Ethan Hickman, Joseph Li and Xiaodi Wu · 2023
Later among the works it cites.
“A quantum-classical performance separation in nonconvex optimization”, 2023
Jiaqi Leng, Yufan Zheng and Xiaodi Wu · 2023
Later among the works it cites.
Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi and Tamás Terlaky · 2023
Later among the works it cites.
“An inexact feasible quantum interior point method for linearly constrained quadratic Ooptimization”
Zeguan Wu et al · 2023
Later among the works it cites.
“Challenges and opportunities in quantum optimization”
Amira Abbas et al · 2024
Later among the works it cites.
“Quantum speedups for linear programming via interior point methods”, 2024
Simon Apers and Sander Gribling · 2024
Later among the works it cites.
“A quantum central path algorithm for linear optimization”, 2024
Brandon Augustino et al · 2024
Later among the works it cites.
“A review on Quantum Approximate Optimization Algorithm and its variants” A review on Quantum Approximate Optimization Algorithm and its variants
Kostas Blekos et al · 2024
Later among the works it cites.
“QHDOPT: A software for nonlinear optimization with Quantum Hamiltonian Descent”
Samuel Kushnir et al · 2024
Later among the works it cites.
“Expanding hardware-efficiently manipulable Hilbert space via Hamiltonian embedding”, 2024
Jiaqi Leng, Joseph Li, Yuxiang Peng and Xiaodi Wu · 2024
Later among the works it cites.
“An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory”
Niklas Pirnay et al · 2024
Later among the works it cites.
“Verifiable quantum advantage without structure”
Takashi Yamakawa and Mark Zhandry · 2024
Later among the works it cites.
“On the computational complexity of Schrödinger operators”, 2024
Yufan Zheng, Jiaqi Leng, Yizhou Liu and Xiaodi Wu · 2024
Later among the works it cites.
“Lecture notes on quantum algorithms” https://www.cs.umd.edu/~amchilds/qa/ , 2025
Andrew. Childs · 2025
Closest in time.
“On speedups for convex optimization via quantum dynamics”, 2025
Shouvanik Chakrabarti et al · 2025
Closest in time.
“Quantum Langevin dynamics for optimization”
Zherui Chen et al · 2025
Closest in time.
“Exponentially better bounds for quantum optimization via dynamical simulation”, 2025
Ahmet Catli, Sophia Simon and Nathan Wiebe · 2025
Closest in time.
“Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA”, 2025
Edward Farhi, Sam Gutmann, Daniel Ranard and Benjamin Villalonga · 2025
Closest in time.
“Optimization by Decoded Quantum Interferometry”, 2025
Stephen. Jordan et al · 2025
Closest in time.
“Quantum Hamiltonian Descent for non-smooth optimization”, 2025
Jiaqi Leng et al · 2025
Closest in time.
“Weyl’s inequality” [Online; accessed 25-January-2025], 2025
Wikipedia contributors · 2025
Closest in time.