Pariteedi kvantoptimeerimine: kodeerimise piirangud

Pariteedi kvantoptimeerimine: kodeerimise piirangud

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

1Parity Quantum Computing GmbH, A-6020 Innsbruck, Austria
2Teoreetilise Füüsika Instituut, Innsbrucki Ülikool, A-6020 Innsbruck, Austria

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

Piirangud muudavad raskete optimeerimisprobleemide lahendamise kvantseadmetes veelgi raskemaks, kuna neid rakendatakse suurte energiatrahvide ja täiendavate kubitikuludega. Pariteedi kaardistamine, mis on kasutusele võetud spin-kodeeringu alternatiivina, muudab probleemi esituseks, mis kasutab ainult paarsusmuutujaid, mis kodeerivad spin-muutujate korruseid. Kombineerides paarsusesituses vahetusinteraktsiooni ja üksikuid spin-flip-termineid, saab kahemõõtmelistes kvantsüsteemides rakendada piiranguid suvaliste $k$-kehade summadele ja korrutistele ilma lisakuludeta.

► BibTeX-i andmed

► Viited

[1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann jt. "Kvant-adiabaatilise evolutsiooni algoritm, mida rakendatakse NP-täieliku probleemi juhuslikel juhtudel". Science 292, 472–475 (2001).
https://​/​doi.org/​10.1126/​science.1057726

[2] David Allouche, Isabelle Andre, Sophie Barbe jt. "Arvutusvalgu disain kui optimeerimisprobleem". Tehisintellekt 212, 59–79 (2014).
https://​/​doi.org/​10.1016/​j.artint.2014.03.005

[3] Simon Gravel ja Veit Elser. "Jaga ja nõustu: üldine lähenemine piirangutega rahulolule". Phys. Rev. E 78, 036706 (2008).
https://​/​doi.org/​10.1103/​PhysRevE.78.036706

[4] Florian Neukart, Gabriele Compostella, Christian Seidel jt. "Liiklusvoo optimeerimine kvantannileri abil" (2017). arXiv:1708.01625.
arXiv: 1708.01625

[5] Eleanor G. Rieffel, Davide Venturelli, Bryan O'Gorman jt. Juhtumiuuring kvantannileri programmeerimisel raskete operatiivplaneerimise probleemide jaoks. Quantum Information Processing 14 (2015).
https://​/​doi.org/​10.1007/​s11128-014-0892-x

[6] Emmanuel Hebrard, Eoin O'Mahony ja Barry O'Sullivan. "Piirangute programmeerimine ja kombinatoorne optimeerimine Numberjackis". Andrea Lodi, Michela Milano ja Paolo Toth, toimetajad, AI- ja OR-tehnikate integreerimine piirangute programmeerimisel kombinatoorse optimeerimise probleemide jaoks. Loengukonspektid arvutiteaduses. Springer (2010).
https:/​/​doi.org/​10.1007/​978-3-642-13520-0_22

[7] MW Johnson, MHS Amin, S. Gildert jt. "Kvantlõõmutamine valmistatud spinnidega". Loodus 473 (2011).
https://​/​doi.org/​10.1038/​nature10012

[8] Pei Cao, Zhaoyan Fan, Robert X. Gao ja Jiong Tang. „Konfiguratsiooni optimeerimise probleemi lahendamine mitme raske piiranguga: täiustatud mitme eesmärgiga simuleeritud lõõmutamisviis” (2017). arXiv:1706.03141.
arXiv: 1706.03141

[9] Frank Arute, Kunal Arya, Ryan Babbush jt. "Kvantide ülemvõim programmeeritava ülijuhtiva protsessori abil". Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[10] Hannes Bernien, Sylvain Schwartz, Alexander Keesling jt. "Paljude kehade dünaamika uurimine 51-aatomilisel kvantsimulaatoril". Nature 551, 579 EP – (2017).
https://​/​doi.org/​10.1038/​nature24622

[11] Jens Koch, Terri M. Yu, Jay Gambetta jt. "Laengutundlik kubiti disain, mis on tuletatud cooperi paari kastist". Phys. Rev. A 76, 042319 (2007).
https://​/​doi.org/​10.1103/​PhysRevA.76.042319

[12] M. Saffman, TG Walker ja K. Mølmer. "Kvantiteave Rydbergi aatomitega". Rev. Mod. Phys. 82, 2313–2363 (2010).
https://​/​doi.org/​10.1103/​RevModPhys.82.2313

[13] Loïc Henriet, Lucas Beguin, Adrien Signoles jt. "Kvantarvutus neutraalsete aatomitega". Quantum 4 (2020).
https:/​/​doi.org/​10.22331/​q-2020-09-21-327

[14] Immanuel Bloch, Jean Dalibard ja Wilhelm Zwerger. "Paljude kehade füüsika ülikülmade gaasidega". Rev. Mod. Phys. 80, 885–964 (2008).
https://​/​doi.org/​10.1103/​RevModPhys.80.885

[15] Zhengbing Bian, Fabian Chudak, Robert Brian Israel jt. "Piiratud optimeerimisprobleemide kaardistamine kvantlõõmutusega koos veadiagnostika rakendamisega". Piirid IKT-s 3 (2016).
https://​/​doi.org/​10.3389/​fict.2016.00014

[16] Adam Douglass, Andrew D. King ja Jack Raymond. "SAT-filtrite ehitamine kvantlõõmutajaga". Marijn Heule ja Sean Weaver, toimetajad, 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. "Paljude NP-probleemide formulatsioonid". Esiosa. Phys. 2, 5 (2014).
https://​/​doi.org/​10.3389/​fphy.2014.00005

[18] Edward Farhi, Jeffrey Goldstone ja Sam Gutmann. "Kvantligikaudne optimeerimisalgoritm" (2014). arXiv:1411.4028.
arXiv: 1411.4028

[19] Tadashi Kadowaki ja Hidetoshi Nishimori. "Kvantlõõmutamine põiksuunalises mudelis". Phys. Rev. E 58, 5355–5363 (1998).
https://​/​doi.org/​10.1103/​PhysRevE.58.5355

[20] Arnab Das ja Bikas K. Chakrabarti. "Kollokvium: kvantlõõmutamine ja analoogkvantarvutus". Rev. Mod. Phys. 80, 1061–1081 (2008).
https://​/​doi.org/​10.1103/​RevModPhys.80.1061

[21] Philipp Hauke, Helmut G. Katzgraber, Wolfgang Lechner jt. "Kvantlõõmutamise perspektiivid: meetodid ja teostused". Aruanded füüsika edusammude kohta 83, 054401 (2020).
https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8

[22] Tomas Vyskocil ja Hristo Djidjev. "Optimeerimisprobleemide võrdõiguslikkuse piirangute manustamine kvantlõõmutajasse". Algoritmid 12 (2019).
https://​/​doi.org/​10.3390/​a12040077

[23] Itay Hen ja Federico M. Spedalieri. "Kvantlõõmutamine piiratud optimeerimiseks". Phys. Rev. Applied 5, 034007 (2016).
https://​/​doi.org/​10.1103/​PhysRevApplied.5.034007

[24] Itay Hen ja Marcelo S. Sarandy. "Juhi hamiltonianlased kvantlõõmutamise piiratud optimeerimiseks". Phys. Rev. A 93, 062312 (2016).
https://​/​doi.org/​10.1103/​PhysRevA.93.062312

[25] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman jt. "Kvantligikaudsest optimeerimisalgoritmist kuni kvantvahelduva operaatorini ansatz". Algoritmid 12 (2019).
https://​/​doi.org/​10.3390/​a12020034

[26] Kazuki Ikeda, Yuma Nakamura ja Travis S. Humble. "Kvantlõõmutamise rakendamine õe planeerimise probleemile". Scientific Reports 9, 12837 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-49172-3

[27] Hirotaka Irie, Goragot Wongpaisarnsin, Masayoshi Terabe jt. "Sõidukite marsruutimise probleemi kvantlõõmutamine aja, oleku ja võimsusega". Sebastian Feld ja Claudia Linnhoff-Popien, toimetajad, Quantum Technology and Optimization Problems. Lk 145–156. Loengukonspektid arvutiteaduses Cham (2019). Springer International Publishing.
https:/​/​doi.org/​10.1007/​978-3-030-14082-3_13

[28] Tobias Stollenwerk, Bryan O'Gorman, Davide Venturelli jt. "Lennuliikluse juhtimise optimaalsete trajektooride konfliktide kõrvaldamiseks rakendatud kvantlõõmutamine". IEEE Transactions on Intelligent Transportation Systems 21, 285–297 (2020).
https://​/​doi.org/​10.1109/​TITS.2019.2891235

[29] Itay Hen ja AP Young. "Kvant-adiabaatilise algoritmi eksponentsiaalne keerukus teatud rahuldamisprobleemide jaoks". Phys. Rev. E 84, 061152 (2011).
https://​/​doi.org/​10.1103/​PhysRevE.84.061152

[30] Hok K. Ng, Banavar Sridhar ja Shon Grabbe. "Lennuki trajektooride optimeerimine mitmel ristluskõrgusega tuulte korral". Journal of Aerospace Information Systems 11 (2014).
https://​/​doi.org/​10.2514/​1.I010084

[31] Eleanor Rieffel, Davide Venturelli, Minh Do jt. "Faasiüleminekutest raskete planeerimisprobleemidega parameetrilised perekonnad". AAAI tehisintellekti konverentsi materjalid 28 (2014).
https://​/​doi.org/​10.1609/​aaai.v28i1.9044

[32] Davide Venturelli, Dominic JJ Marchand ja Galo Rojo. "Quantum Annealing Implementation of Job-Shop Scheduling" (2016). arXiv:1506.08479.
arXiv: 1506.08479

[33] Gili Rosenberg, Poya Haghnegahdar, Phil Goddard jt. "Optimaalse kauplemistrajektoori probleemi lahendamine kvantlõõmutaja abil". 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 ja Eleanor G. Rieffel. “$XY$ mikserid: analüütilised ja numbrilised tulemused kvantvahelduva operaatori ansatz jaoks”. Phys. Rev. A 101, 012320 (2020).
https://​/​doi.org/​10.1103/​PhysRevA.101.012320

[35] Jeremy Cook, Stephan Eidenbenz ja Andreas Bärtschi. "Kvanti vahelduv operaator ansatz maksimaalsel k-tipu kattel". 2020. aastal toimub IEEE rahvusvaheline kvantarvutite ja -tehnoloogia konverents (QCE). Lk 83–92. (2020).
https://​/​doi.org/​10.1109/​QCE49297.2020.00021

[36] Wolfgang Lechner, Philipp Hauke ​​ja Peter Zoller. "Kvantlõõmutusarhitektuur kohalike interaktsioonide täieliku ühenduvusega". Sci. Adv. 1, 1500838 (2015).
https://​/​doi.org/​10.1126/​sciadv.1500838

[37] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff jt. "Pariteedi kvantoptimeerimine: koostaja" (2021). arXiv:2105.06233.
arXiv: 2105.06233

[38] Michael Fellner, Kilian Ender, Roeland ter Hoeven ja Wolfgang Lechner. "Pariteedi kvantoptimeerimine: võrdlusnäitajad" (2021). arXiv:2105.06240.
arXiv: 2105.06240

[39] Vicky Choi. "Väike kinnistamine adiabaatilises kvantarvutuses: I. Parameetrite seadistamise probleem". Quantum Information Processing 7, 193–209 (2008).
https:/​/​doi.org/​10.1007/​s11128-008-0082-9

[40] Walter Vinci, Tameem Albash, Gerardo Paz-Silva jt. "Kvantlõõmutamise korrektsioon väikese manustamisega". Phys. Rev. A 92, 042310 (2015).
https://​/​doi.org/​10.1103/​PhysRevA.92.042310

[41] Yu Yamashiro, Masaki Ohkuwa, Hidetoshi Nishimori ja Daniel A. Lidar. "Pöördlõõmutamise dünaamika täielikult ühendatud $p$-spin mudeli jaoks". Phys. Rev. A 100, 052321 (2019).
https://​/​doi.org/​10.1103/​PhysRevA.100.052321

[42] Tameem Albash ja Daniel A. Lidar. "Adiabaatiline kvantarvutus". Rev. Mod. Phys. 90, 015002 (2018).
https://​/​doi.org/​10.1103/​RevModPhys.90.015002

[43] Rolando D. Somma, Daniel Nagaj ja Mária Kieferová. "Kvantkiirendamine kvantlõõmutamise teel". Phys. Rev. Lett. 109, 050501 (2012).
https://​/​doi.org/​10.1103/​PhysRevLett.109.050501

[44] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin jt. "Erinevad optimeerimisstrateegiad kvantadiabaatilise algoritmi abil" (2014). arXiv:1401.7320.
arXiv: 1401.7320

[45] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo ja Matthias Troyer. "Mittestokvastilised hamiltonianid ja tärkava spinklaasi kvantlõõmutamine". Phys. Rev. B 95, 184416 (2017).
https://​/​doi.org/​10.1103/​PhysRevB.95.184416

[46] Andreas Hartmann ja Wolfgang Lechner. "Kiired vastudiabaatilised pühkimised võremõõturi adiabaatilises kvantarvutuses". Uus J. Phys. 21, 043025 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab14a0

[47] MHS Amin. "Adiabaatilise teoreemi kooskõla". Phys. Rev. Lett. 102, 220401 (2009).
https://​/​doi.org/​10.1103/​PhysRevLett.102.220401

[48] Lukas M. Sieberer ja Wolfgang Lechner. "Iseerimiskonfiguratsioonide programmeeritavad superpositsioonid". Phys. Rev. A 97, 052329 (2018).
https://​/​doi.org/​10.1103/​PhysRevA.97.052329

[49] Andreas Bärtschi ja Stephan Eidenbenz. "Dikke olekute deterministlik ettevalmistamine". Arvutusteooria alustes. Lk 126–139. Springer International Publishing (2019).
https:/​/​doi.org/​10.1007/​978-3-030-25027-0_9

[50] Wolfgang Lechner. "Kvantligikaudne optimeerimine paralleelsete väravatega". IEEE Transactions on Quantum Engineering 1, 1–6 (2020).
https://​/​doi.org/​10.1109/​TQE.2020.3034798

[51] SE Anderson, KC Younge ja G. Raithel. "Rydbergi aatomite püüdmine optilises võres". Phys. Rev. Lett. 107, 263001 (2011).
https://​/​doi.org/​10.1103/​PhysRevLett.107.263001

[52] S. Ebadi, A. Keesling, M. Cain jt. "Maksimaalse sõltumatu komplekti kvantoptimeerimine Rydbergi aatomimassiivide abil". Science 376, 1209–1215 (2022).
https://​/​doi.org/​10.1126/​science.abo6587

[53] TM Graham, Y. Song, J. Scott jt. "Mitme qubit põimumine ja algoritmid neutraalse aatomiga kvantarvutis". Nature 604, 457–462 (2022).
https:/​/​doi.org/​10.1038/​s41586-022-04603-6

[54] Dolev Bluvstein, Harry Levine, Giulia Semeghini jt. "Kvantprotsessor, mis põhineb takerdunud aatomimassiivide koherentsel transpordil". Nature 604, 451–456 (2022).
https:/​/​doi.org/​10.1038/​s41586-022-04592-6

[55] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng jt. "Kvantoptimeerimine nelja korpusega Rydbergi väravate kaudu". Phys. Rev. Lett. 128, 120503 (2022).
https://​/​doi.org/​10.1103/​PhysRevLett.128.120503

[56] Joseph W. Britton, Brian C. Sawyer, Adam C. Keith jt. "Isingi kahemõõtmelised interaktsioonid lõksus olevas sadade keerutustega kvantsimulaatoris". Loodus 484 (2012).
https://​/​doi.org/​10.1038/​nature10981

[57] JI Cirac ja P. Zoller. "Skaleeritav kvantarvuti ioonidega mikrolõksudes". Nature 404, 579–581 (2000).
https://​/​doi.org/​10.1038/​35007021

[58] Muir Kumph, Michael Brownnutt ja Rainer Blatt. "Adresseeritavate interaktsioonidega raadiosageduslike ioonilõksude kahemõõtmelised massiivid". New Journal of Physics 13, 073043 (2011).
https:/​/​doi.org/​10.1088/​1367-2630/​13/​7/​073043

[59] Manuel Mielenz, Henning Kalis, Matthias Wittemer jt. "Individuaalselt juhitavate ioonide massiivid, mis sobivad kahemõõtmeliste kvantsimulatsioonide jaoks". Nature Communications 7, ncomms11839 (2016).
https://​/​doi.org/​10.1038/​ncomms11839

[60] B Foxen, JY Mutus, E Lucero jt. "Qubitiga ühilduvad ülijuhtivad ühendused". Quantum Science and Technology 3, 014005 (2017).
https://​/​doi.org/​10.1088/​2058-9565/​aa94fc

[61] Ming Gong, Shiyu Wang, Chen Zha jt. "Kvant kõnnib programmeeritava kahemõõtmelise 62-kubitise ülijuhtiva protsessoriga". Science 372, 948–952 (2021).
https://​/​doi.org/​10.1126/​science.abg7812

[62] Tim Menke, William P. Banner, Thomas R. Bergamaschi jt. "Tuunitavate kolme keha interaktsioonide demonstreerimine ülijuhtivate kubitite vahel". Phys. Rev. Lett. 129, 220501 (2022).
https://​/​doi.org/​10.1103/​PhysRevLett.129.220501

[63] Nico W. Hendrickx, William IL Lawrie, Maximilian Russ jt. "Nelja kubitine germaaniumi kvantprotsessor". Nature 591, 580–585 (2021).
https:/​/​doi.org/​10.1038/​s41586-021-03332-6

[64] LMK Vandersypen, H. Bluhm, JS Clarke jt. "Spin-qubitide liidestamine kvantpunktides ja doonorites – kuumad, tihedad ja sidusad". npj Quantum Information 3, 34 (2017).
https://​/​doi.org/​10.1038/​s41534-017-0038-y

[65] M. Veldhorst, HGJ Eenink, CH Yang ja AS Dzurak. "Silicon CMOS arhitektuur spin-põhise kvantarvuti jaoks". Nature Communications 8, 1766 (2017).
https:/​/​doi.org/​10.1038/​s41467-017-01905-6

[66] Ruoyu Li, Luca Petit, David P. Franke jt. "Räni kvantpunkt-kubittide risttala võrk". Science Advances 4, eaar3960 (2018).
https://​/​doi.org/​10.1126/​sciadv.abg9158

[67] JR Johansson, PD Nation ja Franco Nori. "Qutip 2: Pythoni raamistik avatud kvantsüsteemide dünaamika jaoks". Computer Physics Communications 184, 1234–1240 (2013).
https://​/​doi.org/​10.1016/​j.cpc.2012.11.019

[68] Tameem Albash, Walter Vinci ja Daniel A. Lidar. Simuleeritud kvantlõõmutamise võrdlus kõik-kõigile ühenduvusskeemide vahel. Phys. Rev. A 94, 022327 (2016).
https://​/​doi.org/​10.1103/​PhysRevA.94.022327

[69] Fernando Pastawski ja John Preskill. "Veaparandus kodeeritud kvantlõõmutamise jaoks". Phys. Rev. A 93, 052325 (2016).
https://​/​doi.org/​10.1103/​PhysRevA.93.052325

[70] Anita Weidinger, Glen Bigan Mbeng ja Wolfgang Lechner. "Veade leevendamine kvantumbkaudse optimeerimise jaoks" (2023). arXiv:2301.05042.
arXiv: 2301.05042

[71] Sergey Bravyi, David P. DiVincenzo ja Daniel Loss. "Schrieffer-Wolffi transformatsioon kvant-mitmekehasüsteemide jaoks". Annals of Physics 326, 2793–2826 (2011).
https://​/​doi.org/​10.1016/​j.aop.2011.06.004

Viidatud

[1] Dylan Herman, Cody Googin, Xiaoyuan Liu, Aleksei Galda, Ilja Safro, Yue Sun, Marco Pistoia ja Juri Aleksejev, "Uuring kvantarvutite kohta rahanduses", arXiv: 2201.02773, (2022).

[2] Sheir Yarkoni, Elena Raponi, Thomas Bäck ja Sebastian Schmitt, "Kvantlõõmutamine tööstuslikeks rakendusteks: tutvustus ja ülevaade", Aruanded füüsika edusammude kohta 85 10, 104001 (2022).

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

[4] PV Sriluckshmy, Vicente Pina-Canelles, Mario Ponce, Manuel G. Algaba, Fedor Šimkovic ja Martin Leib, "Parameetriliste mitmekbitiliste Pauli väravate optimaalne riistvaraline dekomponeerimine", arXiv: 2303.04498, (2023).

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

[6] Narendra N. Hegade, Koushik Paul, F. Albarrán-Arriagada, Xi Chen ja Enrique Solano, "Digitiseeritud adiabaatiline kvantfaktoriseerimine", Physical Review A 104 5, L050403 (2021).

[7] Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler ja Wolfgang Lechner, „Kvantarvutite kodeerimisest sõltumatu optimeerimisprobleemi formuleering”, arXiv: 2302.03711, (2023).

[8] R. Cumming ja T. Thomas, "Kvantarvuti kasutamine reaalse maailma probleemi lahendamiseks – mida on tänapäeval võimalik saavutada?", arXiv: 2211.13080, (2022).

Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2023-03-18 10:03:05). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.

On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2023-03-18 10:03:04).

Ajatempel:

Veel alates Quantum Journal