{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:46:06Z","timestamp":1740181566810,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,1,30]],"date-time":"2023-01-30T00:00:00Z","timestamp":1675036800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,30]],"date-time":"2023-01-30T00:00:00Z","timestamp":1675036800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"DOI":"10.1007\/s42979-022-01638-4","type":"journal-article","created":{"date-parts":[[2023,1,30]],"date-time":"2023-01-30T12:02:53Z","timestamp":1675080173000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Approaches to Constrained Quantum Approximate Optimization"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8182-2764","authenticated-orcid":false,"given":"Zain H.","family":"Saleem","sequence":"first","affiliation":[]},{"given":"Teague","family":"Tomesh","sequence":"additional","affiliation":[]},{"given":"Bilal","family":"Tariq","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Suchara","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,30]]},"reference":[{"issue":"4","key":"1638_CR1","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/s00453-008-9251-6","volume":"53","author":"C Amb\u00fchl","year":"2009","unstructured":"Amb\u00fchl C, Mastrolilli Monaldo. Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica. 2009;53(4):488.","journal-title":"Algorithmica"},{"issue":"7848","key":"1638_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1038\/s41586-021-03202-1","volume":"591","author":"JM Arrazola","year":"2021","unstructured":"Arrazola JM, Bergholm V, Br\u00e1dler K, Bromley TR, Collins MJ, Dhand I, Fumagalli A, Gerrits T, Goussev A, Helt LG, et al. Quantum circuits with many photons on a programmable nanophotonic chip. Nature. 2021;591(7848):54\u201360.","journal-title":"Nature"},{"issue":"7779","key":"1638_CR3","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, Biswas R, Boixo S, Brandao FGSL, Buell DA, et al. Quantum supremacy using a programmable superconducting processor. Nature. 2019;574(7779):505\u201310.","journal-title":"Nature"},{"key":"1638_CR4","unstructured":"Auyeung A, Abraham A. The largest compatible subset problem for phylogenetic data. 2004. arXiv preprint arXiv:cs\/0405025."},{"key":"1638_CR5","unstructured":"Cain M, Farhi E, Gutmann S, Ranard D, Tang E. The qaoa gets stuck starting from a good classical string, 2022. arXiv:2207.05089."},{"key":"1638_CR6","doi-asserted-by":"crossref","unstructured":"Chen S, Liu Y, Otten M, Seif A, Fefferman B, Jiang L. The learnability of pauli noise. 2022. arXiv preprint arXiv:2206.06362.","DOI":"10.1038\/s41467-022-35759-4"},{"key":"1638_CR7","unstructured":"Crooks GE. Performance of the quantum approximate optimization algorithm on the maximum cut problem. 2018. arXiv preprint arXiv:1811.08419."},{"key":"1638_CR8","doi-asserted-by":"publisher","first-page":"264","DOI":"10.22331\/q-2020-05-11-264","volume":"4","author":"AM Dalzell","year":"2020","unstructured":"Dalzell AM, Harrow AW, Koh DE, La\u00a0Placa RL. How many qubits are needed for quantum computational supremacy? Quantum. 2020;4:264.","journal-title":"Quantum"},{"key":"1638_CR9","doi-asserted-by":"publisher","first-page":"479","DOI":"10.22331\/q-2021-06-17-479","volume":"5","author":"DJ Egger","year":"2021","unstructured":"Egger DJ, Mare\u010dek J, Woerner S. Warm-starting quantum optimization. Quantum. 2021;5:479.","journal-title":"Quantum"},{"key":"1638_CR10","unstructured":"Farhi E, Harrow AW. Quantum supremacy through the quantum approximate optimization algorithm. 2016. arXiv preprint arXiv:1602.07674."},{"key":"1638_CR11","unstructured":"Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm. 2014. arXiv preprint arXiv:1411.4028."},{"key":"1638_CR12","unstructured":"Farhi E, Gamarnik D, Gutmann S. The Quantum Approximate Optimization Algorithm needs to see the whole graph: worst case examples. 2020. arXiv preprint arXiv:2005.08747."},{"key":"1638_CR13","unstructured":"Farhi E, Gamarnik D, Gutmann S. The Quantum Approximate Optimization Algorithm needs to see the whole graph: a typical case. 2020. arXiv preprint arXiv:2004.09002."},{"issue":"6","key":"1638_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.3390\/a15060202","volume":"15","author":"FG Fuchs","year":"2022","unstructured":"Fuchs FG, Lye KO, M\u00f8llNilsen H, Stasik AJ, Sartor G. Constraint preserving mixers for the quantum approximate optimization algorithm. Algorithms. 2022;15(6):202.","journal-title":"Algorithms"},{"issue":"1","key":"1638_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41534-016-0004-0","volume":"3","author":"JM Gambetta","year":"2017","unstructured":"Gambetta JM, Chow JM, Steffen M. Building logical qubits in a superconducting quantum computing system. npj Quantum Inf. 2017;3(1):1\u20137.","journal-title":"npj Quantum Inf"},{"issue":"2","key":"1638_CR16","doi-asserted-by":"publisher","first-page":"34","DOI":"10.3390\/a12020034","volume":"12","author":"S Hadfield","year":"2019","unstructured":"Hadfield S, Wang Z, O\u2019Gorman B, Rieffel EG, Venturelli D, Biswas R. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms. 2019;12(2):34.","journal-title":"Algorithms"},{"key":"1638_CR17","volume-title":"Quantum algorithms for scientific computing and approximate optimization","author":"SA Hadfield","year":"2018","unstructured":"Hadfield SA. Quantum algorithms for scientific computing and approximate optimization. Columbia University; 2018."},{"issue":"7","key":"1638_CR18","doi-asserted-by":"publisher","first-page":"2350","DOI":"10.1007\/s10773-017-3389-4","volume":"56","author":"Y He","year":"2017","unstructured":"He Y, Luo M-X, Zhang E, Wang H-K, Wang X-F. Decompositions of n-qubit Toffoli gates with linear circuit complexity. Int J Theoret Phys. 2017;56(7):2350\u201361.","journal-title":"Int J Theoret Phys"},{"issue":"2","key":"1638_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11128-021-03001-7","volume":"20","author":"R Herrman","year":"2021","unstructured":"Herrman R, Ostrowski J, Humble TS, Siopsis G. Lower bounds on circuit depth of the quantum approximate optimization algorithm. Quantum Inf Process. 2021;20(2):1\u201317.","journal-title":"Quantum Inf Process"},{"key":"1638_CR20","doi-asserted-by":"crossref","unstructured":"Kalra A, Qureshi F, Tisi M. Portfolio asset identification using graph algorithms on a quantum annealer. 2018 Available at SSRN 3333537.","DOI":"10.2139\/ssrn.3333537"},{"key":"1638_CR21","unstructured":"Karp RM. Reducibility among combinatorial problems. In: Complexity of computer computations: proceedings of a symposium on the complexity of computer computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program. IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, Springer, US; 1972. p. 85\u2013103."},{"key":"1638_CR22","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas A. Ising formulations of many NP problems. Front Phys. 2014;2:5.","journal-title":"Front Phys"},{"key":"1638_CR23","unstructured":"Pichler H, Wang S-T, Zhou L, Choi S, Lukin MD. Quantum optimization for maximum independent set using rydberg atom arrays. 2018. arXiv preprint arXiv:1808.10816."},{"key":"1638_CR24","unstructured":"Porras D et\u00a0al. Hybrid quantum-classical optimization for financial index tracking. 2021. Technical report, arXiv. org."},{"key":"1638_CR25","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill J. Quantum computing in the NISQ era and beyond. Quantum. 2018;2:79.","journal-title":"Quantum"},{"key":"1638_CR26","doi-asserted-by":"crossref","unstructured":"Safar M, Habib S. Hard constrained vertex-cover communication algorithm for WSN. In: International Conference on embedded and ubiquitous computing, Vol. 4808. 2007; p. 635\u2013649. Springer.","DOI":"10.1007\/978-3-540-77092-3_55"},{"issue":"20","key":"1638_CR27","doi-asserted-by":"publisher","DOI":"10.1088\/0953-4075\/49\/20\/202001","volume":"49","author":"M Saffman","year":"2016","unstructured":"Saffman M. Quantum computing with atomic qubits and Rydberg interactions: progress and challenges. J Phys B: At Mol Opt Phys. 2016;49(20): 202001.","journal-title":"J Phys B: At Mol Opt Phys"},{"issue":"1","key":"1638_CR28","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1093\/nsr\/nwy088","volume":"6","author":"M Saffman","year":"2019","unstructured":"Saffman M. Quantum computing with neutral atoms. Natl Sci Rev. 2019;6(1):24\u20135.","journal-title":"Natl Sci Rev"},{"key":"1638_CR29","unstructured":"Saleem ZH, Tomesh T, Perlin MA, Gokhale P, Suchara M. Quantum divide and conquer for combinatorial optimization and distributed computing. 2021. arXiv preprint arXiv:2107.07532."},{"issue":"04","key":"1638_CR30","doi-asserted-by":"publisher","first-page":"2050011","DOI":"10.1142\/S0219749920500112","volume":"18","author":"H SaleemZain","year":"2020","unstructured":"SaleemZain H. Max-independent set and the quantum alternating operator ansatz. Int J Quantum Inf. 2020;18(04):2050011.","journal-title":"Int J Quantum Inf"},{"issue":"3","key":"1638_CR31","doi-asserted-by":"publisher","first-page":"032311","DOI":"10.1103\/PhysRevA.75.032311","volume":"75","author":"C Sch\u00f6n","year":"2007","unstructured":"Sch\u00f6n C, Hammerer K, Wolf MM, Cirac JI, Solano E. Sequential generation of matrix-product states in cavity QED. Phys Rev A. 2007;75(3):032311.","journal-title":"Phys Rev A"},{"key":"1638_CR32","doi-asserted-by":"crossref","unstructured":"Shaydulin R, Lotshaw PC, Larson J, Ostrowski J, Humble TS. Parameter transfer for quantum approximate optimization of weighted maxcut. 2022. arXiv preprint arXiv:2201.11785.","DOI":"10.1145\/3584706"},{"issue":"5","key":"1638_CR33","first-page":"461","volume":"9","author":"VV Shende","year":"2009","unstructured":"Shende VV, Markov IL. On the CNOT-cost of TOFFOLI gates. Quantum Inf Comput. 2009;9(5):461\u201386 (ISSN 1533-7146).","journal-title":"Quantum Inf Comput"},{"key":"1638_CR34","unstructured":"Tomesh T. quantum-constrained-optimization. 2022. https:\/\/github.com\/teaguetomesh\/quantum-constrained-optimization."},{"key":"1638_CR35","doi-asserted-by":"publisher","first-page":"781","DOI":"10.22331\/q-2022-08-22-781","volume":"6","author":"T Tomesh","year":"2022","unstructured":"Tomesh T, Saleem ZH, Suchara M. Quantum local search with the quantum alternating operator ansatz. Quantum. 2022;6:781.","journal-title":"Quantum"},{"key":"1638_CR36","doi-asserted-by":"publisher","unstructured":"Virtanen P, Gommers R, Oliphant TE, Haberland M, Reddy T, Cournapeau D, Burovski E, Peterson P, Weckesser W, Bright J, van der Walt SJ, Brett M, Wilson J, Jarrod MK., Mayorov N, Nelson ARJ, Jones E, Kern R, Larson E, Carey C J, Polat \u0130, Feng Y, Moore EW, Vander Plas J, Laxalde D, Perktold J, Cimrman R, Henriksen I, Quintero E.A, Harris CR, Archibald AM, Ribeiro AH, Pedregosa F, van Mulbregt P, SciPy 1.0 Contributors.. SciPy 10: fundamental algorithms for scientific computing in Python. Nat Methods. 2020;17:261\u201372. https:\/\/doi.org\/10.1038\/s41592-019-0686-2.","DOI":"10.1038\/s41592-019-0686-2"},{"issue":"4","key":"1638_CR37","doi-asserted-by":"publisher","first-page":"042335","DOI":"10.1103\/PhysRevA.79.042335","volume":"79","author":"H Wang","year":"2009","unstructured":"Wang H, Ashhab S, Nori F. Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer. Phys Rev A. 2009;79(4):042335.","journal-title":"Phys Rev A"},{"issue":"2","key":"1638_CR38","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.97.022304","volume":"97","author":"Z Wang","year":"2018","unstructured":"Wang Z, Hadfield S, Jiang Z, Rieffel EG. Quantum approximate optimization algorithm for MaxCut: a fermionic view. Phys Rev A. 2018;97(2): 022304.","journal-title":"Phys Rev A"},{"issue":"1","key":"1638_CR39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.101.012320","volume":"101","author":"Z Wang","year":"2020","unstructured":"Wang Z, Rubin NC, Dominy JM, Rieffel EG. XY mixers: analytical and numerical results for the quantum alternating operator ansatz. Phys Rev A. 2020;101(1): 012320.","journal-title":"Phys Rev A"},{"issue":"1","key":"1638_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-019-13534-2","volume":"10","author":"K Wright","year":"2019","unstructured":"Wright K, Beck KM, Debnath S, Amini JM, Nam Y, Grzesiak N, Chen JS, Pisenti NC, Chmielewski M, Collins C, et al. Benchmarking an 11-qubit quantum computer. Nat Commun. 2019;10(1):1\u20136.","journal-title":"Nat Commun"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01638-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-022-01638-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01638-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T03:29:31Z","timestamp":1679542171000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-022-01638-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,30]]},"references-count":40,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["1638"],"URL":"https:\/\/doi.org\/10.1007\/s42979-022-01638-4","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2023,1,30]]},"assertion":[{"value":"29 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"183"}}