Rask kvantekretsskjæring med randomiserte målinger

Rask kvantekretsskjæring med randomiserte målinger

Kilde node: 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 Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
3Center for Computational Quantum Physics, Flatiron Institute, New York, NY, 10010, USA
4Institutt for fysikk, Columbia University, New York, 10027, USA

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Vi foreslår en ny metode for å utvide størrelsen på en kvanteberegning utover antallet fysiske qubits tilgjengelig på en enkelt enhet. Dette oppnås ved tilfeldig å sette inn måle-og-forbered kanaler for å uttrykke utgangstilstanden til en stor krets som en separerbar tilstand på tvers av forskjellige enheter. Metoden vår bruker randomiserte målinger, noe som resulterer i en prøveoverhead som er $widetilde{O}(4^k / varepsilon ^2)$, der $varepsilon $ er nøyaktigheten til beregningen og $k$ antallet parallelle ledninger som er "kutte" for å oppnå mindre underkretser. Vi viser også en informasjonsteoretisk nedre grense for $Omega(2^k / varepsilon ^2)$ for enhver sammenlignbar prosedyre. Vi bruker teknikkene våre for å vise at kretser i Quantum Approximate Optimization Algorithm (QAOA) med $p$ sammenfiltrende lag kan simuleres av kretser på en brøkdel av det opprinnelige antallet qubits med en overhead som er omtrent $2^{O(pkappa) }$, der $kappa$ er størrelsen på en kjent balansert toppunktseparator i grafen som koder for optimaliseringsproblemet. Vi får numeriske bevis på praktiske hastigheter ved å bruke metoden vår brukt på QAOA, sammenlignet med tidligere arbeid. Til slutt undersøker vi den praktiske gjennomførbarheten av å bruke kretsskjæreprosedyren på storskala QAOA-problemer på grupperte grafer ved å bruke en $30$-qubit-simulator for å evaluere variasjonsenergien til et $129$-qubit-problem, samt utføre en $62$ -qubit-optimalisering.

► BibTeX-data

► Referanser

[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 av stabilisatorkretser" Phys. Rev. A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] J. Avron, Ofer Casper og Ilan Rozen, "Quantefordel og støyreduksjon i distribuert 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 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 og AG Green, "Parallell 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 Wiersema, 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 av kvantekretser dominert av 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 kvantemiddelverdier" 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, "hindringer for variasjonskvanteoptimalisering fra symmetribeskyttelse" Fysisk. 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 av kvantekretser ved lav-rangs stabilisatordekomposisjoner" Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones "Å finne gode omtrentlige toppunkt- og kantpartisjoner er NP-hard" 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 "Kvantekapasiteten til kanaler med vilkårlig korrelert støy" 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ærmingsalgoritmer for minimumsvektsvertexseparatorer" 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" Reviews in Mathematical Physics 15, 629–641 (2003).
https: / / doi.org/ 10.1142 / S0129055X03001709

[32] Hsin-Yuan Huang, Richard Kueng og John Preskill, "Forutsi mange egenskaper til et kvantesystem fra svært 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 stabilisatortilstander er komplekse projektive 3-design" (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 grenser for å lære kvantetilstander 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øydimensjonal kvantemaskinlæring med små kvantedatamaskiner" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https: / / arxiv.org/ abs / 2203.13739

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

[42] Kosuke Mitarai og Keisuke Fujii "Konstruerer en virtuell to-qubit-port ved å prøve én-qubit-operasjoner" New Journal of Physics 23, 023021 (2021).
https://​/​doi.org/​10.1088/​1367-2630/​abd7bc

[43] Kosuke Mitarai og Keisuke Fujii "Overhead for simulering av 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 av store kvantekretser på en liten kvantedatamaskin" 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 variasjonell egenverdiløser på en fotonisk kvanteprosessor" Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Christophe Piveteau og David Sutter "Kretsstrikk med klassisk kommunikasjon" (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, "Forutsi energi- og strømforbruket til sterke og svake skalerings-HPC-applikasjoner" 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 enkel metode for sampling av tilfeldige 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 "Clifford-gruppen danner et enhetlig 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, "Kretstilkobling øker med kvante-klassisk-kvantegrensesnitt" (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 enhetlige 3-designs" Phys. Rev. A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Sitert av

[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 ledningsskjæring med klassisk kommunikasjon", arxiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen og Michael Foss-Feig, "Qubit-gjenbrukskompilering med midtkretsmåling og tilbakestilling", 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øker effekten av kretsskjæring i QAOA for MaxCut-problemet på NISQ-enheter", 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, "Rotasjonsinspirert kretskuttoptimalisering", 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 ytelseskarakterisering av 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 oversikt over bildeklassifisering med variasjonelle tensor-nettverk kvantekretser", arxiv: 2209.11058, (2022).

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2023-03-03 16:49:02). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

On Crossrefs siterte tjeneste ingen data om sitering av verk ble funnet (siste forsøk 2023-03-03 16:49:00).

Tidstempel:

Mer fra Kvantejournal