Découpe rapide de circuits quantiques avec des mesures aléatoires

Republié par Platon

Suiveurs: 0

Angus Lowe^1,2, Matija Medvidovic^1,3,4, Anthony Hayes¹, Lee J. O'Riordan¹, Thomas R. Bromley¹, Juan Miguel Arrazola¹, et Nathan Killoran¹

¹Xanadu, Toronto, ON, M5G 2C8, Canada
²Centre de physique théorique, Massachusetts Institute of Technology, Cambridge, MA, 02139, États-Unis
³Centre de physique quantique computationnelle, Flatiron Institute, New York, NY, 10010, États-Unis
⁴Département de physique, Columbia University, New York, 10027, États-Unis

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

Abstract

Nous proposons une nouvelle méthode pour étendre la taille d'un calcul quantique au-delà du nombre de qubits physiques disponibles sur un seul appareil. Ceci est accompli en insérant de manière aléatoire des canaux de mesure et de préparation pour exprimer l'état de sortie d'un grand circuit sous la forme d'un état séparable sur des dispositifs distincts. Notre méthode utilise des mesures aléatoires, ce qui donne une surcharge d'échantillon qui est $widetilde{O}(4^k / varepsilon ^2)$, où $varepsilon $ est la précision du calcul et $k$ le nombre de fils parallèles qui sont "couper" pour obtenir des sous-circuits plus petits. Nous montrons également une limite inférieure de la théorie de l'information de $Omega(2^k / varepsilon ^2)$ pour toute procédure comparable. Nous utilisons nos techniques pour montrer que les circuits de l'algorithme d'optimisation approximative quantique (QAOA) avec des couches d'enchevêtrement $p$ peuvent être simulés par des circuits sur une fraction du nombre original de qubits avec une surcharge d'environ $2^{O(pkappa) }$, où $kappa$ est la taille d'un séparateur de sommets équilibré connu du graphe qui encode le problème d'optimisation. Nous obtenons des preuves numériques des accélérations pratiques en utilisant notre méthode appliquée au QAOA, par rapport aux travaux antérieurs. Enfin, nous étudions la faisabilité pratique de l'application de la procédure de découpage de circuit à des problèmes QAOA à grande échelle sur des graphes groupés en utilisant un simulateur $30$-qubit pour évaluer l'énergie variationnelle d'un problème $129$-qubit ainsi que pour effectuer un $62$-qubit. -Optimisation des qubits.

► Données BibTeX

@article{Lowe2023fastquantumcircuit, doi = {10.22331/q-2023-03-02-934}, url = {https://doi.org/10.22331/q-2023-03-02-934}, titre = {Quantique rapide coupe de circuit avec mesures aléatoires}, auteur = {Lowe, Angus et Medvidovi{'{c}}, Matija et Hayes, Anthony et O'Riordan, Lee J. et Bromley, Thomas R. et Arrazola, Juan Miguel et Killoran, Nathan }, journal = {{Quantum}}, issn = {2521-327X}, éditeur = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {934}, mois = mars, année = {2023} }

► Références

https:///github.com/XanaduAI/randomized-measurements-circuit-cutting (2022).
https:///github.com/XanaduAI/randomized-measurements-circuit-cutting

Scott Aaronson et Daniel Gottesman "Simulation améliorée des circuits stabilisateurs" Phys. Rev. A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

J. Avron, Ofer Casper et Ilan Rozen, "Avantage quantique et réduction du bruit dans l'informatique quantique distribuée" Phys. Rév. A 104, 052404 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.104.052404

Thomas Ayral, François-Marie Le Régent, Zain Saleem, Yuri Alexeev et Martin Suchara, "Quantum Divide and Compute: Hardware Demonstrations and Noisy Simulations" 2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) 138–140 (2020).
https:///doi.org/10.1109/ISVLSI49217.2020.00034

F. Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann et AG Green, "Simulation quantique parallèle de grands systèmes sur de petits ordinateurs NISQ" npj Quantum Information 7, 79 (2021).
https://doi.org/10.1038/s41534-021-00420-3

Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, Amintor Dusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, Aroosa Ijaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain, Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert A. Lang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Johannes Jakob Meyer, JA Montañez-Barrera, Romain Moyard, Zeyue Niu, Lee James O'Riordan, Steven Oud, Ashish Panigrahi, Chae-Yeun Park, Daniel Polatajko, Nicolás Quesada, Chase Roberts, Nahum Sá, Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, Ingrid Strandberg, Jay Soni, Antal Száva, Slimane Thabet, Rodrigo A. Vargas-Hernández , Trevor Vincent, Nicola Vitucci, Maurice Weber, David Wierichs, Roeland Wier sema, Moritz Willmann, Vincent Wong, Shaoming Zhang et Nathan Killoran, « PennyLane : différenciation automatique des calculs quantiques-classiques hybrides » (2018).
https:///doi.org/10.48550/ARXIV.1811.04968
https: / / arxiv.org/ abs / 1811.04968

Sergey Bravyiant David Gosset "Simulation classique améliorée des circuits quantiques dominée par Clifford Gates" Phys. Rév. Lett. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

Sergey Bravyi, David Gosset et Ramis Movassagh, "Algorithmes classiques pour les valeurs moyennes quantiques" Nature Physics 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8

Sergey Bravyi, Graeme Smith et John A. Smolin, Phys. Rév. X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

Sergey Bravyi, Alexander Kliesch, Robert Koenig et Eugene Tang, "Obstacles to Variational Quantum Optimization from Symmetry Protection" Phys. Rév. Lett. 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset et Mark Howard, "Simulation de circuits quantiques par décompositions de stabilisateurs de rang inférieur" Quantum 3, 181 (2019).
https://doi.org/10.22331/q-2019-09-02-181

Thang Nguyen Buiand Curt Jones "Trouver de bonnes partitions approximatives de sommets et d'arêtes est NP-difficile" Information Processing Letters 42, 153–159 (1992).
https://doi.org/10.1016/0020-0190(92)90140-Q
https:///www.sciencedirect.com/science/article/pii/002001909290140Q

Francesco Buscemiand Nilanjana Datta "La capacité quantique des canaux avec un bruit arbitrairement corrélé" Transactions IEEE sur la théorie de l'information 56, 1447–1460 (2010).
https: / / doi.org/ 10.1109 / TIT.2009.2039166

Senrui Chen, Wenjun Yu, Pei Zeng et Steven T. Flammia, "Robust Shadow Estimation" PRX Quantum 2, 030348 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.030348

Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe et Shuchen Zhu, «Théorie de l'erreur de trotteur avec mise à l'échelle du commutateur» Examen physique X 11 (2021).
https: / / doi.org/ 10.1103 / physrevx.11.011020

Thomas M. Coverand Joy A. Thomas "Éléments de la théorie de l'information" Wiley (2005).
https:///doi.org/10.1002/047174882x

Vedran Dunjko, Yimin Ge et J. Ignacio Cirac, "Accélérations de calcul à l'aide de petits dispositifs quantiques" Phys. Rév. Lett. 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch et Peter Zoller, « La boîte à outils de mesure aléatoire » (2022).
https:///doi.org/10.48550/ARXIV.2203.11374
https: / / arxiv.org/ abs / 2203.11374

Leo Fang, Andreas Hehn, Harun Bayraktar et Sam Stanwyck, "NVIDIA/cuQuantum : cuQuantum v22.05.0" (2022).
https: / / doi.org/ 10.5281 / zenodo.6574510

Robert M. Fano "Transmission de l'information : une théorie statistique des communications" MIT Press (1966).

Edward Farhi, David Gamarnik et Sam Gutmann, "L'algorithme d'optimisation approximative quantique doit voir l'ensemble du graphique : un cas typique" (2020).
https:///doi.org/10.48550/ARXIV.2004.09002
https: / / arxiv.org/ abs / 2004.09002

Edward Farhi, David Gamarnik et Sam Gutmann, "L'algorithme d'optimisation approximative quantique doit voir l'ensemble du graphique : les pires exemples" (2020).
https:///doi.org/10.48550/ARXIV.2005.08747
https: / / arxiv.org/ abs / 2005.08747

Edward Farhi, Jeffrey Goldstone et Sam Gutmann, "Un algorithme d'optimisation approximative quantique" (2014).
https:///doi.org/10.48550/ARXIV.1411.4028
https: / / arxiv.org/ abs / 1411.4028

Edward Farhi, Jeffrey Goldstone et Sam Gutmann, "Un algorithme d'optimisation approximative quantique appliqué à un problème de contrainte d'occurrence bornée" (2014).
https:///doi.org/10.48550/ARXIV.1412.6062
https: / / arxiv.org/ abs / 1412.6062

Edward Farhiand Aram W Harrow "La suprématie quantique grâce à l'algorithme d'optimisation approximative quantique" (2016).
https:///doi.org/10.48550/ARXIV.1602.07674
https: / / arxiv.org/ abs / 1602.07674

Uriel Feige, MohammadTaghi Hajiaghayi et James R. Lee, "Algorithmes d'approximation améliorés pour les séparateurs de sommets de poids minimum" SIAM Journal on Computing 38, 629–657 (2008).
https: / / doi.org/ 10.1137 / 05064299X

Johnnie Gray et Stefanos Kourtis « Contraction du réseau de tenseurs hyper-optimisé » Quantum 5, 410 (2021).
https://doi.org/10.22331/q-2021-03-15-410

M Guţă, J Kahn, R Kueng et JA Tropp, "Tomographie à état rapide avec limites d'erreur optimales" Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu et Nengkun Yu, «Sample-Optimal Tomography of Quantum States» IEEE Transactions on Information Theory 63, 5628–5641 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2719044

Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli et Rupak Biswas, "De l'algorithme d'optimisation approximative quantique à un opérateur alternatif quantique Ansatz" Algorithmes 12 (2019).
https: / / doi.org/ 10.3390 / a12020034
https://www.mdpi.com/1999-4893/12/2/34

Michael Horodecki, Peter W. Shor et Mary Beth Ruskai, "Entanglement Breaking Channels" Reviews in Mathematical Physics 15, 629–641 (2003).
https: / / doi.org/ 10.1142 / S0129055X03001709

Hsin-Yuan Huang, Richard Kueng et John Preskill, "Prédire de nombreuses propriétés d'un système quantique à partir de très peu de mesures" Nature Physics 16, 1050–1057 (2020).
https://doi.org/10.1038/s41567-020-0932-7

William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley et E Miles Stoudenmire, "Vers l'apprentissage automatique quantique avec des réseaux de tenseurs" Quantum Science and Technology 4, 024001 (2019).
https: / / doi.org/ 10.1088 / 2058-9565 / aaea94

Richard Kueng et David Gross "Les états stabilisateurs de Qubit sont des 3-designs projectifs complexes" (2015).
https:///doi.org/10.48550/ARXIV.1510.02767
https: / / arxiv.org/ abs / 1510.02767

Junde Li, Mahabubul Alam et Swaroop Ghosh, "Optimisation approximative quantique à grande échelle via Divide-and-Conquer" (2021).
https:///doi.org/10.48550/ARXIV.2102.13288
https: / / arxiv.org/ abs / 2102.13288

Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac et Nathan Killoran, "Incorporations quantiques pour l'apprentissage automatique" (2020).
https:///doi.org/10.48550/ARXIV.2001.03622
https: / / arxiv.org/ abs / 2001.03622

Angus Lowe et Ashwin Nayak « Limites inférieures pour l'apprentissage des états quantiques avec des mesures à copie unique » (2022).
https:///doi.org/10.48550/ARXIV.2207.14438
https: / / arxiv.org/ abs / 2207.14438

Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel et Yuri Alexeev, "Seuils de fréquence d'échantillonnage pour l'avantage quantique de l'algorithme d'optimisation approximative quantique" (2022).
https:///doi.org/10.48550/ARXIV.2206.03579
https: / / arxiv.org/ abs / 2206.03579

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

Simon C. Marshall, Casper Gyurik et Vedran Dunjko, "Apprentissage automatique quantique de haute dimension avec de petits ordinateurs quantiques" (2022).
https:///doi.org/10.48550/ARXIV.2203.13739
https: / / arxiv.org/ abs / 2203.13739

Matija Medvidović et Giuseppe Carleo "Simulation variationnelle classique de l'algorithme d'optimisation approximative quantique" npj Quantum Information 7 (2021).
https: / / doi.org/ 10.1038 / s41534-021-00440-z

Kosuke Mitarai et Keisuke Fujii "Construire une porte virtuelle à deux qubits en échantillonnant des opérations à un seul qubit" New Journal of Physics 23, 023021 (2021).
https:///doi.org/10.1088/1367-2630/abd7bc

Kosuke Mitarai et Keisuke Fujii « Overhead pour simuler un canal non local avec des canaux locaux par échantillonnage quasi probabiliste » Quantum 5, 388 (2021).
https://doi.org/10.22331/q-2021-01-28-388

Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan et Ion Stoica, « Ray : un cadre distribué pour les applications d'IA émergentes » (2017) .
https:///doi.org/10.48550/ARXIV.1712.05889
https: / / arxiv.org/ abs / 1712.05889

Hakop Pashayan, Joel J. Wallman et Stephen D. Bartlett, "Estimation des probabilités de résultat des circuits quantiques à l'aide de quasi-probabilités" Phys. Rév. Lett. 115, 070501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.115.070501

Tianyi Peng, Aram W. Harrow, Maris Ozols et Xiaodi Wu, "Simulation de grands circuits quantiques sur un petit ordinateur quantique" Lettres d'examen physique 125 (2020).
https: / / doi.org/ 10.1103 / physrevlett.125.150504

Michael A. Perlin, Zain H. Saleem, Martin Suchara et James C. Osborn, « Coupure de circuit quantique avec tomographie à probabilité maximale » npj Quantum Information 7 (2021).
https://doi.org/10.1038/s41534-021-00390-6

Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik et Jeremy L. O'Brien, "Un solveur variationnel de valeurs propres sur un processeur quantique photonique" Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

Christophe Piveteau et David Sutter « Tricot de circuit avec communication classique » (2022).
https:///doi.org/10.48550/ARXIV.2205.00016
https: / / arxiv.org/ abs / 2205.00016

Zain H. Saleem, Teague Tomesh, Michael A. Perlin, Pranav Gokhale et Martin Suchara, «Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing» (2021).
arXiv: 2107.07532

Igal Sason et Sergio Verdú "$f$ - Inégalités de divergence" IEEE Transactions on Information Theory 62, 5973–6006 (2016).
https: / / doi.org/ 10.1109 / TIT.2016.2603151

Maria Schuld, Alex Bocharov, Krysta M. Svore et Nathan Wiebe, « Classificateurs quantiques centrés sur le circuit » Physical Review A 101 (2020).
https: / / doi.org/ 10.1103 / physreva.101.032308

Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac et Nathan Killoran, "Évaluer les gradients analytiques sur le matériel quantique" Phys. Rév. A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

Hayk Shoukourian, Torsten Wilde, Axel Auweter et Arndt Bode, "Prédire la consommation d'énergie et d'énergie des applications HPC à mise à l'échelle forte et faible" Supercomputing Frontiers and Innovations 1, 20–41 (2014).
https:///doi.org/10.14529/jsfi140202

Wei Tangand Margaret Martonosi "ScaleQC : un cadre évolutif pour le calcul hybride sur les processeurs quantiques et classiques" (2022).
https:///doi.org/10.48550/ARXIV.2207.00933
https: / / arxiv.org/ abs / 2207.00933

Ewout Van Den Berg « Une méthode simple pour échantillonner des opérateurs de Clifford aléatoires » 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 54–59 (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

Zhihui Wang, Stuart Hadfield, Zhang Jiang et Eleanor G. Rieffel, "Algorithme d'optimisation approximative quantique pour MaxCut : une vue fermionique" Phys. Rév. A 97, 022304 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022304

John Watrous "La théorie de l'information quantique" Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

Zak Webb « Le groupe Clifford forme un 3-design unitaire » (2015).
https:///doi.org/10.48550/ARXIV.1510.02769
https: / / arxiv.org/ abs / 1510.02769

Roeland Wiersema, Leonardo Guerini, Juan Felipe Carrasquilla et Leandro Aolita, « La connectivité des circuits est renforcée par les interfaces quantiques-classiques-quantiques » (2022).
https:///doi.org/10.48550/ARXIV.2203.04984
https: / / arxiv.org/ abs / 2203.04984

Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao et You Zhou, Phys. Rév. Lett. 127, 040501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.040501

Huangjun Zhu "Les groupes multiqubits de Clifford sont des 3-conceptions unitaires" Phys. Rév. A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Cité par

[1] Lirandë Pira et Chris Ferrie, "Une invitation aux réseaux de neurones quantiques distribués", arXiv: 2211.07056, (2022).

[2] Lukas Brenner, Christophe Piveteau, et David Sutter, "La coupe de fil optimale avec la communication classique", arXiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen et Michael Foss-Feig, "Compilation de réutilisation de Qubit avec mesure et réinitialisation en milieu de circuit", arXiv: 2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge et Christopher Mutschler, "Cutting multi-control quantum gates with ZX calculus", arXiv: 2302.00387, (2023).

[5] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger et Benjamin Weder, "Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices", arXiv: 2302.01792, (2023).

[6] Ritajit Majumdar et Christopher J. Wood, "Erreur atténuée quantum circuit cutting", arXiv: 2211.13431, (2022).

[7] Daniel T. Chen, Zain H. Saleem et Michael A. Perlin, "Quantum Divide and Conquer for Classical Shadows", arXiv: 2212.00761, (2022).

[8] Gideon Uchehara, Tor M. Aamodt et Olivia Di Matteo, "Optimisation de la coupe de circuit inspirée par la rotation", arXiv: 2211.07358, (2022).

[9] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer et Andre Luckow, « A performance characterization of quantum generative models », arXiv: 2301.09363, (2023).

[10] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch et Juan Miguel Arrazola, "Un aperçu pratique de la classification d'images avec des circuits quantiques à réseau tenseur variationnel", arXiv: 2209.11058, (2022).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2023-03-03 16:49:02). 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 2023-03-03 16:49:00).

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.

Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
Platoblockchain. Intelligence métaverse Web3. Connaissance Amplifiée. Accéder ici.
La source: https://quantum-journal.org/papers/q-2023-03-02-934/

Horodatage: 2 mars 2023