Paritätsquantenoptimierung: Codierungsbeschränkungen

Paritätsquantenoptimierung: Codierungsbeschränkungen

Zeitstempel: 17. März 2023, 5:56 Uhr

Maike Drieb-Schön1,2, Kilian Ender1,2, Younes Javanmard1und Wolfgang Lechner1,2

1Parity Quantum Computing GmbH, A-6020 Innsbruck, Österreich
2Institut für Theoretische Physik, Universität Innsbruck, A-6020 Innsbruck, Österreich

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Beschränkungen machen schwierige Optimierungsprobleme auf Quantengeräten noch schwieriger zu lösen, da sie mit großen Energieeinbußen und zusätzlichem Qubit-Overhead implementiert werden. Die als Alternative zur Spincodierung eingeführte Paritätsabbildung übersetzt das Problem in eine Darstellung, die nur Paritätsvariablen verwendet, die Produkte von Spinvariablen codiert. Durch die Kombination von Austauschwechselwirkung und Einzelspin-Flip-Termen in der Paritätsdarstellung können Beschränkungen für Summen und Produkte beliebiger $k$-Körper-Terme ohne zusätzlichen Overhead in zweidimensionalen Quantensystemen implementiert werden.

Paritätsquantenoptimierung: Codierungsbeschränkungen PlatoBlockchain Data Intelligence. Vertikale Suche. Ai.

► BibTeX-Daten

► Referenzen

[1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, et al. "Ein quantenadiabatischer Evolutionsalgorithmus, der auf zufällige Instanzen eines NP-vollständigen Problems angewendet wird". Wissenschaft 292, 472–475 (2001).
https: / / doi.org/ 10.1126 / science.1057726

[2] David Allouche, Isabelle André, Sophie Barbe, et al. "Computational Protein Design als Optimierungsproblem". Künstliche Intelligenz 212, 59–79 (2014).
https:/​/​doi.org/​10.1016/​j.artint.2014.03.005

[3] Simon Kies und Veit Elser. "Teile und stimme überein: Ein allgemeiner Ansatz zur Befriedigung von Einschränkungen". Phys. Rev. E 78, 036706 (2008).
https: / / doi.org/ 10.1103 / PhysRevE.78.036706

[4] Florian Neukart, Gabriele Compostella, Christian Seidel, et al. „Verkehrsflussoptimierung mit einem Quantenannealer“ (2017). arXiv:1708.01625.
arXiv: 1708.01625

[5] Eleanor G. Rieffel, Davide Venturelli, Bryan O'Gorman, et al. „Eine Fallstudie zur Programmierung eines Quantenannealers für schwierige Betriebsplanungsprobleme“. Quanteninformationsverarbeitung 14 (2015).
https: / / doi.org/ 10.1007 / s11128-014-0892-x

[6] Emmanuel Hebrard, Eoin O'Mahony und Barry O'Sullivan. "Constraint-Programmierung und kombinatorische Optimierung in Numberjack". In Andrea Lodi, Michela Milano und Paolo Toth, Herausgeber, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Vorlesungsunterlagen in Informatik. Springer (2010).
https:/​/​doi.org/​10.1007/​978-3-642-13520-0_22

[7] MW Johnson, MHS Amin, S. Gildert, et al. „Quantenglühen mit hergestellten Spins“. Natur 473 (2011).
https: / / doi.org/ 10.1038 / nature10012

[8] Pei Cao, Zhaoyan Fan, Robert X. Gao und Jiong Tang. „Lösung des Konfigurationsoptimierungsproblems mit mehreren harten Einschränkungen: Ein verbesserter simulierter Annealing-Ansatz mit mehreren Zielen“ (2017). arXiv:1706.03141.
arXiv: 1706.03141

[9] Frank Arute, Kunal Arya, Ryan Babbush, et al. „Quantenüberlegenheit mit einem programmierbaren supraleitenden Prozessor“. Natur 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[10] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, et al. "Untersuchung der Vielteilchendynamik an einem 51-Atom-Quantensimulator". Natur 551, 579 EP – (2017).
https: / / doi.org/ 10.1038 / nature24622

[11] Jens Koch, Terri M. Yu, Jay Gambetta, et al. "Aufladungsunempfindliches Qubit-Design, abgeleitet von der Cooper-Pair-Box". Phys. Rev. A 76, 042319 (2007).
https: / / doi.org/ 10.1103 / PhysRevA.76.042319

[12] M. Saffman, TG Walker und K. Mølmer. „Quanteninformation mit Rydberg-Atomen“. 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. „Quantencomputing mit neutralen Atomen“. Quantum 4 (2020).
https:/​/​doi.org/​10.22331/​q-2020-09-21-327

[14] Immanuel Bloch, Jean Dalibard und Wilhelm Zwerger. „Vielteilchenphysik mit ultrakalten Gasen“. 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. „Abbildung eingeschränkter Optimierungsprobleme auf Quantenglühen mit Anwendung auf die Fehlerdiagnose“. Grenzen in IKT 3 (2016).
https://​/​doi.org/​10.3389/​fict.2016.00014

[16] Adam Douglass, Andrew D. King und Jack Raymond. „Aufbau von SAT-Filtern mit einem Quantum Annealer“. In Marijn Heule und Sean Weaver, Herausgeber, 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] Andreas Lukas. „Ising-Formulierungen vieler NP-Probleme“. Vorderseite. Phys. 2, 5 (2014).
https: / / doi.org/ 10.3389 / fphy.2014.00005

[18] Edward Farhi, Jeffrey Goldstone und Sam Gutmann. „Ein quantennaher Optimierungsalgorithmus“ (2014). arXiv:1411.4028.
arXiv: 1411.4028

[19] Tadashi Kadowaki und Hidetoshi Nishimori. „Quantenglühen im Transversalisierungsmodell“. Phys. Rev. E 58, 5355–5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355

[20] Arnab Das und Bikas K. Chakrabarti. „Kolloquium: Quantenglühen und analoge Quantencomputing“. 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. "Perspektiven des Quantenglühens: Methoden und Implementierungen". Berichte über Fortschritte in der Physik 83, 054401 (2020).
https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8

[22] Tomas Vyskocil und Hristo Djidjev. "Einbettung von Gleichheitsbeschränkungen von Optimierungsproblemen in einen Quantenannealer". Algorithmen 12 (2019).
https: // doi.org/ 10.3390 / a12040077

[23] Itay Hen und Federico M. Spedalieri. "Quantenglühen für eingeschränkte Optimierung". Phys. Rev. Angewendet 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007

[24] Itay Hen und Marcelo S. Sarandy. „Treiber-Hamiltonianer für eingeschränkte Optimierung beim Quantenglühen“. Phys. Rev. A 93, 062312 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.062312

[25] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, et al. „Vom Quanten-Approximations-Optimierungsalgorithmus zum Quanten-Wechseloperator-Ansatz“. Algorithmen 12 (2019).
https: // doi.org/ 10.3390 / a12020034

[26] Kazuki Ikeda, Yuma Nakamura und Travis S. Humble. "Anwendung von Quantum Annealing auf das Problem der Krankenschwesterplanung". Wissenschaftliche Berichte 9, 12837 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-49172-3

[27] Hirotaka Irie, Goragot Wongpaisarnsin, Masayoshi Terabe, et al. „Quantenglühen des Fahrzeugroutingproblems mit Zeit, Zustand und Kapazität“. In Sebastian Feld und Claudia Linnhoff-Popien, Herausgeber, Quantentechnologie und Optimierungsprobleme. Seiten 145–156. Vorlesungsskript Informatik 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 zur Auflösung optimaler Trajektorien für das Flugverkehrsmanagement“. IEEE-Transaktionen zu intelligenten Transportsystemen 21, 285–297 (2020).
https://​/​doi.org/​10.1109/​TITS.2019.2891235

[29] Itay Hen und AP Young. „Exponentielle Komplexität des quantenadiabatischen Algorithmus für bestimmte Erfüllbarkeitsprobleme“. Phys. Rev. E 84, 061152 (2011).
https: / / doi.org/ 10.1103 / PhysRevE.84.061152

[30] Hok K. Ng, Banavar Sridhar und Shon Grabbe. „Optimierung von Flugzeugflugbahnen mit mehreren Reiseflughöhen bei Vorhandensein von Winden“. Zeitschrift für Luft- und Raumfahrtinformationssysteme 11 (2014).
https://​/​doi.org/​10.2514/​1.I010084

[31] Eleanor Rieffel, Davide Venturelli, Minh Do, et al. "Parametrisierte Familien harter Planungsprobleme aus Phasenübergängen". Proceedings of the AAAI Conference on Artificial Intelligence 28 (2014).
https: / / doi.org/ 10.1609 / aaai.v28i1.9044

[32] Davide Venturelli, Dominic JJ Marchand und Galo Rojo. „Quantum Annealing-Implementierung der Job-Shop-Planung“ (2016). arXiv:1506.08479.
arXiv: 1506.08479

[33] Gili Rosenberg, Poya Haghnegahdar, Phil Goddard, et al. "Lösung des Problems der optimalen Handelsbahn mit einem Quantenannealer". 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 und Eleanor G. Rieffel. „$XY$-Mischer: Analytische und numerische Ergebnisse für den Quanten-Wechseloperator-Ansatz“. Phys. Rev. A 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

[35] Jeremy Cook, Stephan Eidenbenz und Andreas Bärtschi. "Der Quantenwechseloperatoransatz zur maximalen k-Vertex-Überdeckung". 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Seiten 83–92. (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00021

[36] Wolfgang Lechner, Philipp Hauke ​​und Peter Zoller. „Eine Quantenglüharchitektur mit All-to-All-Konnektivität durch lokale Wechselwirkungen“. Wissenschaft. Erw. 1, 1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838

[37] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff, et al. „Paritätsquantenoptimierung: Compiler“ (2021). arXiv:2105.06233.
arXiv: 2105.06233

[38] Michael Fellner, Kilian Ender, Roeland ter Hoeven und Wolfgang Lechner. „Paritätsquantenoptimierung: Benchmarks“ (2021). arXiv:2105.06240.
arXiv: 2105.06240

[39] Vicky Choi. "Minor-Einbettung in die adiabatische Quantenberechnung: I. Das Parametereinstellungsproblem". Quanteninformationsverarbeitung 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-Korrektur mit geringer Einbettung“. Phys. Rev. A 92, 042310 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.92.042310

[41] Yu Yamashiro, Masaki Ohkuwa, Hidetoshi Nishimori und Daniel A. Lidar. "Dynamik des Reverse Annealing für das vollständig verbundene $p$-Spin-Modell". Phys. Rev. A 100, 052321 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.052321

[42] Tameem Albash und Daniel A. Lidar. „Adiabatisches Quantenrechnen“. Rev. Mod. Phys. 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002

[43] Rolando D. Somma, Daniel Nagaj und Mária Kieferová. „Quantenbeschleunigung durch Quantenglühen“. 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. „Unterschiedliche Strategien zur Optimierung mit dem quantenadiabatischen Algorithmus“ (2014). arXiv:1401.7320.
arXiv: 1401.7320

[45] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo und Matthias Troyer. "Nichtstoquastische Hamiltonianer und Quantenglühen eines ising Spin-Glases". Phys. Rev. B 95, 184416 (2017).
https://doi.org/ 10.1103/PhysRevB.95.184416

[46] Andreas Hartmann und Wolfgang Lechner. "Schnelle gegendiabatische Sweeps im adiabatischen Quantencomputing von Gittermessgeräten". Neu J. Phys. 21, 043025 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab14a0

[47] MHS-Amin. „Konsistenz des Adiabatensatzes“. Phys. Rev. Lett. 102, 220401 (2009).
https://doi.org/ 10.1103/PhysRevLett.102.220401

[48] Lukas M. Sieberer und Wolfgang Lechner. „Programmierbare Überlagerungen von Ising-Konfigurationen“. Phys. Rev. A 97, 052329 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.052329

[49] Andreas Bärtschi und Stephan Eidenbenz. „Deterministische Vorbereitung von Dicke-Zuständen“. In Grundlagen der Computertheorie. Seiten 126–139. Springer International Publishing (2019).
https:/​/​doi.org/​10.1007/​978-3-030-25027-0_9

[50] Wolfgang Lechner. „Quantennäherungsoptimierung mit parallelisierbaren Gattern“. IEEE Transactions on Quantum Engineering 1, 1–6 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3034798

[51] SE Anderson, KC Younge und G. Raithel. „Rydberg-Atome in einem optischen Gitter einfangen“. Phys. Rev. Lett. 107, 263001 (2011).
https://doi.org/ 10.1103/PhysRevLett.107.263001

[52] S. Ebadi, A. Keesling, M. Cain, et al. "Quantenoptimierung des maximalen unabhängigen Satzes mit Rydberg-Atom-Arrays". Wissenschaft 376, 1209–1215 (2022).
https://​/​doi.org/​10.1126/​science.abo6587

[53] TM Graham, Y. Song, J. Scott, et al. „Multi-Qubit-Verschränkung und Algorithmen auf einem Quantencomputer mit neutralen Atomen“. Natur 604, 457–462 (2022).
https:/​/​doi.org/​10.1038/​s41586-022-04603-6

[54] Dolev Bluvstein, Harry Levine, Giulia Semeghini, et al. „Ein Quantenprozessor, der auf dem kohärenten Transport verschränkter Atomarrays basiert“. Natur 604, 451–456 (2022).
https:/​/​doi.org/​10.1038/​s41586-022-04592-6

[55] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng, et al. „Quantenoptimierung durch Rydberg-Gatter mit vier Körpern“. 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. „Technische zweidimensionale Ising-Wechselwirkungen in einem gefangenen Ionen-Quantensimulator mit Hunderten von Spins“. Natur 484 (2012).
https: / / doi.org/ 10.1038 / nature10981

[57] JI Cirac und P. Zoller. „Ein skalierbarer Quantencomputer mit Ionen in einer Anordnung von Mikrofallen“. Natur 404, 579–581 (2000).
https: / / doi.org/ 10.1038 / 35007021

[58] Muir Kumph, Michael Brownnutt und Rainer Blatt. "Zweidimensionale Arrays von Hochfrequenz-Ionenfallen mit adressierbaren Wechselwirkungen". Neue Zeitschrift für Physik 13, 073043 (2011).
https:/​/​doi.org/​10.1088/​1367-2630/​13/​7/​073043

[59] Manuel Mielenz, Henning Kalis, Matthias Wittemer, et al. "Arrays von einzeln kontrollierten Ionen, die für zweidimensionale Quantensimulationen geeignet sind". Nature Communications 7, ncomms11839 (2016).
https: / / doi.org/ 10.1038 / ncomms11839

[60] B. Foxen, J. Y. Mutus, E. Lucero, et al. „Qubit-kompatible supraleitende Verbindungen“. Quantenwissenschaft und -technologie 3, 014005 (2017).
https://​/​doi.org/​10.1088/​2058-9565/​aa94fc

[61] Ming Gong, Shiyu Wang, Chen Zha, et al. „Quantum Walks auf einem programmierbaren zweidimensionalen 62-Qubit-Supraleiter-Prozessor“. Wissenschaft 372, 948–952 (2021).
https://​/​doi.org/​10.1126/​science.abg7812

[62] Tim Menke, William P. Banner, Thomas R. Bergamaschi, et al. „Demonstration abstimmbarer Dreikörper-Wechselwirkungen zwischen supraleitenden Qubits“. Phys. Rev. Lett. 129, 220501 (2022).
https://doi.org/ 10.1103/PhysRevLett.129.220501

[63] Nico W. Hendrickx, William Il Lawrie, Maximilian Russ, et al. „Ein Vier-Qubit-Germanium-Quantenprozessor“. Natur 591, 580–585 (2021).
https:/​/​doi.org/​10.1038/​s41586-021-03332-6

[64] LMK Vandersypen, H. Bluhm, JS Clarke, et al. „Schnittstelle von Spin-Qubits in Quantenpunkten und Donatoren – heiß, dicht und kohärent“. npj Quantum Information 3, 34 (2017).
https: / / doi.org/ 10.1038 / s41534-017-0038-y

[65] M. Veldhorst, HGJ Eenink, CH Yang und AS Dzurak. „Silizium-CMOS-Architektur für einen Spin-basierten Quantencomputer“. Nature Communications 8, 1766 (2017).
https:/​/​doi.org/​10.1038/​s41467-017-01905-6

[66] Ruoyu Li, Luca Petit, David P. Franke, et al. „Ein Crossbar-Netzwerk für Silizium-Quantenpunkt-Qubits“. Science Advances 4, ear3960 (2018).
https://​/​doi.org/​10.1126/​sciadv.abg9158

[67] JR Johansson, PD Nation und Franco Nori. „Qutip 2: Ein Python-Framework für die Dynamik offener Quantensysteme“. Computer Physics Communications 184, 1234–1240 (2013).
https: / / doi.org/ 10.1016 / j.cpc.2012.11.019

[68] Tameem Albash, Walter Vinci und Daniel A. Lidar. "Simulierter Quantenglühvergleich zwischen All-to-All-Konnektivitätsschemata". Phys. Rev. A 94, 022327 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.94.022327

[69] Fernando Pastawski und John Preskill. „Fehlerkorrektur für codiertes Quantenglühen“. Phys. Rev. A 93, 052325 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.052325

[70] Anita Weidinger, Glen Bigan Mbeng und Wolfgang Lechner. „Fehlerminderung für die Quantennäherungsoptimierung“ (2023). arXiv:2301.05042.
arXiv: 2301.05042

[71] Sergey Bravyi, David P. DiVincenzo und Daniel Loss. „Schrieffer-Wolff-Transformation für Quanten-Vielteilchensysteme“. Annalen der Physik 326, 2793–2826 (2011).
https: / / doi.org/ 10.1016 / j.aop.2011.06.004

Zitiert von

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

[2] Sheir Yarkoni, Elena Raponi, Thomas Bäck und Sebastian Schmitt, „Quantum Annealing for Industry Applications: Introduction and Review“, Berichte über Fortschritte in der Physik 85 10, 104001 (2022).

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

[4] PV Sriluckshmy, Vicente Pina-Canelles, Mario Ponce, Manuel G. Algaba, Fedor Šimkovic und Martin Leib, „Optimal, hardware native decomposition of parametrized multi-qubit Pauli gates“, arXiv: 2303.04498, (2023).

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

[6] Narendra N. Hegade, Koushik Paul, F. Albarrán-Arriagada, Xi Chen und Enrique Solano, „Digitalisierte adiabatische Quantenfaktorisierung“, Physische Überprüfung A 104 5, L050403 (2021).

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

[8] R. Cumming und T. Thomas, „Mit einem Quantencomputer ein reales Problem lösen – was kann heute erreicht werden?“, arXiv: 2211.13080, (2022).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 03:18:10 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-03-18 10:03:04).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal