Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms

M. Halldórsson and J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (1994) pp. 439–448

1994

Earlier work this paper cites.

T. Kadowaki and H. Nishimori, Quantum annealing in the transverse ising model, Physical Review E 58

1998

Earlier work this paper cites.

P. K. Agarwal, M. Van Kreveld, and S. Suri, Label placement by maximum independent set in rectangles, Computational Geometry 11

1998

Earlier work this paper cites.

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arxiv (2000) , arXiv:quant-ph/0001106 [quant-ph]

2000

Earlier work this paper cites.

S. Butenko, Maximum independent set and related problems, with applications (University of Florida, 2003)

2003

Earlier work this paper cites.

S. Sakai, M. Togasaki, and K. Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem, Discrete Applied Mathematics 126

2003

Earlier work this paper cites.

E. Farhi, D. Gamarnik, and S. Gutmann, The quantum approximate optimization algorithm needs to see the whole graph: A typical case, arXiv preprint arXiv:2004.09002 (2020a)

Original

2004

Earlier work this paper cites.

E. Farhi, D. Gamarnik, and S. Gutmann, The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples, arXiv preprint arXiv:2005.08747 (2020b)

Original

2005

Earlier work this paper cites.

C. Bazgan, B. Escoffier, and V. T. Paschos, Completeness in standard and differential approximation classes: Poly-(D) APX-and (D) PTAS-completeness, Theoretical Computer Science 339

2005

Earlier work this paper cites.

A. Vahdatpour, F. Dabiri, M. Moazeni, and M. Sarrafzadeh, Theoretical bound and practical analysis of connected dominating set in ad hoc and sensor networks, in Distributed Computing: 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings 22 (Springer, 2008) pp. 481–495

2008

Earlier work this paper cites.

S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Hybrid quantum-classical algorithms for approximate graph coloring, arXiv preprint arXiv:2011.13420 (2020b)

Original

2011

Earlier work this paper cites.

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and approximation: Combinatorial optimization problems and their approximability properties (Springer Science & Business Media, 2012)

2012

Earlier work this paper cites.

E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014)

2014

Earlier work this paper cites.

A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5

2014

Earlier work this paper cites.

While, as we have seen, the lowest depth quantum expectation values can be efficiently computed classically, efficient classical sampling from said circuits is not believed to be possible Farhi et al. 2014 ; Farhi and Harrow 2016 which hints at further possibilities for quantum advantage in practice

2016

Earlier work this paper cites.

E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algorithm, arXiv preprint arXiv:1602.07674 (2016)

Original

2016

Earlier work this paper cites.

Approaches for MIS not directly related to QAOA have also been proposed such as Ref. Yu et al. 2021 ; Djidjev et al. 2018

2018

Earlier work this paper cites.

Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quantum approximate optimization algorithm for maxcut: A fermionic view, Physical Review A 97

2018

Earlier work this paper cites.

S. A. Hadfield, Quantum algorithms for scientific computing and approximate optimization (Columbia University, 2018)

2018

Cited alongside, same era.

T. Albash and D. A. Lidar, Adiabatic quantum computation, Reviews of Modern Physics 90

2018

Cited alongside, same era.

H. N. Djidjev, G. Chapuis, G. Hahn, and G. Rizk, Efficient combinatorial optimization using quantum annealing, arXiv preprint arXiv:1801.08653 (2018)

Original

2018

Cited alongside, same era.

S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12

2019

Cited alongside, same era.

Z. H. Saleem, Max-independent set and the quantum alternating operator ansatz, International Journal of Quantum Information 18

2020

Y. J. Patel, S. Jerbi, T. Bäck, and V. Dunjko, Reinforcement learning assisted recursive qaoa (2022), arXiv:2207.06294 [quant-ph]

Original

2022

Later among the works it cites.

R. Ayanzadeh, J. Dorband, M. Halem, and T. Finin, Quantum-assisted greedy algorithms, in IGARSS 2022-2022 IEEE International Geoscience and Remote Sensing Symposium (IEEE, 2022) pp. 4911–4914

2022

Later among the works it cites.

M. J. Schuetz, J. K. Brubaker, and H. G. Katzgraber, Combinatorial optimization with physics-inspired graph neural networks, Nature Machine Intelligence 4

2022

Later among the works it cites.

A. Ozaeta, W. van Dam, and P. L. McMahon, Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems, Quantum Science and Technology 7

2022

Later among the works it cites.