Parity Quantum Optimization: Benchmarks

Michael Fellner, Kilian Ender, Roeland ter Hoeven, and Wolfgang Lechner

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

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


We present benchmarks of the parity transformation for the Quantum Approximate Optimization Algorithm (QAOA). We analyse the gate resources required to implement a single QAOA cycle for real-world scenarios. In particular, we consider random spin models with higher order terms, as well as the problems of predicting financial crashes and finding the ground states of electronic structure Hamiltonians. For the spin models studied our findings imply a significant advantage of the parity mapping compared to the standard gate model. In combination with full parallelizability of gates this has the potential to boost the race for demonstrating quantum advantage.

► BibTeX data

► References

[1] Tadashi Kadowaki and Hidetoshi Nishimori. ``Quantum annealing in the transverse ising model''. Physical Review E 58, 5355–5363 (1998).

[2] Tameem Albash and Daniel A. Lidar. ``Adiabatic quantum computation''. Reviews of Modern Physics 90, 015002 (2018).

[3] M. Born and V. Fock. ``Beweis des adiabatensatzes''. Zeitschrift für Physik 51, 165–180 (1928).

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

[5] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).

[6] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, et al. ``From the quantum approximate optimization algorithm to a quantum alternating operator ansatz''. Algorithms 12, 34 (2019).

[7] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, et al. ``For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances'' (2018). arXiv:1812.04170.

[8] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, et al. ``Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices''. Physical Review X 10, 021067 (2020).

[9] Madita Willsch, Dennis Willsch, Fengping Jin, et al. ``Benchmarking the quantum approximate optimization algorithm''. Quantum Information Processing 19, 197 (2020).

[10] 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.

[11] Andrew Lucas. ``Ising formulations of many np problems''. Frontiers in Physics 2, 5 (2014).

[12] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff, et al. ``Parity quantum optimization: Compiler'' (2021). arXiv:2105.06233.

[13] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. ``A quantum annealing architecture with all-to-all connectivity from local interactions''. Science Advances 1, e1500838 (2015).

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

[15] Wolfgang Lechner. ``Quantum approximate optimization with parallelizable gates''. IEEE Transactions on Quantum Engineering 1, 1–6 (2020).

[16] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng, et al. ``Quantum optimization via four-body rydberg gates''. Physical Review Letters 128, 120503 (2022).

[17] 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).

[18] Tobias Stollenwerk, Bryan O’Gorman, Davide Venturelli, et al. ``Quantum annealing applied to de-conflicting optimal trajectories for air traffic management''. IEEE Transactions on Intelligent Transportation Systems 21, 285–297 (2020).

[19] Rongxin Xia, Teng Bian, and Sabre Kais. ``Electronic structure calculations and the ising hamiltonian''. The Journal of Physical Chemistry B 122, 3384–3395 (2018).

[20] Román Orús, Samuel Mugel, and Enrique Lizaso. ``Forecasting financial crashes with quantum computing''. Physical Review A 99, 2469–9934 (2019).

[21] Shuxian Jiang, Keith A. Britt, Alexander J. McCaskey, et al. ``Quantum annealing for prime factorization''. Scientific Reports 8, 17667 (2018).

[22] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, et al. ``Noisy intermediate-scale quantum algorithms''. Reviews of Modern Physics 94, 015004 (2022).

[23] Jonathan Wurtz and Peter Love. ``Maxcut quantum approximate optimization algorithm performance guarantees for $p>1$''. Physical Review A 103, 042612 (2021).

[24] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte. ``Parameter concentrations in quantum approximate optimization''. Physical Review A 104, L010401 (2021).

[25] Michael Streif and Martin Leib. ``Training the quantum approximate optimization algorithm without access to a quantum processing unit''. Quantum Science and Technology 5, 034008 (2020).

[26] Immanuel Bloch, Jean Dalibard, and Wilhelm Zwerger. ``Many-body physics with ultracold gases''. Reviews of Modern Physics 80, 885–964 (2008).

[27] M. Saffman, T. G. Walker, and K. Mølmer. ``Quantum information with rydberg atoms''. Reviews of Modern Physics 82, 2313–2363 (2010).

[28] Loïc Henriet, Lucas Beguin, Adrien Signoles, et al. ``Quantum computing with neutral atoms''. Quantum 4, 327 (2020).

[29] Frank Arute, Kunal Arya, Ryan Babbush, et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).

[30] Alexander Cowtan, Silas Dilkes, Ross Duncan, et al. ``Phase gadget synthesis for shallow circuits''. Electronic Proceedings in Theoretical Computer Science 318, 213–228 (2020).

[31] Arianne Meijer-van de Griend and Ross Duncan. ``Architecture-aware synthesis of phase polynomials for NISQ devices'' (2020). arXiv:2004.06052.

[32] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, et al. ``t$|$ket$\rangle$: a retargetable compiler for NISQ devices''. Quantum Science and Technology 6, 014003 (2020).

[33] Cheng Xue, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo. ``Effects of quantum noise on quantum approximate optimization algorithm''. Chinese Physics Letters 38, 030302 (2021).

[34] Jeffrey Marshall, Filip Wudarski, Stuart Hadfield, and Tad Hogg. ``Characterizing local noise in QAOA circuits''. IOP SciNotes 1, 025208 (2020).

[35] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, et al. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nature Physics 17, 332–336 (2021).

[36] Kilian Ender, Anette Messinger, Michael Fellner, et al. ``Modular parity quantum approximate optimization''. PRX Quantum 3, 030304 (2022).

[37] D. Sornette. ``Why stock markets crash: Critical events in complex financial systems''. Princeton University Press. (2019).

[38] Arturo Estrella and Frederic Mishkin. ``Predicting u.s. recessions: Financial variables as leading indicators''. The Review of Economics and Statistics 80, 45–61 (1998).

[39] Yongcheng Ding, Javier Gonzalez-Conde, Lucas Lamata, et al. ``Toward prediction of financial crashes with a d-wave quantum annealer''. Entropy 25, 323 (2023).

[40] Matthew Elliott, Benjamin Golub, and Matthew O. Jackson. ``Financial networks and contagion''. American Economic Review 104, 3115–53 (2014).

[41] Brett Hemenway and Sanjeev Khanna. ``Sensitivity and computational complexity in financial networks''. Algorithmic Finance 5, 95–110 (2016).

[42] Michael Streif, Florian Neukart, and Martin Leib. ``Solving quantum chemistry problems with a d-wave quantum annealer'' (2019). arXiv:1811.05256.

[43] P. Jordan and E. Wigner. ``Über das Paulische Äquivalenzverbot''. Zeitschrift für Physik 47, 631–651 (1928).

[44] Sergey B. Bravyi and Alexei Yu. Kitaev. ``Fermionic quantum computation''. Annals of Physics 298, 210–226 (2002).

[45] Jacob T. Seeley, Martin J. Richard, and Peter J. Love. ``The bravyi-kitaev transformation for quantum computation of electronic structure''. The Journal of Chemical Physics 137, 224109 (2012).

[46] Jarrod R McClean, Nicholas C Rubin, Kevin J Sung, et al. ``OpenFermion: the electronic structure package for quantum computers''. Quantum Science and Technology 5, 034014 (2020).

[47] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, et al. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5, 4213 (2014).

Cited by

[1] Laith Abualigah, Saif AlNajdawi, Abiodun M. Ikotun, Agostino Forestiero, Faiza Gul, Absalom E. Ezugwu, Heming Jia, Mohsen Zare, Shubham Mahajan, and Mohammad Alshinwan, Metaheuristic Optimization Algorithms 147 (2024) ISBN:9780443139253.

[2] Zhengming Guo, Tingting Song, and Ge Lin, "Portfolio optimization based on quantum linear algorithm", Physica Scripta 99 8, 085107 (2024).

[3] 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.

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

[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] 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).

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

[8] 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).

[9] 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).

[10] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff, Maike Drieb-Schön, and Wolfgang Lechner, "Parity Quantum Optimization: Compiler", arXiv:2105.06233, (2021).

[11] 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).

[12] 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).

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

[14] 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).

[15] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff, Maike Drieb-Schön, and Wolfgang Lechner, "Parity Quantum Optimization: Compiler", Quantum 7, 950 (2023).

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-15 19:38:43) and SAO/NASA ADS (last updated successfully 2024-07-15 19:38:44). The list may be incomplete as not all publishers provide suitable and complete citation data.