Fetching the paper…
Reading the bibliography…
We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph{quantum} algorithms such as the Quantum Approximate Optimization Algorithm (QAOA).
The theory of branching processes
Theodore Edward Harris et al · 1963
Earlier work this paper cites.
On the Einstein-Podolsky-Rosen paradox
John S Bell · 1964
Earlier work this paper cites.
Solvable model of a spin-glass
David Sherrington and Scott Kirkpatrick · 1975
Earlier work this paper cites.
A sequence of approximated solutions to the SK model for spin glasses
Giorgio Parisi · 1980
Earlier work this paper cites.
On Cayley’s formula for counting forests
Lajos Takács · 1990
Earlier work this paper cites.
Algorithms for constraint-satisfaction problems: A survey
Vipin Kumar · 1992
Earlier work this paper cites.
On the Medians of Gamma Distributions and an Equation of Ramanujan
K. P. Choi · 1994
Earlier work this paper cites.
Constraint satisfaction problems: Algorithms and applications
Sally C Brailsford, Chris N Potts, and Barbara M Smith · 1999
Earlier work this paper cites.
The Bethe lattice spin glass revisited
Marc Mézard and Giorgio Parisi · 2001
Earlier work this paper cites.
The thermodynamic limit in mean field spin glass models
Francesco Guerra and Fabio Lucio Toninelli · 2002
Earlier work this paper cites.
Replica bounds for optimization problems and diluted spin systems
Silvio Franz and Michele Leone · 2003
Earlier work this paper cites.
Understanding belief propagation and its generalizations
Jonathan S Yedidia, William T Freeman, Yair Weiss, et al · 2003
Earlier work this paper cites.
Random multi-overlap structures and cavity fields in diluted spin glasses
Luca De Sanctis · 2004
Earlier work this paper cites.
The high temperature region of the Viana–Bray diluted spin glass model
Francesco Guerra and Fabio Lucio Toninelli · 2004
Earlier work this paper cites.
Bounds for diluted mean-fields spin glass models
Dmitry Panchenko and Michel Talagrand · 2004
Earlier work this paper cites.
Survey propagation: An algorithm for satisfiability
Alfredo Braunstein, Marc Mézard, and Riccardo Zecchina · 2005
Earlier work this paper cites.
On the unique games conjecture
Subhash Khot and Nisheeth K Vishnoi · 2005
Earlier work this paper cites.
On the solution-space geometry of random constraint satisfaction problems
Dimitris Achlioptas and Federico Ricci-Tersenghi · 2006
Earlier work this paper cites.
The parisi formula
Michel Talagrand · 2006
Earlier work this paper cites.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007
Earlier work this paper cites.
Optimal algorithms and inapproximability results for every CSP?
Prasad Raghavendra · 2008
Cited alongside, same era.
Hoeffding’s inequality for supermartingales
Xiequan Fan, Ion Grama, and Quansheng Liu · 2012
Cited alongside, same era.
A quantum approximate optimization algorithm
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2014
Cited alongside, same era.
Dmitry Panchenko · 2014
Cited alongside, same era.
The Parisi formula for mixed p p -spin models
Dmitry Panchenko · 2014
Optimization of the Sherrington-Kirkpatrick Hamiltonian
A. Montanari · 2019
Later among the works it cites.
Hartree-Fock on a superconducting qubit quantum computer
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, et al · 2020
Later among the works it cites.
The SK model is infinite step replica symmetry breaking at zero temperature
Antonio Auffinger, Wei-Kuo Chen, and Qiang Zeng · 2020
Later among the works it cites.
Obstacles to variational quantum optimization from symmetry protection
Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang · 2020
Later among the works it cites.
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
Edward Farhi, David Gamarnik, and Sam Gutmann · 2020
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.
Diluted mean-field spin-glass models at criticality
Giorgio Parisi, Federico Ricci-Tersenghi, and Tommaso Rizzo · 2014
Cited alongside, same era.
Satisfiability threshold for random regular NAE-SAT
Jian Ding, Allan Sly, and Nike Sun · 2016
Cited alongside, same era.
A short note on Poisson tail bounds
Clément Canonne · 2017
Cited alongside, same era.
Extremal cuts of sparse random graphs
Amir Dembo, Andrea Montanari, and Subhabrata Sen · 2017
Cited alongside, same era.
Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven · 2018
Cited alongside, same era.
The full replica symmetry breaking in the Ising spin glass on random regular graph
Francesco Concetti · 2018
Cited alongside, same era.
Edward Farhi, David Gamarnik, and Sam Gutmann · 2020
Later among the works it cites.
Low-Degree Hardness of Random Optimization Problems
David Gamarnik, Aukosh Jagannath, and Alexander S Wein · 2020
Later among the works it cites.
Bounds on MAXCUT QAOA performance for p > 1
Jonathan Wurtz and Peter J Love · 2020
Later among the works it cites.
Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices
Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin · 2020
Later among the works it cites.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2021
Closest in time.
Classical algorithms and quantum limitations for maximum cut on high-girth graphs
Boaz Barak and Kunal Marwaha · 2021
Closest in time.
The quantum Wasserstein distance of order 1
Giacomo De Palma, Milad Marvian, Dario Trevisan, and Seth Lloyd · 2021
Closest in time.
Optimization of mean-field spin glasses
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2021
Closest in time.
Quantum phases of matter on a 256-atom programmable quantum simulator
Sepehr Ebadi, Tout T Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, et al · 2021
Closest in time.
The overlap gap property and approximate message passing algorithms for p p -spin models
David Gamarnik and Aukosh Jagannath · 2021
Closest in time.
Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu, Qingling Zhu, Youwei Zhao, Shaowei Li, Shaojun Guo, et al · 2021
Closest in time.
Local classical MAX-CUT algorithm outperforms p = 2 p=2 QAOA on high-girth regular graphs
Kunal Marwaha · 2021
Closest in time.
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification
Antares Chen, Jonathan Shi, and Luca Trevisan · 2022
Closest in time.
Optimal low-degree hardness of maximum independent set
Alexander S Wein · 2022
Closest in time.