Snel snijden in kwantumcircuits met gerandomiseerde metingen

Snel snijden in kwantumcircuits met gerandomiseerde metingen

Bronknooppunt: 1990460

Angus Lowe1,2, Matija Medvidovic1,3,4, Antonius Hayes1, Lee J. O'Riordan1, Thomas R.Bromley1, Juan Miguel Arrazola1, en Nathan Killoran1

1Xanadu, Toronto, ON, M5G 2C8, Canada
2Centrum voor Theoretische Fysica, Massachusetts Institute of Technology, Cambridge, MA, 02139, VS
3Centrum voor Computational Quantum Physics, Flatiron Institute, New York, NY, 10010, VS.
4Afdeling Natuurkunde, Columbia University, New York, 10027, VS

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

We stellen een nieuwe methode voor om de omvang van een kwantumberekening uit te breiden tot buiten het aantal fysieke qubits dat beschikbaar is op een enkel apparaat. Dit wordt bereikt door willekeurig meet-en-voorbereidingskanalen in te voegen om de uitvoerstatus van een groot circuit uit te drukken als een scheidbare status over verschillende apparaten. Onze methode maakt gebruik van gerandomiseerde metingen, resulterend in een steekproefoverhead die $widetilde{O}(4^k / varepsilon ^2)$ is, waarbij $varepsilon $ de nauwkeurigheid van de berekening is en $k$ het aantal parallelle draden dat "knippen" om kleinere subcircuits te verkrijgen. We tonen ook een informatietheoretische ondergrens van $Omega(2^k / varepsilon ^2)$ voor elke vergelijkbare procedure. We gebruiken onze technieken om te laten zien dat circuits in het Quantum Approximate Optimization Algorithm (QAOA) met $p$ verstrengelingslagen kunnen worden gesimuleerd door circuits op een fractie van het oorspronkelijke aantal qubits met een overhead van ongeveer $2^{O(pkappa) }$, waarbij $kappa$ de grootte is van een bekende gebalanceerde hoekpuntscheider van de grafiek die het optimalisatieprobleem codeert. We verkrijgen numeriek bewijs van praktische versnellingen met behulp van onze methode toegepast op de QAOA, vergeleken met eerder werk. Ten slotte onderzoeken we de praktische haalbaarheid van het toepassen van de circuitcutting-procedure op grootschalige QAOA-problemen op geclusterde grafieken door een $30$-qubit-simulator te gebruiken om de variatie-energie van een $129$-qubit-probleem te evalueren en een $62$-qubit-probleem uit te voeren. -qubit-optimalisatie.

► BibTeX-gegevens

► Referenties

[1] https://​/​github.com/​XanaduAI/​randomized-measurements-circuit-cutting (2022).
https://​/​github.com/​XanaduAI/​randomized-measurements-circuit-cutting

[2] Scott Aaronson en Daniel Gottesman "Verbeterde simulatie van stabilisatorcircuits" Phys. Rev. A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] J. Avron, Ofer Casper en Ilan Rozen, "Kwantumvoordeel en ruisonderdrukking bij gedistribueerde kwantumcomputing" Phys. Rev. A 104, 052404 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.104.052404

[4] Thomas Ayral, François-Marie Le Régent, Zain Saleem, Yuri Alexeev en 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

[5] F. Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann en AG Green, "Parallel quantum simulation of large systems on small NISQ computers" npj Quantum Information 7, 79 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00420-3

[6] 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 en Nathan Killoran, "PennyLane: Automatic differentiation of hybrid quantum-classical computations" (2018).
https://​/​doi.org/​10.48550/​ARXIV.1811.04968
https: / / arxiv.org/ abs / 1811.04968

[7] Sergey Bravyi en David Gosset "Verbeterde klassieke simulatie van kwantumcircuits gedomineerd door Clifford Gates" Phys. Eerwaarde Lett. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

[8] Sergey Bravyi, David Gosset en Ramis Movassagh, "Klassieke algoritmen voor kwantumgemiddelde waarden" Nature Physics 17, 337-341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Sergey Bravyi, Graeme Smith en John A. Smolin, "Trading Classical and Quantum Computational Resources" Phys. Rev X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[10] Sergey Bravyi, Alexander Kliesch, Robert Koenig en Eugene Tang, "Obstakels voor Variational Quantum Optimization from Symmetry Protection" Phys. Eerwaarde Lett. 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[11] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset en Mark Howard, "Simulatie van kwantumcircuits door ontbindingen van lage stabilisatoren" Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones "Het vinden van goede benaderende vertex- en randpartities is NP-moeilijk" 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

[13] Francesco Buscemi en Nilanjana Datta "De kwantumcapaciteit van kanalen met willekeurig gecorreleerde ruis" IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https: / / doi.org/ 10.1109 / TIT.2009.2039166

[14] Senrui Chen, Wenjun Yu, Pei Zeng en Steven T. Flammia, "Robuuste schaduwschatting" PRX Quantum 2, 030348 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.030348

[15] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe en Shuchen Zhu, "Theory of Trotter Error with Commutator Scaling" Physical Review X 11 (2021).
https: / / doi.org/ 10.1103 / physrevx.11.011020

[16] Thomas M. Cover en Joy A. Thomas "Elements of Information Theory" Wiley (2005).
https://​/​doi.org/​10.1002/​047174882x

[17] Vedran Dunjko, Yimin Ge en J. Ignacio Cirac, "Computationele versnellingen met behulp van kleine kwantumapparaten" Phys. Eerwaarde Lett. 121, 250501 (2018).
https: / / doi.org/ 10.1103 / PhysRevLett.121.250501

[18] Andreas Elben, Steven T. Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill, Benoît Vermersch en Peter Zoller, "The randomized measurement toolbox" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.11374
https: / / arxiv.org/ abs / 2203.11374

[19] Leo Fang, Andreas Hehn, Harun Bayraktar en Sam Stanwyck, “NVIDIA/​cuQuantum: cuQuantum v22.05.0” (2022).
https: / / doi.org/ 10.5281 / zenodo.6574510

[20] Robert M. Fano "Transmissie van informatie: een statistische theorie van communicatie" MIT Press (1966).

[21] Edward Farhi, David Gamarnik en Sam Gutmann, "Het kwantumbenaderende optimalisatie-algoritme moet de hele grafiek zien: een typisch geval" (2020).
https://​/​doi.org/​10.48550/​ARXIV.2004.09002
https: / / arxiv.org/ abs / 2004.09002

[22] Edward Farhi, David Gamarnik en Sam Gutmann, "Het kwantumbenaderende optimalisatie-algoritme moet de hele grafiek zien: worstcasevoorbeelden" (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https: / / arxiv.org/ abs / 2005.08747

[23] Edward Farhi, Jeffrey Goldstone en Sam Gutmann, “A Quantum Approximate Optimization Algorithm” (2014).
https://​/​doi.org/​10.48550/​ARXIV.1411.4028
https: / / arxiv.org/ abs / 1411.4028

[24] Edward Farhi, Jeffrey Goldstone en Sam Gutmann, "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem" (2014).
https://​/​doi.org/​10.48550/​ARXIV.1412.6062
https: / / arxiv.org/ abs / 1412.6062

[25] Edward Farhiand Aram W Harrow "Quantum Supremacy through the Quantum Approximate Optimization Algorithm" (2016).
https://​/​doi.org/​10.48550/​ARXIV.1602.07674
https: / / arxiv.org/ abs / 1602.07674

[26] Uriel Feige, MohammadTaghi Hajiaghayi en James R. Lee, "Verbeterde benaderingsalgoritmen voor Vertex-scheidingstekens met minimaal gewicht" SIAM Journal on Computing 38, 629-657 (2008).
https: / / doi.org/ 10.1137 / 05064299X

[27] Johnnie Gray en Stefanos Kourtis "Hyper-geoptimaliseerde contractie van het tensornetwerk" Quantum 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[28] M Guţă, J Kahn, R Kueng en JA Tropp, "Fast-state tomografie met optimale foutgrenzen" Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).
https: / / doi.org/ 10.1088 / 1751-8121 / ab8111

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu en 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

[30] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli en Rupak Biswas, "From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz" Algorithms 12 (2019).
https: / / doi.org/ 10.3390 / a12020034
https:/​/​www.mdpi.com/​1999-4893/​12/​2/​34

[31] Michael Horodecki, Peter W. Shor en Mary Beth Ruskai, "Entanglement Breaking Channels" Recensies in Mathematical Physics 15, 629-641 (2003).
https: / / doi.org/ 10.1142 / S0129055X03001709

[32] Hsin-Yuan Huang, Richard Kueng en John Preskill, "Veel eigenschappen van een kwantumsysteem voorspellen op basis van zeer weinig metingen" Nature Physics 16, 1050–1057 (2020).
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[33] William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley en E Miles Stoudenmire, "Towards quantum machine learning with tensor networks" Quantum Science and Technology 4, 024001 (2019).
https: / / doi.org/ 10.1088 / 2058-9565 / aaea94

[34] Richard Kuengand David Gross "Qubit-stabilisatortoestanden zijn complexe projectieve 3-ontwerpen" (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https: / / arxiv.org/ abs / 1510.02767

[35] Junde Li, Mahabubul Alam en Swaroop Ghosh, "Grootschalige kwantumbenaderende optimalisatie via verdeel-en-heers" (2021).
https://​/​doi.org/​10.48550/​ARXIV.2102.13288
https: / / arxiv.org/ abs / 2102.13288

[36] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac en Nathan Killoran, "Quantum-inbedding voor machine learning" (2020).
https://​/​doi.org/​10.48550/​ARXIV.2001.03622
https: / / arxiv.org/ abs / 2001.03622

[37] Angus Lowe en Ashwin Nayak "Ondergrenzen voor het leren van kwantumtoestanden met metingen in één kopie" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.14438
https: / / arxiv.org/ abs / 2207.14438

[38] Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel en Yuri Alexeev, "Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2206.03579
https: / / arxiv.org/ abs / 2206.03579

[39] Igor L. Markovand Yaoyun Shi "Quantumberekening simuleren door Tensor Networks te contracteren" SIAM Journal on Computing 38, 963-981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[40] Simon C. Marshall, Casper Gyurik en Vedran Dunjko, "Hoogdimensionale kwantummachine learning met kleine kwantumcomputers" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https: / / arxiv.org/ abs / 2203.13739

[41] Matija Medvidović en Giuseppe Carleo "Klassieke variatiesimulatie van het Quantum Approximate Optimization Algorithm" npj Quantum Information 7 (2021).
https: / / doi.org/ 10.1038 / s41534-021-00440-z

[42] Kosuke Mitarai en Keisuke Fujii "Een virtuele poort van twee qubits bouwen door bewerkingen van één qubit te bemonsteren" New Journal of Physics 23, 023021 (2021).
https: / / doi.org/ 10.1088 / 1367-2630 / abd7bc

[43] Kosuke Mitarai en Keisuke Fujii "Overhead voor het simuleren van een niet-lokaal kanaal met lokale kanalen door middel van quasiprobability sampling" Quantum 5, 388 (2021).
https:/​/​doi.org/​10.22331/​q-2021-01-28-388

[44] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan en Ion Stoica, “Ray: A Distributed Framework for Emerging AI Applications” (2017) .
https://​/​doi.org/​10.48550/​ARXIV.1712.05889
https: / / arxiv.org/ abs / 1712.05889

[45] Hakop Pashayan, Joel J. Wallman en Stephen D. Bartlett, "Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities" Phys. Eerwaarde Lett. 115, 070501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.115.070501

[46] Tianyi Peng, Aram W. Harrow, Maris Ozols en Xiaodi Wu, "Simuleren van grote kwantumcircuits op een kleine kwantumcomputer", Physical Review Letters 125 (2020).
https: / / doi.org/ 10.1103 / physrevlett.125.150504

[47] Michael A. Perlin, Zain H. Saleem, Martin Suchara en James C. Osborn, "Quantum circuit cutting with maximum-likelihood tomography" npj Quantum Information 7 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00390-6

[48] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik en Jeremy L. O'Brien, "Een oplosser van verschillende eigenwaarden op een fotonische kwantumprocessor" Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Christophe Piveteau en David Sutter “Circuitbreien met klassieke communicatie” (2022).
https://​/​doi.org/​10.48550/​ARXIV.2205.00016
https: / / arxiv.org/ abs / 2205.00016

[50] Zain H. Saleem, Teague Tomesh, Michael A. Perlin, Pranav Gokhale en Martin Suchara, "Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing" (2021).
arXiv: 2107.07532

[51] Igal Sason en Sergio Verdú "$f$ -Divergence Inequalities" IEEE Transactions on Information Theory 62, 5973-6006 (2016).
https: / / doi.org/ 10.1109 / TIT.2016.2603151

[52] Maria Schuld, Alex Bocharov, Krysta M. Svore en Nathan Wiebe, "Circuit-centric quantum classifiers" Physical Review A 101 (2020).
https: / / doi.org/ 10.1103 / physreva.101.032308

[53] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac en Nathan Killoran, "Analytische gradiënten evalueren op kwantumhardware" Phys. Rev. A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[54] Hayk Shoukourian, Torsten Wilde, Axel Auweter en Arndt Bode, "Voorspellen van het energie- en stroomverbruik van sterk en zwak schalende HPC-toepassingen" Supercomputing Frontiers and Innovations 1, 20–41 (2014).
https://​/​doi.org/​10.14529/​jsfi140202

[55] Wei Tangand Margaret Martonosi "ScaleQC: een schaalbaar raamwerk voor hybride berekeningen op kwantum- en klassieke processors" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.00933
https: / / arxiv.org/ abs / 2207.00933

[56] Ewout Van Den Berg "Een eenvoudige methode om willekeurige Clifford-operators te bemonsteren" 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 54–59 (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[57] Zhihui Wang, Stuart Hadfield, Zhang Jiang en Eleanor G. Rieffel, "Quantum benaderend optimalisatie-algoritme voor MaxCut: een fermionische weergave" Phys. Rev. A 97, 022304 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022304

[58] John Watrous "De theorie van kwantuminformatie" Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[59] Zak Webb "De Clifford-groep vormt een unitair 3-ontwerp" (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02769
https: / / arxiv.org/ abs / 1510.02769

[60] Roeland Wiersema, Leonardo Guerini, Juan Felipe Carrasquilla en Leandro Aolita, "Circuitconnectiviteit verbetert door kwantum-klassieke-kwantuminterfaces" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https: / / arxiv.org/ abs / 2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao en You Zhou, "Quantumsimulatie met hybride tensornetwerken" Phys. Eerwaarde Lett. 127, 040501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.040501

[62] Huangjun Zhu "Multiqubit Clifford-groepen zijn unitaire 3-ontwerpen" Phys. Rev A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Geciteerd door

[1] Lirandë Pira en Chris Ferrie, "Een uitnodiging voor gedistribueerde kwantumneurale netwerken", arXiv: 2211.07056, (2022).

[2] Lukas Brenner, Christophe Piveteau en David Sutter, "Optimaal draadsnijden met klassieke communicatie", arXiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen en Michael Foss-Feig, "Qubit-reuse-compilatie met mid-circuitmeting en reset", arXiv: 2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge en 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 en Benjamin Weder, "Onderzoek naar het effect van circuitonderbreking in QAOA voor het MaxCut-probleem op NISQ-apparaten", arXiv: 2302.01792, (2023).

[6] Ritajit Majumdar en Christopher J. Wood, "Foutverzachtende kwantumcircuitsnijding", arXiv: 2211.13431, (2022).

[7] Daniel T. Chen, Zain H. Saleem en Michael A. Perlin, "Quantum verdeel en heers voor klassieke schaduwen", arXiv: 2212.00761, (2022).

[8] Gideon Uchehara, Tor M. Aamodt en Olivia Di Matteo, "Op rotatie geïnspireerde circuitonderbrekingsoptimalisatie", arXiv: 2211.07358, (2022).

[9] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer en Andre Luckow, "Een prestatiekarakterisering van kwantumgeneratieve modellen", arXiv: 2301.09363, (2023).

[10] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch en Juan Miguel Arrazola, "Een praktisch overzicht van beeldclassificatie met kwantumcircuits van variaties tensornetwerken", arXiv: 2209.11058, (2022).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2023-03-03 16:49:02). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2023-03-03 16:49:00).

Tijdstempel:

Meer van Quantum Journaal