Simulazione rapida di circuiti planari di Clifford

Simulazione rapida di circuiti planari di Clifford

Timestamp: 12 febbraio 2024 10:28

Davide Gosset1,2,3, Daniel Grier1,4,5, Alex Kerzner1,2e Luke Schaeffer1,2,6

1Institute for Quantum Computing, Università di Waterloo, Canada
2Dipartimento di Combinatoria e Ottimizzazione, Università di Waterloo, Canada
3Perimeter Institute for Theoretical Physics, Waterloo, Canada
4Cheriton School of Computer Science, Università di Waterloo, Canada
5Dipartimento di Informatica e Ingegneria e Dipartimento di Matematica, Università della California, San Diego, USA
6Centro congiunto per l'informazione quantistica e l'informatica, College Park, Maryland, Stati Uniti

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Un circuito quantistico generale può essere simulato classicamente in tempo esponenziale. Se ha un layout planare, allora un algoritmo di contrazione della rete tensoreale dovuto a Markov e Shi ha un runtime esponenziale nella radice quadrata della sua dimensione, o più in generale esponenziale nella larghezza dell'albero del grafico sottostante. Separatamente, Gottesman e Knill hanno dimostrato che se tutte le porte sono limitate a Clifford, allora esiste una simulazione temporale polinomiale. Combiniamo queste due idee e mostriamo che la larghezza dell'albero e la planarità possono essere sfruttate per migliorare la simulazione del circuito di Clifford. Il nostro risultato principale è un algoritmo classico con scalabilità asintotica in fase di esecuzione come $ n^{omega/2}$ $lt$ $n^{1.19}$ che campiona la distribuzione di output ottenuta misurando tutti i qubit $n$ di uno stato del grafico planare in date basi di Pauli. Qui $omega$ è l'esponente della moltiplicazione di matrici. Forniamo anche un algoritmo classico con lo stesso tempo di esecuzione asintotico che campiona la distribuzione di output di qualsiasi circuito di Clifford a profondità costante in una geometria planare. Il nostro lavoro migliora gli algoritmi classici conosciuti con runtime cubico.

Un ingrediente chiave è una mappatura che, data una scomposizione ad albero di un grafo $G$, produce un circuito di Clifford con una struttura che rispecchia la decomposizione dell'albero e che emula la misurazione dello stato del grafico corrispondente. Forniamo una simulazione classica di questo circuito con il tempo di esecuzione indicato sopra per grafi planari e altrimenti $nt^{omega-1}$ dove $t$ è la larghezza della scomposizione dell'albero. Il nostro algoritmo incorpora due subroutine che possono avere interesse indipendente. La prima è una versione in tempo di moltiplicazione di matrice della simulazione Gottesman-Knill della misurazione multi-qubit sugli stati dello stabilizzatore. Il secondo è un nuovo algoritmo classico per risolvere sistemi lineari simmetrici su $mathbb{F}_2$ in una geometria planare, estendendo lavori precedenti che si applicavano solo a sistemi lineari non singolari in un contesto analogo.

Simulazione rapida di circuiti planari di Clifford PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Immagine in primo piano: In senso orario da sinistra: un grafico, una bella scomposizione dell'albero e un circuito che prepara lo stato del grafico corrispondente.

[Contenuto incorporato]

► dati BibTeX

► Riferimenti

, 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. "Supremazia quantistica utilizzando un processore superconduttore programmabile". Natura 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

, “Documentazione quantistica IBM”. https://​/​docs.quantum.ibm.com/​run.
https://​/​docs.quantum.ibm.com/​run

, Matthew D Reed, Leonardo DiCarlo, Simon E Nigg, Luyan Sun, Luigi Frunzio, Steven M Girvin e Robert J Schoelkopf. “Realizzazione di correzione di errori quantistici a tre qubit con circuiti superconduttori”. Natura 482, 382–385 (2012).
https: / / doi.org/ 10.1038 / nature10786

, Antonio D Córcoles, Easwar Magesan, Srikanth J Srinivasan, Andrew W Cross, Matthias Steffen, Jay M Gambetta e Jerry M Chow. "Dimostrazione di un codice di rilevamento degli errori quantistici utilizzando un reticolo quadrato di quattro qubit superconduttori". Comunicazioni sulla natura 6, 1–10 (2015).
https: / / doi.org/ 10.1038 / ncomms7979

, Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang, et al. “Estendere la vita di un bit quantistico con la correzione degli errori nei circuiti superconduttori”. Natura 536, 441–445 (2016).
https: / / doi.org/ 10.1038 / nature18949

, Igor L Markov e Yaoyun Shi. "Simulazione del calcolo quantistico contraendo reti tensoriali". SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756 mila

, Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy e Hartmut Neven. “Simulazione di circuiti quantistici a bassa profondità come modelli grafici complessi non orientati” (2017).

, Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset e Mark Howard. "Simulazione di circuiti quantistici mediante decomposizioni di stabilizzatori di basso rango". Quantico 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

, Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W Draeger, Eric T Holland e Robert Wisnieff. “Rompere la barriera dei 49 qubit nella simulazione di circuiti quantistici” (2017).

, Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh e Robert Wisnieff. "Sfruttare l'archiviazione secondaria per simulare circuiti Sycamore profondi da 54 qubit" (2019).

, Boaz Barak, Chi-Ning Chou e Xun Gao. "Spoofing del benchmarking dell'entropia incrociata lineare in circuiti quantistici superficiali" (2020).

, Barbara M Terhal e David P DiVincenzo. “Calcolo quantistico adattivo, circuiti quantistici a profondità costante e giochi di Arthur-Merlin” (2002).

, Michael J Bremner, Richard Jozsa e Dan J Shepherd. "La simulazione classica dei calcoli quantistici di pendolarismo implica il collasso della gerarchia polinomiale". Atti della Royal Society A: Scienze matematiche, fisiche e ingegneristiche 467, 459–472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

, Scott Aaronson e Alex Arkhipov. “La complessità computazionale dell’ottica lineare”. In Atti del quarantatreesimo simposio annuale ACM sulla teoria dell'informatica. Pagine 333–342. (2011).
https: / / doi.org/ 10.1145 / 1993636.1993682 mila

, Daniele Gottesmann. “La rappresentazione di Heisenberg dei computer quantistici” (1998).

, Sergey Bravyi e David Gosset. "Simulazione classica migliorata di circuiti quantistici dominati da porte di Clifford". Lettere di revisione fisica 116, 250501 (2016).
https: / / doi.org/ 10.1103 / physrevlett.116.250501

, Scott Aaronson e Daniel Gottesman. "Simulazione migliorata dei circuiti stabilizzatori". Revisione fisica A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

, Sergey Bravyi, David Gosset e Robert König. "Vantaggio quantistico con circuiti superficiali". Scienza 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

, Adam Bene Watts, Robin Kothari, Luke Schaeffer e Avishay Tal. "Separazione esponenziale tra circuiti quantistici superficiali e circuiti classici superficiali a ventaglio illimitato". Negli atti del 51° simposio annuale ACM SIGACT sulla teoria dell'informatica. Pagine 515–526. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316404 mila

, Daniel Grier e Luke Schaeffer. "Circuiti interattivi di Clifford poco profondi: vantaggio quantistico contro $mathsf{NC}^1$ e oltre". Negli atti del 52esimo simposio annuale ACM SIGACT sulla teoria dell'informatica. Pagine 875–888. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384332 mila

, Sergey Bravyi, David Gosset, Robert Koenig e Marco Tomamichel. "Vantaggio quantistico con circuiti poco profondi e rumorosi". Fisica della naturaPagine 1–6 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

, Robert Raussendorf e Hans J. Briegel. “Un computer quantistico unidirezionale”. Lettere di revisione fisica 86, 5188 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

, Josh Alman e Virginia Vassilevska Williams. “Un metodo laser raffinato e una moltiplicazione della matrice più rapida” (2020).

, Chaowen Guan e Kenneth W. Regan. “Circuiti stabilizzatori, forme quadratiche e rango di matrice di calcolo” (2019).

, Daniel Grier e Luke Schaeffer. “gridCHP++, licenza Apache versione 2.0”. https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0.
https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0

, Alan Giorgio. “Dissezione annidata di una mesh regolare di elementi finiti”. SIAM Journal sull'analisi numerica 10, 345–363 (1973).
https: / / doi.org/ 10.1137 / 0710032 mila

, Richard J Lipton, Donald J Rose e Robert Endre Tarjan. “Dissezione nidificata generalizzata”. Rivista SIAM sull'analisi numerica 16, 346–358 (1979).
https: / / doi.org/ 10.1137 / 0716027 mila

, Noga Alon e Raffaello Yuster. “Risoluzione di sistemi lineari mediante dissezione annidata”. Nel 2010 IEEE 51° Simposio annuale sui fondamenti dell'informatica. Pagine 225–234. IEEE (2010).
https: / / doi.org/ 10.1109 / FOCS.2010.28

, Richard J. Lipton e Robert Endre Tarjan. "Un teorema separatore per grafi planari". SIAM Journal on Applied Mathematics 36, 177–189 (1979).
https: / / doi.org/ 10.1137 / 0136016 mila

, Scott Aaronson e Lijie Chen. "Fondamenti teorici della complessità degli esperimenti di supremazia quantistica". Nella 32a conferenza sulla complessità computazionale (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2017).

, Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman e Yaoyun Shi. “Simulazione classica di circuiti quantistici di dimensioni intermedie” (2018).

, Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho e Salvatore Mandrà. “Stabilire la frontiera della supremazia quantistica con una simulazione di 281 pflop/s”. Scienza e tecnologia quantistica 5, 034003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7eeb

, Stefan Arnborg, Derek G Corneil e Andrzej Proskurowski. "Complessità nel trovare immersioni in un albero $k$". SIAM Journal on Algebraic Discrete Methods 8, 277–284 (1987).
https: / / doi.org/ 10.1137 / 0608024 mila

, HL Bodlaender. “Una guida turistica attraverso gli alberi”. Acta Cybernetica 11, 1–21 (1993).

, Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov e Michał Pilipczuk. "Un algoritmo $c^kn$ con approssimazione 5 per la larghezza dell'albero". SIAM Journal on Computing 45, 317–378 (2016).
https: / / doi.org/ 10.1137 / 130947374 mila

, Sergey Bravyi, Graeme Smith e John A Smolin. “Scambio di risorse computazionali classiche e quantistiche”. Revisione fisica X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

, M.Van den Nest. “Simulazione classica del calcolo quantistico, il teorema di Gottesman-Knill e poco oltre” (2008).

, Alex Kerzner. “Simulazione Clifford: tecniche e applicazioni”. Tesi di master. Università di Waterloo. (2021).

, Carsten Damm. "Problemi completati per $oplus{L}$". In Jürgen Dassow e Jozef Kelemen, curatori, Aspects and Prospects of Theoretical Computer Science. Pagine 130–137. Berlino, Heidelberg (1990). Springer Berlino Heidelberg.
https:/​/​doi.org/​10.1016/​0020-0190(90)90150-V

, David Eppstein (2007). commons.wikimedia.org/​wiki/​File:Tree_decomposition.svg, accesso ​08/​31/​2020.

, Hans L Bodlaender e Ton Kloks. "Migliori algoritmi per la larghezza del percorso e la larghezza dell'albero dei grafici". In Automata, Languages ​​and Programming: 18th International Colloquium Madrid, Spagna, 8–12 luglio 1991 Atti 18. Pagine 544–555. Springer (1991).
https:/​/​doi.org/​10.1007/​3-540-54233-7_162

, Oscar H Ibarra, Shlomo Moran e Roger Hui. "Una generalizzazione dell'algoritmo e delle applicazioni di decomposizione rapida della matrice LUP". Giornale degli algoritmi 3, 45–56 (1982).
https:/​/​doi.org/​10.1016/​0196-6774(82)90007-4

, Adi Ben-Israel e Thomas NE Greville. “Inversi generalizzati: teoria e applicazioni”. Volume 15. Springer Scienza e media aziendali. (2003).
https: / / doi.org/ 10.1007 / b97366

, Michael T. Goodrich. “Separatori planari e triangolazione di poligoni paralleli”. Journal of Computer and System Sciences 51, 374–389 (1995).
https: / / doi.org/ 10.1006 / jcss.1995.1076

, Jeroen Dehaene e Bart De Moor. "Gruppo di Clifford, stati stabilizzatori e operazioni lineari e quadratiche su $mathrm{GF}$(2)". Revisione fisica A 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

, Simon Anders e Hans J. Briegel. "Simulazione rapida di circuiti stabilizzatori utilizzando una rappresentazione dello stato grafico". Revisione fisica A 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

, Sergej Bravyi. Comunicazione personale, 2017 (2017).

, Maarten Van den Nest, Jeroen Dehaene e Bart De Moor. "Descrizione grafica dell'azione delle trasformazioni locali di Clifford sugli stati dei grafici". Revisione fisica A 69, 022316 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.69.022316

Citato da

[1] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer e Jay M. Gambetta, "Valutare i vantaggi e i rischi dei computer quantistici", arXiv: 2401.16317, (2024).

[2] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd e Alioscia Hamma, "Apprendimento di decodificatori efficienti per scrambler quantistici quasi caotici", arXiv: 2212.11338, (2022).

[3] Ryan L. Mann, "Simulazione di calcoli quantistici con polinomi di Tutte", npj Informazioni quantistiche 7, 141 (2021).

[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao e Shashank Virmani, "Simulazione classica efficiente di circuiti quantistici a stati cluster con input alternativi", arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun e Xiangdong Zhang, "Schema classico parallelo ad alte prestazioni per simulare circuiti quantistici superficiali", arXiv: 2103.00693, (2021).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2024-02-13 03:31:05). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2024-02-13 03:31:02).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.

Timestamp:

Di più da Diario quantistico