Parity Quantum Optimization: Benchmarks

Republished By Plato

Followers: 0

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.

Abstract

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

@article{Fellner2023parityquantum, doi = {10.22331/q-2023-03-17-952}, url = {https://doi.org/10.22331/q-2023-03-17-952}, title = {Parity {Q}uantum {O}ptimization: {B}enchmarks}, author = {Fellner, Michael and Ender, Kilian and ter Hoeven, Roeland and Lechner, Wolfgang}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {952}, month = mar, year = {2023}<br /> }

► References

[1] Tadashi Kadowaki and Hidetoshi Nishimori. “Quantum annealing in the transverse ising model”. Physical Review E 58, 5355–5363 (1998).
https://doi.org/10.1103/physreve.58.5355

[2] Tameem Albash and Daniel A. Lidar. “Adiabatic quantum computation”. Reviews of Modern Physics 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002

[3] M. Born and V. Fock. “Beweis des adiabatensatzes”. Zeitschrift für Physik 51, 165–180 (1928).
https://doi.org/10.1007/BF01343193

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

[5] John Preskill. “Quantum computing in the NISQ era and beyond”. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[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).
https://doi.org/10.3390/a12020034

[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.
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).
https://doi.org/10.1103/PhysRevX.10.021067

[9] Madita Willsch, Dennis Willsch, Fengping Jin, et al. “Benchmarking the quantum approximate optimization algorithm”. Quantum Information Processing 19, 197 (2020).
https://doi.org/10.1007/s11128-020-02692-8

[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.
arXiv:2005.08747

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

[12] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff, et al. “Parity quantum optimization: Compiler” (2021). arXiv:2105.06233.
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).
https://doi.org/10.1126/sciadv.1500838

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

[15] 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

[16] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng, et al. “Quantum optimization via four-body rydberg gates”. Physical Review Letters 128, 120503 (2022).
https://doi.org/10.1103/PhysRevLett.128.120503

[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).
https://doi.org/10.1038/srep00571

[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).
https://doi.org/10.1109/TITS.2019.2891235

[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).
https://doi.org/10.1021/acs.jpcb.7b10371

[20] Román Orús, Samuel Mugel, and Enrique Lizaso. “Forecasting financial crashes with quantum computing”. Physical Review A 99, 2469–9934 (2019).
https://doi.org/10.1103/physreva.99.060301

[21] Shuxian Jiang, Keith A. Britt, Alexander J. McCaskey, et al. “Quantum annealing for prime factorization”. Scientific Reports 8, 17667 (2018).
https://doi.org/10.1038/s41598-018-36058-z

[22] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, et al. “Noisy intermediate-scale quantum algorithms”. Reviews of Modern Physics 94, 015004 (2022).
https://doi.org/10.1103/RevModPhys.94.015004

[23] Jonathan Wurtz and Peter Love. “Maxcut quantum approximate optimization algorithm performance guarantees for $p>1$”. Physical Review A 103, 042612 (2021).
https://doi.org/10.1103/PhysRevA.103.042612

[24] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte. “Parameter concentrations in quantum approximate optimization”. Physical Review A 104, L010401 (2021).
https://doi.org/10.1103/PhysRevA.104.L010401

[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).
https://doi.org/10.1088/2058-9565/ab8c2b

[26] Immanuel Bloch, Jean Dalibard, and Wilhelm Zwerger. “Many-body physics with ultracold gases”. Reviews of Modern Physics 80, 885–964 (2008).
https://doi.org/10.1103/RevModPhys.80.885

[27] M. Saffman, T. G. Walker, and K. Mølmer. “Quantum information with rydberg atoms”. Reviews of Modern Physics 82, 2313–2363 (2010).
https://doi.org/10.1103/RevModPhys.82.2313

[28] 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

[29] 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

[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).
https://doi.org/10.4204/eptcs.318.13

[31] Arianne Meijer-van de Griend and Ross Duncan. “Architecture-aware synthesis of phase polynomials for NISQ devices” (2020). arXiv:2004.06052.
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).
https://doi.org/10.1088/2058-9565/ab8e92

[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).
https://doi.org/10.1088/0256-307X/38/3/030302

[34] Jeffrey Marshall, Filip Wudarski, Stuart Hadfield, and Tad Hogg. “Characterizing local noise in QAOA circuits”. IOP SciNotes 1, 025208 (2020).
https://doi.org/10.1088/2633-1357/abb0d7

[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).
https://doi.org/10.1038/s41567-020-01105-y

[36] Kilian Ender, Anette Messinger, Michael Fellner, et al. “Modular parity quantum approximate optimization”. PRX Quantum 3, 030304 (2022).
https://doi.org/10.1103/PRXQuantum.3.030304

[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).
https://doi.org/10.1162/003465398557320

[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).
https://doi.org/10.3390/e25020323

[40] Matthew Elliott, Benjamin Golub, and Matthew O. Jackson. “Financial networks and contagion”. American Economic Review 104, 3115–53 (2014).
https://doi.org/10.1257/aer.104.10.3115

[41] Brett Hemenway and Sanjeev Khanna. “Sensitivity and computational complexity in financial networks”. Algorithmic Finance 5, 95–110 (2016).
https://doi.org/10.3233/AF-160166

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

[43] P. Jordan and E. Wigner. “Über das Paulische Äquivalenzverbot”. Zeitschrift für Physik 47, 631–651 (1928).
https://doi.org/10.1007/BF01331938

[44] Sergey B. Bravyi and Alexei Yu. Kitaev. “Fermionic quantum computation”. Annals of Physics 298, 210–226 (2002).
https://doi.org/10.1006/aphy.2002.6254

[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).
https://doi.org/10.1063/1.4768229

[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).
https://doi.org/10.1088/2058-9565/ab8ebc

[47] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, et al. “A variational eigenvalue solver on a photonic quantum processor”. Nature Communications 5, 4213 (2014).
https://doi.org/10.1038/ncomms5213

Cited by

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

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

[3] P. V. Sriluckshmy, Vicente Pina-Canelles, Mario Ponce, Manuel G. Algaba, Fedor Šimkovic, and Martin Leib, “Optimal, hardware native decomposition of parameterized multi-qubit Pauli gates”, arXiv:2303.04498, (2023).

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

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

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

[7] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner, “Error Mitigation for Quantum Approximate Optimization”, arXiv:2301.05042, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-03-17 22:08:31). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-03-17 22:08:29).

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
Source: https://quantum-journal.org/papers/q-2023-03-17-952/

Time Stamp: March 17, 2023

Time Stamp: Sep 25, 2023

Parity Quantum Optimization: Benchmarks

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

More from Quantum Journal

The $2T$-qutrit, a two-mode bosonic qutrit

An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs

LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States

High-accuracy Hamiltonian learning via delocalized quantum state evolutions

Probability in many-worlds theories

1000 Quantum papers!

Benchmarking the Planar Honeycomb Code

Time-marching based quantum solvers for time-dependent linear differential equations

Faster Born probability estimation via gate merging and frame optimisation

Causal structure in the presence of sectorial constraints, with application to the quantum switch

Analysis of arbitrary superconducting quantum circuits accompanied by a Python package: SQcircuit

About Us

Vertical Search & Ai

Platform

Stay Connected

Account