Parity Quantum Optimization: Encoding Constraints

Republished By Plato

Followers: 0

Maike Drieb-Schön^1,2, Kilian Ender^1,2, Younes Javanmard¹, and Wolfgang Lechner^1,2

¹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

Constraints make hard optimization problems even harder to solve on quantum devices because they are implemented with large energy penalties and additional qubit overhead. The parity mapping, which has been introduced as an alternative to the spin encoding, translates the problem to a representation using only parity variables that encodes products of spin variables. In combining exchange interaction and single spin flip terms in the parity representation, constraints on sums and products of arbitrary $k$-body terms can be implemented without additional overhead in two-dimensional quantum systems.

► BibTeX data

@article{DriebSchon2023parityquantum, doi = {10.22331/q-2023-03-17-951}, url = {https://doi.org/10.22331/q-2023-03-17-951}, title = {Parity {Q}uantum {O}ptimization: {E}ncoding {C}onstraints}, author = {Drieb-Sch{“{o}}n, Maike and Ender, Kilian and Javanmard, Younes and Lechner, Wolfgang}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {951}, month = mar, year = {2023}<br /> }

► References

[1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, et al. “A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem”. Science 292, 472–475 (2001).
https://doi.org/10.1126/science.1057726

[2] David Allouche, Isabelle Andre, Sophie Barbe, et al. “Computational protein design as an optimization problem”. Artificial Intelligence 212, 59–79 (2014).
https://doi.org/10.1016/j.artint.2014.03.005

[3] Simon Gravel and Veit Elser. “Divide and concur: A general approach to constraint satisfaction”. Phys. Rev. E 78, 036706 (2008).
https://doi.org/10.1103/PhysRevE.78.036706

[4] Florian Neukart, Gabriele Compostella, Christian Seidel, et al. “Traffic flow optimization using a quantum annealer” (2017). arXiv:1708.01625.
arXiv:1708.01625

[5] Eleanor G. Rieffel, Davide Venturelli, Bryan O’Gorman, et al. “A case study in programming a quantum annealer for hard operational planning problems”. Quantum Information Processing 14 (2015).
https://doi.org/10.1007/s11128-014-0892-x

[6] Emmanuel Hebrard, Eoin O’Mahony, and Barry O’Sullivan. “Constraint Programming and Combinatorial Optimisation in Numberjack”. In Andrea Lodi, Michela Milano, and Paolo Toth, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science. Springer (2010).
https://doi.org/10.1007/978-3-642-13520-0_22

[7] M. W. Johnson, M. H. S. Amin, S. Gildert, et al. “Quantum annealing with manufactured spins”. Nature 473 (2011).
https://doi.org/10.1038/nature10012

[8] Pei Cao, Zhaoyan Fan, Robert X. Gao, and Jiong Tang. “Solving Configuration Optimization Problem with Multiple Hard Constraints: An Enhanced Multi-Objective Simulated Annealing Approach” (2017). arXiv:1706.03141.
arXiv:1706.03141

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

[10] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, et al. “Probing many-body dynamics on a 51-atom quantum simulator”. Nature 551, 579 EP – (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] 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

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

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

[15] Zhengbing Bian, Fabian Chudak, Robert Brian Israel, et al. “Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis”. Frontiers in ICT 3 (2016).
https://doi.org/10.3389/fict.2016.00014

[16] Adam Douglass, Andrew D. King, and Jack Raymond. “Constructing SAT Filters with a Quantum Annealer”. In Marijn Heule and Sean Weaver, editors, Theory and Applications of Satisfiability Testing – SAT 2015. Lecture Notes in Computer Science Cham (2015). Springer International Publishing.
https://doi.org/10.1007/978-3-319-24318-4_9

[17] Andrew Lucas. “Ising formulations of many NP problems”. Front. Phys. 2, 5 (2014).
https://doi.org/10.3389/fphy.2014.00005

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

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

[20] Arnab Das and Bikas K. Chakrabarti. “Colloquium: Quantum annealing and analog quantum computation”. Rev. Mod. Phys. 80, 1061–1081 (2008).
https://doi.org/10.1103/RevModPhys.80.1061

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

[22] Tomas Vyskocil and Hristo Djidjev. “Embedding equality constraints of optimization problems into a quantum annealer”. Algorithms 12 (2019).
https://doi.org/10.3390/a12040077

[23] Itay Hen and Federico M. Spedalieri. “Quantum annealing for constrained optimization”. Phys. Rev. Applied 5, 034007 (2016).
https://doi.org/10.1103/PhysRevApplied.5.034007

[24] Itay Hen and Marcelo S. Sarandy. “Driver hamiltonians for constrained optimization in quantum annealing”. Phys. Rev. A 93, 062312 (2016).
https://doi.org/10.1103/PhysRevA.93.062312

[25] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, et al. “From the quantum approximate optimization algorithm to a quantum alternating operator ansatz”. Algorithms 12 (2019).
https://doi.org/10.3390/a12020034

[26] Kazuki Ikeda, Yuma Nakamura, and Travis S. Humble. “Application of Quantum Annealing to Nurse Scheduling Problem”. Scientific Reports 9, 12837 (2019).
https://doi.org/10.1038/s41598-019-49172-3

[27] Hirotaka Irie, Goragot Wongpaisarnsin, Masayoshi Terabe, et al. “Quantum Annealing of Vehicle Routing Problem with Time, State and Capacity”. In Sebastian Feld and Claudia Linnhoff-Popien, editors, Quantum Technology and Optimization Problems. Pages 145–156. Lecture Notes in Computer Science Cham (2019). Springer International Publishing.
https://doi.org/10.1007/978-3-030-14082-3_13

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

[29] Itay Hen and A. P. Young. “Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems”. Phys. Rev. E 84, 061152 (2011).
https://doi.org/10.1103/PhysRevE.84.061152

[30] Hok K. Ng, Banavar Sridhar, and Shon Grabbe. “Optimizing Aircraft Trajectories with Multiple Cruise Altitudes in the Presence of Winds”. Journal of Aerospace Information Systems 11 (2014).
https://doi.org/10.2514/1.I010084

[31] Eleanor Rieffel, Davide Venturelli, Minh Do, et al. “Parametrized Families of Hard Planning Problems from Phase Transitions”. Proceedings of the AAAI Conference on Artificial Intelligence 28 (2014).
https://doi.org/10.1609/aaai.v28i1.9044

[32] Davide Venturelli, Dominic J. J. Marchand, and Galo Rojo. “Quantum Annealing Implementation of Job-Shop Scheduling” (2016). arXiv:1506.08479.
arXiv:1506.08479

[33] Gili Rosenberg, Poya Haghnegahdar, Phil Goddard, et al. “Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer”. IEEE Journal of Selected Topics in Signal Processing 10 (2016).
https://doi.org/10.1109/JSTSP.2016.2574703

[34] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. “$XY$ mixers: Analytical and numerical results for the quantum alternating operator ansatz”. Phys. Rev. A 101, 012320 (2020).
https://doi.org/10.1103/PhysRevA.101.012320

[35] Jeremy Cook, Stephan Eidenbenz, and Andreas Bärtschi. “The quantum alternating operator ansatz on maximum k-vertex cover”. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 83–92. (2020).
https://doi.org/10.1109/QCE49297.2020.00021

[36] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. “A quantum annealing architecture with all-to-all connectivity from local interactions”. Sci. Adv. 1, 1500838 (2015).
https://doi.org/10.1126/sciadv.1500838

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

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

[39] Vicky Choi. “Minor-embedding in adiabatic quantum computation: I. The parameter setting problem”. Quantum Information Processing 7, 193–209 (2008).
https://doi.org/10.1007/s11128-008-0082-9

[40] Walter Vinci, Tameem Albash, Gerardo Paz-Silva, et al. “Quantum annealing correction with minor embedding”. Phys. Rev. A 92, 042310 (2015).
https://doi.org/10.1103/PhysRevA.92.042310

[41] Yu Yamashiro, Masaki Ohkuwa, Hidetoshi Nishimori, and Daniel A. Lidar. “Dynamics of reverse annealing for the fully connected $p$-spin model”. Phys. Rev. A 100, 052321 (2019).
https://doi.org/10.1103/PhysRevA.100.052321

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

[43] Rolando D. Somma, Daniel Nagaj, and Mária Kieferová. “Quantum speedup by quantum annealing”. Phys. Rev. Lett. 109, 050501 (2012).
https://doi.org/10.1103/PhysRevLett.109.050501

[44] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, et al. “Different strategies for optimization using the quantum adiabatic algorithm” (2014). arXiv:1401.7320.
arXiv:1401.7320

[45] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo, and Matthias Troyer. “Nonstoquastic hamiltonians and quantum annealing of an ising spin glass”. Phys. Rev. B 95, 184416 (2017).
https://doi.org/10.1103/PhysRevB.95.184416

[46] Andreas Hartmann and Wolfgang Lechner. “Rapid counter-diabatic sweeps in lattice gauge adiabatic quantum computing”. New J. Phys. 21, 043025 (2019).
https://doi.org/10.1088/1367-2630/ab14a0

[47] M. H. S. Amin. “Consistency of the adiabatic theorem”. Phys. Rev. Lett. 102, 220401 (2009).
https://doi.org/10.1103/PhysRevLett.102.220401

[48] Lukas M. Sieberer and Wolfgang Lechner. “Programmable superpositions of ising configurations”. Phys. Rev. A 97, 052329 (2018).
https://doi.org/10.1103/PhysRevA.97.052329

[49] Andreas Bärtschi and Stephan Eidenbenz. “Deterministic preparation of dicke states”. In Fundamentals of Computation Theory. Pages 126–139. Springer International Publishing (2019).
https://doi.org/10.1007/978-3-030-25027-0_9

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

[51] S. E. Anderson, K. C. Younge, and G. Raithel. “Trapping rydberg atoms in an optical lattice”. Phys. Rev. Lett. 107, 263001 (2011).
https://doi.org/10.1103/PhysRevLett.107.263001

[52] S. Ebadi, A. Keesling, M. Cain, et al. “Quantum optimization of maximum independent set using rydberg atom arrays”. Science 376, 1209–1215 (2022).
https://doi.org/10.1126/science.abo6587

[53] T. M. Graham, Y. Song, J. Scott, et al. “Multi-qubit entanglement and algorithms on a neutral-atom quantum computer”. Nature 604, 457–462 (2022).
https://doi.org/10.1038/s41586-022-04603-6

[54] Dolev Bluvstein, Harry Levine, Giulia Semeghini, et al. “A quantum processor based on coherent transport of entangled atom arrays”. Nature 604, 451–456 (2022).
https://doi.org/10.1038/s41586-022-04592-6

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

[56] Joseph W. Britton, Brian C. Sawyer, Adam C. Keith, et al. “Engineered two-dimensional Ising interactions in a trapped-ion quantum simulator with hundreds of spins”. Nature 484 (2012).
https://doi.org/10.1038/nature10981

[57] J. I. Cirac and P. Zoller. “A scalable quantum computer with ions in an array of microtraps”. Nature 404, 579–581 (2000).
https://doi.org/10.1038/35007021

[58] Muir Kumph, Michael Brownnutt, and Rainer Blatt. “Two-dimensional arrays of radio-frequency ion traps with addressable interactions”. New Journal of Physics 13, 073043 (2011).
https://doi.org/10.1088/1367-2630/13/7/073043

[59] Manuel Mielenz, Henning Kalis, Matthias Wittemer, et al. “Arrays of individually controlled ions suitable for two-dimensional quantum simulations”. Nature Communications 7, ncomms11839 (2016).
https://doi.org/10.1038/ncomms11839

[60] B Foxen, J Y Mutus, E Lucero, et al. “Qubit compatible superconducting interconnects”. Quantum Science and Technology 3, 014005 (2017).
https://doi.org/10.1088/2058-9565/aa94fc

[61] Ming Gong, Shiyu Wang, Chen Zha, et al. “Quantum walks on a programmable two-dimensional 62-qubit superconducting processor”. Science 372, 948–952 (2021).
https://doi.org/10.1126/science.abg7812

[62] Tim Menke, William P. Banner, Thomas R. Bergamaschi, et al. “Demonstration of tunable three-body interactions between superconducting qubits”. Phys. Rev. Lett. 129, 220501 (2022).
https://doi.org/10.1103/PhysRevLett.129.220501

[63] Nico W. Hendrickx, William I. L. Lawrie, Maximilian Russ, et al. “A four-qubit germanium quantum processor”. Nature 591, 580–585 (2021).
https://doi.org/10.1038/s41586-021-03332-6

[64] L. M. K. Vandersypen, H. Bluhm, J. S. Clarke, et al. “Interfacing spin qubits in quantum dots and donors—hot, dense, and coherent”. npj Quantum Information 3, 34 (2017).
https://doi.org/10.1038/s41534-017-0038-y

[65] M. Veldhorst, H. G. J. Eenink, C. H. Yang, and A. S. Dzurak. “Silicon CMOS architecture for a spin-based quantum computer”. Nature Communications 8, 1766 (2017).
https://doi.org/10.1038/s41467-017-01905-6

[66] Ruoyu Li, Luca Petit, David P. Franke, et al. “A crossbar network for silicon quantum dot qubits”. Science Advances 4, eaar3960 (2018).
https://doi.org/10.1126/sciadv.abg9158

[67] J.R. Johansson, P.D. Nation, and Franco Nori. “Qutip 2: A python framework for the dynamics of open quantum systems”. Computer Physics Communications 184, 1234–1240 (2013).
https://doi.org/10.1016/j.cpc.2012.11.019

[68] Tameem Albash, Walter Vinci, and Daniel A. Lidar. “Simulated-quantum-annealing comparison between all-to-all connectivity schemes”. Phys. Rev. A 94, 022327 (2016).
https://doi.org/10.1103/PhysRevA.94.022327

[69] Fernando Pastawski and John Preskill. “Error correction for encoded quantum annealing”. Phys. Rev. A 93, 052325 (2016).
https://doi.org/10.1103/PhysRevA.93.052325

[70] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner. “Error mitigation for quantum approximate optimization” (2023). arXiv:2301.05042.
arXiv:2301.05042

[71] Sergey Bravyi, David P. DiVincenzo, and Daniel Loss. “Schrieffer–wolff transformation for quantum many-body systems”. Annals of Physics 326, 2793–2826 (2011).
https://doi.org/10.1016/j.aop.2011.06.004

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

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

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

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

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

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-03-18 22:04:48). 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-18 22:04:47).

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.