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.
Abstract
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.
Featured image: An illustrative example of the quantum local search algorithm constructing a local neighborhood within a larger graph.
Popular summary
► BibTeX data
► References
[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028, 2014.
arXiv:1411.4028
[2] Stuart Andrew Hadfield. Quantum Algorithms for Scientific Computing and Approximate Optimization. arXiv preprint arXiv:1805.03265, 2018.
arXiv:1805.03265
[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.
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.
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.
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.
arXiv:1602.07674
[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.
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.
https://github.com/teaguetomesh/quantum-local-search
[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.
arXiv:2005.08747
[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.
arXiv:2004.09002
[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.
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.
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.
arXiv:2010.06660
[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.
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.
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.
https://www.osti.gov/biblio/960616
[17] Princeton University Department of Computer Science. CS Cluster Computing. https://csguide.cs.princeton.edu/resources/clusters, 2022.
https://csguide.cs.princeton.edu/resources/clusters
[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.
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.
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.
arXiv:1907.07216
[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.
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.
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.
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.
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.
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.
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.
https://doi.org/10.1145/3307650.3322253
Cited by
[1] Zain H. Saleem, Teague Tomesh, Michael A. Perlin, Pranav Gokhale, and Martin Suchara, “Divide and Conquer for Combinatorial Optimization and Distributed Quantum Computation”, arXiv:2107.07532.
The above citations are from SAO/NASA ADS (last updated successfully 2022-08-22 12:17:18). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2022-08-22 12:17:16: Could not fetch cited-by data for 10.22331/q-2022-08-22-781 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
