Hitra simulacija ravninskih Cliffordovih vezij

Hitra simulacija ravninskih Cliffordovih vezij

Časovni žig: 12. februar 2024 10
Izvorno vozlišče: 2478537

David Gosset1,2,3, Daniel Grier1,4,5, Alex Kerzner1,2in Luke Schaeffer1,2,6

1Inštitut za kvantno računalništvo, Univerza v Waterlooju, Kanada
2Oddelek za kombinatoriko in optimizacijo, Univerza Waterloo, Kanada
3Perimeter Institute for Theoretical Physics, Waterloo, Kanada
4Cheriton School of Computer Science, Univerza Waterloo, Kanada
5Oddelek za računalništvo in tehniko ter Oddelek za matematiko Univerze v Kaliforniji, San Diego, ZDA
6Skupni center za kvantne informacije in računalništvo, College Park, Maryland, ZDA

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Splošno kvantno vezje je mogoče klasično simulirati v eksponentnem času. Če ima planarno postavitev, potem ima algoritem krčenja tenzorskega omrežja po Markovu in Shiju eksponentno trajanje izvajanja v kvadratnem korenu svoje velikosti ali na splošno eksponentno v drevesni širini osnovnega grafa. Ločeno sta Gottesman in Knill pokazala, da če so vsa vrata omejena na Clifford, potem obstaja polinomska časovna simulacija. Združili smo ti dve ideji in pokazali, da je mogoče drevesno širino in planarnost izkoristiti za izboljšanje simulacije Cliffordovega vezja. Naš glavni rezultat je klasičen algoritem z asimptotičnim skaliranjem izvajalnega časa kot $ n^{omega/2}$ $lt$ $n^{1.19}$, ki vzorči iz izhodne porazdelitve, dobljene z merjenjem vseh $n$ kubitov stanja ravninskega grafa v danih Paulijevih bazah. Tu je $omega$ eksponent množenja matrike. Ponujamo tudi klasični algoritem z enakim asimptotičnim časom izvajanja, ki vzorči iz izhodne porazdelitve katerega koli Cliffordovega vezja s konstantno globino v ravninski geometriji. Naše delo izboljšuje znane klasične algoritme s kubičnim časom izvajanja.

Ključna sestavina je preslikava, ki glede na drevesno razgradnjo nekega grafa $G$ ustvari Cliffordovo vezje s strukturo, ki zrcali drevesno razgradnjo in posnema merjenje ustreznega stanja grafa. Zagotavljamo klasično simulacijo tega vezja z zgoraj navedenim časom izvajanja za ravninske grafe in sicer $nt^{omega-1}$, kjer je $t$ širina drevesne razgradnje. Naš algoritem vključuje dva podprograma, ki sta lahko neodvisno zanimiva. Prva je različica matričnega množenja in časa Gottesman-Knillove simulacije večkubitnih meritev na stanjih stabilizatorja. Drugi je nov klasični algoritem za reševanje simetričnih linearnih sistemov nad $mathbb{F}_2$ v ravninski geometriji, ki razširja prejšnja dela, ki so veljala samo za nesingularne linearne sisteme v analogni nastavitvi.

Predstavljena slika: v smeri urinega kazalca z leve: graf, lepa razčlenitev drevesa in vezje, ki pripravlja ustrezno stanje grafa.

[Vgrajeni vsebina]

► BibTeX podatki

► Reference

[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. "Kvantna premoč z uporabo programabilnega superprevodnega procesorja". Narava 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] "Ibm kvantna dokumentacija". https://​/​docs.quantum.ibm.com/​run.
https://​/​docs.quantum.ibm.com/​run

[3] Matthew D Reed, Leonardo DiCarlo, Simon E Nigg, Luyan Sun, Luigi Frunzio, Steven M Girvin in Robert J Schoelkopf. "Realizacija tri-kubitne kvantne korekcije napak s superprevodnimi vezji". Narava 482, 382–385 (2012).
https: / / doi.org/ 10.1038 / nature10786

[4] Antonio D Córcoles, Easwar Magesan, Srikanth J Srinivasan, Andrew W Cross, Matthias Steffen, Jay M Gambetta in Jerry M Chow. "Demonstracija kode za kvantno odkrivanje napak z uporabo kvadratne mreže štirih superprevodnih kubitov". Nature Communications 6, 1–10 (2015).
https: / / doi.org/ 10.1038 / ncomms7979

[5] Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang idr. "Podaljšanje življenjske dobe kvantnega bita s popravljanjem napak v superprevodnih vezjih". Narava 536, 441–445 (2016).
https: / / doi.org/ 10.1038 / nature18949

[6] Igor L Markov in Yaoyun Shi. "Simulacija kvantnega računanja s krčenjem tenzorskih mrež". SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[7] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy in Hartmut Neven. »Simulacija nizkoglobinskih kvantnih vezij kot kompleksnih neusmerjenih grafičnih modelov« (2017).

[8] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset in Mark Howard. "Simulacija kvantnih vezij z razpadi stabilizatorjev nizkega ranga". Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[9] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W Draeger, Eric T Holland in Robert Wisnieff. »Prebijanje 49-kubitne pregrade pri simulaciji kvantnih vezij« (2017).

[10] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh in Robert Wisnieff. »Izkoriščanje sekundarnega pomnilnika za simulacijo globokih 54-qubitnih vezij Sycamore« (2019).

[11] Boaz Barak, Chi-Ning Chou in Xun Gao. »Ponarejanje linearnega navzkrižnega entropijskega primerjanja v plitvih kvantnih vezjih« (2020).

[12] Barbara M Terhal in David P DiVincenzo. »Prilagodljivo kvantno računanje, kvantna vezja s konstantno globino in igre Arthur-Merlin« (2002).

[13] Michael J Bremner, Richard Jozsa in Dan J Shepherd. "Klasična simulacija komutiranih kvantnih izračunov implicira propad polinomske hierarhije". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459–472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

[14] Scott Aaronson in Alex Arkhipov. "Računalniška kompleksnost linearne optike". V zborniku triinštiridesetega letnega simpozija ACM o teoriji računalništva. Strani 333–342. (2011).
https: / / doi.org/ 10.1145 / 1993636.1993682

[15] Daniel Gottesman. “Heisenbergova predstavitev kvantnih računalnikov” (1998).

[16] Sergey Bravyi in David Gosset. "Izboljšana klasična simulacija kvantnih vezij, kjer prevladujejo Cliffordova vrata". Fizična pregledna pisma 116, 250501 (2016).
https: / / doi.org/ 10.1103 / physrevlett.116.250501

[17] Scott Aaronson in Daniel Gottesman. "Izboljšana simulacija stabilizatorskih vezij". Physical Review A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[18] Sergey Bravyi, David Gosset in Robert König. "Kvantna prednost s plitvimi vezji". Znanost 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

[19] Adam Bene Watts, Robin Kothari, Luke Schaeffer in Avishay Tal. "Eksponentna ločitev med plitvimi kvantnimi vezji in neomejenimi plitvimi klasičnimi vezji". V zborniku 51. letnega simpozija ACM SIGACT o teoriji računalništva. Strani 515–526. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316404

[20] Daniel Grier in Luke Schaeffer. “Interaktivna plitva Cliffordova vezja: kvantna prednost proti $mathsf{NC}^1$ in več”. V zborniku 52. letnega simpozija ACM SIGACT o teoriji računalništva. Strani 875–888. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384332

[21] Sergey Bravyi, David Gosset, Robert Koenig in Marco Tomamichel. "Kvantna prednost s hrupnimi plitvimi vezji". Nature PhysicsPages 1–6 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[22] Robert Raussendorf in Hans J Briegel. "Enosmerni kvantni računalnik". Physical Review Letters 86, 5188 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[23] Josh Alman in Virginia Vassilevska Williams. »Rafinirana laserska metoda in hitrejše množenje matrik« (2020).

[24] Chaowen Guan in Kenneth W Regan. »Stabilizatorska vezja, kvadratne oblike in računalniški matrični rang« (2019).

[25] Daniel Grier in Luke Schaeffer. “gridCHP++, licenca Apache različica 2.0”. https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0.
https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0

[26] Alan George. "Ugnezdena disekcija pravilne mreže končnih elementov". SIAM Journal on Numerical Analysis 10, 345–363 (1973).
https: / / doi.org/ 10.1137 / 0710032

[27] Richard J Lipton, Donald J Rose in Robert Endre Tarjan. "Splošna ugnezdena disekcija". Revija SIAM o numerični analizi 16, 346–358 (1979).
https: / / doi.org/ 10.1137 / 0716027

[28] Noga Alon in Raphael Yuster. “Reševanje linearnih sistemov z ugnezdeno disekcijo”. Leta 2010 IEEE 51. letni simpozij o temeljih računalništva. Strani 225–234. IEEE (2010).
https: / / doi.org/ 10.1109 / FOCS.2010.28

[29] Richard J. Lipton in Robert Endre Tarjan. “Ločilni izrek za ravninske grafe”. SIAM Journal on Applied Mathematics 36, 177–189 (1979).
https: / / doi.org/ 10.1137 / 0136016

[30] Scott Aaronson in Lijie Chen. “Teoretični temelji zapletenosti eksperimentov kvantne nadvlade”. Na 32. konferenci o računalniški kompleksnosti (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).

[31] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman in Yaoyun Shi. »Klasična simulacija kvantnih vezij srednje velikosti« (2018).

[32] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho in Salvatore Mandrà. "Vzpostavitev meje kvantne premoči s simulacijo 281 pflop/​s". Kvantna znanost in tehnologija 5, 034003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7eeb

[33] Stefan Arnborg, Derek G Corneil in Andrzej Proskurowski. “Zapletenost iskanja vložitev v $k$-drevo”. SIAM Journal on Algebraic Discrete Methods 8, 277–284 (1987).
https: / / doi.org/ 10.1137 / 0608024

[34] HL Bodlaender. “Turistični vodnik po drevesnih širinah”. Acta Cybernetica 11, 1–21 (1993).

[35] Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov in Michał Pilipczuk. “$c^kn$ 5-približni algoritem za drevesno širino”. SIAM Journal on Computing 45, 317–378 (2016).
https: / / doi.org/ 10.1137 / 130947374

[36] Sergey Bravyi, Graeme Smith in John A Smolin. »Trgovanje s klasičnimi in kvantnimi računalniškimi viri«. Physical Review X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[37] M Van den Nest. »Klasična simulacija kvantnega računanja, Gottesman-Knillov izrek in malo več« (2008).

[38] Alex Kerzner. "Cliffordova simulacija: tehnike in aplikacije". magistrsko delo. Univerza Waterloo. (2021).

[39] Carsten Damm. “Težave so končane za $oplus{L}$”. V Jürgen Dassow in Jozef Kelemen, urednika, Aspects and Prospects of Theoretical Computer Science. Strani 130–137. Berlin, Heidelberg (1990). Springer Berlin Heidelberg.
https:/​/​doi.org/​10.1016/​0020-0190(90)90150-V

[40] David Eppstein (2007). commons.wikimedia.org/​wiki/​Datoteka:Tree_decomposition.svg, dostopno 08.

[41] Hans L Bodlaender in Ton Kloks. “Boljši algoritmi za širino poti in drevesno širino grafov”. V avtomatih, jezikih in programiranju: 18. mednarodni kolokvij Madrid, Španija, 8.–12. julij 1991. Zbornik 18. Strani 544–555. Springer (1991).
https:/​/​doi.org/​10.1007/​3-540-54233-7_162

[42] Oscar H Ibarra, Shlomo Moran in Roger Hui. "Posplošitev hitrega algoritma za razgradnjo matrike LUP in aplikacij". Journal of Algorithms 3, 45–56 (1982).
https:/​/​doi.org/​10.1016/​0196-6774(82)90007-4

[43] Adi Ben-Israel in Thomas NE Greville. "Splošni inverzi: teorija in aplikacije". Zvezek 15. Springer Science & Business Media. (2003).
https: / / doi.org/ 10.1007 / b97366

[44] Michael T Goodrich. “Planarni separatorji in vzporedna mnogokotna triangulacija”. Journal of Computer and System Sciences 51, 374–389 (1995).
https: / / doi.org/ 10.1006 / jcss.1995.1076

[45] Jeroen Dehaene in Bart De Moor. “Cliffordova skupina, stabilizatorska stanja ter linearne in kvadratne operacije nad $mathrm{GF}$(2)”. Physical Review A 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

[46] Simon Anders in Hans J Briegel. "Hitra simulacija stabilizatorskih vezij z uporabo predstavitve stanja v grafu". Physical Review A 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

[47] Sergej Bravi. Osebna komunikacija, 2017 (2017).

[48] Maarten Van den Nest, Jeroen Dehaene in Bart De Moor. “Grafični opis delovanja lokalnih Cliffordovih transformacij na stanja grafa”. Physical Review A 69, 022316 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.69.022316

Navedel

[1] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer in Jay M. Gambetta, »Ocena koristi in tveganj kvantnih računalnikov«, arXiv: 2401.16317, (2024).

[2] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd in Alioscia Hamma, »Učenje učinkovitih dekoderjev za kvazikaotične kvantne kodirnike«, arXiv: 2212.11338, (2022).

[3] Ryan L. Mann, "Simulacija kvantnih izračunov s Tuttejevimi polinomi", npj Kvantne informacije 7, 141 (2021).

[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao in Shashank Virmani, "Učinkovita klasična simulacija kvantnih vezij stanja grozda z alternativnimi vhodi", arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun in Xiangdong Zhang, "Visoko zmogljiva vzporedna klasična shema za simulacijo plitvih kvantnih vezij", arXiv: 2103.00693, (2021).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2024-02-13 03:31:05). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2024-02-13 03:31:02).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal