Fetching the paper…
Reading the bibliography…
We consider the maximum cut and maximum independent set problems on random regular graphs in the infinite-size limit, and calculate the energy densities achieved by QAOA for high degrees up to $d=100$.
“Classical and quantum bounded depth approximation algorithms” (2019)
M. B. Hastings · 1905
Earlier work this paper cites.
“Obstacles to state preparation and variational optimization from symmetry protection”
Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang · 1910
Earlier work this paper cites.
“The overlap gap property and approximate message passing algorithms for p p -spin models” (2019)
David Gamarnik and Aukosh Jagannath · 1911
Earlier work this paper cites.
“Simulating physics with computers”
Richard P. Feynman · 1982
Earlier work this paper cites.
“Independent sets in regular graphs of high girth”
B. D. McKay · 1987
Earlier work this paper cites.
“On the independence and chromatic numbers of random regular graphs”
A.M Frieze and T Łuczak · 1992
Earlier work this paper cites.
“Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”
Michel X. Goemans and David P. Williamson · 1995
Earlier work this paper cites.
“A Fast quantum mechanical algorithm for database search” (1996)
Lov K. Grover · 1996
Earlier work this paper cites.
“Greed is good: Approximating independent sets in sparse and bounded-degree graphs”
M. M. Hallórsson and J. Radhakrishnan · 1997
Earlier work this paper cites.
“Large independent sets on random d d -regular graphs with fixed degree d d ” (2020)
Raffaele Marino and Scott Kirkpatrick · 2003
Earlier work this paper cites.
“The quantum approximate optimization algorithm needs to see the whole graph: A typical case” (2020)
Edward Farhi, David Gamarnik, and Sam Gutmann · 2004
Earlier work this paper cites.
“Max cut in cubic graphs”
Eran Halperin, Dror Livnat, and Uri Zwick · 2004
Earlier work this paper cites.
Edward Farhi, David Gamarnik, and Sam Gutmann · 2005
Earlier work this paper cites.
“Clustering of solutions in the random satisfiability problem”
M. Mézard, T. Mora, and R. Zecchina · 2005
Earlier work this paper cites.
“Regular trees in random regular graphs” (2006)
Eran Makover and Jeffrey McGowan · 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.
“Quantum algorithm for linear systems of equations”
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Earlier work this paper cites.
“The ising antiferromagnet and max cut on random regular graphs” (2020)
Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, and Gregory B. Sorkin · 2009
Earlier work this paper cites.
“Conjecture on the maximum cut and bisection width in random regular graphs”
Lenka Zdeborová and Stefan Boettcher · 2009
Earlier work this paper cites.
“Maxcut qaoa performance guarantees for p >1”
Jonathan Wurtz and Peter J. Love · 2010
Earlier work this paper cites.
“On independent sets in random graphs”
Amin Coja-Oghlan and Charilaos Efthymiou · 2010
Earlier work this paper cites.
“Optimal low-degree hardness of maximum independent set” (2020)
Alexander S. Wein · 2010
Earlier work this paper cites.
“On the solution-space geometry of random constraint satisfaction problems”
Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi · 2011
Earlier work this paper cites.
“Goals and opportunities in quantum simulation”
J. Ignacio Cirac and Peter Zoller · 2012
Earlier work this paper cites.
“Limits of local-global convergent graph sequences” (2012)
Hamed Hatami, László Lovász, and Balázs Szegedy · 2012
Earlier work this paper cites.
“Limits of local algorithms over sparse random graphs” (2013)
David Gamarnik and Madhu Sudan · 2013
Earlier work this paper cites.
“Quantum simulation”
I. M. Georgescu, S. Ashhab, and Franco Nori · 2014
Cited alongside, same era.
“A quantum approximate optimization algorithm” (2014)
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2014
Cited alongside, same era.
“Local algorithms for independent sets are half-optimal”
Mustazee Rahman and Balint Virag · 2014
Cited alongside, same era.
“Large cuts with local algorithms on triangle-free graphs” (2014) arXiv:1402.2543
Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela · 2014
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou · 2021
Later among the works it cites.
“Transferability of optimal qaoa parameters between random graphs” (2021)
Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro · 2021
Later among the works it cites.
“Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs”
Jonathan Wurtz and Danylo Lykov · 2021
Later among the works it cites.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke · 2021
Later among the works it cites.
“Classical algorithms and quantum limitations for maximum cut on high-girth graphs”
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
“Extremal cuts of sparse random graphs”
Amir Dembo, Andrea Montanari, and Subhabrata Sen · 2015
Cited alongside, same era.
“Quantum supremacy through the quantum approximate optimization algorithm” (2016)
Edward Farhi and Aram W Harrow · 2016
Cited alongside, same era.
“From the quantum approximate optimization algorithm to a quantum alternating operator ansatz”
Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas · 2017
Cited alongside, same era.
“Combinatorial optimization on gate model quantum computers: A survey” (2017)
Ehsan Zahedinejad and Arman Zaribafiyan · 2017
Cited alongside, same era.
“Suboptimality of local algorithms for a class of max-cut problems”
Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman · 2017
Cited alongside, same era.
“The sk model is infinite step replica symmetry breaking at zero temperature”
Antonio Auffinger, Wei-Kuo Chen, and Qiang Zeng · 2017
Cited alongside, same era.
“Cubic graphs with small independence ratio” (2017)
József Balogh, Alexandr Kostochka, and Xujun Liu · 2017
Cited alongside, same era.
Boaz Barak and Kunal Marwaha · 2021
Later among the works it cites.
“Local classical max-cut algorithm outperforms p = 2 p=2 qaoa on high-girth regular graphs”
Kunal Marwaha · 2021
Later among the works it cites.
Sami Boulebnane and Ashley Montanaro · 2021
Later among the works it cites.
“The overlap gap property: a geometric barrier to optimizing over random structures”
David Gamarnik · 2021
Later among the works it cites.
“Limitations of local quantum algorithms on random max-k-xor and beyond” (2021)
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi · 2021
Later among the works it cites.
“Benchmarking quantum coprocessors in an application-centric, hardware-agnostic, and scalable way”
Simon Martiel, Thomas Ayral, and Cyril Allouche · 2021
Later among the works it cites.
“Training variational quantum algorithms is np-hard”
Lennart Bittel and Martin Kliesch · 2021
Later among the works it cites.
Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel, and Yuri Alexeev · 2022
Later among the works it cites.
“The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size”
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou · 2022
Later among the works it cites.
“Recursive qaoa outperforms the original qaoa for the max-cut problem on complete graphs”
Eunok Bae and Soojoon Lee · 2022
Later among the works it cites.
“Reinforcement learning assisted recursive qaoa”
Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko · 2022
Later among the works it cites.
“Quantum optimization: Potential, challenges, and the path forward” (2023)
Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O’Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Victor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal · 2023
Later among the works it cites.
“A review on quantum approximate optimization algorithm and its variants”
Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer · 2023
Later among the works it cites.
Alexey Galda, Eesh Gupta, Jose Falla, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro · 2023
Later among the works it cites.
“Local algorithms and the failure of log-depth quantum advantage on sparse random csps” (2023)
Antares Chen, Neng Huang, and Kunal Marwaha · 2023
Later among the works it cites.
Friedrich Wagner, Jonas Nüßlein, and Frauke Liers · 2023
Later among the works it cites.
“Quantum-enhanced greedy combinatorial optimization solver”
Maxime Dupont, Bram Evert, Mark J. Hodson, Bhuvanesh Sundar, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B. Maciejewski, Stuart Hadfield, M. Sohaib Alam, Zhihui Wang, Shon Grabbe, P. Aaron Lott, Eleanor G. Rieffel, Davide Venturelli, and Matthew J. Reagor · 2023
Later among the works it cites.
“Quantum relax-and-round algorithm for combinatorial optimization” (2023)
Maxime Dupont and Bhuvanesh Sundar · 2023
Later among the works it cites.
“Quantum-informed recursive optimization algorithms” (2023)
Jernej Rudi Finžgar, Aron Kerschbaumer, Martin J. A. Schuetz, Christian B. Mendl, and Helmut G. Katzgraber · 2023
Later among the works it cites.
“Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson’s Max-Cut at Low Circuit Depths”
Reuben Tate, Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta · 2023
Later among the works it cites.
“The overlap gap property limits limit swapping in qaoa” (2024)
Mark Xin Hong Goh · 2024
Closest in time.