Simularea rapidă a circuitelor plane Clifford

Simularea rapidă a circuitelor plane Clifford

Marca temporală: 12 februarie 2024 10:28

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

1Institutul de calcul cuantic, Universitatea din Waterloo, Canada
2Departamentul de Combinatorică și Optimizare, Universitatea din Waterloo, Canada
3Institutul Perimetru pentru Fizică Teoretică, Waterloo, Canada
4Cheriton School of Computer Science, Universitatea din Waterloo, Canada
5Departamentul de Informatică și Inginerie și Departamentul de Matematică, Universitatea din California, San Diego, SUA
6Centrul comun pentru informații cuantice și informatică, College Park, Maryland, SUA

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Un circuit cuantic general poate fi simulat clasic în timp exponențial. Dacă are un aspect plan, atunci un algoritm de contracție a rețelei tensoriale datorat lui Markov și Shi are un timp de rulare exponențial în rădăcina pătrată a dimensiunii sale sau, mai general, exponențial în lățimea arborelui graficului de bază. Separat, Gottesman și Knill au arătat că, dacă toate porțile sunt limitate să fie Clifford, atunci există o simulare de timp polinomială. Combinăm aceste două idei și arătăm că lățimea arborelui și planaritatea pot fi exploatate pentru a îmbunătăți simularea circuitului Clifford. Rezultatul nostru principal este un algoritm clasic cu scalarea timpului de execuție asimptotic ca $ n^{omega/2}$ $lt$ $n^{1.19}$ care eșantioane din distribuția de ieșire obținută prin măsurarea tuturor $n$ qubiți ai stării unui grafic plan. in bazele Pauli date. Aici $omega$ este exponentul de multiplicare a matricei. De asemenea, oferim un algoritm clasic cu același timp de rulare asimptotic care prelevează din distribuția de ieșire a oricărui circuit Clifford cu adâncime constantă într-o geometrie plană. Lucrarea noastră îmbunătățește algoritmii clasici cunoscuți cu timp de rulare cubic.

Un ingredient cheie este o mapare care, având în vedere o descompunere arborescentă a unui grafic $G$, produce un circuit Clifford cu o structură care oglindește descompunerea arborelui și care emulează măsurarea stării grafice corespunzătoare. Oferim o simulare clasică a acestui circuit cu timpul de rulare menționat mai sus pentru graficele plane și, în caz contrar, $nt^{omega-1}$ unde $t$ este lățimea descompunerii arborelui. Algoritmul nostru încorporează două subrutine care pot fi de interes independent. Prima este o versiune matrice-multiplicare-timp a simulării Gottesman-Knill a măsurării multi-qubit pe stările stabilizatorului. Al doilea este un nou algoritm clasic pentru rezolvarea sistemelor liniare simetrice peste $mathbb{F}_2$ într-o geometrie plană, extinzând lucrările anterioare care s-au aplicat doar sistemelor liniare non-singulare în context analog.

Simulare rapidă a circuitelor Clifford plane PlatoBlockchain Data Intelligence. Căutare verticală. Ai.

Imagine prezentată: în sensul acelor de ceasornic de la stânga: un grafic, o descompunere frumoasă a arborelui și un circuit care pregătește starea grafică corespunzătoare.

[Conținutul încorporat]

► Date BibTeX

► Referințe

[1] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell și colab. „Supremația cuantică folosind un procesor supraconductor programabil”. Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] „Documentația cuantică IBM”. 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 și Robert J Schoelkopf. „Realizarea corectării erorilor cuantice de trei qubiți cu circuite supraconductoare”. Nature 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 și Jerry M Chow. „Demonstrarea unui cod de detectare a erorilor cuantice folosind o rețea pătrată de patru qubiți supraconductori”. 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 și colab. „Extinderea duratei de viață a unui bit cuantic cu corectarea erorilor în circuitele supraconductoare”. Nature 536, 441–445 (2016).
https: / / doi.org/ 10.1038 / nature18949

[6] Igor L Markov și Yaoyun Shi. „Simularea calculului cuantic prin contractarea rețelelor tensorale”. SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[7] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy și Hartmut Neven. „Simularea circuitelor cuantice de mică adâncime ca modele grafice complexe nedirecționate” (2017).

[8] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset și Mark Howard. „Simularea circuitelor cuantice prin descompunere de stabilizator de rang scăzut”. 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 și Robert Wisnieff. „Spăgerea barierei de 49 de qubiți în simularea circuitelor cuantice” (2017).

[10] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh și Robert Wisnieff. „Exploarea stocării secundare pentru a simula circuite Sycamore profunde de 54 de qubiți” (2019).

[11] Boaz Barak, Chi-Ning Chou și Xun Gao. „Spoofing liniar cross-entropie benchmarking în circuite cuantice superficiale” (2020).

[12] Barbara M Terhal și David P DiVincenzo. „Calcul cuantic adaptiv, circuite cuantice cu adâncime constantă și jocuri Arthur-Merlin” (2002).

[13] Michael J Bremner, Richard Jozsa și Dan J Shepherd. „Simularea clasică a calculelor cuantice de navetă implică colapsul ierarhiei polinomiale”. 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 și Alex Arkhipov. „Complexitatea computațională a opticii liniare”. În Actele celui de-al patruzeci și treilea simpozion anual ACM despre teoria calculului. Paginile 333–342. (2011).
https: / / doi.org/ 10.1145 / 1993636.1993682

[15] Daniel Gottesman. „Reprezentarea Heisenberg a calculatoarelor cuantice” (1998).

[16] Serghei Bravyi și David Gosset. „Simularea clasică îmbunătățită a circuitelor cuantice dominate de porțile Clifford”. Scrisorile de revizuire fizică 116, 250501 (2016).
https: / / doi.org/ 10.1103 / physrevlett.116.250501

[17] Scott Aaronson și Daniel Gottesman. „Simularea îmbunătățită a circuitelor stabilizatoare”. Physical Review A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[18] Sergey Bravyi, David Gosset și Robert König. „Avantaj cuantic cu circuite superficiale”. Science 362, 308–311 (2018).
https://​/​doi.org/​10.1126/​science.aar3106

[19] Adam Bene Watts, Robin Kothari, Luke Schaeffer și Avishay Tal. „Separarea exponențială între circuitele cuantice superficiale și circuitele clasice superficiale nelimitate de ventilator”. În Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing. Paginile 515–526. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316404

[20] Daniel Grier și Luke Schaeffer. „Circuite interactive Clifford superficiale: avantaj cuantic față de $mathsf{NC}^1$ și nu numai”. În Proceedings of the 52th Annual ACM SIGACT Symposium on Theory of Computing. Paginile 875–888. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384332

[21] Sergey Bravyi, David Gosset, Robert Koenig și Marco Tomamichel. „Avantaj cuantic cu circuite superficiale zgomotoase”. Fizica naturiiPagini 1–6 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

[22] Robert Raussendorf și Hans J Briegel. „Un computer cuantic unidirecțional”. Physical Review Letters 86, 5188 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[23] Josh Alman și Virginia Vassilevska Williams. „O metodă laser rafinată și o multiplicare mai rapidă a matricei” (2020).

[24] Chaowen Guan și Kenneth W Regan. „Circuite stabilizatoare, forme pătratice și rangul matricei de calcul” (2019).

[25] Daniel Grier și Luke Schaeffer. „gridCHP++, licență Apache versiunea 2.0”. https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0.
https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0

[26] Alan George. „Disecția imbricată a unei rețele obișnuite cu elemente finite”. SIAM Journal on Numerical Analysis 10, 345–363 (1973).
https: / / doi.org/ 10.1137 / 0710032

[27] Richard J Lipton, Donald J Rose și Robert Endre Tarjan. „Disecție imbricată generalizată”. Jurnal SIAM de analiză numerică 16, 346–358 (1979).
https: / / doi.org/ 10.1137 / 0716027

[28] Noga Alon și Raphael Yuster. „Rezolvarea sistemelor liniare prin disecție imbricată”. În 2010, cel de-al 51-lea simpozion anual IEEE privind fundamentele informaticii. Paginile 225–234. IEEE (2010).
https: / / doi.org/ 10.1109 / FOCS.2010.28

[29] Richard J. Lipton și Robert Endre Tarjan. „O teoremă de separare pentru graficele plane”. SIAM Journal on Applied Mathematics 36, 177–189 (1979).
https: / / doi.org/ 10.1137 / 0136016

[30] Scott Aaronson și Lijie Chen. „Basele teoretice ale complexității experimentelor de supremație cuantică”. În a 32-a Conferință de complexitate computațională (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).

[31] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman și Yaoyun Shi. „Simularea clasică a circuitelor cuantice de dimensiuni intermediare” (2018).

[32] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho și Salvatore Mandrà. „Stabilirea frontierei supremației cuantice cu o simulare de 281 pflop/s”. Quantum Science and Technology 5, 034003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7eeb

[33] Stefan Arnborg, Derek G Corneil și Andrzej Proskurowski. „Complexitatea găsirii înglobărilor într-un arbore $k$”. SIAM Journal on Algebraic Discrete Methods 8, 277–284 (1987).
https: / / doi.org/ 10.1137 / 0608024

[34] HL Bodlaender. „Un ghid turistic prin lățimea copacilor”. Acta Cybernetica 11, 1–21 (1993).

[35] Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov și Michał Pilipczuk. „Un algoritm de aproximare $c^kn$ cu 5 pentru lățimea arborelui”. SIAM Journal on Computing 45, 317–378 (2016).
https: / / doi.org/ 10.1137 / 130947374

[36] Sergey Bravyi, Graeme Smith și John A Smolin. „Comercializarea resurselor de calcul clasice și cuantice”. Physical Review X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[37] M Van den Nest. „Simularea clasică a calculului cuantic, teorema Gottesman-Knill și puțin dincolo” (2008).

[38] Alex Kerzner. „Simularea Clifford: tehnici și aplicații”. Teza de masterat. Universitatea din Waterloo. (2021).

[39] Carsten Damm. „Probleme finalizate pentru $oplus{L}$”. În Jürgen Dassow și Jozef Kelemen, editori, Aspecte și perspective ale informaticii teoretice. Paginile 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/​Fișier:Tree_decomposition.svg, accesat 08/​31/​2020.

[41] Hans L Bodlaender și Ton Kloks. „Algoritmi mai buni pentru lățimea căii și lățimea arborelui graficelor”. În Automate, Languages ​​and Programming: 18th International Coloquium Madrid, Spania, iulie 8–12, 1991 Proceedings 18. Paginile 544–555. Springer (1991).
https:/​/​doi.org/​10.1007/​3-540-54233-7_162

[42] Oscar H Ibarra, Shlomo Moran și Roger Hui. „O generalizare a algoritmului de descompunere rapidă a matricei LUP și a aplicațiilor”. Journal of Algorithms 3, 45–56 (1982).
https:/​/​doi.org/​10.1016/​0196-6774(82)90007-4

[43] Adi Ben-Israel și Thomas NE Greville. „Inversul generalizat: teorie și aplicații”. Volumul 15. Springer Science & Business Media. (2003).
https: / / doi.org/ 10.1007 / b97366

[44] Michael T Goodrich. „Separatoare plane și triangularea poligoanelor paralele”. Journal of Computer and System Sciences 51, 374–389 (1995).
https: / / doi.org/ 10.1006 / jcss.1995.1076

[45] Jeroen Dehaene și Bart De Moor. „Grupul Clifford, stări stabilizatoare și operații liniare și pătratice pe $mathrm{GF}$(2)”. Physical Review A 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

[46] Simon Anders și Hans J Briegel. „Simularea rapidă a circuitelor stabilizatoare folosind o reprezentare grafică a stării”. Physical Review A 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

[47] Serghei Bravyi. Comunicare personală, 2017 (2017).

[48] Maarten Van den Nest, Jeroen Dehaene și Bart De Moor. „Descrierea grafică a acțiunii transformărilor locale Clifford asupra stărilor grafice”. Physical Review A 69, 022316 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.69.022316

Citat de

[1] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer și Jay M. Gambetta, „Assessing the Benefits and Risks of Quantum Computers”, arXiv: 2401.16317, (2024).

[2] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd și Alioscia Hamma, „Learning efficient decoders for quasi-haotic quantum scramblers”, arXiv: 2212.11338, (2022).

[3] Ryan L. Mann, „Simularea calculelor cuantice cu polinoame Tutte”, Informații cuantice npj 7, 141 (2021).

[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao și Shashank Virmani, „Efficient classical simulation of cluster state quantum circuits with alternative inputs”, arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun și Xiangdong Zhang, „Schema clasică paralelă de înaltă performanță pentru simularea circuitelor cuantice superficiale”, arXiv: 2103.00693, (2021).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2024-02-13 03:31:05). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2024-02-13 03:31:02).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic