Schnelles Schneiden von Quantenschaltkreisen mit randomisierten Messungen

Schnelles Schneiden von Quantenschaltkreisen mit randomisierten Messungen

Quellknoten: 1990460

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

1Xanadu, Toronto, ON, M5G 2C8, Kanada
2Zentrum für Theoretische Physik, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
3Zentrum für Computational Quantum Physics, Flatiron Institute, New York, NY, 10010, USA
4Institut für Physik, Columbia University, New York, 10027, USA

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Wir schlagen eine neue Methode vor, um die Größe einer Quantenberechnung über die Anzahl der auf einem einzelnen Gerät verfügbaren physischen Qubits hinaus zu erweitern. Dies wird durch zufälliges Einfügen von Mess- und Vorbereitungskanälen erreicht, um den Ausgangszustand einer großen Schaltung als trennbaren Zustand über verschiedene Geräte hinweg auszudrücken. Unsere Methode verwendet randomisierte Messungen, was zu einem Stichproben-Overhead von $widetilde{O}(4^k / varepsilon ^2)$ führt, wobei $varepsilon $ die Genauigkeit der Berechnung und $k$ die Anzahl der parallelen Drähte ist „schneiden“, um kleinere Teilschaltungen zu erhalten. Wir zeigen auch eine informationstheoretische Untergrenze von $Omega(2^k / varepsilon ^2)$ für jedes vergleichbare Verfahren. Wir verwenden unsere Techniken, um zu zeigen, dass Schaltungen im Quantum Approximate Optimization Algorithm (QAOA) mit $p$ Verschränkungsschichten durch Schaltungen mit einem Bruchteil der ursprünglichen Anzahl von Qubits mit einem Overhead von etwa $2^{O(pkappa) simuliert werden können. }$, wobei $kappa$ die Größe eines bekannten ausgeglichenen Scheitelpunkttrennzeichens des Graphen ist, der das Optimierungsproblem codiert. Wir erhalten numerische Beweise für praktische Beschleunigungen unter Verwendung unserer Methode, die auf die QAOA angewendet wird, im Vergleich zu früheren Arbeiten. Schließlich untersuchen wir die praktische Durchführbarkeit der Anwendung des Circuit-Cutting-Verfahrens auf groß angelegte QAOA-Probleme auf geclusterten Graphen, indem wir einen $30$-Qubit-Simulator verwenden, um die Variationsenergie eines $129$-Qubit-Problems zu bewerten und ein $62$-Problem durchzuführen -Qubit-Optimierung.

► BibTeX-Daten

► Referenzen

[1] https:/​/​github.com/​XanaduAI/​Randomized-Measurements-Circuit-Cutting (2022).
https:/​/​github.com/​XanaduAI/​Randomized-Measurements-Circuit-Cutting

[2] Scott Aaronson und Daniel Gottesman „Verbesserte Simulation von Stabilisatorschaltungen“ Phys. Rev. A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] J. Avron, Ofer Casper und Ilan Rozen, „Quantenvorteil und Rauschunterdrückung beim verteilten Quantencomputing“ 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 und 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 und AG Green, „Parallele Quantensimulation großer Systeme auf kleinen NISQ-Computern“ 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 und Nathan Killoran, „PennyLane: Automatische Differenzierung hybrider Quanten-klassischer Berechnungen“ (2018).
https://​/​doi.org/​10.48550/​ARXIV.1811.04968
https: / / arxiv.org/ abs / 1811.04968

[7] Sergey Bravyiand David Gosset „Verbesserte klassische Simulation von Quantenschaltkreisen dominiert von Clifford Gates“ Phys. Rev. Lett. 116, 250501 (2016).
https://doi.org/ 10.1103/PhysRevLett.116.250501

[8] Sergey Bravyi, David Gosset und Ramis Movassagh, „Klassische Algorithmen für Quantenmittelwerte“ Nature Physics 17, 337–341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Sergey Bravyi, Graeme Smith und 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 und Eugene Tang, „Hindernisse für die Variationsquantenoptimierung durch Symmetrieschutz“ 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 und Mark Howard, „Simulation of Quantum Circuits by Low-Rank Stabilizer Decompositions“ Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones „Das Finden guter ungefährer Vertex- und Kantenpartitionen ist NP-schwer“ 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 „Die Quantenkapazität von Kanälen mit willkürlich korreliertem Rauschen“ IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https: / / doi.org/ 10.1109 / TIT.2009.2039166

[14] Senrui Chen, Wenjun Yu, Pei Zeng und 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 und 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 und Joy A. Thomas „Elemente der Informationstheorie“ Wiley (2005).
https://​/​doi.org/​10.1002/​047174882x

[17] Vedran Dunjko, Yimin Ge und J. Ignacio Cirac, „Rechenbeschleunigungen mit kleinen Quantengeräten“ 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 und 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 und Sam Stanwyck, „NVIDIA/​cuQuantum: cuQuantum v22.05.0“ (2022).
https: / / doi.org/ 10.5281 / zenodo.6574510

[20] Robert M. Fano „Übertragung von Informationen: eine statistische Theorie der Kommunikation“ MIT Press (1966).

[21] Edward Farhi, David Gamarnik und Sam Gutmann, „Der 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 und Sam Gutmann, „Der Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst-Case-Beispiele“ (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https: / / arxiv.org/ abs / 2005.08747

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

[24] Edward Farhi, Jeffrey Goldstone und Sam Gutmann, „Ein 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 und 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 Gray und Stefanos Kourtis „Hyperoptimierte Tensornetzwerkkontraktion“ Quantum 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[28] M Guţă, J Kahn, R Kueng und JA Tropp, „Schnelle Zustandstomographie mit optimalen Fehlergrenzen“, 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 und 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 und 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 und 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 und John Preskill, „Vorhersage vieler Eigenschaften eines Quantensystems aus sehr wenigen Messungen“ 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 und E. Miles Stoudenmire, „Auf dem Weg zum Quantenmaschinenlernen mit Tensornetzwerken“, Quantum Science and Technology 4, 024001 (2019).
https: / / doi.org/ 10.1088 / 2058-9565 / aaea94

[34] Richard Kuengand David Gross „Qubit-Stabilisatorzustände sind komplexe projektive 3-Designs“ (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https: / / arxiv.org/ abs / 1510.02767

[35] Junde Li, Mahabubul Alam und 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 und 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 und Ashwin Nayak „Untere Grenzen für das Lernen von Quantenzuständen mit Einzelkopiemessungen“ (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 und 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 und Vedran Dunjko, „Hochdimensionales maschinelles Quantenlernen mit kleinen Quantencomputern“ (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.13739
https: / / arxiv.org/ abs / 2203.13739

[41] Matija Medvidović und Giuseppe Carleo „Klassische Variationssimulation des Quantum Approximate Optimization Algorithm“ npj Quantum Information 7 (2021).
https: / / doi.org/ 10.1038 / s41534-021-00440-z

[42] Kosuke Mitaraiand Keisuke Fujii „Konstruieren eines virtuellen Zwei-Qubit-Gatters durch Abtasten von Einzel-Qubit-Operationen“ New Journal of Physics 23, 023021 (2021).
https: / / doi.org/ 10.1088 / 1367-2630 / abd7bc

[43] Kosuke Mitaraiand Keisuke Fujii „Overhead für die Simulation eines nicht-lokalen Kanals mit lokalen Kanälen durch Quasiwahrscheinlichkeits-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 und 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 und Stephen D. Bartlett, „Schätzung der Ergebniswahrscheinlichkeiten von Quantenschaltkreisen unter Verwendung von Quasiwahrscheinlichkeiten“ Phys. Rev. Lett. 115, 070501 (2015).
https://doi.org/ 10.1103/PhysRevLett.115.070501

[46] Tianyi Peng, Aram W. Harrow, Maris Ozols und Xiaodi Wu, „Simulating Large Quantum Circuits on a Small Quantum Computer“, Physical Review Letters 125 (2020).
https://doi.org/ 10.1103/physrevlett.125.150504

[47] Michael A. Perlin, Zain H. Saleem, Martin Suchara und 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 und Jeremy L. O'Brien, „Ein Variationseigenwertlöser auf einem photonischen Quantenprozessor“ Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Christophe Piveteau und David Sutter „Rundstricken mit klassischer Kommunikation“ (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 und Martin Suchara, „Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing“ (2021).
arXiv: 2107.07532

[51] Igal Sasonand 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 und Nathan Wiebe, „Circuit-centric Quantenklassifizierer“ Physical Review A 101 (2020).
https: / / doi.org/ 10.1103 / physreva.101.032308

[53] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac und Nathan Killoran, „Evaluating Analytic gradients onquantum hardware“ Phys. Rev. A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[54] Hayk Shoukourian, Torsten Wilde, Axel Auweter und Arndt Bode, „Vorhersage des Energie- und Stromverbrauchs von stark und schwach skalierenden HPC-Anwendungen“ Supercomputing Frontiers and Innovations 1, 20–41 (2014).
https://​/​doi.org/​10.14529/​jsfi140202

[55] Wei Tangand Margaret Martonosi „ScaleQC: Ein skalierbares Framework für hybride Berechnungen auf Quanten- und klassischen Prozessoren“ (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.00933
https: / / arxiv.org/ abs / 2207.00933

[56] Ewout Van Den Berg „Eine einfache Methode zum Abtasten zufälliger Clifford-Operatoren“ 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 und Eleanor G. Rieffel, „Quantennäherungs-Optimierungsalgorithmus für MaxCut: Eine fermionische Ansicht“ Phys. Rev. A 97, 022304 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022304

[58] John Watrous „Die Theorie der Quanteninformation“ Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[59] Zak Webb „Die Clifford-Gruppe bildet ein einheitliches 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 und Leandro Aolita, „Circuit Connectivity Boosts by Quantum-Classical-Quantum Interfaces“ (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https: / / arxiv.org/ abs / 2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao und 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-Gruppen sind einheitliche 3-Designs“ Phys. Rev. A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Zitiert von

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

[2] Lukas Brenner, Christophe Piveteau und David Sutter, „Optimales Drahtschneiden mit klassischer Kommunikation“, arXiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen und Michael Foss-Feig, „Qubit-Reuse Compilation with Mid-Circuit Measurement and Reset“, arXiv: 2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge und 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 und Benjamin Weder, „Untersuchung der Wirkung von Schaltungsunterbrechungen in QAOA für das MaxCut-Problem bei NISQ-Geräten“, arXiv: 2302.01792, (2023).

[6] Ritajit Majumdar und Christopher J. Wood, „Error gemildertes Schneiden von Quantenschaltungen“, arXiv: 2211.13431, (2022).

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

[8] Gideon Uchehara, Tor M. Aamodt und Olivia Di Matteo, „Rotationsinspirierte Schaltungsschnittoptimierung“, arXiv: 2211.07358, (2022).

[9] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer und Andre Luckow, „Eine Leistungscharakterisierung von generativen Quantenmodellen“, arXiv: 2301.09363, (2023).

[10] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch und Juan Miguel Arrazola, „Ein praktischer Überblick über die Bildklassifizierung mit Variations-Tensor-Netzwerk-Quantenschaltkreisen“, arXiv: 2209.11058, (2022).

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 03:03:16 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-03-03 16:49:00).

Zeitstempel:

Mehr von Quantenjournal