Szybkie cięcie obwodów kwantowych z losowymi pomiarami

Szybkie cięcie obwodów kwantowych z losowymi pomiarami

Węzeł źródłowy: 1990460

Angusa Lowe'a1,2, Matija Medvidović1,3,4, Anthony'ego Hayesa1, Lee J. O'Riordan1, Thomasa R. Bromleya1, Juana Miguela Arrazoli1i Nathana Killorana1

1Xanadu, Toronto, ON, M5G 2C8, Kanada
2Centrum Fizyki Teoretycznej, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
3Centrum Obliczeniowej Fizyki Kwantowej, Flatiron Institute, Nowy Jork, NY, 10010, USA
4Wydział Fizyki Uniwersytetu Columbia, Nowy Jork, 10027, USA

Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.

Abstrakcyjny

Proponujemy nową metodę rozszerzenia rozmiaru obliczeń kwantowych poza liczbę kubitów fizycznych dostępnych na jednym urządzeniu. Osiąga się to poprzez losowe wstawianie kanałów pomiaru i przygotowania, aby wyrazić stan wyjściowy dużego obwodu jako stan rozdzielny w różnych urządzeniach. Nasza metoda wykorzystuje losowe pomiary, co daje narzut próbki, który wynosi $widetilde{O}(4^k / varepsilon ^2)$, gdzie $varepsilon $ to dokładność obliczeń, a $k$ to liczba równoległych przewodów, które są „wyciąć”, aby uzyskać mniejsze podobwody. Pokazujemy również informacyjno-teoretyczną dolną granicę $Omega(2^k / varepsilon^2)$ dla dowolnej porównywalnej procedury. Używamy naszych technik, aby pokazać, że obwody w Quantum Approximate Optimization Algorithm (QAOA) z $p$ splątanymi warstwami mogą być symulowane przez obwody na ułamku oryginalnej liczby kubitów z narzutem, który wynosi około $2^{O(pkappa) }$, gdzie $kappa$ jest wielkością znanego zbalansowanego separatora wierzchołków grafu, który koduje problem optymalizacyjny. Uzyskujemy liczbowe dowody praktycznego przyspieszenia, stosując naszą metodę zastosowaną do QAOA, w porównaniu z poprzednimi pracami. Na koniec badamy praktyczną wykonalność zastosowania procedury cięcia obwodów do wielkoskalowych problemów QAOA na grafach klastrowych za pomocą symulatora kubitów za 30 USD w celu oceny energii wariacyjnej problemu kubitowego za 129 USD, a także przeprowadzania 62 USD -optymalizacja kubitów.

► Dane BibTeX

► Referencje

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

[2] Scott Aaronson i Daniel Gottesman „Ulepszona symulacja obwodów stabilizatora” Phys. Wersja A 70, 052328 (2004).
https: / / doi.org/ 10.1103 / PhysRevA.70.052328

[3] J. Avron, Ofer Casper i Ilan Rozen, „Przewaga kwantowa i redukcja szumów w rozproszonych obliczeniach kwantowych” Phys. Wersja 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 i Martin Suchara, „Quantum Divide and Compute: Hardware Demonstrations and Noisy Simulations” Doroczne sympozjum IEEE Computer Society 2020 na temat VLSI (ISVLSI) 138–140 (2020).
https://​/​doi.org/​10.1109/​ISVLSI49217.2020.00034

[5] F. Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann i AG Green, „Równoległa symulacja kwantowa dużych systemów na małych komputerach 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 i Nathan Killoran, „PennyLane: Automatyczne różnicowanie hybrydowych obliczeń kwantowo-klasycznych” (2018).
https://​/​doi.org/​10.48550/​ARXIV.1811.04968
https: / / arxiv.org/ abs / 1811.04968

[7] Sergey Bravyiand David Gosset „Ulepszona klasyczna symulacja obwodów kwantowych zdominowanych przez Clifforda Gatesa” Phys. Wielebny Lett. 116, 250501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.116.250501

[8] Sergey Bravyi, David Gosset i Ramis Movassagh, „Klasyczne algorytmy kwantowych wartości średnich” Nature Physics 17, 337–341 (2021).
https:/​/​doi.org/​10.1038/​s41567-020-01109-8

[9] Sergey Bravyi, Graeme Smith i John A. Smolin, „Trading Classical and Quantum Computational Resources” Phys. Wersja X 6, 021043 (2016).
https: / / doi.org/ 10.1103 / PhysRevX.6.021043

[10] Sergey Bravyi, Alexander Kliesch, Robert Koenig i Eugene Tang, „Przeszkody w wariacyjnej optymalizacji kwantowej wynikającej z ochrony symetrii” Phys. Wielebny Lett. 125, 260505 (2020).
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505

[11] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset i Mark Howard, „Symulacja obwodów kwantowych przez rozkłady stabilizatorów niskiego rzędu” Quantum 3, 181 (2019).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[12] Thang Nguyen Buiand Curt Jones „Znajdowanie dobrych przybliżonych partycji wierzchołków i krawędzi jest NP-trudne” 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 „Kwantowa pojemność kanałów z dowolnie skorelowanym szumem” IEEE Transactions on Information Theory 56, 1447–1460 (2010).
https: / / doi.org/ 10.1109 / TIT.2009.2039166

[14] Senrui Chen, Wenjun Yu, Pei Zeng i 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 i 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 i Joy A. Thomas „Elementy teorii informacji” Wiley (2005).
https://​/​doi.org/​10.1002/​047174882x

[17] Vedran Dunjko, Yimin Ge i J. Ignacio Cirac, „Przyspieszenia obliczeniowe przy użyciu małych urządzeń kwantowych” Phys. Wielebny 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 i Peter Zoller, „Zestaw narzędzi do pomiarów losowych” (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.11374
https: / / arxiv.org/ abs / 2203.11374

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

[20] Robert M. Fano „Transmisja informacji: statystyczna teoria komunikacji” MIT Press (1966).

[21] Edward Farhi, David Gamarnik i Sam Gutmann, „Algorytm przybliżonej optymalizacji kwantowej musi zobaczyć cały wykres: typowy przypadek” (2020).
https://​/​doi.org/​10.48550/​ARXIV.2004.09002
https: / / arxiv.org/ abs / 2004.09002

[22] Edward Farhi, David Gamarnik i Sam Gutmann, „Algorytm przybliżonej optymalizacji kwantowej musi zobaczyć cały wykres: przykłady najgorszych przypadków” (2020).
https://​/​doi.org/​10.48550/​ARXIV.2005.08747
https: / / arxiv.org/ abs / 2005.08747

[23] Edward Farhi, Jeffrey Goldstone i 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 i 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 „Supremacja kwantowa dzięki algorytmowi przybliżonej optymalizacji kwantowej” (2016).
https://​/​doi.org/​10.48550/​ARXIV.1602.07674
https: / / arxiv.org/ abs / 1602.07674

[26] Uriel Feige, MohammadTaghi Hajiaghayi i 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 i Stefanos Kourtis „Hyper-zoptymalizowany skurcz sieci tensorowej” Quantum 5, 410 (2021).
https:/​/​doi.org/​10.22331/​q-2021-03-15-410

[28] M Guţă, J Kahn, R Kueng i JA Tropp, „Tomografia szybkiego stanu z optymalnymi granicami błędów” 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 i 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 i 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 i Mary Beth Ruskai, „Entanglement Breaking Channels” Recenzje w Mathematical Physics 15, 629–641 (2003).
https: / / doi.org/ 10.1142 / S0129055X03001709

[32] Hsin-Yuan Huang, Richard Kueng i John Preskill, „Przewidywanie wielu właściwości układu kwantowego na podstawie bardzo niewielu pomiarów” 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 i E Miles Stoudenmire, „Ku kwantowemu uczeniu maszynowemu z sieciami tensorowymi” Quantum Science and Technology 4, 024001 (2019).
https: / / doi.org/ 10.1088 / 2058-9565 / aaea94

[34] Richard Kuengand David Gross „Stany stabilizatora Qubit to złożone projekty rzutowe 3” (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02767
https: / / arxiv.org/ abs / 1510.02767

[35] Junde Li, Mahabubul Alam i 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 i 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 i Ashwin Nayak „Dolne granice uczenia się stanów kwantowych za pomocą pomiarów pojedynczych kopii” (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 i Yuri Alexeev, „Progi częstotliwości próbkowania dla przewagi kwantowej algorytmu przybliżonej optymalizacji kwantowej” (2022).
https://​/​doi.org/​10.48550/​ARXIV.2206.03579
https: / / arxiv.org/ abs / 2206.03579

[39] Igor L. Markovand Yaoyun Shi „Symulowanie obliczeń kwantowych przez kontraktowanie sieci tensorowych” SIAM Journal on Computing 38, 963–981 (2008).
https: / / doi.org/ 10.1137 / 050644756

[40] Simon C. Marshall, Casper Gyurik i 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ć i Giuseppe Carleo „Klasyczna symulacja wariacyjna algorytmu przybliżonej optymalizacji kwantowej” npj Quantum Information 7 (2021).
https: / / doi.org/ 10.1038 / s41534-021-00440-z

[42] Kosuke Mitaraiand Keisuke Fujii „Konstruowanie wirtualnej bramki z dwoma kubitami poprzez próbkowanie operacji na jednym kubicie” New Journal of Physics 23, 023021 (2021).
https: / / doi.org/ 10.1088 / 1367-2630 / abd7bc

[43] Kosuke Mitaraiand Keisuke Fujii „Opłata za symulację kanału nielokalnego z kanałami lokalnymi przez próbkowanie quasi-prawdopodobieństwa” 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 i 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 i Stephen D. Bartlett, „Oszacowywanie prawdopodobieństwa wyników obwodów kwantowych przy użyciu quasiprawopodobieństw” Phys. Wielebny Lett. 115, 070501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.115.070501

[46] Tianyi Peng, Aram W. Harrow, Maris Ozols i Xiaodi Wu, „Symulowanie dużych obwodów kwantowych na małym komputerze kwantowym” Physical Review Letters 125 (2020).
https: / / doi.org/ 10.1103 / physrevlett.125.150504

[47] Michael A. Perlin, Zain H. Saleem, Martin Suchara i James C. Osborn, „Cięcie obwodów kwantowych za pomocą tomografii o największej wiarygodności” 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 i Jeremy L. O'Brien, „Wariacyjne narzędzie do rozwiązywania wartości własnych fotonicznego procesora kwantowego” Nature Communications 5 (2014).
https: / / doi.org/ 10.1038 / ncomms5213

[49] Christophe Piveteau i David Sutter „Dzierganie obwodowe z klasyczną komunikacją” (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 i 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 i Nathan Wiebe, „Obwodocentryczne klasyfikatory kwantowe” Physical Review A 101 (2020).
https: / / doi.org/ 10.1103 / physreva.101.032308

[53] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac i Nathan Killoran, „Ocena gradientów analitycznych na sprzęcie kwantowym” Phys. Rev. A 99, 032331 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.99.032331

[54] Hayk Shoukourian, Torsten Wilde, Axel Auweter i Arndt Bode, „Przewidywanie zużycia energii i mocy przez aplikacje HPC o silnym i słabym skalowaniu”, Supercomputing Frontiers and Innovations 1, 20–41 (2014).
https://​/​doi.org/​10.14529/​jsfi140202

[55] Wei Tangand Margaret Martonosi „ScaleQC: skalowalna struktura obliczeń hybrydowych na procesorach kwantowych i klasycznych” (2022).
https://​/​doi.org/​10.48550/​ARXIV.2207.00933
https: / / arxiv.org/ abs / 2207.00933

[56] Ewout Van Den Berg „Prosta metoda próbkowania losowych operatorów Clifforda” 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 i Eleanor G. Rieffel, „Algorytm przybliżonej optymalizacji kwantowej dla MaxCut: widok fermionowy” Phys. Wersja A 97, 022304 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.97.022304

[58] John Watrous „Teoria informacji kwantowej” Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142

[59] Zak Webb „Grupa Clifforda tworzy jednolity 3-projekt” (2015).
https://​/​doi.org/​10.48550/​ARXIV.1510.02769
https: / / arxiv.org/ abs / 1510.02769

[60] Roeland Wiersema, Leonardo Guerini, Juan Felipe Carrasquilla i Leandro Aolita, „Łączność obwodów zwiększa się dzięki interfejsom kwantowo-klasyczno-kwantowym” (2022).
https://​/​doi.org/​10.48550/​ARXIV.2203.04984
https: / / arxiv.org/ abs / 2203.04984

[61] Xiao Yuan, Jinzhao Sun, Junyu Liu, Qi Zhao i You Zhou, „Symulacja kwantowa z hybrydowymi sieciami tensorowymi” Phys. Wielebny Lett. 127, 040501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.040501

[62] Huangjun Zhu „Wielokubitowe grupy Clifforda są jednolitymi 3-konstrukcjami” Phys. Rev. A 96, 062336 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Cytowany przez

[1] Lirandë Pira i Chris Ferrie, „Zaproszenie do rozproszonych kwantowych sieci neuronowych”, arXiv: 2211.07056, (2022).

[2] Lukas Brenner, Christophe Piveteau i David Sutter, „Optymalne cięcie drutu z klasyczną komunikacją”, arXiv: 2302.03366, (2023).

[3] Matthew DeCross, Eli Chertkov, Megan Kohagen i Michael Foss-Feig, „Kompilacja Qubit-reuse with mid-circuit measurement and reset”, arXiv: 2210.08039, (2022).

[4] Christian Ufrecht, Maniraman Periyasamy, Sebastian Rietsch, Daniel D. Scherer, Axel Plinge i Christopher Mutschler, „Wycinanie wielokontrolnych bramek kwantowych za pomocą rachunku ZX”, arXiv: 2302.00387, (2023).

[5] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger i Benjamin Weder, „Badanie wpływu cięcia obwodu w QAOA na problem MaxCut na urządzeniach NISQ”, arXiv: 2302.01792, (2023).

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

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

[8] Gideon Uchehara, Tor M. Aamodt i Olivia Di Matteo, „Optymalizacja cięcia obwodu inspirowana rotacją”, arXiv: 2211.07358, (2022).

[9] Carlos A. Riofrío, Oliver Mitevski, Caitlin Jones, Florian Krellner, Aleksandar Vučković, Joseph Doetsch, Johannes Klepsch, Thomas Ehmer i Andre Luckow, „Charakterystyka wydajności kwantowych modeli generatywnych”, arXiv: 2301.09363, (2023).

[10] Diego Guala, Shaoming Zhang, Esther Cruz, Carlos A. Riofrío, Johannes Klepsch i Juan Miguel Arrazola, „Praktyczny przegląd klasyfikacji obrazów z wariacyjnymi obwodami kwantowymi sieci tensorowej”, arXiv: 2209.11058, (2022).

Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2023-03-03 16:49:02). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.

On Serwis cytowany przez Crossref nie znaleziono danych na temat cytowania prac (ostatnia próba 2023-03-03 16:49:00).

Znak czasu:

Więcej z Dziennik kwantowy