Parity Quantum Optimization: Compiler

Kilian Ender; Roeland ter Hoeven; Benjamin E. Niehoff; Maike Drieb-Schön; Wolfgang Lechner

doi:10.22331/q-2023-03-17-950

Parity Quantum Optimization: Compiler

Kilian Ender^1,2, Roeland ter Hoeven^1,2, Benjamin E. Niehoff¹, Maike Drieb-Schön^1,2, and Wolfgang Lechner^1,2

¹Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria
²Institute for Theoretical Physics, University of Innsbruck, A-6020 Innsbruck, Austria

Published:	2023-03-17, volume 7, page 950
Eprint:	arXiv:2105.06233v2
Doi:	https://doi.org/10.22331/q-2023-03-17-950
Citation:	Quantum 7, 950 (2023).

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

Abstract

We introduce parity quantum optimization with the aim of solving optimization problems consisting of arbitrary $k$-body interactions and side conditions using planar quantum chip architectures. The method introduces a decomposition of the problem graph with arbitrary $k$-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.

► BibTeX data

@article{Ender2023parityquantum,
  doi = {10.22331/q-2023-03-17-950},
  url = {https://doi.org/10.22331/q-2023-03-17-950},
  title = {Parity {Q}uantum {O}ptimization: {C}ompiler},
  author = {Ender, Kilian and ter Hoeven, Roeland and Niehoff, Benjamin E. and Drieb-Sch{\"{o}}n, Maike and Lechner, Wolfgang},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {950},
  month = mar,
  year = {2023}
}

► References

[1] Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. ``Optimization by simulated annealing''. Science 220, 671–680 (1983).
https://doi.org/10.1126/science.220.4598.671

[2] Andrew Lucas. ``Ising formulations of many np problems''. Frontiers in Physics 2, 5 (2014).
https://doi.org/10.3389/fphy.2014.00005

[3] J. I. Cirac and P. Zoller. ``Quantum computations with cold trapped ions''. Phys. Rev. Lett. 74, 4091–4094 (1995).
https://doi.org/10.1103/PhysRevLett.74.4091

[4] Rainer Blatt and Christian F Roos. ``Quantum simulations with trapped ions''. Nature Physics 8, 277–284 (2012).
https://doi.org/10.1038/nphys2252

[5] David Kielpinski, Chris Monroe, and David J Wineland. ``Architecture for a large-scale ion-trap quantum computer''. Nature 417, 709–711 (2002).
https://doi.org/10.1038/nature00784

[6] D Jaksch, JI Cirac, P Zoller, et al. ``Fast quantum gates for neutral atoms''. Phys. Rev. Lett. 85, 2208–2211 (2000).
https://doi.org/10.1103/PhysRevLett.85.2208

[7] Loïc Henriet, Lucas Beguin, Adrien Signoles, et al. ``Quantum computing with neutral atoms''. Quantum 4, 327 (2020).
https://doi.org/10.22331/q-2020-09-21-327

[8] M. Saffman, T. G. Walker, and K. Mølmer. ``Quantum information with rydberg atoms''. Rev. Mod. Phys. 82, 2313–2363 (2010).
https://doi.org/10.1103/RevModPhys.82.2313

[9] Immanuel Bloch, Jean Dalibard, and Wilhelm Zwerger. ``Many-body physics with ultracold gases''. Rev. Mod. Phys. 80, 885–964 (2008).
https://doi.org/10.1103/RevModPhys.80.885

[10] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, et al. ``Probing many-body dynamics on a 51-atom quantum simulator''. Nature 551, 579–584 (2017).
https://doi.org/10.1038/nature24622

[11] Jens Koch, Terri M. Yu, Jay Gambetta, et al. ``Charge-insensitive qubit design derived from the cooper pair box''. Phys. Rev. A 76, 042319 (2007).
https://doi.org/10.1103/PhysRevA.76.042319

[12] Andreas Wallraff, David I Schuster, Alexandre Blais, et al. ``Strong coupling of a single photon to a superconducting qubit using circuit quantum electrodynamics''. Nature 431, 162–167 (2004).
https://doi.org/10.1038/nature02851

[13] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, et al. ``Quantum annealing with manufactured spins''. Nature 473, 194–198 (2011).
https://doi.org/10.1038/nature10012

[14] Frank Arute, Kunal Arya, Ryan Babbush, et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5

[15] L Childress, MV Gurudev Dutt, JM Taylor, et al. ``Coherent dynamics of coupled electron and nuclear spin qubits in diamond''. Science 314, 281–285 (2006).
https://doi.org/10.1126/science.1131871

[16] Jeremy L O'brien, Akira Furusawa, and Jelena Vučković. ``Photonic quantum technologies''. Nature Photonics 3, 687–695 (2009).
https://doi.org/10.1038/nphoton.2009.229

[17] Xiaogang Qiang, Xiaoqi Zhou, Jianwei Wang, et al. ``Large-scale silicon quantum photonics implementing arbitrary two-qubit processing''. Nature photonics 12, 534–539 (2018).
https://doi.org/10.1038/s41566-018-0236-y

[18] G. G. Guerreschi and A. Y. Matsuura. ``Qaoa for max-cut requires hundreds of qubits for quantum speed-up''. Scientific Reports 9, 6903 (2019).
https://doi.org/10.1038/s41598-019-43176-9

[19] Edward Farhi, David Gamarnik, and Sam Gutmann. ``The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples'' (2020). arXiv:2005.08747.
arXiv:2005.08747

[20] Tameem Albash and Daniel A. Lidar. ``Adiabatic quantum computation''. Rev. Mod. Phys. 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002

[21] Tadashi Kadowaki and Hidetoshi Nishimori. ``Quantum annealing in the transverse ising model''. Phys. Rev. E 58, 5355–5363 (1998).
https://doi.org/10.1103/PhysRevE.58.5355

[22] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, et al. ``Perspectives of quantum annealing: methods and implementations''. Reports on Progress in Physics 83, 054401 (2020).
https://doi.org/10.1088/1361-6633/ab85b8

[23] Rongxin Xia, Teng Bian, and Sabre Kais. ``Electronic structure calculations and the ising hamiltonian''. The Journal of Physical Chemistry B 122, 3384–3395 (2018).
https://doi.org/10.1021/acs.jpcb.7b10371

[24] Alejandro Perdomo-Ortiz, Neil Dickson, Marshall Drew-Brook, et al. ``Finding low-energy conformations of lattice protein models by quantum annealing''. Scientific Reports 2, 571 (2012).
https://doi.org/10.1038/srep00571

[25] Baonan Wang, Feng Hu, Haonan Yao, and Chao Wang. ``Prime factorization algorithm based on parameter optimization of ising model''. Scientific Reports 10, 7106 (2020).
https://doi.org/10.1038/s41598-020-62802-5

[26] Román Orús, Samuel Mugel, and Enrique Lizaso. ``Forecasting financial crashes with quantum computing''. Phys. Rev. A 99, 060301 (2019).
https://doi.org/10.1103/PhysRevA.99.060301

[27] Maike Drieb-Schön, Younes Javanmard, Kilian Ender, and Wolfgang Lechner. ``Parity quantum optimization: Encoding constraints'' (2021). arXiv:2105.06235.
arXiv:2105.06235

[28] Michael Fellner, Kilian Ender, Roeland ter Hoeven, and Wolfgang Lechner. ``Parity quantum optimization: Benchmarks'' (2021). arXiv:2105.06240.
arXiv:2105.06240

[29] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. ``A quantum annealing architecture with all-to-all connectivity from local interactions''. Science Advances 1 (2015).
https://doi.org/10.1126/sciadv.1500838

[30] Fernando Pastawski and John Preskill. ``Error correction for encoded quantum annealing''. Phys. Rev. A 93 (2016).
https://doi.org/10.1103/PhysRevA.93.052325

[31] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028

[32] Wolfgang Lechner. ``Quantum approximate optimization with parallelizable gates''. IEEE Transactions on Quantum Engineering 1, 1–6 (2020).
https://doi.org/10.1109/TQE.2020.3034798

[33] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, et al. ``Quantum optimization using variational algorithms on near-term quantum devices''. Quantum Science and Technology 3, 030503 (2018).
https://doi.org/10.1088/2058-9565/aab822

[34] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[35] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, et al. ``Noisy intermediate-scale quantum algorithms''. Rev. Mod. Phys. 94, 015004 (2022).
https://doi.org/10.1103/RevModPhys.94.015004

Cited by

[1] F. Q. Guo, Shi-Lei Su, Weibin Li, and X. Q. Shao, "Parity-controlled gate in a two-dimensional neutral-atom array", Physical Review A 111 2, 022420 (2025).

[2] Maike Drieb-Schön, Florian Dreier, and Wolfgang Lechner, "Bundling of bipartite entanglement", Physical Review A 114 1, 012401 (2026).

[3] Ryoji Miyazaki and Tsuyoshi Yamamoto, "Four-body coupler for superconducting qubits based on Josephson parametric oscillators", Physical Review A 111 6, 062612 (2025).

[4] Berend Klaver, Stefan M. A. Rombouts, Michael Fellner, Anette Messinger, Kilian Ender, Katharina Ludwig, and Wolfgang Lechner, "SWAP-less implementation of quantum algorithms", Physical Review A 113 1, 012443 (2026).

[5] Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler, and Wolfgang Lechner, "Encoding-independent optimization problem formulation for quantum computing", Frontiers in Quantum Science and Technology 2, 1229471 (2023).

[6] Anita Weidinger, Glen Bigan Mbeng, Michael Fellner, Davit Khachatryan, and Wolfgang Lechner, "Performance of parity QAOA for the signed Max-Cut problem", New Journal of Physics 28 3, 034514 (2026).

[7] Toshiki Matsumine, Hideki Ochiai, and Junji Shikata, "Quantum Algorithms for the Physical Layer: Potential Applications to Physical Layer Security", IEEE Access 13, 13988 (2025).

[8] Florian Ginzel, Michael Fellner, Christian Ertler, Lars R. Schreiber, Hendrik Bluhm, and Wolfgang Lechner, "Scalable parity architecture with a shuttling-based spin qubit processor", Physical Review B 110 7, 075302 (2024).

[9] Roeland ter Hoeven, Benjamin E Niehoff, Sagar Sudhir Kale, and Wolfgang Lechner, "Constructive plaquette compilation for the parity architecture", Quantum Science and Technology 9 3, 035056 (2024).

[10] Michele Cattelan, Jemma Bennett, Sheir Yarkoni, and Wolfgang Lechner, "Scalable embedding of parity constraints in quantum annealing hardware", Physical Review A 111 1, 012435 (2025).

[11] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner, "Error mitigation for quantum approximate optimization", Physical Review A 108 3, 032408 (2023).

[12] E. Eilkhas, B. Lari, and H. Hassanabadi, "Hadamard Gate in Non-equilibrium Conditions Under Parity Defined in the Wigner Algebra", International Journal of Theoretical Physics 65 3, 68 (2026).

[13] Martin Lanthaler, Benjamin E. Niehoff, and Wolfgang Lechner, "Scalable set of reversible parity gates for integer factorization", Communications Physics 6 1, 73 (2023).

[14] Pooja Vaikar and Amol Potgantwar, 2026 IEEE International Conference on Emerging Computing and Intelligent Technologies (ICoECIT) 1 (2026) ISBN:979-8-3315-8997-4.

[15] Isaac D. Smith, Berend Klaver, Hendrik Poulsen Nautrup, Wolfgang Lechner, and Hans J. Briegel, "Minimally universal parity quantum computing", Physical Review A 112 3, 032606 (2025).

[16] Daniel Basilewitsch, Clemens Dlaska, and Wolfgang Lechner, "Comparing planar quantum computing platforms at the quantum speed limit", Physical Review Research 6 2, 023026 (2024).

[17] Ji Liu, Alvin Gonzales, Benchen Huang, Zain Hamid Saleem, and Paul Hovland, 2025 IEEE International Symposium on High Performance Computer Architecture (HPCA) 158 (2025) ISBN:979-8-3315-0647-6.

[18] Pierre Cazals, Amalia Sorondo, Victor Onofre, Constantin Dalyac, Wesley Coelho, and Vittorio Vitale, "Quantum optimization on Rydberg-atom arrays with arbitrary connectivity: Gadget limitations and a heuristic approach", Physical Review A 112 6, 062416 (2025).

[19] Pooja Vaikar and Amol Potgantwar, Lecture Notes in Networks and Systems 1495, 681 (2026) ISBN:978-981-96-8042-9.

[20] Roeland ter Hoeven, Anette Messinger, and Wolfgang Lechner, "Flexible constraint compilation in the parity architecture", Physical Review A 108 4, 042606 (2023).

[21] Isaac D. Smith, Hendrik Poulsen Nautrup, and Hans J. Briegel, "Parity Quantum Computing as yz -Plane Measurement-Based Quantum Computing", Physical Review Letters 132 22, 220602 (2024).

[22] Shreyas Harshal Pradhan, Hadi Mohammed Soufy, Vishal Anand, Rik Chattopadhyay, Subhadip Mitra, and Samyadeb Bhattacharya, "Unraveling the non-Markovian spin-boson model and quantum quasi-Otto cycle", Physical Review A 112 4, 042222 (2025).

[23] Martin Lanthaler, Clemens Dlaska, Kilian Ender, and Wolfgang Lechner, "Rydberg-Blockade-Based Parity Quantum Optimization", Physical Review Letters 130 22, 220601 (2023).

[24] Berend Klaver, Stefan Rombouts, Michael Fellner, Anette Messinger, Kilian Ender, Katharina Ludwig, and Wolfgang Lechner, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 541 (2024) ISBN:979-8-3315-4137-8.

[25] Anette Messinger, Michael Fellner, and Wolfgang Lechner, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 120 (2023) ISBN:979-8-3503-4323-6.

[26] Florian Dreier and Wolfgang Lechner, "On the uniqueness of compiling graphs under the parity transformation", Journal of Mathematical Physics 67 2, 022201 (2026).

[27] Leo Stenzel, Roeland ter Hoeven, Ryoji Miyazaki, Tomohiro Yamaji, Masayuki Shirane, and Wolfgang Lechner, "Spin model for quantum annealing with Kerr parametric oscillators", Physical Review A 113 6, 062621 (2026).

[28] Sheir Yarkoni, Elena Raponi, Thomas Bäck, and Sebastian Schmitt, "Quantum annealing for industry applications: introduction and review", Reports on Progress in Physics 85 10, 104001 (2022).

[29] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia, and Yuri Alexeev, "A Survey of Quantum Computing for Finance", arXiv:2201.02773, (2022).

[30] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

[31] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, and Marco Pistoia, "Constrained optimization via quantum Zeno dynamics", Communications Physics 6 1, 219 (2023).

[32] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng, Andreas Kruckenhauser, Wolfgang Lechner, and Rick van Bijnen, "Quantum Optimization via Four-Body Rydberg Gates", Physical Review Letters 128 12, 120503 (2022).

[33] Kilian Ender, Anette Messinger, Michael Fellner, Clemens Dlaska, and Wolfgang Lechner, "Modular Parity Quantum Approximate Optimization", PRX Quantum 3 3, 030304 (2022).

[34] Krzysztof Domino, Akash Kundu, Özlem Salehi, and Krzysztof Krawiec, "Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing", Quantum Information Processing 21 9, 337 (2022).

[35] Narendra N. Hegade, Koushik Paul, F. Albarrán-Arriagada, Xi Chen, and Enrique Solano, "Digitized adiabatic quantum factorization", Physical Review A 104 5, L050403 (2021).

[36] P. V. Sriluckshmy, Vicente Pina-Canelles, Mario Ponce, Manuel G. Algaba, IV Fedor Šimkovic, and Martin Leib, "Optimal, hardware native decomposition of parameterized multi-qubit Pauli gates", Quantum Science and Technology 8 4, 045029 (2023).

[37] Maike Drieb-Schön, Kilian Ender, Younes Javanmard, and Wolfgang Lechner, "Parity Quantum Optimization: Encoding Constraints", arXiv:2105.06235, (2021).

[38] Michael Fellner, Kilian Ender, Roeland ter Hoeven, and Wolfgang Lechner, "Parity Quantum Optimization: Benchmarks", arXiv:2105.06240, (2021).

[39] Michael Fellner, Anette Messinger, Kilian Ender, and Wolfgang Lechner, "Applications of universal parity quantum computation", Physical Review A 106 4, 042442 (2022).

[40] R. Cumming and T. Thomas, "Using a quantum computer to solve a real-world problem -- what can be achieved today?", arXiv:2211.13080, (2022).

[41] Maike Drieb-Schön, Kilian Ender, Younes Javanmard, and Wolfgang Lechner, "Parity Quantum Optimization: Encoding Constraints", Quantum 7, 951 (2023).

[42] Mohammadsadegh Khazali and Wolfgang Lechner, "Scalable quantum processors empowered by the Fermi scattering of Rydberg electrons", Communications Physics 6 1, 57 (2023).

[43] Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler, and Wolfgang Lechner, "Encoding-Independent Optimization Problem Formulation for Quantum Computing", arXiv:2302.03711, (2023).

[44] Michael Fellner, Kilian Ender, Roeland ter Hoeven, and Wolfgang Lechner, "Parity Quantum Optimization: Benchmarks", Quantum 7, 952 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-17 07:14:08) and SAO/NASA ADS (last updated successfully 2026-07-16 15:39:50). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-17 07:14:08: Cannot retrieve data from ADS due to rate limitations.

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.