Snabb kvantkretsskärning med randomiserade mätningar

Snabb kvantkretsskärning med randomiserade mätningar

Tidsstämpel: 2 mars 2023 11:42
Källnod: 1990460

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

1Xanadu, Toronto, ON, M5G 2C8, Kanada
2Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
3Center for Computational Quantum Physics, Flatiron Institute, New York, NY, 10010, USA
4Institutionen för fysik, Columbia University, New York, 10027, USA

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Vi föreslår en ny metod för att utöka storleken på en kvantberäkning utöver antalet fysiska kvantbitar som finns tillgängliga på en enda enhet. Detta åstadkoms genom att slumpmässigt infoga mät-och-förbered-kanaler för att uttrycka utgångstillståndet för en stor krets som ett separerbart tillstånd över distinkta enheter. Vår metod använder slumpmässiga mätningar, vilket resulterar i ett prov overhead som är $widetilde{O}(4^k / varepsilon ^2)$, där $varepsilon $ är noggrannheten i beräkningen och $k$ antalet parallella ledningar som är "klipp" för att erhålla mindre underkretsar. Vi visar också en informationsteoretisk nedre gräns för $Omega(2^k / varepsilon ^2)$ för varje jämförbar procedur. Vi använder våra tekniker för att visa att kretsar i Quantum Approximate Optimization Algorithm (QAOA) med $p$ intrasslande lager kan simuleras av kretsar på en bråkdel av det ursprungliga antalet qubits med en overhead som är ungefär $2^{O(pkappa) }$, där $kappa$ är storleken på en känd balanserad vertexseparator i grafen som kodar optimeringsproblemet. Vi får numeriska bevis på praktiska snabbare med vår metod som tillämpas på QAOA, jämfört med tidigare arbete. Slutligen undersöker vi den praktiska genomförbarheten av att tillämpa kretsskärningsproceduren på storskaliga QAOA-problem på klustrade grafer genom att använda en $30$-qubit-simulator för att utvärdera variationsenergin för ett $129$-qubit-problem samt utföra en $62$ -qubit-optimering.

► BibTeX-data

► Referenser

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

[2] Scott Aaronson och Daniel Gottesman "Förbättrad simulering av stabilisatorkretsar" Phys. Rev. A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] J. Avron, Ofer Casper och Ilan Rozen, "Kvantfördelar och brusreducering i distribuerad kvantberäkning" 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 och 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 och AG Green, "Parallell kvantsimulering av stora system på små NISQ-datorer" 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 och 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 och David Gosset "Förbättrad klassisk simulering av kvantkretsar dominerade av Clifford Gates" Phys. Rev. Lett. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

[8] Sergey Bravyi, David Gosset och Ramis Movasagh, "Klassiska algoritmer för kvantmedelvärden" Nature Physics 17, 337–341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Sergey Bravyi, Graeme Smith och 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 och Eugene Tang, "Hinder för variationskvantumoptimering från symmetriskydd" 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 och Mark Howard, "Simulering av kvantkretsar genom lågnivåstabilisatornedbrytningar" Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones "Att hitta bra ungefärliga vertex- och kantpartitioner är NP-hårt" 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 och Nilanjana Datta "Kvantumkapaciteten hos kanaler med godtyckligt korrelerat brus" IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https: / / doi.org/ 10.1109 / TIT.2009.2039166

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

[17] Vedran Dunjko, Yimin Ge och 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 och 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 och 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 och 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 och Sam Gutmann, "The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples" (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https: / / arxiv.org/ abs / 2005.08747

[23] Edward Farhi, Jeffrey Goldstone och 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 och 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 och James R. Lee, "Förbättrade approximationsalgoritmer för minimumviktsvertexseparatorer" SIAM Journal on Computing 38, 629–657 (2008).
https: / / doi.org/ 10.1137 / 05064299X

[27] Johnnie Gray och 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 och 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 och 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 och 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 och Mary Beth Ruskai, "Entanglement Breaking Channels" Recensioner i Mathematical Physics 15, 629–641 (2003).
https: / ⠀ </ ⠀ <doi.org/†<10.1142 / ⠀ <S0129055X03001709

[32] Hsin-Yuan Huang, Richard Kueng och John Preskill, "Förutsäga många egenskaper hos ett kvantsystem från mycket få mätningar" 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 och 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 stabilisatortillstånd är komplexa projektiva 3-designer" (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https: / / arxiv.org/ abs / 1510.02767

[35] Junde Li, Mahabubul Alam och 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 och 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 och Ashwin Nayak "Lägre gränser för att lära sig kvanttillstånd med enstaka mätningar" (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 och 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 Computation by Contracting Tensor Networks" SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[40] Simon C. Marshall, Casper Gyurik och Vedran Dunjko, "High Dimensional Quantum Machine Learning With Small Quantum Computers" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https: / / arxiv.org/ abs / 2203.13739

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

[42] Kosuke Mitarai och Keisuke Fujii "Konstruera en virtuell två-qubit-grind genom att sampla en-qubit-operationer" New Journal of Physics 23, 023021 (2021).
https: / / doi.org/ 10.1088 / 1367-2630 / abd7bc

[43] Kosuke Mitarai och Keisuke Fujii "Overhead för simulering av en icke-lokal kanal med lokala kanaler genom 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 och 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 och 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 och Xiaodi Wu, "Simulering av stora kvantkretsar på en liten kvantdator" Physical Review Letters 125 (2020).
https: / / doi.org/ 10.1103 / physrevlett.125.150504

[47] Michael A. Perlin, Zain H. Saleem, Martin Suchara och 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 och Jeremy L. O'Brien, "En variation av egenvärden på en fotonisk kvantprocessor" Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Christophe Piveteau och 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 och Martin Suchara, "Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing" (2021).
arXiv: 2107.07532

[51] Igal Sason och 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 och 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 och 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 och Arndt Bode, "Predicting the energy and power consumer of strong and weak scaling HPC applications" 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 metod för sampling av slumpmässiga 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 och Eleanor G. Rieffel, "Quantum approximative optimization algorithm for MaxCut: A fermionic 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 bildar en 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 och Leandro Aolita, "Kretsanslutningen ökar genom kvant-klassisk-kvantgränssnitt" (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https: / / arxiv.org/ abs / 2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao och 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 är enhetliga 3-designer" Phys. Rev. A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Citerad av

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

[2] Lukas Brenner, Christophe Piveteau och David Sutter, "Optimal trådklippning med klassisk kommunikation", arXiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen och Michael Foss-Feig, "Qubit-återanvändningskompilering med mittkretsmätning och återställning", arXiv: 2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge och 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 och Benjamin Weder, "Undersöka effekten av kretsklippning i QAOA för MaxCut-problemet på NISQ-enheter", arXiv: 2302.01792, (2023).

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

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

[8] Gideon Uchehara, Tor M. Aamodt och Olivia Di Matteo, "Rotationsinspirerad kretssnittsoptimering", arXiv: 2211.07358, (2022).

[9] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer och 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 och Juan Miguel Arrazola, "En praktisk översikt över bildklassificering med variationer i tensornätverkskvantumkretsar", arXiv: 2209.11058, (2022).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-03-03 16:49:02). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2023-03-03 16:49:00).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal