Quantum Local Search with the Quantum Alternating Operator Ansatz

Teague Tomesh1, Zain H. Saleem2, and Martin Suchara2

1Department of Computer Science, Princeton University, Princeton, NJ 08540, USA.
2Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439, USA.

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We study the performance of this algorithm on 3-regular, Community, and Erdős-Rényi graphs with up to 100 nodes.

Current quantum computers are limited in terms of both their size and quality. This is an issue if our goal is to solve problems on typical, real-world data sets which may contain many thousands or millions of points. To help circumvent this restriction we investigate algorithms which combine the efforts of both classical and quantum computers to help extend the reach of current quantum systems. Specifically, we consider a local search algorithm which allows a hybrid quantum-classical system to solve very large problems by iteratively solving many smaller subproblems. We hope that such methods will be useful in extending the capabilities of quantum-classical systems now and in the future.

► BibTeX data

► References

[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028, 2014.

[2] Stuart Andrew Hadfield. Quantum Algorithms for Scientific Computing and Approximate Optimization. arXiv preprint arXiv:1805.03265, 2018.

[3] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. Algorithms, 12(2):34, 2019. https:/​/​doi.org/​10.3390/​a12020034.

[4] Emile Aarts and Jan K. Lenstra. Local Search in Combinatorial Optimization. Princeton University Press, 2003. https:/​/​doi.org/​10.2307/​j.ctv346t9c.

[5] Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Ilya Safro, Susan Mniszewski, and Yuri Alexeev. Network Community Detection on Small Quantum Computers. Advanced Quantum Technologies, 2(9):1900029, 2019. https:/​/​doi.org/​10.1002/​qute.201900029.

[6] Edward Farhi and Aram W Harrow. Quantum Supremacy Through the Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1602.07674, 2016.

[7] Richard M Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, pages 85–103. Springer, 1972. https:/​/​doi.org/​10.1007/​978-1-4684-2001-2_9.

[8] Teague Tomesh. quantum-local-search. https:/​/​github.com/​teaguetomesh/​quantum-local-search, 2021.

[9] Edward Farhi, David Gamarnik, and Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples. arXiv preprint arXiv:2005.08747, 2020.

[10] Edward Farhi, David Gamarnik, and Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. arXiv preprint arXiv:2004.09002, 2020.

[11] Zain Hamid Saleem. Max-independent set and the quantum alternating operator ansatz. International Journal of Quantum Information, 18(04):2050011, 2020. https:/​/​doi.org/​10.1142/​S0219749920500112.

[12] Daniel J Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, 2021. https:/​/​doi.org/​10.22331/​q-2021-06-17-479.

[13] Zain H. Saleem, Teague Tomesh, Bilal Tariq, and Martin Suchara. Approaches to Constrained Quantum Approximate Optimization. arXiv preprint arXiv:2010.06660, 2020.

[14] Rebekah Herrman, Phillip C Lotshaw, James Ostrowski, Travis S Humble, and George Siopsis. Multi-angle quantum approximate optimization algorithm. Scientific Reports, 12(6781), 2022. https:/​/​doi.org/​10.1038/​s41598-022-10555-8.

[15] Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75–174, 2010. https:/​/​doi.org/​10.1016/​j.physrep.2009.11.002.

[16] Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab. (LANL), Los Alamos, NM, United States, 2008. https:/​/​www.osti.gov/​biblio/​960616.

[17] Princeton University Department of Computer Science. CS Cluster Computing. https:/​/​csguide.cs.princeton.edu/​resources/​clusters, 2022.

[18] Ravi Boppana and Magnús M Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32:180–196, 1992. https:/​/​doi.org/​10.1007/​BF01994876.

[19] Andrew Cross. The IBM Q experience and QISKit open-source quantum computing software. In APS March Meeting Abstracts, volume 2018, pages L58–003, 2018.

[20] Diogo V Andrade, Mauricio GC Resende, and Renato F Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18:525–547, 2012. https:/​/​doi.org/​10.1007/​s10732-012-9196-4.

[21] Michael Krivelevich, Tamás Mészáros, Peleg Michaeli, and Clara Shikhelman. Greedy Maximal Independent Sets via Local Limits. arXiv preprint arXiv:1907.07216, 2019.

[22] Qinghua Wu and Jin-Kao Hao. A review on algorithms for maximum clique problems. European Journal of Operational Research, 242(3):693–709, 2015. https:/​/​doi.org/​10.1016/​j.ejor.2014.09.064.

[23] Vivek V. Shende and Igor L. Markov. On the CNOT-Cost of TOFFOLI Gates. Quantum Info. Comput., 9(5):461–486, May 2009.

[24] Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang, and Xiao-Feng Wang. Decompositions of n-qubit Toffoli Gates with Linear Circuit Complexity. International Journal of Theoretical Physics, 56(7):2350–2361, 2017. https:/​/​doi.org/​10.1007/​s10773-017-3389-4.

[25] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A, 52(5):3457, 1995. https:/​/​doi.org/​10.1103/​PhysRevA.52.3457.

[26] Mark Saffman. Quantum computing with neutral atoms. National Science Review, 6(1):24–25, 2019. https:/​/​doi.org/​10.1093/​nsr/​nwy088.

[27] Thomas Bækkegaard, LB Kristensen, Niels JS Loft, Christian Kraglund Andersen, David Petrosyan, and Nikolaj T Zinner. Realization of efficient quantum gates with a superconducting qubit-qutrit circuit. Scientific Reports, 9:13389, 2019. https:/​/​doi.org/​10.1038/​s41598-019-49657-1.

[28] Or Katz, Marko Cetina, and Christopher Monroe. $N$-Body Interactions between Trapped Ion Qubits via Spin-Dependent Squeezing. Phys. Rev. Lett., 129:063603, Aug 2022. https:/​/​doi.org/​10.1103/​PhysRevLett.129.063603.

[29] Pranav Gokhale, Jonathan M Baker, Casey Duckering, Natalie C Brown, Kenneth R Brown, and Frederic T Chong. Asymptotic Improvements to Quantum Circuits via Qutrits. In Proceedings of the 46th International Symposium on Computer Architecture, pages 554–566, 2019. https:/​/​doi.org/​10.1145/​3307650.3322253.

Cited by

[1] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger, and Benjamin Weder, "Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices", Quantum Science and Technology 8 4, 045022 (2023).

[2] Elham Torabian and Roman V. Krems, "Compositional optimization of quantum circuits for quantum kernels of support vector machines", Physical Review Research 5 1, 013211 (2023).

[3] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun, and Marco Pistoia, "Alignment between initial state and mixer improves QAOA performance for constrained optimization", npj Quantum Information 9 1, 121 (2023).

[4] Teague Tomesh, Zain H. Saleem, Michael A. Perlin, Pranav Gokhale, Martin Suchara, and Margaret Martonosi, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 1 (2023) ISBN:979-8-3503-4323-6.

[5] Zain H. Saleem, Teague Tomesh, Bilal Tariq, and Martin Suchara, "Approaches to Constrained Quantum Approximate Optimization", SN Computer Science 4 2, 183 (2023).

[6] David Bucher, Jonas Nüßlein, Corey O'Meara, Ivan Angelov, Benedikt Wimmer, Kumar Ghosh, Giorgio Cortiana, and Claudia Linnhoff-Popien, "Dynamic Price Incentivization for Carbon Emission Reduction using Quantum Optimization", arXiv:2309.05502, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-19 09:12:42) and SAO/NASA ADS (last updated successfully 2024-04-19 09:12:43). The list may be incomplete as not all publishers provide suitable and complete citation data.