Paritetskvanteoptimalisering: kodingsbegrensninger

Paritetskvanteoptimalisering: kodingsbegrensninger

Tidsstempel: 17. mars 2023 5:56

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

1Parity Quantum Computing GmbH, A-6020 Innsbruck, Østerrike
2Institutt for teoretisk fysikk, Universitetet i Innsbruck, A-6020 Innsbruck, Østerrike

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Begrensninger gjør vanskelige optimaliseringsproblemer enda vanskeligere å løse på kvanteenheter fordi de er implementert med store energistraff og ekstra qubit-overhead. Paritetskartleggingen, som har blitt introdusert som et alternativ til spinn-kodingen, oversetter problemet til en representasjon som bare bruker paritetsvariabler som koder produkter av spinnvariabler. Ved å kombinere utvekslingsinteraksjon og single spin flip-termer i paritetsrepresentasjonen, kan begrensninger på summer og produkter av vilkårlige $k$-kroppstermer implementeres uten ekstra overhead i todimensjonale kvantesystemer.

Paritetskvanteoptimalisering: Kodingsbegrensninger PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

► BibTeX-data

► Referanser

[1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, et al. "En kvante-adiabatisk evolusjonsalgoritme brukt på tilfeldige tilfeller av et NP-komplett problem". Science 292, 472–475 (2001).
https: / / doi.org/ 10.1126 / science.1057726

[2] David Allouche, Isabelle Andre, Sophie Barbe, et al. "Beregningsproteindesign som et optimaliseringsproblem". Kunstig intelligens 212, 59–79 (2014).
https://doi.org/ 10.1016/j.artint.2014.03.005

[3] Simon Gravel og Veit Elser. "Del og enig: En generell tilnærming til begrensningstilfredshet". Phys. Rev. E 78, 036706 (2008).
https: / / doi.org/ 10.1103 / PhysRevE.78.036706

[4] Florian Neukart, Gabriele Compostella, Christian Seidel, et al. "Trafikkflytoptimalisering ved bruk av en kvanteglør" (2017). arXiv:1708.01625.
arxiv: 1708.01625

[5] Eleanor G. Rieffel, Davide Venturelli, Bryan O'Gorman, et al. "Et casestudie i programmering av en kvanteglør for vanskelige operasjonelle planleggingsproblemer". Quantum Information Processing 14 (2015).
https: / / doi.org/ 10.1007 / s11128-014-0892-x

[6] Emmanuel Hebrard, Eoin O'Mahony og Barry O'Sullivan. "Begrensningsprogrammering og kombinatorisk optimalisering i Numberjack". I Andrea Lodi, Michela Milano og Paolo Toth, redaktører, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problemer. Forelesningsnotater i informatikk. 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. "Kvanteglødning med produserte spinn". Nature 473 (2011).
https: / / doi.org/ 10.1038 / nature10012

[8] Pei Cao, Zhaoyan Fan, Robert X. Gao og Jiong Tang. "Løse konfigurasjonsoptimaliseringsproblem med flere harde begrensninger: En forbedret multi-objektiv simulert annealing-tilnærming" (2017). arXiv:1706.03141.
arxiv: 1706.03141

[9] Frank Arute, Kunal Arya, Ryan Babbush, et al. "Kvanteoverlegenhet ved bruk av en programmerbar superledende prosessor". Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[10] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, et al. "Undersøkelse av mange-kroppsdynamikk på en 51-atoms kvantesimulator". Nature 551, 579 EP – (2017).
https: / / doi.org/ 10.1038 / nature24622

[11] Jens Koch, Terri M. Yu, Jay Gambetta, et al. "Ladingufølsom qubit-design avledet fra Cooper Pair-boksen". Phys. Rev. A 76, 042319 (2007).
https: / / doi.org/ 10.1103 / PhysRevA.76.042319

[12] M. Saffman, TG Walker og K. Mølmer. "Kvanteinformasjon med rydberg-atomer". 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. "Kvanteberegning med nøytrale atomer". Quantum 4 (2020).
https:/​/​doi.org/​10.22331/​q-2020-09-21-327

[14] Immanuel Bloch, Jean Dalibard og Wilhelm Zwerger. "Mangekroppsfysikk med ultrakalde gasser". 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. "Kartlegge begrensede optimaliseringsproblemer til kvantegløding med applikasjon til feildiagnose". Grenser i IKT 3 (2016).
https://​/​doi.org/​10.3389/​fict.2016.00014

[16] Adam Douglass, Andrew D. King og Jack Raymond. "Konstruere SAT-filtre med en Quantum Annealer". I Marijn Heule og Sean Weaver, redaktører, 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-formuleringer av mange NP-problemer". Front. Phys. 2, 5 (2014).
https: / / doi.org/ 10.3389 / fphy.2014.00005

[18] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. "En omtrentlig kvanteoptimaliseringsalgoritme" (2014). arXiv:1411.4028.
arxiv: 1411.4028

[19] Tadashi Kadowaki og Hidetoshi Nishimori. "Kvanteutglødning i den tverrgående isingsmodellen". Phys. Rev. E 58, 5355-5363 (1998).
https: / / doi.org/ 10.1103 / PhysRevE.58.5355

[20] Arnab Das og Bikas K. Chakrabarti. "Kollokvium: Kvanteutglødning og analog kvanteberegning". 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. "Perspektiver av kvanteglødning: metoder og implementeringer". Reports on Progress in Physics 83, 054401 (2020).
https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8

[22] Tomas Vyskocil og Hristo Djidjev. "Innbygging av likhetsbegrensninger for optimaliseringsproblemer i en kvantegløder". Algoritmer 12 (2019).
https: / / doi.org/ 10.3390 / a12040077

[23] Itay Hen og Federico M. Spedalieri. "Kvanteutglødning for begrenset optimalisering". Phys. Rev. Søkt 5, 034007 (2016).
https: / / doi.org/ 10.1103 / PhysRevApplied.5.034007

[24] Itay Hen og Marcelo S. Sarandy. "Driver hamiltonians for begrenset optimalisering i kvanteutglødning". Phys. Rev. A 93, 062312 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.062312

[25] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, et al. "Fra den omtrentlige kvanteoptimaliseringsalgoritmen til en kvantealternerende operatøransatz". Algoritmer 12 (2019).
https: / / doi.org/ 10.3390 / a12020034

[26] Kazuki Ikeda, Yuma Nakamura og Travis S. Humble. "Anvendelse av kvanteglødning på sykepleierplanleggingsproblem". Scientific Reports 9, 12837 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-49172-3

[27] Hirotaka Irie, Goragot Wongpaisarnsin, Masayoshi Terabe, et al. "Kvanteutglødning av kjøretøysrutingsproblem med tid, tilstand og kapasitet". I Sebastian Feld og Claudia Linnhoff-Popien, redaktører, Quantum Technology and Optimization Problems. Side 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. "Kvanteglødning brukt på de-konfliktende optimale baner for lufttrafikkstyring". IEEE Transactions on Intelligent Transportation Systems 21, 285–297 (2020).
https://​/​doi.org/​10.1109/​TITS.2019.2891235

[29] Itay Hen og A. P. Young. "Eksponentiell kompleksitet av den kvante-adiabatiske algoritmen for visse tilfredshetsproblemer". Phys. Rev. E 84, 061152 (2011).
https: / / doi.org/ 10.1103 / PhysRevE.84.061152

[30] Hok K. Ng, Banavar Sridhar og Shon Grabbe. "Optimalisering av flybaner med flere cruisehøyder i nærvær av vind". Journal of Aerospace Information Systems 11 (2014).
https://​/​doi.org/​10.2514/​1.I010084

[31] Eleanor Rieffel, Davide Venturelli, Minh Do, et al. "Parametriserte familier med vanskelige planleggingsproblemer fra faseoverganger". 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 og 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. "Løse problemet med den optimale handelsbanen ved å bruke en kvantegløder". 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 og Eleanor G. Rieffel. "$XY$-miksere: Analytiske og numeriske resultater for kvantealternerende operatøransatz". Phys. Rev. A 101, 012320 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.101.012320

[35] Jeremy Cook, Stephan Eidenbenz og Andreas Bärtschi. "Den kvante alternerende operatøransatz på maksimalt k-vertex-deksel". I 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Side 83–92. (2020).
https: / / doi.org/ 10.1109 / QCE49297.2020.00021

[36] Wolfgang Lechner, Philipp Hauke ​​og Peter Zoller. "En kvanteutglødningsarkitektur med alt-til-alle-tilkobling fra lokale interaksjoner". Sci. Adv. 1, 1500838 (2015).
https: / / doi.org/ 10.1126 / sciadv.1500838

[37] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff, et al. "Paritetskvanteoptimalisering: kompilator" (2021). arXiv:2105.06233.
arxiv: 2105.06233

[38] Michael Fellner, Kilian Ender, Roeland ter Hoeven og Wolfgang Lechner. "Paritetskvanteoptimalisering: Benchmarks" (2021). arXiv:2105.06240.
arxiv: 2105.06240

[39] Vicky Choi. "Mindre innebygging i adiabatisk kvanteberegning: I. Parameterinnstillingsproblemet". 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. "Kvanteutglødningskorreksjon med mindre innebygging". Phys. Rev. A 92, 042310 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.92.042310

[41] Yu Yamashiro, Masaki Ohkuwa, Hidetoshi Nishimori og Daniel A. Lidar. "Dynamikk for omvendt gløding for den fullt tilkoblede $p$-spinn-modellen". Phys. Rev. A 100, 052321 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.052321

[42] Tameem Albash og Daniel A. Lidar. "Adiabatisk kvanteberegning". Rev. Mod. Phys. 90, 015002 (2018).
https: / / doi.org/ 10.1103 / RevModPhys.90.015002

[43] Rolando D. Somma, Daniel Nagaj og Mária Kieferová. "Kvantehastighet ved kvanteglødning". 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. "Ulike strategier for optimalisering ved bruk av den kvante-adiabatiske algoritmen" (2014). arXiv:1401.7320.
arxiv: 1401.7320

[45] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo og Matthias Troyer. "Ikke-stoquastic hamiltonians og kvanteutglødning av et ising spin glass". Phys. Rev. B 95, 184416 (2017).
https: / / doi.org/ 10.1103 / PhysRevB.95.184416

[46] Andreas Hartmann og Wolfgang Lechner. "Raske mot-diabatiske sveip i gittermåler adiabatisk kvanteberegning". Ny J. Phys. 21, 043025 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab14a0

[47] M.H.S. Amin. "Konsistens av det adiabatiske teoremet". Phys. Rev. Lett. 102, 220401 (2009).
https: / / doi.org/ 10.1103 / PhysRevLett.102.220401

[48] Lukas M. Sieberer og Wolfgang Lechner. "Programmerbare superposisjoner av ising-konfigurasjoner". Phys. Rev. A 97, 052329 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.052329

[49] Andreas Bärtschi og Stephan Eidenbenz. "Deterministisk forberedelse av dicke-tilstander". I Fundamentals of Computation Theory. Side 126–139. Springer International Publishing (2019).
https:/​/​doi.org/​10.1007/​978-3-030-25027-0_9

[50] Wolfgang Lechner. "Omtrentlig kvanteoptimalisering med parallelliserbare porter". IEEE Transactions on Quantum Engineering 1, 1–6 (2020).
https: / / doi.org/ 10.1109 / TQE.2020.3034798

[51] S.E. Anderson, K.C. Younge og G. Raithel. "Fange rydberg-atomer i et optisk gitter". Phys. Rev. Lett. 107, 263001 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.107.263001

[52] S. Ebadi, A. Keesling, M. Cain, et al. "Kvanteoptimalisering av maksimalt uavhengig sett ved bruk av rydberg-atommatriser". Science 376, 1209–1215 (2022).
https://​/​doi.org/​10.1126/​science.abo6587

[53] T.M. Graham, Y. Song, J. Scott, et al. "Multi-qubit sammenfiltring og algoritmer på en nøytral-atom kvantedatamaskin". Nature 604, 457–462 (2022).
https:/​/​doi.org/​10.1038/​s41586-022-04603-6

[54] Dolev Bluvstein, Harry Levine, Giulia Semeghini, et al. "En kvanteprosessor basert på sammenhengende transport av sammenfiltrede atommatriser". Nature 604, 451–456 (2022).
https:/​/​doi.org/​10.1038/​s41586-022-04592-6

[55] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng, et al. "Kvanteoptimalisering via rydbergporter med fire kropper". 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. "Konstruert todimensjonale Ising-interaksjoner i en fanget-ion kvantesimulator med hundrevis av spinn". Nature 484 (2012).
https: / / doi.org/ 10.1038 / nature10981

[57] J.I. Cirac og P. Zoller. "En skalerbar kvantedatamaskin med ioner i en rekke mikrofeller". Nature 404, 579–581 (2000).
https: / / doi.org/ 10.1038 / 35007021

[58] Muir Kumph, Michael Brownnutt og Rainer Blatt. "Todimensjonale arrayer av radiofrekvente ionefeller med adresserbare interaksjoner". 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 av individuelt kontrollerte ioner egnet for todimensjonale kvantesimuleringer". Nature Communications 7, ncomms11839 (2016).
https: / / doi.org/ 10.1038 / ncomms11839

[60] B Foxen, JY Mutus, E Lucero, et al. "Qubit-kompatible superledende sammenkoblinger". 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 går på en programmerbar todimensjonal 62-qubit superledende prosessor". Science 372, 948–952 (2021).
https://doi.org/ 10.1126/science.abg7812

[62] Tim Menke, William P. Banner, Thomas R. Bergamaschi, et al. "Demonstrasjon av avstembare trekroppsinteraksjoner mellom superledende 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. "En fire-qubit germanium kvanteprosessor". 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 i kvanteprikker og donorer - varme, tette og sammenhengende". 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 og A. S. Dzurak. "Silisium CMOS-arkitektur for en spinnbasert kvantedatamaskin". Naturkommunikasjon 8, 1766 (2017).
https:/​/​doi.org/​10.1038/​s41467-017-01905-6

[66] Ruoyu Li, Luca Petit, David P. Franke, et al. "Et tverrstangsnettverk for silisiumkvanteprikk-qubits". Science Advances 4, ear3960 (2018).
https://​/​doi.org/​10.1126/​sciadv.abg9158

[67] J.R. Johansson, P.D. Nation og Franco Nori. "Qutip 2: Et pytonrammeverk for dynamikken til åpne kvantesystemer". Computer Physics Communications 184, 1234–1240 (2013).
https: / / doi.org/ 10.1016 / j.cpc.2012.11.019

[68] Tameem Albash, Walter Vinci og Daniel A. Lidar. "Simulert-kvante-annealing sammenligning mellom alt-til-alle tilkoblingsordninger". Phys. Rev. A 94, 022327 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.94.022327

[69] Fernando Pastawski og John Preskill. "Feilretting for kodet kvanteutglødning". Phys. Rev. A 93, 052325 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.93.052325

[70] Anita Weidinger, Glen Bigan Mbeng og Wolfgang Lechner. "Feilredusering for omtrentlig kvanteoptimalisering" (2023). arXiv:2301.05042.
arxiv: 2301.05042

[71] Sergey Bravyi, David P. DiVincenzo og Daniel Loss. "Schrieffer-wolff-transformasjon for kvante-mangekroppssystemer". Annals of Physics 326, 2793–2826 (2011).
https: / / doi.org/ 10.1016 / j.aop.2011.06.004

Sitert av

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

[2] Sheir Yarkoni, Elena Raponi, Thomas Bäck og Sebastian Schmitt, "Quantum annealing for industry applications: introduction and review", Rapporter om fremgang i fysikk 85 10, 104001 (2022).

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

[4] PV Sriluckshmy, Vicente Pina-Canelles, Mario Ponce, Manuel G. Algaba, Fedor Šimkovic og Martin Leib, "Optimal, maskinvarenative dekomponering av parameteriserte multi-qubit Pauli-porter", arxiv: 2303.04498, (2023).

[5] Michael Fellner, Kilian Ender, Roeland ter Hoeven og Wolfgang Lechner, "Parity Quantum Optimization: Benchmarks", arxiv: 2105.06240, (2021).

[6] Narendra N. Hegade, Koushik Paul, F. Albarrán-Arriagada, Xi Chen og Enrique Solano, "Digitisert adiabatisk kvantefaktorisering", Fysisk gjennomgang A 104 5, L050403 (2021).

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

[8] R. Cumming og T. Thomas, "Bruke en kvantedatamaskin for å løse et problem i den virkelige verden - hva kan oppnås i dag?", arxiv: 2211.13080, (2022).

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2023-03-18 10:03:05). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2023-03-18 10:03:04).

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal