Simulation rapide de circuits planaires de Clifford

Simulation rapide de circuits planaires de Clifford

Horodatage: 12 février 2024 10:28

David Goset1,2,3, Daniel Grier1,4,5, Alex Kerzner1,2, et Luke Schaeffer1,2,6

1Institut d'informatique quantique, Université de Waterloo, Canada
2Département de combinatoire et d'optimisation, Université de Waterloo, Canada
3Institut Périmètre de physique théorique, Waterloo, Canada
4École d'informatique Cheriton, Université de Waterloo, Canada
5Département d'informatique et d'ingénierie et Département de mathématiques, Université de Californie, San Diego, États-Unis
6Centre commun pour l'information quantique et l'informatique, College Park, Maryland, États-Unis

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Un circuit quantique général peut être simulé classiquement en temps exponentiel. S'il a une disposition planaire, alors un algorithme de contraction de réseau tenseur dû à Markov et Shi a une exponentielle d'exécution dans la racine carrée de sa taille, ou plus généralement exponentielle dans la largeur de l'arbre du graphe sous-jacent. Par ailleurs, Gottesman et Knill ont montré que si toutes les portes sont limitées à Clifford, alors il existe une simulation temporelle polynomiale. Nous combinons ces deux idées et montrons que la largeur des arbres et la planarité peuvent être exploitées pour améliorer la simulation des circuits de Clifford. Notre résultat principal est un algorithme classique avec une mise à l'échelle asymptotique du temps d'exécution comme $ n^{omega/2}$ $lt$ $n^{1.19}$ qui échantillonne à partir de la distribution de sortie obtenue en mesurant tous les $n$ qubits d'un état de graphe planaire. dans des bases Pauli données. Ici $omega$ est l'exposant de multiplication matricielle. Nous fournissons également un algorithme classique avec le même temps d'exécution asymptotique qui échantillonne la distribution de sortie de tout circuit Clifford à profondeur constante dans une géométrie planaire. Notre travail améliore les algorithmes classiques connus avec un temps d'exécution cubique.

Un ingrédient clé est une cartographie qui, étant donné une décomposition arborescente d'un graphe $G$, produit un circuit de Clifford avec une structure qui reflète la décomposition arborescente et qui émule la mesure de l'état du graphe correspondant. Nous fournissons une simulation classique de ce circuit avec le temps d'exécution indiqué ci-dessus pour les graphes planaires et sinon $nt^{omega-1}$ où $t$ est la largeur de la décomposition arborescente. Notre algorithme intègre deux sous-programmes qui peuvent avoir un intérêt indépendant. La première est une version en temps de multiplication matricielle de la simulation Gottesman-Knill de mesure multi-qubits sur les états stabilisateurs. Le second est un nouvel algorithme classique pour résoudre des systèmes linéaires symétriques sur $mathbb{F}_2$ dans une géométrie planaire, étendant les travaux antérieurs qui ne s'appliquaient qu'aux systèmes linéaires non singuliers dans un cadre analogue.

Simulation rapide des circuits planaires de Clifford PlatoBlockchain Data Intelligence. Recherche verticale. Aï.

Image présentée : Dans le sens des aiguilles d'une montre à partir de la gauche : un graphique, une belle décomposition arborescente et un circuit préparant l'état du graphique correspondant.

[Contenu intégré]

► Données BibTeX

► Références

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. "La suprématie quantique à l'aide d'un processeur supraconducteur programmable". Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

« Documentation quantique 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 et Robert J Schoelkopf. "Réalisation d'une correction d'erreur quantique à trois qubits avec des circuits supraconducteurs". Nature 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 et Jerry M Chow. "Démonstration d'un code de détection d'erreurs quantiques utilisant un réseau carré de quatre qubits supraconducteurs". Communications sur la nature 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. « Prolonger la durée de vie d'un bit quantique avec correction d'erreurs dans les circuits supraconducteurs ». Nature 536, 441-445 (2016).
https: / / doi.org/ 10.1038 / nature18949

Igor L Markov et Yaoyun Shi. "Simuler le calcul quantique en contractant des réseaux de tenseurs". SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy et Hartmut Neven. « Simulation de circuits quantiques de faible profondeur en tant que modèles graphiques complexes non orientés » (2017).

Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset et Mark Howard. "Simulation de circuits quantiques par décompositions de stabilisateurs de bas rang". Quantique 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 et Robert Wisnieff. « Briser la barrière des 49 qubits dans la simulation des circuits quantiques » (2017).

Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh et Robert Wisnieff. « Exploiter le stockage secondaire pour simuler des circuits Sycamore profonds de 54 qubits » (2019).

Boaz Barak, Chi-Ning Chou et Xun Gao. « Analyse comparative de l'entropie croisée linéaire dans les circuits quantiques peu profonds » (2020).

Barbara M Terhal et David P DiVincenzo. « Calcul quantique adaptatif, circuits quantiques à profondeur constante et jeux Arthur-Merlin » (2002).

Michael J Bremner, Richard Jozsa et Dan J Shepherd. "La simulation classique des calculs quantiques de déplacement implique l'effondrement de la hiérarchie polynomiale". Actes de la Royal Society A : Sciences mathématiques, physiques et techniques 467, 459-472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

Scott Aaronson et Alex Arkhipov. "La complexité informatique de l'optique linéaire". Dans Actes du quarante-troisième symposium annuel de l'ACM sur la théorie de l'informatique. Pages 333 à 342. (2011).
https: / / doi.org/ 10.1145 / 1993636.1993682

Daniel Gottesmann. « La représentation Heisenberg des ordinateurs quantiques » (1998).

Sergueï Bravyi et David Gosset. "Simulation classique améliorée des circuits quantiques dominés par les portes de Clifford". Lettres d'examen physique 116, 250501 (2016).
https: / / doi.org/ 10.1103 / physrevlett.116.250501

Scott Aaronson et Daniel Gottesman. "Amélioration de la simulation des circuits stabilisateurs". Examen physique A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

Sergey Bravyi, David Gosset et Robert König. « Avantage quantique avec des circuits peu profonds ». Sciences 362, 308-311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

Adam Bene Watts, Robin Kothari, Luke Schaeffer et Avishay Tal. "Séparation exponentielle entre les circuits quantiques peu profonds et les circuits classiques peu profonds illimités en éventail". Dans les actes du 51e symposium annuel ACM SIGACT sur la théorie de l'informatique. Pages 515 à 526. (2019).
https: / / doi.org/ 10.1145 / 3313276.3316404

Daniel Grier et Luke Schaeffer. "Circuits Clifford interactifs peu profonds : avantage quantique par rapport à $mathsf{NC}^1$ et au-delà". Dans les actes du 52e symposium annuel ACM SIGACT sur la théorie de l'informatique. Pages 875 à 888. (2020).
https: / / doi.org/ 10.1145 / 3357713.3384332

Sergey Bravyi, David Gosset, Robert Koenig et Marco Tomamichel. « Avantage quantique avec des circuits peu profonds et bruyants ». Physique de la naturePages 1 à 6 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

Robert Raussendorf et Hans J Briegel. "Un ordinateur quantique à sens unique". Lettres d'examen physique 86, 5188 (2001).
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

Josh Alman et Virginia Vassilevska Williams. « Une méthode laser raffinée et une multiplication matricielle plus rapide » (2020).

Chaowen Guan et Kenneth W Regan. « Circuits stabilisateurs, formes quadratiques et rang de matrice de calcul » (2019).

Daniel Grier et Luke Schaeffer. « gridCHP++, licence Apache version 2.0 ». https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0.
https://​/​github.com/​danielgrier/​gridCHPpp/​tree/​v1.0.0

Alan Georges. « Dissection imbriquée d'un maillage d'éléments finis régulier ». Journal SIAM sur l'analyse numérique 10, 345-363 (1973).
https: / / doi.org/ 10.1137 / 0710032

Richard J Lipton, Donald J Rose et Robert Endre Tarjan. « Dissection emboîtée généralisée ». Revue SIAM sur l'analyse numérique 16, 346-358 (1979).
https: / / doi.org/ 10.1137 / 0716027

Noga Alon et Raphaël Yuster. "Résoudre des systèmes linéaires par dissection imbriquée". En 2010, 51e symposium annuel de l'IEEE sur les fondements de l'informatique. Pages 225 à 234. IEEE (2010).
https: / / doi.org/ 10.1109 / FOCS.2010.28

Richard J. Lipton et Robert Endre Tarjan. "Un théorème du séparateur pour les graphes planaires". Journal SIAM sur les mathématiques appliquées 36, 177-189 (1979).
https: / / doi.org/ 10.1137 / 0136016

Scott Aaronson et Lijie Chen. « Fondements théoriques de la complexité des expériences de suprématie quantique ». Lors de la 32e Conférence sur la complexité informatique (CCC 2017). Château Dagstuhl-Leibniz-Zentrum für Informatik (2017).

Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman et Yaoyun Shi. « Simulation classique de circuits quantiques de taille intermédiaire » (2018).

Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho et Salvatore Mandrà. "Établir la frontière de la suprématie quantique avec une simulation à 281 pflop/​s". Science et technologie quantiques 5, 034003 (2020).
https: / / doi.org/ 10.1088 / 2058-9565 / ab7eeb

Stefan Arnborg, Derek G Corneil et Andrzej Proskurowski. "Complexité de trouver des plongements dans un arbre $k$". SIAM Journal sur les méthodes algébriques discrètes 8, 277-284 (1987).
https: / / doi.org/ 10.1137 / 0608024

HL Bodlaender. « Un guide touristique à travers la largeur des arbres ». Acta Cybernétique 11, 1-21 (1993).

Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov et Michał Pilipczuk. "Un algorithme d'approximation $c^kn$ 5 pour la largeur de l'arbre". SIAM Journal sur l'informatique 45, 317-378 (2016).
https: / / doi.org/ 10.1137 / 130947374

Sergey Bravyi, Graeme Smith et John A Smolin. « Échange de ressources informatiques classiques et quantiques ». Examen physique X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

M Van den Nest. « Simulation classique du calcul quantique, le théorème de Gottesman-Knill et légèrement au-delà » (2008).

Alex Kerzner. « Simulation Clifford : Techniques et applications ». La thèse de master. Université de Waterloo. (2021).

Carsten Damm. "Problèmes terminés pour $oplus{L}$". Dans Jürgen Dassow et Jozef Kelemen, éditeurs, Aspects et perspectives de l'informatique théorique. Pages 130 à 137. Berlin, Heidelberg (1990). Springer Berlin-Heidelberg.
https:/​/​doi.org/​10.1016/​0020-0190(90)90150-V

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

Hans L Bodlaender et Ton Kloks. "De meilleurs algorithmes pour la largeur de chemin et la largeur d'arbre des graphiques". Dans Automates, langages et programmation : 18e Colloque international de Madrid, Espagne, 8-12 juillet 1991 Actes 18. Pages 544-555. Springer (1991).
https:/​/​doi.org/​10.1007/​3-540-54233-7_162

Oscar H. Ibarra, Shlomo Moran et Roger Hui. "Une généralisation de l'algorithme de décomposition matricielle rapide LUP et de ses applications". Journal des algorithmes 3, 45-56 (1982).
https:/​/​doi.org/​10.1016/​0196-6774(82)90007-4

Adi Ben-Israël et Thomas NE Greville. « Inverses généralisées : théorie et applications ». Volume 15. Springer Science & Business Médias. (2003).
https: / / doi.org/ 10.1007 / b97366

Michael T. Goodrich. "Séparateurs planaires et triangulation de polygones parallèles". Journal des sciences informatiques et des systèmes 51, 374-389 (1995).
https: / / doi.org/ 10.1006 / jcss.1995.1076

Jeroen Dehaene et Bart De Moor. "Groupe de Clifford, états stabilisateurs et opérations linéaires et quadratiques sur $mathrm{GF}$(2)". Examen physique A 68, 042318 (2003).
https: / / doi.org/ 10.1103 / PhysRevA.68.042318

Simon Anders et Hans J Briegel. "Simulation rapide de circuits stabilisateurs à l'aide d'une représentation graphique d'état". Examen physique A 73, 022334 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.73.022334

Sergueï Bravyi. Communication personnelle, 2017 (2017).

Maarten Van den Nest, Jeroen Dehaene et Bart De Moor. « Description graphique de l'action des transformations locales de Clifford sur les états des graphes ». Examen physique A 69, 022316 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.69.022316

Cité par

[1] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer et Jay M. Gambetta, « Évaluation des avantages et des risques des ordinateurs quantiques », arXiv: 2401.16317, (2024).

[2] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd et Alioscia Hamma, "Apprentissage de décodeurs efficaces pour les brouilleurs quantiques quasi-chaotiques", arXiv: 2212.11338, (2022).

[3] Ryan L. Mann, « Simulation de calculs quantiques avec les polynômes de Tutte », npj Informations quantiques 7, 141 (2021).

[4] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao et Shashank Virmani, « Simulation classique efficace des circuits quantiques à état de cluster avec entrées alternatives », arXiv: 2201.07655, (2022).

[5] Shihao Zhang, Jiacheng Bao, Yifan Sun, Lvzhou Li, Houjun Sun et Xiangdong Zhang, « Schéma classique parallèle haute performance pour simuler des circuits quantiques peu profonds », arXiv: 2103.00693, (2021).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2024-02-13 03:31:05). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2024-02-13 03:31:02).

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Horodatage:

Plus de Journal quantique