Hitro kvantno rezanje vezja z naključnimi meritvami

Hitro kvantno rezanje vezja z naključnimi meritvami

Časovni žig: 2. marec 2023 11
Izvorno vozlišče: 1990460

Angus Lowe1,2, Matija Medvidović1,3,4, Anthony Hayes1, Lee J. O'Riordan1, Thomas R. Bromley1, Juan Miguel Arrazola1in Nathan Killoran1

1Xanadu, Toronto, ON, M5G 2C8, Kanada
2Center za teoretično fiziko, Massachusetts Institute of Technology, Cambridge, MA, 02139, ZDA
3Center za računalniško kvantno fiziko, Inštitut Flatiron, New York, NY, 10010, ZDA
4Oddelek za fiziko, Univerza Columbia, New York, 10027, ZDA

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Predlagamo novo metodo za razširitev velikosti kvantnega izračuna preko števila fizičnih kubitov, ki so na voljo v eni napravi. To se doseže z naključnim vstavljanjem kanalov za merjenje in pripravo, da se izrazi izhodno stanje velikega vezja kot ločljivo stanje v različnih napravah. Naša metoda uporablja naključne meritve, kar ima za posledico vzorčno obremenitev, ki je $widetilde{O}(4^k / varepsilon ^2)$, kjer je $varepsilon $ natančnost izračuna in $k$ število vzporednih žic, ki so "cut", da dobimo manjša podvezja. Prikazujemo tudi informacijsko-teoretično spodnjo mejo $Omega(2^k / varepsilon ^2)$ za kateri koli primerljiv postopek. S svojimi tehnikami pokažemo, da je mogoče vezja v algoritmu kvantne približne optimizacije (QAOA) z $p$ zapletajočimi plastmi simulirati s vezji na delčku prvotnega števila kubitov s stroški, ki so približno $2^{O(pkappa) }$, kjer je $kappa$ velikost znanega uravnoteženega ločilnika vozlišč grafa, ki kodira problem optimizacije. Z našo metodo, uporabljeno za QAOA, pridobimo številčne dokaze o praktičnih pospešitvah v primerjavi s prejšnjim delom. Končno raziskujemo praktično izvedljivost uporabe postopka rezanja vezja za obsežne probleme QAOA na gručastih grafih z uporabo simulatorja $30$-qubit za ovrednotenje variacijske energije $129$-qubit problema kot tudi za izvedbo $62$-qubit simulatorja. -Qubit optimizacija.

► BibTeX podatki

► Reference

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

[2] Scott Aaronson in Daniel Gottesman "Izboljšana simulacija stabilizatorskih vezij" Phys. Rev. A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] J. Avron, Ofer Casper in Ilan Rozen, »Kvantna prednost in zmanjšanje hrupa v porazdeljenem kvantnem računalništvu« 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 in Martin Suchara, "Quantum Divide and Compute: Hardware Demonstrations and Noisy Simulations" 2020 Letni simpozij IEEE Computer Society o VLSI (ISVLSI) 138–140 (2020).
https://​/​doi.org/​10.1109/​ISVLSI49217.2020.00034

[5] F. Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann in AG Green, »Vzporedna kvantna simulacija velikih sistemov na majhnih računalnikih NISQ« 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 in Nathan Killoran, »PennyLane: Samodejna diferenciacija hibridnih kvantno-klasičnih izračunov« (2018).
https://​/​doi.org/​10.48550/​ARXIV.1811.04968
https: / / arxiv.org/ abs / 1811.04968

[7] Sergey Bravyiand David Gosset »Izboljšana klasična simulacija kvantnih vezij, ki jih obvladuje Clifford Gates« Phys. Rev. Lett. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

[8] Sergey Bravyi, David Gosset in Ramis Movassagh, »Klasični algoritmi za kvantne srednje vrednosti« Nature Physics 17, 337–341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Sergey Bravyi, Graeme Smith in John A. Smolin, »Trgovanje s klasičnimi in kvantnimi računalniškimi viri« Phys. Rev. X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[10] Sergey Bravyi, Alexander Kliesch, Robert Koenig in Eugene Tang, "Ovire za variacijsko kvantno optimizacijo zaradi zaščite simetrije" Phys. Rev. Lett. 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[11] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset in Mark Howard, »Simulacija kvantnih vezij z razpadi stabilizatorjev nizkega ranga« Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones "Iskanje dobrih približnih particij vozlišč in robov je NP-težko" 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 Buscemiand Nilanjana Datta »Kvantna zmogljivost kanalov s poljubno koreliranim šumom« IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https: / / doi.org/ 10.1109 / TIT.2009.2039166

[14] Senrui Chen, Wenjun Yu, Pei Zeng in Steven T. Flammia, »Robust Shadow Estimation« PRX Quantum 2, 030348 (2021).
https: / / doi.org/ 10.1103 / PRXQuantum.2.030348

[15] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe in 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 in Joy A. Thomas "Elementi teorije informacij" Wiley (2005).
https://​/​doi.org/​10.1002/​047174882x

[17] Vedran Dunjko, Yimin Ge in J. Ignacio Cirac, »Računalniške pospešitve z uporabo majhnih kvantnih naprav« Phys. Rev. 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 in Peter Zoller, »Zbirka orodij za naključno merjenje« (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.11374
https: / / arxiv.org/ abs / 2203.11374

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

[20] Robert M. Fano »Prenos informacij: statistična teorija komunikacij« MIT Press (1966).

[21] Edward Farhi, David Gamarnik in Sam Gutmann, »Algoritem kvantne približne optimizacije mora videti celoten graf: tipičen primer« (2020).
https://​/​doi.org/​10.48550/​ARXIV.2004.09002
https: / / arxiv.org/ abs / 2004.09002

[22] Edward Farhi, David Gamarnik in Sam Gutmann, »Algoritem kvantne približne optimizacije mora videti celoten graf: primeri najslabšega primera« (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https: / / arxiv.org/ abs / 2005.08747

[23] Edward Farhi, Jeffrey Goldstone in Sam Gutmann, »Algoritem kvantne približne optimizacije« (2014).
https://​/​doi.org/​10.48550/​ARXIV.1411.4028
https: / / arxiv.org/ abs / 1411.4028

[24] Edward Farhi, Jeffrey Goldstone in Sam Gutmann, »Kvantni približni optimizacijski algoritem, uporabljen pri problemu omejene omejitve pojavljanja« (2014).
https://​/​doi.org/​10.48550/​ARXIV.1412.6062
https: / / arxiv.org/ abs / 1412.6062

[25] Edward Farhiand Aram W Harrow »Kvantna premoč skozi kvantni približni optimizacijski algoritem« (2016).
https://​/​doi.org/​10.48550/​ARXIV.1602.07674
https: / / arxiv.org/ abs / 1602.07674

[26] Uriel Feige, MohammadTaghi Hajiaghayi in James R. Lee, »Improved Approximation Algorithms for Minimum Weight Vertex Separators« SIAM Journal on Computing 38, 629–657 (2008).
https: / / doi.org/ 10.1137 / 05064299X

[27] Johnnie Grayand Stefanos Kourtis »Hiperoptimizirano krčenje tenzorskega omrežja« Quantum 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[28] M Guţă, J Kahn, R Kueng in JA Tropp, »Hitra tomografija stanja z optimalnimi mejami napak« 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 in 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 in Rupak Biswas, »Od algoritma kvantne približne optimizacije do kvantnega izmeničnega operatorja Ansatz« Algoritmi 12 (2019).
https: / / doi.org/ 10.3390 / a12020034
https:/​/​www.mdpi.com/​1999-4893/​12/​2/​34

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

[32] Hsin-Yuan Huang, Richard Kueng in John Preskill, »Napovedovanje številnih lastnosti kvantnega sistema iz zelo malo meritev« 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 in E Miles Stoudenmire, »Proti kvantnemu strojnemu učenju s tenzorskimi omrežji« Kvantna znanost in tehnologija 4, 024001 (2019).
https: / / doi.org/ 10.1088 / 2058-9565 / aaea94

[34] Richard Kuengand David Gross »Stanja stabilizatorja Qubit so zapleteni projektivni 3-dizajni« (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https: / / arxiv.org/ abs / 1510.02767

[35] Junde Li, Mahabubul Alam in Swaroop Ghosh, »Large-scale Quantum Approximate Optimization via Divide and Conquer« (2021).
https://​/​doi.org/​10.48550/​ARXIV.2102.13288
https: / / arxiv.org/ abs / 2102.13288

[36] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac in Nathan Killoran, »Kvantne vdelave za strojno učenje« (2020).
https://​/​doi.org/​10.48550/​ARXIV.2001.03622
https: / / arxiv.org/ abs / 2001.03622

[37] Angus Lowe in Ashwin Nayak »Spodnje meje za učenje kvantnih stanj z meritvami v eni kopiji« (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 in Yuri Alexeev, »Pragi frekvence vzorčenja za kvantno prednost algoritma kvantne približne optimizacije« (2022).
https://​/​doi.org/​10.48550/​ARXIV.2206.03579
https: / / arxiv.org/ abs / 2206.03579

[39] Igor L. Markovand Yaoyun Shi »Simulacija kvantnega računanja s krčenjem tenzorskih omrežij« SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[40] Simon C. Marshall, Casper Gyurik in Vedran Dunjko, »Visokodimenzionalno kvantno strojno učenje z majhnimi kvantnimi računalniki« (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https: / / arxiv.org/ abs / 2203.13739

[41] Matija Medvidović in Giuseppe Carleo “Klasična variacijska simulacija kvantnega približnega optimizacijskega algoritma” npj Quantum Information 7 (2021).
https: / / doi.org/ 10.1038 / s41534-021-00440-z

[42] Kosuke Mitarai in Keisuke Fujii »Konstruiranje virtualnih dvokubitnih vrat z vzorčenjem enojnih kubitnih operacij« New Journal of Physics 23, 023021 (2021).
https: / / doi.org/ 10.1088 / 1367-2630 / abd7bc

[43] Kosuke Mitarai in Keisuke Fujii »Režijski stroški za simulacijo nelokalnega kanala z lokalnimi kanali s kvaziverjetnostnim vzorčenjem« 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 in Ion Stoica, »Ray: 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 in Stephen D. Bartlett, »Ocenjevanje verjetnosti izida kvantnih vezij z uporabo kvaziverjetnosti« Phys. Rev. Lett. 115, 070501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.115.070501

[46] Tianyi Peng, Aram W. Harrow, Maris Ozols in Xiaodi Wu, »Simulacija velikih kvantnih vezij na majhnem kvantnem računalniku« Physical Review Letters 125 (2020).
https: / / doi.org/ 10.1103 / physrevlett.125.150504

[47] Michael A. Perlin, Zain H. Saleem, Martin Suchara in James C. Osborn, »Kvantno rezanje vezja s tomografijo največje verjetnosti« 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 in Jeremy L. O'Brien, "Variacijski razreševalec lastnih vrednosti na fotonskem kvantnem procesorju" Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Christophe Piveteau in David Sutter »Pletenje v vezju s klasično komunikacijo« (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 in Martin Suchara, »Kvantna razdeli in vladaj za kombinatorično optimizacijo in porazdeljeno računalništvo« (2021).
arXiv: 2107.07532

[51] Igal Sason in 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 in Nathan Wiebe, “Circuit-centric kvantni klasifikatorji” Physical Review A 101 (2020).
https: / / doi.org/ 10.1103 / physreva.101.032308

[53] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac in Nathan Killoran, “Vrednotenje analitičnih gradientov na kvantni strojni opremi” Phys. Rev. A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[54] Hayk Shoukourian, Torsten Wilde, Axel Auweter in Arndt Bode, »Napovedovanje porabe energije in moči močnih in šibkih skalirnih HPC aplikacij« Superračunalniške meje in inovacije 1, 20–41 (2014).
https://​/​doi.org/​10.14529/​jsfi140202

[55] Wei Tangand Margaret Martonosi »ScaleQC: Razširljivo ogrodje za hibridno računanje na kvantnih in klasičnih procesorjih« (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.00933
https: / / arxiv.org/ abs / 2207.00933

[56] Ewout Van Den Berg »Preprosta metoda za vzorčenje naključnih Cliffordovih operaterjev« 2021 Mednarodna konferenca IEEE o kvantnem računališču in inženirstvu (QCE) 54–59 (2021).
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[57] Zhihui Wang, Stuart Hadfield, Zhang Jiang in Eleanor G. Rieffel, »Algoritem kvantne približne optimizacije za MaxCut: fermionski pogled« Phys. Rev. A 97, 022304 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022304

[58] John Watrous “The Theory of Quantum Information” Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[59] Zak Webb »Skupina Clifford tvori enoten 3-dizajn« (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02769
https: / / arxiv.org/ abs / 1510.02769

[60] Roeland Wiersema, Leonardo Guerini, Juan Felipe Carrasquilla in Leandro Aolita, »Kvantno-klasično-kvantni vmesniki povečujejo povezljivost vezij« (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https: / / arxiv.org/ abs / 2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao in You Zhou, »Kvantna simulacija s hibridnimi tenzorskimi omrežji« Phys. Rev. Lett. 127, 040501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.040501

[62] Huangjun Zhu "Multiqubit Cliffordove skupine so enotni 3-dizajni" Phys. Rev. A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Navedel

[1] Lirandë Pira in Chris Ferrie, "Vabilo k porazdeljenim kvantnim nevronskim mrežam", arXiv: 2211.07056, (2022).

[2] Lukas Brenner, Christophe Piveteau in David Sutter, »Optimalno rezanje žice s klasično komunikacijo«, arXiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen in Michael Foss-Feig, "Kompilacija ponovne uporabe Qubit z merjenjem in ponastavitvijo vmesnega tokokroga", arXiv: 2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge in 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 in Benjamin Weder, "Raziskovanje učinka rezanja vezja v QAOA za problem MaxCut na napravah NISQ", arXiv: 2302.01792, (2023).

[6] Ritajit Majumdar in Christopher J. Wood, "Rezanje kvantnega vezja z zmanjšanjem napak", arXiv: 2211.13431, (2022).

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

[8] Gideon Uchehara, Tor M. Aamodt in Olivia Di Matteo, »Optimizacija rezanja vezja na podlagi vrtenja«, arXiv: 2211.07358, (2022).

[9] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer in 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 in Juan Miguel Arrazola, »Praktični pregled klasifikacije slik s kvantnimi vezji variacijskega tenzorskega omrežja« arXiv: 2209.11058, (2022).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2023-03-03 16:49:02). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2023-03-03 16:49:00).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal