Hurtig simulering af plane Clifford-kredsløb

Hurtig simulering af plane Clifford-kredsløb

Tidsstempel: 12. februar 2024 kl. 10:28

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

1Institute for Quantum Computing, University of Waterloo, Canada
2Institut for kombinatorik og optimering, University of Waterloo, Canada
3Perimeter Institut for Teoretisk Fysik, Waterloo, Canada
4Cheriton School of Computer Science, University of Waterloo, Canada
5Department of Computer Science and Engineering og Department of Mathematics, University of California, San Diego, USA
6Joint Center for Quantum Information and Computer Science, College Park, Maryland, USA

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Et generelt kvantekredsløb kan simuleres klassisk i eksponentiel tid. Hvis den har et plant layout, så har en tensor-netværkskontraktionsalgoritme på grund af Markov og Shi en runtime-eksponentiel i kvadratroden af ​​dens størrelse, eller mere generelt eksponentiel i træbredden af ​​den underliggende graf. Separat viste Gottesman og Knill, at hvis alle porte er begrænset til at være Clifford, så er der en polynomisk tidssimulering. Vi kombinerer disse to ideer og viser, at træbredde og planaritet kan udnyttes til at forbedre Clifford kredsløbssimulering. Vores hovedresultat er en klassisk algoritme med runtime skalering asymptotisk som $ n^{omega/2}$ $lt$ $n^{1.19}$, som sampler fra outputfordelingen opnået ved at måle alle $n$ qubits i en plan graftilstand i givne Pauli-baser. Her er $omega$ matrixmultiplikationseksponenten. Vi leverer også en klassisk algoritme med den samme asymptotiske kørselstid, som sampler fra outputfordelingen af ​​ethvert Clifford-kredsløb med konstant dybde i en plan geometri. Vores arbejde forbedrer kendte klassiske algoritmer med cubic runtime.

En nøgleingrediens er en kortlægning, som givet en trænedbrydning af en graf $G$ producerer et Clifford-kredsløb med en struktur, der afspejler trænedbrydningen, og som emulerer måling af den tilsvarende graftilstand. Vi leverer en klassisk simulering af dette kredsløb med runtime angivet ovenfor for plane grafer og ellers $nt^{omega-1}$ hvor $t$ er bredden af ​​træets dekomponering. Vores algoritme inkorporerer to underrutiner, som kan være af uafhængig interesse. Den første er en matrix-multiplikations-tidsversion af Gottesman-Knill-simuleringen af ​​multi-qubit-måling på stabilisatortilstande. Den anden er en ny klassisk algoritme til at løse symmetriske lineære systemer over $mathbb{F}_2$ i en plan geometri, der udvider tidligere værker, som kun gjaldt for ikke-singulære lineære systemer i den analoge indstilling.

Fast simulation of planar Clifford circuits PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Udvalgt billede: Med uret fra venstre: En graf, en flot trænedbrydning og et kredsløb, der forbereder den tilsvarende graftilstand.

[Indlejret indhold]

► BibTeX-data

► Referencer

[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. "Kvanteoverlegenhed ved hjælp af en programmerbar superledende processor". Nature 574, 505-510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] "Ibm kvantedokumentation". 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 og Robert J Schoelkopf. "Realisering af tre-qubit kvantefejlkorrektion med superledende kredsløb". 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 og Jerry M Chow. "Demonstration af en kvantefejldetekteringskode ved hjælp af et kvadratisk gitter på fire superledende qubits". Naturformidling 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, et al. "Forlængelse af levetiden for en kvantebit med fejlkorrektion i superledende kredsløb". Nature 536, 441-445 (2016).
https://​/​doi.org/​10.1038/​nature18949

[6] Igor L Markov og Yaoyun Shi. "Simulering af kvanteberegning ved at kontrahere tensornetværk". SIAM Journal on Computing 38, 963–981 (2008).
https://​/​doi.org/​10.1137/​050644756

[7] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy og Hartmut Neven. "Simulering af kvantekredsløb med lav dybde som komplekse urettede grafiske modeller" (2017).

[8] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset og Mark Howard. "Simulering af kvantekredsløb ved stabilisatornedbrydninger med lav rang". 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 og Robert Wisnieff. "At bryde 49-qubit-barrieren i simuleringen af ​​kvantekredsløb" (2017).

[10] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh og Robert Wisnieff. "Udnyttelse af sekundær lagring til at simulere dybe 54-qubit Sycamore-kredsløb" (2019).

[11] Boaz Barak, Chi-Ning Chou og Xun Gao. "Spoofing lineær krydsentropi benchmarking i lavvandede kvantekredsløb" (2020).

[12] Barbara M Terhal og David P DiVincenzo. "Adaptiv kvanteberegning, kvantekredsløb med konstant dybde og Arthur-Merlin-spil" (2002).

[13] Michael J Bremner, Richard Jozsa og Dan J Shepherd. "Klassisk simulering af pendlende kvanteberegninger indebærer kollaps af polynomiehierarkiet". 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 og Alex Arkhipov. "Den beregningsmæssige kompleksitet af lineær optik". I Proceedings af det 333. årlige ACM-symposium om Theory of computing. Side 342–2011. (XNUMX).
https://​/​doi.org/​10.1145/​1993636.1993682

[15] Daniel Gottesman. "Heisenberg-repræsentationen af ​​kvantecomputere" (1998).

[16] Sergey Bravyi og David Gosset. "Forbedret klassisk simulering af kvantekredsløb domineret af Clifford gates". Physical review letters 116, 250501 (2016).
https://​/​doi.org/​10.1103/​physrevlett.116.250501

[17] Scott Aaronson og Daniel Gottesman. "Forbedret simulering af stabilisatorkredsløb". Physical Review A 70, 052328 (2004).
https://​/​doi.org/​10.1103/​PhysRevA.70.052328

[18] Sergey Bravyi, David Gosset og Robert König. "Kvantefordel med lavvandede kredsløb". Science 362, 308-311 (2018).
https://​doi.org/​10.1126/​science.aar3106

[19] Adam Bene Watts, Robin Kothari, Luke Schaeffer og Avisay Tal. "Eksponentiel adskillelse mellem lavvandede kvantekredsløb og ubegrænsede fan-in lavvandede klassiske kredsløb". I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Side 515–526. (2019).
https://​/​doi.org/​10.1145/​3313276.3316404

[20] Daniel Grier og Luke Schaeffer. "Interaktive lavvandede Clifford-kredsløb: kvantefordel mod $mathsf{NC}^1$ og mere". I Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Side 875–888. (2020).
https://​/​doi.org/​10.1145/​3357713.3384332

[21] Sergey Bravyi, David Gosset, Robert Koenig og Marco Tomamichel. "Kvantefordel med støjende lavvandede kredsløb". NaturfysikSide 1-6 (2020).
https://​/​doi.org/​10.1038/​s41567-020-0948-z

[22] Robert Raussendorf og Hans J Briegel. "En envejs kvantecomputer". Physical Review Letters 86, 5188 (2001).
https://​/​doi.org/​10.1103/​PhysRevLett.86.5188

[23] Josh Alman og Virginia Vassilevska Williams. "En raffineret lasermetode og hurtigere matrixmultiplikation" (2020).

[24] Chaowen Guan og Kenneth W Regan. "Stabilisatorkredsløb, kvadratiske former og computing matrix rang" (2019).

[25] Daniel Grier og Luke Schaeffer. "gridCHP++, Apache-licens version 2.0". https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0.
https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0

[26] Alan George. "Indlejret dissektion af et regulært finit element mesh". SIAM Journal on Numerical Analysis 10, 345-363 (1973).
https://​/​doi.org/​10.1137/​0710032

[27] Richard J Lipton, Donald J Rose og Robert Endre Tarjan. "Generaliseret indlejret dissektion". SIAM tidsskrift om numerisk analyse 16, 346–358 (1979).
https://​/​doi.org/​10.1137/​0716027

[28] Noga Alon og Raphael Yuster. "Løsning af lineære systemer gennem indlejret dissektion". I 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. Side 225-234. IEEE (2010).
https://​/​doi.org/​10.1109/​FOCS.2010.28

[29] Richard J. Lipton og Robert Endre Tarjan. "En separatorsætning for plane grafer". SIAM Journal on Applied Mathematics 36, 177–189 (1979).
https://​/​doi.org/​10.1137/​0136016

[30] Scott Aaronson og Lijie Chen. "Kompleksitetsteoretiske grundlag for kvanteoverherredømmeeksperimenter". I 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).

[31] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman og Yaoyun Shi. "Klassisk simulering af mellemstore kvantekredsløb" (2018).

[32] Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho og Salvatore Mandrà. "Etablering af kvanteoverherredømmets grænse med en 281 pflop/s simulering". Quantum Science and Technology 5, 034003 (2020).
https:/​/​doi.org/​10.1088/​2058-9565/​ab7eeb

[33] Stefan Arnborg, Derek G Corneil og Andrzej Proskurowski. "Kompleksiteten ved at finde indlejringer i et $k$-træ". SIAM Journal on Algebraic Discrete Methods 8, 277-284 (1987).
https://​/​doi.org/​10.1137/​0608024

[34] HL Bodlaender. "En turistguide gennem træbredden". Acta Cybernetica 11, 1-21 (1993).

[35] Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov og Michał Pilipczuk. "En $c^kn$ 5-tilnærmelsesalgoritme for træbredde". SIAM Journal on Computing 45, 317–378 (2016).
https://​/​doi.org/​10.1137/​130947374

[36] Sergey Bravyi, Graeme Smith og John A Smolin. "Handel med klassiske og kvanteberegningsressourcer". Fysisk gennemgang X 6, 021043 (2016).
https://​/​doi.org/​10.1103/​PhysRevX.6.021043

[37] M Van den Nest. "Klassisk simulering af kvanteberegning, Gottesman-Knill-sætningen og lidt videre" (2008).

[38] Alex Kerzner. "Clifford-simulering: Teknikker og applikationer". Kandidatafhandling. University of Waterloo. (2021).

[39] Carsten Damm. "Problemer fuldført for $oplus{L}$". I Jürgen Dassow og Jozef Kelemen, redaktører, Aspects and Prospects of Theoretical Computer Science. Side 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/​File:Tree_decomposition.svg, tilgået 08/​31/​2020.

[41] Hans L Bodlaender og Ton Kloks. "Bedre algoritmer til stibredden og træbredden af ​​grafer". In Automata, Languages ​​and Programming: 18th International Colloquium Madrid, Spanien, 8.-12. juli, 1991 Proceedings 18. Side 544-555. Springer (1991).
https:/​/​doi.org/​10.1007/​3-540-54233-7_162

[42] Oscar H Ibarra, Shlomo Moran og Roger Hui. "En generalisering af den hurtige LUP-matrixnedbrydningsalgoritme og applikationer". Journal of Algorithms 3, 45-56 (1982).
https:/​/​doi.org/​10.1016/​0196-6774(82)90007-4

[43] Adi Ben-Israel og Thomas NE Greville. "Generaliserede inverse: teori og anvendelser". Bind 15. Springer Science & Business Media. (2003).
https://doi.org/​10.1007/​b97366

[44] Michael T Goodrich. "Planseparatorer og parallel polygontriangulering". Journal of Computer and System Sciences 51, 374–389 (1995).
https://​/​doi.org/​10.1006/​jcss.1995.1076

[45] Jeroen Dehaene og Bart De Moor. "Clifford-gruppe, stabilisatortilstande og lineære og kvadratiske operationer over $mathrm{GF}$(2)". Physical Review A 68, 042318 (2003).
https://​/​doi.org/​10.1103/​PhysRevA.68.042318

[46] Simon Anders og Hans J Briegel. "Hurtig simulering af stabilisatorkredsløb ved hjælp af en graftilstandsrepræsentation". Physical Review A 73, 022334 (2006).
https://​/​doi.org/​10.1103/​PhysRevA.73.022334

[47] Sergey Bravyi. Personlig kommunikation, 2017 (2017).

[48] Maarten Van den Nest, Jeroen Dehaene og Bart De Moor. "Grafisk beskrivelse af virkningen af ​​lokale Clifford-transformationer på graftilstande". Physical Review A 69, 022316 (2004).
https://​/​doi.org/​10.1103/​PhysRevA.69.022316

Citeret af

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

[2] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd og Alioscia Hamma, "Læring af effektive dekodere til kvasi-kaotiske kvanteforvrængere", arXiv: 2212.11338, (2022).

[3] Ryan L. Mann, "Simulering af kvanteberegninger med Tutte-polynomier", npj Quantum Information 7, 141 (2021).

[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao og Shashank Virmani, "Effektiv klassisk simulering af klyngetilstands kvantekredsløb med alternative input", arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun og Xiangdong Zhang, "Højtydende parallel klassisk skema til simulering af lavvandede kvantekredsløb", arXiv: 2103.00693, (2021).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-02-13 03:31:05). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2024-02-13 03:31:02).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

Tidsstempel:

Mere fra Quantum Journal