{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:49:57Z","timestamp":1778604597698,"version":"3.51.4"},"reference-count":29,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-1730082"],"award-info":[{"award-number":["CCF-1730082"]}]},{"name":"National Science Foundation","award":["2037984"],"award-info":[{"award-number":["2037984"]}]},{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["DE-AC02-06CH11357"],"award-info":[{"award-number":["DE-AC02-06CH11357"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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\u0151s-R\u00e9nyi graphs with up to 100 nodes.<\/jats:p>","DOI":"10.22331\/q-2022-08-22-781","type":"journal-article","created":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T12:19:16Z","timestamp":1661170756000},"page":"781","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":15,"title":["Quantum Local Search with the Quantum Alternating Operator Ansatz"],"prefix":"10.22331","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2610-8661","authenticated-orcid":false,"given":"Teague","family":"Tomesh","sequence":"first","affiliation":[{"name":"Department of Computer Science, Princeton University, Princeton, NJ 08540, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zain H.","family":"Saleem","sequence":"additional","affiliation":[{"name":"Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Suchara","sequence":"additional","affiliation":[{"name":"Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2022,8,22]]},"reference":[{"key":"0","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028, 2014."},{"key":"1","unstructured":"Stuart Andrew Hadfield. Quantum Algorithms for Scientific Computing and Approximate Optimization. arXiv preprint arXiv:1805.03265, 2018."},{"key":"2","doi-asserted-by":"publisher","unstructured":"Stuart Hadfield, Zhihui Wang, Bryan O\u2019Gorman, 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.","DOI":"10.3390\/a12020034"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Emile Aarts and Jan K. Lenstra. Local Search in Combinatorial Optimization. Princeton University Press, 2003. https:\/\/doi.org\/10.2307\/j.ctv346t9c.","DOI":"10.2307\/j.ctv346t9c"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1002\/qute.201900029"},{"key":"5","unstructured":"Edward Farhi and Aram W Harrow. Quantum Supremacy Through the Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1602.07674, 2016."},{"key":"6","doi-asserted-by":"publisher","unstructured":"Richard M Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, pages 85\u2013103. Springer, 1972. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"7","unstructured":"Teague Tomesh. quantum-local-search. https:\/\/github.com\/teaguetomesh\/quantum-local-search, 2021."},{"key":"8","unstructured":"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."},{"key":"9","unstructured":"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."},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1142\/S0219749920500112"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Daniel J Egger, Jakub Mare\u010dek, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, 2021. https:\/\/doi.org\/10.22331\/q-2021-06-17-479.","DOI":"10.22331\/q-2021-06-17-479"},{"key":"12","unstructured":"Zain H. Saleem, Teague Tomesh, Bilal Tariq, and Martin Suchara. Approaches to Constrained Quantum Approximate Optimization. arXiv preprint arXiv:2010.06660, 2020."},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41598-022-10555-8"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Santo Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75\u2013174, 2010. https:\/\/doi.org\/10.1016\/j.physrep.2009.11.002.","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"15","unstructured":"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."},{"key":"16","unstructured":"Princeton University Department of Computer Science. CS Cluster Computing. https:\/\/csguide.cs.princeton.edu\/resources\/clusters, 2022."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Ravi Boppana and Magn\u00fas M Halld\u00f3rsson. Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32:180\u2013196, 1992. https:\/\/doi.org\/10.1007\/BF01994876.","DOI":"10.1007\/BF01994876"},{"key":"18","unstructured":"Andrew Cross. The IBM Q experience and QISKit open-source quantum computing software. In APS March Meeting Abstracts, volume 2018, pages L58\u2013003, 2018."},{"key":"19","doi-asserted-by":"publisher","unstructured":"Diogo V Andrade, Mauricio GC Resende, and Renato F Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18:525\u2013547, 2012. https:\/\/doi.org\/10.1007\/s10732-012-9196-4.","DOI":"10.1007\/s10732-012-9196-4"},{"key":"20","unstructured":"Michael Krivelevich, Tam\u00e1s M\u00e9sz\u00e1ros, Peleg Michaeli, and Clara Shikhelman. Greedy Maximal Independent Sets via Local Limits. arXiv preprint arXiv:1907.07216, 2019."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Qinghua Wu and Jin-Kao Hao. A review on algorithms for maximum clique problems. European Journal of Operational Research, 242(3):693\u2013709, 2015. https:\/\/doi.org\/10.1016\/j.ejor.2014.09.064.","DOI":"10.1016\/j.ejor.2014.09.064"},{"key":"22","doi-asserted-by":"crossref","unstructured":"Vivek V. Shende and Igor L. Markov. On the CNOT-Cost of TOFFOLI Gates. Quantum Info. Comput., 9(5):461\u2013486, May 2009.","DOI":"10.26421\/QIC8.5-6-8"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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\u20132361, 2017. https:\/\/doi.org\/10.1007\/s10773-017-3389-4.","DOI":"10.1007\/s10773-017-3389-4"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Mark Saffman. Quantum computing with neutral atoms. National Science Review, 6(1):24\u201325, 2019. https:\/\/doi.org\/10.1093\/nsr\/nwy088.","DOI":"10.1093\/nsr\/nwy088"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Thomas B\u00e6kkegaard, 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.","DOI":"10.1038\/s41598-019-49657-1"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.129.063603"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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\u2013566, 2019. https:\/\/doi.org\/10.1145\/3307650.3322253.","DOI":"10.1145\/3307650.3322253"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-08-22-781\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T12:19:25Z","timestamp":1661170765000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-08-22-781\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,22]]},"references-count":29,"URL":"https:\/\/doi.org\/10.22331\/q-2022-08-22-781","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,22]]},"article-number":"781"}}