Clifford Circuits Can Be Properly PAC Learned If And Only If $textsf{RP}=textsf{NP}$

Opublikowane ponownie przez Plato

Obserwuje: 0

Wydział Informatyki Uniwersytetu Teksasu w Austin

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

Abstrakcyjny

Czy mając zbiór danych obejmujący stany wejściowe, pomiary i prawdopodobieństwa, można skutecznie przewidzieć prawdopodobieństwa pomiaru związane z obwodem kwantowym? Najnowsza praca Caro i Datty [19] badał problem uczenia się obwodów kwantowych PAC w sensie teorii informacji, pozostawiając otwarte kwestie wydajności obliczeniowej. W szczególności jedną z kandydujących klas obwodów, dla których możliwy byłby skuteczny proces uczenia, były obwody Clifforda, ponieważ wiadomo, że odpowiedni zestaw stanów generowanych przez takie obwody, zwany stanami stabilizatora, jest skutecznie możliwy do nauczenia się za pomocą PAC [44] Tutaj podajemy wynik negatywny, pokazując, że prawidłowe uczenie się obwodów CNOT z błędem 1/poly($n$) jest trudne dla klasycznych uczniów, chyba że $textsf{RP = NP}$, co wyklucza możliwość silnych uczniów w ramach standardowej teorii złożoności założenia. Jako klasyczny analog i podzbiór obwodów Clifforda, w naturalny sposób prowadzi to do wyniku twardości również w przypadku obwodów Clifforda. Dodatkowo pokazujemy, że jeśli $textsf{RP = NP}$ to istniałyby wydajne, właściwe algorytmy uczenia się dla obwodów CNOT i Clifforda. Za pomocą podobnych argumentów odkrywamy również, że efektywny, właściwy moduł uczący się kwantowy dla takich obwodów istnieje wtedy i tylko wtedy, gdy $textsf{NP ⊆ RQP}$. Pozostawiamy otwartym problem twardości z powodu niewłaściwego uczenia się lub błędu $mathcal{O(1)}$ do przyszłej pracy.

► Dane BibTeX

@article{Liang2023cliffordcircuitscan, doi = {10.22331/q-2023-06-07-1036}, url = {https://doi.org/10.22331/q-2023-06-07-1036}, title = {Clifford {C}ircuits can be {P}roperly {PAC} {L}earned if and only if {$textsf{RP}=textsf{NP}$}}, author = {Liang, Daniel}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1036}, month = jun, year = {2023}
}

► Referencje

[1] Scotta Aaronsona. Możliwość uczenia się stanów kwantowych. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463 (2088): 3089–3114, 2007. 10.1098/rspa.2007.0113.
https: / / doi.org/ 10.1098 / rspa.2007.0113

[2] Scotta Aaronsona. Tomografia cieni stanów kwantowych. W materiałach z 50. dorocznego sympozjum ACM SIGACT na temat teorii informatyki, STOC 2018, s. 325–338, Nowy Jork, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355599. 10.1145/3188745.3188802.
https: / / doi.org/ 10.1145 / 3188745.3188802

[3] Scotta Aaronsona i Daniela Gottesmana. Ulepszona symulacja obwodów stabilizatora. Przegląd fizyczny A, 70 (5): 052328, 2004. 10.1103/physreva.70.052328.
https: / / doi.org/ 10.1103 / physreva.70.052328

[4] J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O'Brien, M. A. Nielsen, and A. G. White. Ancilla-assisted quantum process tomography. Phys. Rev. Lett., 90: 193601, May 2003. 10.1103/PhysRevLett.90.193601.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[5] Martin Anthony i Peter L. Bartlett. Uczenie funkcji poprzez interpolację. Kombinatoryka, prawdopodobieństwo i obliczenia, 9 (3): 213–225, 2000. 10.1017/S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam i Ronald de Wolf. Kolumna gościnna: Przegląd teorii uczenia się kwantowego. ACM SIGACT News, 48 (2): 41–67, 2017. 10.1145/3106700.3106710.
https: / / doi.org/ 10.1145 / 3106700.3106710

[7] Srinivasan Arunachalam and Ronald de Wolf. Optimal Quantum Sample Complexity of Learning Algorithms. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:31, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/LIPIcs.CCC.2017.25.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.25

[8] Srinivasan Arunachalam, Alex B Grilo i Henry Yuen. Uczenie się zapytań statystycznych kwantowych. Przedruk arXiv arXiv:2002.08240, 2020. https:///doi.org/10.48550/arXiv.2002.08240.
https:///doi.org/10.48550/arXiv.2002.08240
arXiv: 2002.08240

[9] Srinivasan Arunachalam, Alex Bredariol Grilo i Aarthi Sundaram. Twardość kwantowa uczenia się płytkich obwodów klasycznych. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[10] Charlesa H. Bennetta i Gillesa Brassarda. Kryptografia kwantowa: dystrybucja klucza publicznego i rzucanie monetą. Informatyka teoretyczna, 560: 7–11, grudzień 2014. ISSN 0304-3975. 10.1016/j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[11] Charlesa H. Bennetta i Stephena J. Wiesnera. Komunikacja za pomocą operatorów jedno- i dwucząstkowych na stanach Einsteina-Podolskiego-Rosena. Fiz. Rev. Lett., 69: 2881–2884, listopad 1992. 10.1103/PhysRevLett.69.2881.
https: / / doi.org/ 10.1103 / PhysRevLett.69.2881

[12] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres i William K. Wootters. Teleportacja nieznanego stanu kwantowego za pomocą podwójnych kanałów klasycznych i einsteina-podolskiego-rosena. Fiz. Rev. Lett., 70: 1895–1899, marzec 1993. 10.1103/PhysRevLett.70.1895.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[13] Ethan Bernstein i Umesh Vazirani. Teoria złożoności kwantowej. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[14] Avrima Bluma. Obliczeniowa trudność uczenia się. http:///www.cs.cmu.edu/ avrim/ML07/lect1007.pdf, 2015. URL http:///www.cs.cmu.edu/ avrim/ML07/lect1007 .pdf. Notatki z wykładów do CS 10-806 Podstawy uczenia maszynowego i nauki o danych.
http:///www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

[15] Avrim L. Blum i Ronald L. Rivest. Uczenie 3-węzłowej sieci neuronowej jest np-kompletne. Sieci neuronowe, 5 (1): 117–127, 1992. ISSN 0893-6080. https:///doi.org/10.1016/S0893-6080(05)80010-3.
https://doi.org/10.1016/S0893-6080(05)80010-3

[16] Anselm Blumer, A. Ehrenfeucht, David Haussler i Manfred K. Warmuth. Uczenie się i wymiar vapnika-chervonenkisa. J. ACM, 36 (4): 929–965, październik 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371

[17] Jonathan F. Buss, Gudmund S Frandsen i Jeffrey O Shallit. Złożoność obliczeniowa niektórych problemów algebry liniowej. Journal of Computer and System Sciences, 58 (3): 572–596, 1999. ISSN 0022-0000. https:///doi.org/10.1006/jcss.1998.1608.
https: / / doi.org/ 10.1006 / jcss.1998.1608

[18] Matthias C. Caro. Klasyfikacja binarna z przykładami klasycznymi i etykietami kwantowymi. Quantum Machine Intelligence, 3 (1), maj 2021. 10.1007/s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[19] Matthias C. Caro i Ishaun Datta. Pseudowymiar obwodów kwantowych. Quantum Machine Intelligence, 2 (2), listopad 2020 r. ISSN 2524-4914. 10.1007/s42484-020-00027-5.
https://doi.org/10.1007/s42484-020-00027-5

[20] Hao-Chung Cheng, Min-Hsiu Hsieh i Ping-Cheng Yeh. Możliwość uczenia się nieznanych pomiarów kwantowych. Informacje kwantowe. Comput., 16 (7–8): 615–656, maj 2016. ISSN 1533-7146. 10.26421/QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] Isaac L. Chuang i MA Nielsen. Recepta na eksperymentalne wyznaczanie dynamiki kwantowej czarnej skrzynki. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

[22] Kai-Min Chung i Han-Hsuan Lin. Przykładowe efektywne algorytmy uczenia kanałów kwantowych w modelu PAC i problem dyskryminacji stanu przybliżonego. W: Min-Hsiu Hsieh, redaktor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), tom 197 Leibniz International Proceedings in Informatics (LIPIcs), strony 3:1–3:22, Dagstuhl, Niemcy, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-198-6. 10.4230/LIPIcs.TQC.2021.3.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2021.3

[23] Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf's. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 815–830, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR. URL https://proceedings.mlr.press/v49/daniely16.html.
https:///proceedings.mlr.press/v49/daniely16.html

[24] Steven T. Flammia, David Gross, Yi-Kai Liu i Jens Eisert. Tomografia kwantowa metodą skompresowanego wykrywania: granice błędów, złożoność próbki i efektywne estymatory. New Journal of Physics, 14 (9): 095022, wrzesień 2012. 10.1088/1367-2630/14/9/095022.
https://doi.org/10.1088/1367-2630/14/9/095022

[25] Paul W. Goldberg i Mark R. Jerrum. Ograniczanie wymiaru vapnika-chervonenkisa klas pojęć sparametryzowanych liczbami rzeczywistymi. Uczenie maszynowe, 18: 131–148, 1995. 10.1007/BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[26] Daniela Gottesmana. Kody stabilizatorów i korekcja błędów kwantowych, 1997.

[27] Daniela Gottesmana. Reprezentacja komputerów kwantowych Heisenberga, 1998.

[28] Venkatesan Guruswami i Prasad Raghavendra. Trudność uczenia się półprzestrzeni z szumem. SIAM Journal on Computing, 39 (2): 742–765, 2009. 10.1137/070685798.
https: / / doi.org/ 10.1137 / 070685798

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu i Nengkun Yu. Próbka-optymalna tomografia stanów kwantowych. Transakcje IEEE dotyczące teorii informacji, strony 1–1, 2017. ISSN 1557-9654. 10.1109/tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

[30] Nika Haghtalab. Lecture 9: Hardness of Learning. https://www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf, 2020. URL https://www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf. Lecture notes for CS6781 - Theoretical Foundations of Machine Learning.
https:///www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf

[31] Hsin-Yuan Huang, Richard Kueng i John Preskill. Przewidywanie wielu właściwości układu kwantowego na podstawie bardzo niewielu pomiarów. Fizyka przyrody, październik 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[32] Jonathana Katza. Notatki o teorii złożoności Wykład 3. https:///www.cs.umd.edu/ jkatz/complexity/f11/lecture3.pdf, 2011. URL https:///www.cs.umd. edu/ jkatz/złożoność/f11/wykład3.pdf. Notatki z wykładów do CS 652 — Teoria złożoności.
https:///www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf

[33] Michael Kharitonov. Cryptographic hardness of distribution-specific learning. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, page 372–381, New York, NY, USA, 1993. Association for Computing Machinery. ISBN 0897915917. 10.1145/167088.167197.
https: / / doi.org/ 10.1145 / 167088.167197

[34] J. Kleinberga i E. Tardosa. Projekt algorytmu. Pearson Education, 2022. ISBN 9780132131087. URL https:///books.google.com/books?id=GORecgAACAAJ.
https:///books.google.com/books?id=GORecgAACAAJ

[35] Adama Klivansa. Model uczenia się PAC. https:///www.cs.utexas.edu/ klivans/f06lec2.pdf, 2005. URL https:///www.cs.utexas.edu/ klivans/f06lec2.pdf. Notatki z wykładów CS 395T Teoria uczenia się obliczeniowego.
https:///www.cs.utexas.edu/~klivans/f06lec2.pdf

[36] Roberta Koeniga i Johna A. Smolina. Jak skutecznie wybrać dowolny element grupy klifów. Journal of Mathematical Physics, 55 (12): 122202, grudzień 2014. ISSN 1089-7658. 10.1063/1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

[37] Richarda Kuenga i Davida Grossa. Stany stabilizatora Qubitu to złożone projekty 3-projekcyjne, 2015.

[38] Ching-Yi Lai i Hao-Chung Cheng. Nauka obwodów kwantowych niektórych bramek t. IEEE Transactions on Information Theory, strony 1–1, 2022. 10.1109/TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

[39] Richard A. Low. Uczenie się i testowanie algorytmów dla grupy klifforda. Fiz. Rev. A, 80: 052314, listopad 2009. 10.1103/PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] Ashley Montanaro. Uczenie się stanów stabilizatora na podstawie próbek Bella, 2017.

[41] Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 899–912, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341325. 10.1145/2897518.2897544.
https: / / doi.org/ 10.1145 / 2897518.2897544

[42] Ryan O'Donnell and John Wright. Efficient quantum tomography ii. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 962–974, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345286. 10.1145/3055399.3055454.
https: / / doi.org/ 10.1145 / 3055399.3055454

[43] Yihui Quek, Srinivasan Arunachalam i John A Smolin. Prywatne uczenie się oznacza stabilność kwantową. W: M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang i J. Wortman Vaughan, redaktorzy, Advances in Neural Information Processing Systems, tom 34, strony 20503–20515. Curran Associates, Inc., 2021. Adres URL https:///proceedings.neurips.cc/paper/2021/file/abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.
https://proceedings.neurips.cc/paper/2021/file/abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf

[44] Andrei Rocchetto. Stany stabilizatora można efektywnie uczyć się za pomocą PAC. Quantum Information & Computation, 18 (7-8): 541–552, 2018. 10.26421/qic18.7-8-1.
https: / / doi.org/ 10.26421 / qic18.7-8-1

[45] Peter W. Shor. Algorytmy czasu wielomianowego dla rozkładu na czynniki pierwsze i logarytmów dyskretnych na komputerze kwantowym. Przegląd SIAM, 41 (2): 303–332, 1999. 10.1137/S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

[46] Daniela R. Simona. O potędze obliczeń kwantowych. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

[47] Leslie G Valiant. Teoria tego, czego można się nauczyć. Komunikaty ACM, 27 (11): 1134–1142, 1984. 10.1145/1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972

[48] Ewouta Van Den Berga. Prosta metoda próbkowania losowych operatorów klifu. W 2021 Międzynarodowa konferencja IEEE na temat obliczeń i inżynierii kwantowej (QCE), strony 54–59, 2021. 10.1109/QCE52317.2021.00021.
https: // doi.org/ 10.1109 / QCE52317.2021.00021

[49] Mithuna Yoganathan. Warunek, w którym klasyczna symulowalność oznacza efektywną zdolność uczenia się stanu, 2019.

[50] Huangjuna Zhu. Grupy klifów wielokubitowych to jednolite 3-projekty. Fiz. Rev. A, 96: 062336, grudzień 2017. 10.1103/PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Cytowany przez

[1] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma, "Learning efficient decoders for quasi-chaotic quantum scramblers", arXiv: 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt i Theodore J. Yoder, „Optymalne algorytmy uczenia się kwantowych stanów fazowych”, arXiv: 2208.07851, (2022).

[3] Anurag Anshu and Srinivasan Arunachalam, "A survey on the complexity of learning quantum states", arXiv: 2305.20069, (2023).

Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2023-06-07 22:21:42). 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-06-07 22:21:40).

Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.

Dystrybucja treści i PR oparta na SEO. Uzyskaj wzmocnienie już dziś.
EVM Finanse. Ujednolicony interfejs dla zdecentralizowanych finansów. Dostęp tutaj.
Quantum Media Group. Wzmocnienie IR/PR. Dostęp tutaj.
PlatoAiStream. Analiza danych Web3. Wiedza wzmocniona. Dostęp tutaj.
Źródło: https://quantum-journal.org/papers/q-2023-06-07-1036/

Znak czasu: 7 czerwca 2023 r.

Znak czasu: Jan 11, 2024

Obwody Clifforda mogą być poprawnie nauczone PAC wtedy i tylko wtedy, gdy $textsf{RP}=textsf{NP}$

Opublikowane ponownie przez Plato

Abstrakcyjny

► Dane BibTeX

► Referencje

Cytowany przez

Więcej z Dziennik kwantowy

Energooszczędny kwantowy pomiar nieniszczący z interfejsem spin-foton

sezonowy sen uległości

Transmisja informacji za pomocą kanałów ciągłego wymazywania kwantowego

Metoda weryfikacji „dziel i zwyciężaj” dla zaszumionych obliczeń kwantowych w skali pośredniej

Niemal deterministyczne hybrydowe generowanie dowolnych stanów grafów fotonicznych przy użyciu pojedynczego emitera kwantowego i optyki liniowej

Powstające projekty stanów kwantowych i biunitarność w dynamice obwodów dual-uniitarnych

Kwantyfikacja zasobów oparta na odległości dla zestawów pomiarów kwantowych

Korelacje ograniczone pomiarami złożonymi

Pochylone paradoksy Hardy'ego do ekstrakcji losowości niezależnej od urządzenia

Procesory kwantowe Fermion-qudit do symulacji teorii cechowania sieciowego z materią

O nas

Wyszukiwanie pionowe i AI

Platforma

Pozostań w kontakcie

Konto