Hurtig kvantekredsløbsskæring med randomiserede målinger

Hurtig kvantekredsløbsskæring med randomiserede målinger

Kildeknude: 1990460

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

1Xanadu, Toronto, ON, M5G 2C8, Canada
2Center for Teoretisk Fysik, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
3Center for Computational Quantum Physics, Flatiron Institute, New York, NY, 10010, USA
4Institut for Fysik, Columbia University, New York, 10027, USA

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Vi foreslår en ny metode til at udvide størrelsen af ​​en kvanteberegning ud over antallet af fysiske qubits, der er tilgængelige på en enkelt enhed. Dette opnås ved tilfældigt at indsætte måle-og-forbered kanaler for at udtrykke udgangstilstanden for et stort kredsløb som en adskillelig tilstand på tværs af forskellige enheder. Vores metode anvender randomiserede målinger, hvilket resulterer i en prøveoverhead, der er $widetilde{O}(4^k / varepsilon ^2)$, hvor $varepsilon $ er nøjagtigheden af ​​beregningen og $k$ antallet af parallelle ledninger, der er "skær" for at opnå mindre underkredsløb. Vi viser også en informationsteoretisk nedre grænse for $Omega(2^k / varepsilon ^2)$ for enhver sammenlignelig procedure. Vi bruger vores teknikker til at vise, at kredsløb i Quantum Approximate Optimization Algorithm (QAOA) med $p$ sammenfiltrende lag kan simuleres af kredsløb på en brøkdel af det oprindelige antal qubits med en overhead, der er omtrent $2^{O(pkappa) }$, hvor $kappa$ er størrelsen af ​​en kendt afbalanceret toppunktseparator af grafen, som koder for optimeringsproblemet. Vi opnår numeriske beviser for praktiske speedups ved hjælp af vores metode anvendt på QAOA sammenlignet med tidligere arbejde. Endelig undersøger vi den praktiske gennemførlighed af at anvende kredsløbsskæringsproceduren på storstilede QAOA-problemer på klyngede grafer ved at bruge en $30$-qubit-simulator til at evaluere variationsenergien af ​​et $129$-qubit-problem samt udføre en $62$ -qubit optimering.

► BibTeX-data

► Referencer

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

[2] Scott Aaronson og Daniel Gottesman "Forbedret simulering af stabilisatorkredsløb" Phys. Rev. A 70, 052328 (2004).
https://​/​doi.org/​10.1103/​PhysRevA.70.052328

[3] J. Avron, Ofer Casper og Ilan Rozen, "Kvantefordel og støjreduktion i distribueret kvanteberegning" Fysisk. 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 og Martin Suchara, "Quantum Divide and Compute: Hardware Demonstrations and Noisy Simulations" 2020 IEEE Computer Society årlige symposium om VLSI (ISVLSI) 138-140 (2020).
https://​/​doi.org/​10.1109/​ISVLSI49217.2020.00034

[5] F. Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann og AG Green, "Parallel kvantesimulering af store systemer på små NISQ-computere" 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 og 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 Bravyian og David Gosset "Forbedret klassisk simulering af kvantekredsløb domineret af Clifford Gates" Fysisk. Rev. Lett. 116, 250501 (2016).
https://​/​doi.org/​10.1103/​PhysRevLett.116.250501

[8] Sergey Bravyi, David Gosset og Ramis Movasagh, "Klassiske algoritmer for kvantemiddelværdier" Nature Physics 17, 337-341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Sergey Bravyi, Graeme Smith og 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 og Eugene Tang, "Forhindringer for variationskvanteoptimering fra symmetribeskyttelse" 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 og Mark Howard, "Simulering af kvantekredsløb ved lav-rangs stabilisatornedbrydning" Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones "At finde gode tilnærmede top- og kantpartitioner er NP-hårdt" 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 og Nilanjana Datta "Kvantekapaciteten af ​​kanaler med vilkårligt korreleret støj" IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https://​/​doi.org/​10.1109/​TIT.2009.2039166

[14] Senrui Chen, Wenjun Yu, Pei Zeng og 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 og 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 og Joy A. Thomas "Elements of Information Theory" Wiley (2005).
https://​/​doi.org/​10.1002/​047174882x

[17] Vedran Dunjko, Yimin Ge og J. Ignacio Cirac, "Computational Speedups Using Small Quantum Devices" 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 og 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 og Sam Stanwyck, "NVIDIA/​cuQuantum: cuQuantum v22.05.0" (2022).
https://​/​doi.org/​10.5281/​zenodo.6574510

[20] Robert M. Fano "Transmission of Information: a Statistical Theory of Communications" MIT Press (1966).

[21] Edward Farhi, David Gamarnik og Sam Gutmann, "The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case" (2020).
https://​/​doi.org/​10.48550/​ARXIV.2004.09002
https://​arxiv.org/​abs/​2004.09002

[22] Edward Farhi, David Gamarnik og Sam Gutmann, "The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case-eksempler" (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https://​arxiv.org/​abs/​2005.08747

[23] Edward Farhi, Jeffrey Goldstone og 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 og 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 og James R. Lee, "Forbedrede tilnærmelsesalgoritmer for minimumsvægtvertexseparatorer" SIAM Journal on Computing 38, 629-657 (2008).
https://doi.org/​10.1137/​05064299X

[27] Johnnie Gray og Stefanos Kourtis "Hyper-optimized tensor network contraction" Quantum 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[28] M Guţă, J Kahn, R Kueng og JA Tropp, "Fast state tomography with optimal error bounds" 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 og 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 og 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 og Mary Beth Ruskai, "Entanglement Breaking Channels" Anmeldelser i Mathematical Physics 15, 629-641 (2003).
https://​/​doi.org/​10.1142/​S0129055X03001709

[32] Hsin-Yuan Huang, Richard Kueng og John Preskill, "Forudsigelse af mange egenskaber ved et kvantesystem ud fra meget få målinger" 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 og 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 stabilisatortilstande er komplekse projektive 3-designs" (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https://​arxiv.org/​abs/​1510.02767

[35] Junde Li, Mahabubul Alam og 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 og Nathan Killoran, "Quantum embeddings for machine learning" (2020).
https://​/​doi.org/​10.48550/​ARXIV.2001.03622
https://​arxiv.org/​abs/​2001.03622

[37] Angus Lowe og Ashwin Nayak "Nedre grænser for at lære kvantetilstande med enkeltkopimålinger" (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 og 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 "Simulating Quantum Computing by Contracting Tensor Networks" SIAM Journal on Computing 38, 963-981 (2008).
https://​/​doi.org/​10.1137/​050644756

[40] Simon C. Marshall, Casper Gyurik og Vedran Dunjko, "Højdimensionel kvantemaskinelæring med små kvantecomputere" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https://​arxiv.org/​abs/​2203.13739

[41] Matija Medvidović og Giuseppe Carleo "Klassisk variationssimulering af Quantum Approximate Optimization Algorithm" npj Quantum Information 7 (2021).
https://​/​doi.org/​10.1038/​s41534-021-00440-z

[42] Kosuke Mitarai og Keisuke Fujii "Konstruktion af en virtuel to-qubit-gate ved at sampne enkelt-qubit-operationer" New Journal of Physics 23, 023021 (2021).
https:/​/​doi.org/​10.1088/​1367-2630/​abd7bc

[43] Kosuke Mitarai og Keisuke Fujii "Overhead til simulering af en ikke-lokal kanal med lokale kanaler ved 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 og 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 og Stephen D. Bartlett, "Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities" Phys. Rev. Lett. 115, 070501 (2015).
https://​/​doi.org/​10.1103/​PhysRevLett.115.070501

[46] Tianyi Peng, Aram W. Harrow, Maris Ozols og Xiaodi Wu, "Simulering af store kvantekredsløb på en lille kvantecomputer" Physical Review Letters 125 (2020).
https://​/​doi.org/​10.1103/​physrevlett.125.150504

[47] Michael A. Perlin, Zain H. Saleem, Martin Suchara og 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 og Jeremy L. O'Brien, "En variationel egenværdiopløser på en fotonisk kvanteprocessor" Nature Communications 5 (2014).
https://​/​doi.org/​10.1038/​ncomms5213

[49] Christophe Piveteau og David Sutter "Circuit knitting with classical communication" (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 og Martin Suchara, "Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing" (2021).
arXiv: 2107.07532

[51] Igal Sason og 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 og 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 og Nathan Killoran, "Evaluating analytic gradients on quantum hardware" Phys. Rev. A 99, 032331 (2019).
https://​/​doi.org/​10.1103/​PhysRevA.99.032331

[54] Hayk Shoukourian, Torsten Wilde, Axel Auweter og Arndt Bode, "Forudsigelse af energi- og strømforbruget af stærke og svage skalerings-HPC-applikationer" Supercomputing Frontiers and Innovations 1, 20-41 (2014).
https:/​/​doi.org/​10.14529/​jsfi140202

[55] Wei Tangand Margaret Martonosi "ScaleQC: A Scalable Framework for Hybrid Computation on Quantum and Classical Processors" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.00933
https://​arxiv.org/​abs/​2207.00933

[56] Ewout Van Den Berg "En simpel metode til at udtage tilfældige Clifford-operatører" 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 og Eleanor G. Rieffel, "Quantum approximative optimization algorithm for MaxCut: A fermonic view" 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 "The Clifford group forms a unitary 3-design" (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02769
https://​arxiv.org/​abs/​1510.02769

[60] Roeland Wiersema, Leonardo Guerini, Juan Felipe Carrasquilla og Leandro Aolita, "Kretsforbindelse øger ved kvante-klassisk-kvante-grænseflader" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https://​arxiv.org/​abs/​2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao og You Zhou, "Quantum Simulation with Hybrid Tensor Networks" Phys. Rev. Lett. 127, 040501 (2021).
https://​/​doi.org/​10.1103/​PhysRevLett.127.040501

[62] Huangjun Zhu "Multiqubit Clifford-grupper er enheds-3-designs" Phys. Rev. A 96, 062336 (2017).
https://​/​doi.org/​10.1103/​PhysRevA.96.062336

Citeret af

[1] Lirandë Pira og Chris Ferrie, "An Invitation to Distributed Quantum Neural Networks", arXiv: 2211.07056, (2022).

[2] Lukas Brenner, Christophe Piveteau og David Sutter, "Optimal ledningsskæring med klassisk kommunikation", arXiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen og Michael Foss-Feig, "Qubit-genbrugskompilering med midtkredsmåling og nulstilling", arXiv: 2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge og 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 og Benjamin Weder, "Undersøgelse af effekten af ​​kredsløbsskæring i QAOA for MaxCut-problemet på NISQ-enheder", arXiv: 2302.01792, (2023).

[6] Ritajit Majumdar og Christopher J. Wood, "Error mitigated quantum circuit cutting", arXiv: 2211.13431, (2022).

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

[8] Gideon Uchehara, Tor M. Aamodt og Olivia Di Matteo, "Rotationsinspireret kredsløbsskæringsoptimering", arXiv: 2211.07358, (2022).

[9] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer og Andre Luckow, "En præstationskarakterisering af kvantegenerative modeller", arXiv: 2301.09363, (2023).

[10] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch og Juan Miguel Arrazola, "En praktisk oversigt over billedklassificering med variationelle tensor-netværks kvantekredsløb", arXiv: 2209.11058, (2022).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2023-03-03 16:49:02). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2023-03-03 16:49:00).

Tidsstempel:

Mere fra Quantum Journal