Fetching the paper…
Reading the bibliography…
We analyze generalizations of quantum algorithms based on the short path framework first proposed by Hastings~[\textit{Quantum} 2, 78 (2018)], which has been extended and shown by Dalzell~et~al.~[STOC~'23] to achieve super-Grover speedups for certain binary optimization problems.
Time-dependent statistics of the Ising model
Roy J. Glauber · 1963
Earlier work this paper cites.
The independence ratio of regular graphs
Béla Bollobás · 1981
Earlier work this paper cites.
Asymptotic evaluation of certain Markov process expectations for large time. IV
Monroe D. Donsker and S.R. Srinivasa Varadhan · 1983
Earlier work this paper cites.
Logarithmic Sobolev inequalities for finite Markov chains
P. Diaconis and L. Saloff-Coste · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Improved approximation algorithms for MAX k-CUT and MAX BISECTION
Alan Frieze and Mark Jerrum · 1997
Earlier work this paper cites.
Logarithmic Sobolev inequality for some models of random walks
Tzong-Yow Lee and Horng-Tzer Yau · 1998
Earlier work this paper cites.
A quantum algorithm for finding the minimum, 1999
Christoph Durr and Peter Hoyer · 1999
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.
A probabilistic algorithm for k k -SAT based on limited local search and restart
Uwe Schöning · 2002
Earlier work this paper cites.
Quantum speed-up of markov chain based algorithms
M. Szegedy · 2004
Earlier work this paper cites.
An improved exponential-time algorithm for k-sat
Ramamohan Paturi, Pavel Pudlák, Michael E Saks, and Francis Zane · 2005
Earlier work this paper cites.
Branching and treewidth based exact algorithms
Fedor V Fomin, Serge Gaspers, and Saket Saurabh · 2006
Earlier work this paper cites.
Counting independent sets up to the tree threshold
Dror Weitz · 2006
Earlier work this paper cites.
Bounds on the bisection width for random d -regular graphs
J. Díaz, M.J. Serna, and N.C. Wormald · 2007
Earlier work this paper cites.
Speedup via quantum sampling
Pawel Wocjan and Anura Abeyesinghe · 2008
Earlier work this paper cites.
Disorder chaos and multiple valleys in spin glasses, 2009
Sourav Chatterjee · 2009
Earlier work this paper cites.
Quantum algorithm for linear systems of equations
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Earlier work this paper cites.
On the hardness of sampling independent sets beyond the tree threshold
Elchanan Mossel, Dror Weitz, and Nicholas Wormald · 2009
Earlier work this paper cites.
Adaptive simulated annealing: A near-optimal connection between sampling and counting
Daniel Štefankovič, Santosh Vempala, and Eric Vigoda · 2009
Earlier work this paper cites.
The number of independent sets in a regular graph
Yufei Zhao · 2009
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.
Improving ppsz for 3-sat using critical variables
Timon Hertli, Robin A Moser, and Dominik Scheder · 2010
Earlier work this paper cites.
Computational transition at the uniqueness threshold
Allan Sly · 2010
Earlier work this paper cites.
Mean field models for spin glasses: Volume I: Basic examples
Michel Talagrand · 2010
Cited alongside, same era.
A conjecture on the maximum cut and bisection width in random regular graphs
Lenka Zdeborová and Stefan Boettcher · 2010
Cited alongside, same era.
Search via quantum walk
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha · 2011
Cited alongside, same era.
Concentration inequalities
Steven P. Lalley · 2013
Cited alongside, same era.
The Satisfiability Problem: Algorithms and Analyses
Uwe Schöning and Jacobo Torán · 2013
Cited alongside, same era.
A quantum approximate optimization algorithm, 2014
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
Faster exponential-time algorithms for approximately counting independent sets
Leslie Ann Goldberg, John Lapinskas, and David Richerby · 2021
Later among the works it cites.
A sharp log-Sobolev inequality for the multislice
Justin Salez · 2021
Later among the works it cites.
Localization schemes: A framework for proving mixing bounds for markov chains, 2022
Yuansi Chen and Ronen Eldan · 2022
Later among the works it cites.
Sudakov-fernique post-amp, and a new proof of the local convexity of the tap free energy, 2022
Michael Celentano · 2022
Later among the works it cites.
Quantum algorithms for sampling log-concave distributions and estimating normalizing constants
Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang · 2022
Later among the works it cites.
Universal quantum speedup for branch-and-bound, branch-and-cut, and tree-search algorithms
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang · 2014
Cited alongside, same era.
Inapproximability of the partition function for the antiferromagnetic ising and hard-core models
ANDREAS GALANIS, Daniel Stefankovic, and Eric Vigoda · 2016
Cited alongside, same era.
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
Andris Ambainis and Martins Kokainis · 2017
Cited alongside, same era.
Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
Andrew M. Childs, Robin Kothari, and Rolando D. Somma · 2017
Cited alongside, same era.
Extremal cuts of sparse random graphs
Amir Dembo, Andrea Montanari, and Subhabrata Sen · 2017
Cited alongside, same era.
Exact algorithms for maximum independent set
Mingyu Xiao and Hiroshi Nagamochi · 2017
Cited alongside, same era.
Shouvanik Chakrabarti, Pierre Minssen, Romina Yalovetzky, and Marco Pistoia · 2022
Later among the works it cites.
The Ising Antiferromagnet and Max Cut on Random Regular Graphs
Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, and Gregory B. Sorkin · 2022
Later among the works it cites.
Upgrading mlsi to lsi for reversible markov chains, 2022
Justin Salez, Konstantin Tikhomirov, and Pierre Youssef · 2022
Later among the works it cites.
Quantum algorithm for estimating volumes of convex bodies
Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu · 2023
Later among the works it cites.
A sublinear-time quantum algorithm for approximating partition functions
Arjan Cornelissen and Yassine Hamoudi · 2023
Later among the works it cites.
Spectral gap of nonreversible markov chains, 2023
Sourav Chatterjee · 2023
Later among the works it cites.
Rapid mixing of glauber dynamics up to uniqueness via contraction
Zongchen Chen, Kuikui Liu, and Eric Vigoda · 2023
Later among the works it cites.
Quantum algorithms: A survey of applications and end-to-end complexities, 2023
Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão · 2023
Later among the works it cites.
Mind the gap: Achieving a super-grover quantum speedup by jumping to the end
Alexander M Dalzell, Nicola Pancotti, Earl T Campbell, and Fernando GSL Brandão · 2023
Later among the works it cites.
Quantum computing for finance
Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev · 2023
Later among the works it cites.
Challenges and opportunities in quantum optimization
Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, et al · 2024
Closest in time.
Sampling from the sherrington-kirkpatrick gibbs measure via algorithmic stochastic localization, 2024
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2024
Closest in time.
Hardness of sampling for the anti-ferromagnetic ising model on random graphs, 2024
Neng Huang, Will Perkins, and Aaron Potechin · 2024
Closest in time.
Optimization by decoded quantum interferometry
Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, and Ryan Babbush · 2024
Closest in time.
Stochastic quantum sampling for non-logconcave distributions and estimating partition functions
Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, and Chunhao Wang · 2024
Closest in time.
Quartic quantum speedups for planted inference
Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, and Ryan Babbush · 2024
Closest in time.
Rapid mixing on random regular graphs beyond uniqueness, 2025
Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang · 2025
Closest in time.
Rapid mixing at the uniqueness threshold, 2025
Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang · 2025
Closest in time.