Fetching the paper…
Reading the bibliography…
We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random.
Étude des coefficients de fourier des fonctions de l p ( g ) l^{p}(g)
Aline Bonami · 1970
Earlier work this paper cites.
On bounded occurrence constraint satisfaction
Johan Håstad · 2000
Earlier work this paper cites.
A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda · 2001
Earlier work this paper cites.
Spatial search by quantum walk
Andrew M Childs and Jeffrey Goldstone · 2004
Earlier work this paper cites.
On the advantage over a random assignment
Johan Håstad and Srinivasan Venkatesh · 2004
Earlier work this paper cites.
Anderson localization makes adiabatic quantum optimization fail
Boris Altshuler, Hari Krovi, and Jérémie Roland · 2010
Earlier work this paper cites.
Lieb-robinson bounds for commutator-bounded operators
Isabeau Prémont-Schwarz, Alioscia Hamma, Israel Klich, and Fotini Markopoulou-Kalamara · 2010
Earlier work this paper cites.
Quantum walks: a comprehensive review
Salvador Elías Venegas-Andraca · 2012
Cited alongside, same era.
Exponential improvement in precision for simulating sparse Hamiltonians
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma · 2014
Cited alongside, same era.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
Analysis of boolean functions
Ryan O’Donnell · 2014
Cited alongside, same era.
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright · 2015
Cited alongside, same era.
Hamiltonian simulation by qubitization
Guang Hao Low and Isaac L Chuang · 2016
Later among the works it cites.
Optimal Hamiltonian simulation by quantum signal processing
Guang Hao Low and Isaac L. Chuang · 2017
Later among the works it cites.
Quantum algorithm for simulating real time evolution of lattice hamiltonians
Jeongwan Haah, Matthew B Hastings, Robin Kothari, and Guang Hao Low · 2018
Later among the works it cites.
A short path quantum algorithm for exact optimization
M. B. Hastings · 2018
Later among the works it cites.
Quantum algorithm for spectral measurement with a lower gate count
David Poulin, Alexei Kitaev, Damian S Steiger, Matthew B Hastings, and Matthias Troyer · 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…
Hamiltonian simulation with nearly optimal dependence on all parameters
D. W. Berry, A. M. Childs, and R. Kothari · 2015
Cited alongside, same era.
Simulating Hamiltonian dynamics with a truncated Taylor series
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
Cited in the paper.
Adam Callison, Nicholas Chancellor, Florian Mintert, and Viv Kendon · 2019
Closest in time.