{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T21:09:12Z","timestamp":1788296952080,"version":"build-2803163510"},"reference-count":35,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T00:00:00Z","timestamp":1679011200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["Y1067-N27"],"award-info":[{"award-number":["Y1067-N27"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We introduce parity quantum optimization with the aim of solving optimization problems consisting of arbitrary <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>-body interactions and side conditions using planar quantum chip architectures. The method introduces a decomposition of the problem graph with arbitrary <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>-body terms using generalized closed cycles of a hypergraph. Side conditions of the optimization problem in form of hard constraints can be included as open cycles containing the terms involved in the side conditions. The generalized parity mapping thus circumvents the need to translate optimization problems to a quadratic unconstrained binary optimization problem (QUBO) and allows for the direct encoding of higher-order constrained binary optimization problems (HCBO) on a square lattice and full parallelizability of gates.<\/jats:p>","DOI":"10.22331\/q-2023-03-17-950","type":"journal-article","created":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T09:55:52Z","timestamp":1679046952000},"page":"950","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":28,"title":["Parity Quantum Optimization: Compiler"],"prefix":"10.22331","volume":"7","author":[{"given":"Kilian","family":"Ender","sequence":"first","affiliation":[{"name":"Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria"},{"name":"Institute for Theoretical Physics, University of Innsbruck, A-6020 Innsbruck, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roeland","family":"ter Hoeven","sequence":"additional","affiliation":[{"name":"Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria"},{"name":"Institute for Theoretical Physics, University of Innsbruck, A-6020 Innsbruck, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin E.","family":"Niehoff","sequence":"additional","affiliation":[{"name":"Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maike","family":"Drieb-Sch\u00f6n","sequence":"additional","affiliation":[{"name":"Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria"},{"name":"Institute for Theoretical Physics, University of Innsbruck, A-6020 Innsbruck, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wolfgang","family":"Lechner","sequence":"additional","affiliation":[{"name":"Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria"},{"name":"Institute for Theoretical Physics, University of Innsbruck, A-6020 Innsbruck, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2023,3,17]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. ``Optimization by simulated annealing&apos;&apos;. Science 220, 671\u2013680 (1983).","DOI":"10.1126\/science.220.4598.671"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Andrew Lucas. ``Ising formulations of many np problems&apos;&apos;. Frontiers in Physics 2, 5 (2014).","DOI":"10.3389\/fphy.2014.00005"},{"key":"2","doi-asserted-by":"publisher","unstructured":"J. I. Cirac and P. Zoller. ``Quantum computations with cold trapped ions&apos;&apos;. Phys. Rev. Lett. 74, 4091\u20134094 (1995).","DOI":"10.1103\/PhysRevLett.74.4091"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Rainer Blatt and Christian F Roos. ``Quantum simulations with trapped ions&apos;&apos;. Nature Physics 8, 277\u2013284 (2012).","DOI":"10.1038\/nphys2252"},{"key":"4","doi-asserted-by":"publisher","unstructured":"David Kielpinski, Chris Monroe, and David J Wineland. ``Architecture for a large-scale ion-trap quantum computer&apos;&apos;. Nature 417, 709\u2013711 (2002).","DOI":"10.1038\/nature00784"},{"key":"5","doi-asserted-by":"publisher","unstructured":"D Jaksch, JI Cirac, P Zoller, et al. ``Fast quantum gates for neutral atoms&apos;&apos;. Phys. Rev. Lett. 85, 2208\u20132211 (2000).","DOI":"10.1103\/PhysRevLett.85.2208"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Lo\u00efc Henriet, Lucas Beguin, Adrien Signoles, et al. ``Quantum computing with neutral atoms&apos;&apos;. Quantum 4, 327 (2020).","DOI":"10.22331\/q-2020-09-21-327"},{"key":"7","doi-asserted-by":"publisher","unstructured":"M. Saffman, T. G. Walker, and K. M\u00f8lmer. ``Quantum information with rydberg atoms&apos;&apos;. Rev. Mod. Phys. 82, 2313\u20132363 (2010).","DOI":"10.1103\/RevModPhys.82.2313"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Immanuel Bloch, Jean Dalibard, and Wilhelm Zwerger. ``Many-body physics with ultracold gases&apos;&apos;. Rev. Mod. Phys. 80, 885\u2013964 (2008).","DOI":"10.1103\/RevModPhys.80.885"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Hannes Bernien, Sylvain Schwartz, Alexander Keesling, et al. ``Probing many-body dynamics on a 51-atom quantum simulator&apos;&apos;. Nature 551, 579\u2013584 (2017).","DOI":"10.1038\/nature24622"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Jens Koch, Terri M. Yu, Jay Gambetta, et al. ``Charge-insensitive qubit design derived from the cooper pair box&apos;&apos;. Phys. Rev. A 76, 042319 (2007).","DOI":"10.1103\/PhysRevA.76.042319"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Andreas Wallraff, David I Schuster, Alexandre Blais, et al. ``Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamics&apos;&apos;. Nature 431, 162\u2013167 (2004).","DOI":"10.1038\/nature02851"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, et al. ``Quantum annealing with manufactured spins&apos;&apos;. Nature 473, 194\u2013198 (2011).","DOI":"10.1038\/nature10012"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Frank Arute, Kunal Arya, Ryan Babbush, et al. ``Quantum supremacy using a programmable superconducting processor&apos;&apos;. Nature 574, 505\u2013510 (2019).","DOI":"10.1038\/s41586-019-1666-5"},{"key":"14","doi-asserted-by":"publisher","unstructured":"L Childress, MV Gurudev Dutt, JM Taylor, et al. ``Coherent dynamics of coupled electron and nuclear spin qubits in diamond&apos;&apos;. Science 314, 281\u2013285 (2006).","DOI":"10.1126\/science.1131871"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Jeremy L O&apos;brien, Akira Furusawa, and Jelena Vu\u010dkovi\u0107. ``Photonic quantum technologies&apos;&apos;. Nature Photonics 3, 687\u2013695 (2009).","DOI":"10.1038\/nphoton.2009.229"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Xiaogang Qiang, Xiaoqi Zhou, Jianwei Wang, et al. ``Large-scale silicon quantum photonics implementing arbitrary two-qubit processing&apos;&apos;. Nature photonics 12, 534\u2013539 (2018).","DOI":"10.1038\/s41566-018-0236-y"},{"key":"17","doi-asserted-by":"publisher","unstructured":"G. G. Guerreschi and A. Y. Matsuura. ``Qaoa for max-cut requires hundreds of qubits for quantum speed-up&apos;&apos;. Scientific Reports 9, 6903 (2019).","DOI":"10.1038\/s41598-019-43176-9"},{"key":"18","unstructured":"Edward Farhi, David Gamarnik, and Sam Gutmann. ``The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples&apos;&apos; (2020). arXiv:2005.08747."},{"key":"19","doi-asserted-by":"publisher","unstructured":"Tameem Albash and Daniel A. Lidar. ``Adiabatic quantum computation&apos;&apos;. Rev. Mod. Phys. 90, 015002 (2018).","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Tadashi Kadowaki and Hidetoshi Nishimori. ``Quantum annealing in the transverse ising model&apos;&apos;. Phys. Rev. E 58, 5355\u20135363 (1998).","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, et al. ``Perspectives of quantum annealing: methods and implementations&apos;&apos;. Reports on Progress in Physics 83, 054401 (2020).","DOI":"10.1088\/1361-6633\/ab85b8"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Rongxin Xia, Teng Bian, and Sabre Kais. ``Electronic structure calculations and the ising hamiltonian&apos;&apos;. The Journal of Physical Chemistry B 122, 3384\u20133395 (2018).","DOI":"10.1021\/acs.jpcb.7b10371"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Alejandro Perdomo-Ortiz, Neil Dickson, Marshall Drew-Brook, et al. ``Finding low-energy conformations of lattice protein models by quantum annealing&apos;&apos;. Scientific Reports 2, 571 (2012).","DOI":"10.1038\/srep00571"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Baonan Wang, Feng Hu, Haonan Yao, and Chao Wang. ``Prime factorization algorithm based on parameter optimization of ising model&apos;&apos;. Scientific Reports 10, 7106 (2020).","DOI":"10.1038\/s41598-020-62802-5"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Rom\u00e1n Or\u00fas, Samuel Mugel, and Enrique Lizaso. ``Forecasting financial crashes with quantum computing&apos;&apos;. Phys. Rev. A 99, 060301 (2019).","DOI":"10.1103\/PhysRevA.99.060301"},{"key":"26","unstructured":"Maike Drieb-Sch\u00f6n, Younes Javanmard, Kilian Ender, and Wolfgang Lechner. ``Parity quantum optimization: Encoding constraints&apos;&apos; (2021). arXiv:2105.06235."},{"key":"27","unstructured":"Michael Fellner, Kilian Ender, Roeland ter Hoeven, and Wolfgang Lechner. ``Parity quantum optimization: Benchmarks&apos;&apos; (2021). arXiv:2105.06240."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Wolfgang Lechner, Philipp Hauke, and Peter Zoller. ``A quantum annealing architecture with all-to-all connectivity from local interactions&apos;&apos;. Science Advances 1 (2015).","DOI":"10.1126\/sciadv.1500838"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Fernando Pastawski and John Preskill. ``Error correction for encoded quantum annealing&apos;&apos;. Phys. Rev. A 93 (2016).","DOI":"10.1103\/PhysRevA.93.052325"},{"key":"30","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm&apos;&apos; (2014). arXiv:1411.4028."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Wolfgang Lechner. ``Quantum approximate optimization with parallelizable gates&apos;&apos;. IEEE Transactions on Quantum Engineering 1, 1\u20136 (2020).","DOI":"10.1109\/TQE.2020.3034798"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, et al. ``Quantum optimization using variational algorithms on near-term quantum devices&apos;&apos;. Quantum Science and Technology 3, 030503 (2018).","DOI":"10.1088\/2058-9565\/aab822"},{"key":"33","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum Computing in the NISQ era and beyond&apos;&apos;. Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, et al. ``Noisy intermediate-scale quantum algorithms&apos;&apos;. Rev. Mod. Phys. 94, 015004 (2022).","DOI":"10.1103\/RevModPhys.94.015004"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-03-17-950\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T09:55:59Z","timestamp":1679046959000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-03-17-950\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,17]]},"references-count":35,"URL":"https:\/\/doi.org\/10.22331\/q-2023-03-17-950","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,17]]},"article-number":"950"}}