Hybrid quantum-classical algorithms for approximate graph coloring

How well can a graph be n n -colored?

Paul M. B. Vitányi · 1981

Earlier work this paper cites.

The asymptotic distribution of short cycles in random regular graphs

Nicholas C. Wormald · 1981

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 spectral technique for coloring random 3-colorable graphs

Noga Alon and Nabil Kahale · 1997

Earlier work this paper cites.

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION

Alan Frieze and M. Jerrum · 1997

Earlier work this paper cites.

On the Hardness of Approximating Max k-Cut and its Dual

Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi · 1997

Earlier work this paper cites.

Fast Approximation Algorithms on Maxcut, k-Coloring, and k-Color Ordering for VLSI Applications

Jun-Dong Cho, S. Raje, and M. Sarrafzadeh · 1998

Earlier work this paper cites.

Approximation Algorithms for MAX-3-CUT and Other Problems via Complex Semidefinite Programming

Michel X. Goemans and David Williamson · 2001

Earlier work this paper cites.

Policy Gradient based Quantum Approximate Optimization Algorithm, 2020

Jiahao Yao, Marin Bukov, and Lin Lin · 2002

Cited alongside, same era.

On Approximate Graph Colouring and MAX- k k -CUT Algorithms Based on the ϑ \vartheta -Function

Etienne Klerk, Dmitrii Pasechnik, and J.P. Warners · 2004

Cited alongside, same era.

The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples, 2020

Edward Farhi, David Gamarnik, and Sam Gutmann · 2005

Cited alongside, same era.

Max- k k -cut and approximating the chromatic number of random graphs

Amin Coja-Oghlan, Cristopher Moore, and Vishal Sanwalani · 2006

Cited alongside, same era.

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007

Cited alongside, same era.

Bridging Classical and Quantum with SDP initialized warm-starts for QAOA, 2020

For Fixed Control Parameters the Quantum Approximate Optimization Algorithm’s Objective Function Value Concentrates for Typical Instances, 2018

Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven · 2018

Later among the works it cites.

Barren plateaus in quantum neural network training landscapes

Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven · 2018

Later among the works it cites.

Complex Semidefinite Programming and Max-k-Cut

Alantha Newman · 2018

Later among the works it cites.

Quantum approximate optimization algorithm for MaxCut: A fermionic view

Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel · 2018

Later among the works it cites.

Multistart Methods for Quantum Approximate Optimization

Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson · 2019

Later among the works it cites.

Obstacles to variational quantum optimization from symmetry protection