Parity Quantum Optimization: Compiler
1Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria
2Institute 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
► 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] Martin Lanthaler, Clemens Dlaska, Kilian Ender, and Wolfgang Lechner, "Rydberg-Blockade-Based Parity Quantum Optimization", Physical Review Letters 130 22, 220601 (2023).
[2] Daniel Basilewitsch, Clemens Dlaska, and Wolfgang Lechner, "Comparing planar quantum computing platforms at the quantum speed limit", Physical Review Research 6 2, 023026 (2024).
[3] 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).
[4] 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.
[5] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner, "Error mitigation for quantum approximate optimization", Physical Review A 108 3, 032408 (2023).
[6] Roeland ter Hoeven, Anette Messinger, and Wolfgang Lechner, "Flexible constraint compilation in the parity architecture", Physical Review A 108 4, 042606 (2023).
[7] 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).
[8] Martin Lanthaler, Benjamin E. Niehoff, and Wolfgang Lechner, "Scalable set of reversible parity gates for integer factorization", Communications Physics 6 1, 73 (2023).
[9] 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).
[10] 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).
[11] 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).
[12] 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).
[13] 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).
[14] Kilian Ender, Anette Messinger, Michael Fellner, Clemens Dlaska, and Wolfgang Lechner, "Modular Parity Quantum Approximate Optimization", PRX Quantum 3 3, 030304 (2022).
[15] 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).
[16] 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).
[17] Mohammadsadegh Khazali and Wolfgang Lechner, "Scalable quantum processors empowered by the Fermi scattering of Rydberg electrons", Communications Physics 6 1, 57 (2023).
[18] Michael Fellner, Kilian Ender, Roeland ter Hoeven, and Wolfgang Lechner, "Parity Quantum Optimization: Benchmarks", arXiv:2105.06240, (2021).
[19] 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).
[20] Maike Drieb-Schön, Kilian Ender, Younes Javanmard, and Wolfgang Lechner, "Parity Quantum Optimization: Encoding Constraints", arXiv:2105.06235, (2021).
[21] Michael Fellner, Anette Messinger, Kilian Ender, and Wolfgang Lechner, "Applications of universal parity quantum computation", Physical Review A 106 4, 042442 (2022).
[22] 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).
[23] R. Cumming and T. Thomas, "Using a quantum computer to solve a real-world problem -- what can be achieved today?", arXiv:2211.13080, (2022).
[24] Michael Fellner, Kilian Ender, Roeland ter Hoeven, and Wolfgang Lechner, "Parity Quantum Optimization: Benchmarks", Quantum 7, 952 (2023).
[25] 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-02 20:09:40) and SAO/NASA ADS (last updated successfully 2024-07-02 20:09:41). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.