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

Heruitgegeven door Plato

volgers: 0

Afdeling Computerwetenschappen, Universiteit van Texas in Austin

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

Is het, gegeven een dataset van invoertoestanden, metingen en waarschijnlijkheden, mogelijk om op efficiënte wijze de meetkansen te voorspellen die verband houden met een kwantumcircuit? Recent werk van Caro en Datta [19] bestudeerde het probleem van het door PAC leren van kwantumcircuits in informatietheoretische zin, waarbij vragen over de rekenefficiëntie openbleven. In het bijzonder was een kandidaat-klasse van circuits waarvoor een efficiënte leerling mogelijk zou kunnen zijn die van Clifford-circuits, aangezien bekend is dat de overeenkomstige reeks toestanden die door dergelijke circuits worden gegenereerd, de zogenaamde stabilisatortoestanden, efficiënt PAC-leerbaar zijn.44]. Hier geven we een negatief resultaat, waaruit blijkt dat het goed leren van CNOT-circuits met een 1/ poly($n$) fout moeilijk is voor klassieke leerlingen, tenzij $textsf{RP = NP}$, waardoor de mogelijkheid van sterke leerlingen onder de standaard complexiteitstheoretische theorie wordt uitgesloten. aannames. Als de klassieke analoog en subset van Clifford-circuits leidt dit uiteraard ook tot een hardheidsresultaat voor Clifford-circuits. Bovendien laten we zien dat als $textsf{RP = NP}$ er efficiënte, goede leeralgoritmen zouden bestaan voor CNOT- en Clifford-circuits. Met vergelijkbare argumenten ontdekken we ook dat er een efficiënte kwantumleerling voor dergelijke circuits bestaat als en slechts als $textsf{NP ⊆ RQP}$. We laten het probleem van de hardheid van onjuist leren of $mathcal{O(1)}$-fouten open voor toekomstig werk.

► BibTeX-gegevens

@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}
}

► Referenties

[1] Scott Aaronson. De leerbaarheid van kwantumtoestanden. Proceedings of the Royal Society A: Wiskundige, Fysische en Technische Wetenschappen, 463 (2088): 3089–3114, 2007. 10.1098/rspa.2007.0113.
https: / / doi.org/ 10.1098 / rspa.2007.0113

[2] Scott Aaronson. Schaduwtomografie van kwantumtoestanden. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pagina 325–338, New York, NY, VS, 2018. Association for Computing Machinery. ISBN 9781450355599. 10.1145/3188745.3188802.
https: / / doi.org/ 10.1145 / 3188745.3188802

[3] Scott Aaronson en Daniel Gottesman. Verbeterde simulatie van stabilisatorcircuits. Fysiek overzicht A, 70 (5): 052328, 2004. 10.1103/physreva.70.052328.
https: / / doi.org/ 10.1103 / physreva.70.052328

[4] JB Altepeter, D. Branning, E. Jeffrey, TC Wei, PG Kwiat, RT Thew, JL O'Brien, MA Nielsen en AG White. Ancilla-ondersteunde kwantumprocestomografie. Fys. Rev. Lett., 90: 193601, mei 2003. 10.1103/PhysRevLett.90.193601.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[5] Martin Anthony en Peter L. Bartlett. Functie leren door interpolatie. Combinatoriek, waarschijnlijkheid en computergebruik, 9 (3): 213–225, 2000. 10.1017/S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam en Ronald de Wolf. Gastcolumn: Een overzicht van de kwantumleertheorie. 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 en Henry Yuen. Kwantumstatistisch leren van query's. arXiv preprint 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 en Aarthi Sundaram. Kwantumhardheid van het leren van ondiepe klassieke circuits. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[10] Charles H. Bennett en Gilles Brassard. Kwantumcryptografie: verspreiding van openbare sleutels en het opgooien van munten. Theoretische informatica, 560: 7–11, december 2014. ISSN 0304-3975. 10.1016/j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[11] Charles H. Bennett en Stephen J. Wiesner. Communicatie via operatoren met één en twee deeltjes over de staten van Einstein-Podolsky-Rosen. Fys. Rev. Lett., 69: 2881–2884, november 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 en William K. Wootters. Teleporteren van een onbekende kwantumtoestand via dubbele klassieke en Einstein-Podolsky-Rosen-kanalen. Fys. Rev. Lett., 70: 1895–1899, maart 1993. 10.1103/PhysRevLett.70.1895.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[13] Ethan Bernstein en Umesh Vazirani. Kwantumcomplexiteitstheorie. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[14] Avrim Blum. Computationele moeilijkheid van leren. http:///www.cs.cmu.edu/ avrim/ML07/lect1007.pdf, 2015. URL http:///www.cs.cmu.edu/ avrim/ML07/lect1007 .pdf. Lezingsaantekeningen voor CS 10-806 Grondslagen van machinaal leren en datawetenschap.
http:///www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

[15] Avrim L. Blum en Ronald L. Rivest. Het trainen van een neuraal netwerk met 3 knooppunten is np-compleet. Neurale netwerken, 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 en Manfred K. Warmuth. Leerbaarheid en de vapnik-chervonenkis-dimensie. J. ACM, 36 (4): 929–965, oktober 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371

[17] Jonathan F Buss, Gudmund S Frandsen en Jeffrey O Shallit. De computationele complexiteit van enkele problemen van lineaire algebra. 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. Binaire classificatie met klassieke instanties en kwantumlabels. Quantum Machine Intelligence, 3 (1), mei 2021. 10.1007/s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[19] Matthias C. Caro en Ishaun Datta. Pseudo-dimensie van kwantumcircuits. Quantum Machine Intelligence, 2 (2), november 2020. 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 en Ping-Cheng Yeh. De leerbaarheid van onbekende kwantummetingen. Kwantuminformatie. Comput., 16 (7–8): 615–656, mei 2016. ISSN 1533-7146. 10.26421/QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] Isaac L. Chuang en MA Nielsen. Voorschrift voor experimentele bepaling van de dynamiek van een kwantumzwarte doos. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

[22] Kai-Min Chung en Han-Hsuan Lin. Voorbeeld van efficiënte algoritmen voor het leren van kwantumkanalen in het PAC-model en het geschatte staatsdiscriminatieprobleem. In Min-Hsiu Hsieh, redacteur, 16e conferentie over de theorie van kwantumcomputers, communicatie en cryptografie (TQC 2021), deel 197 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 3:1–3:22, Dagstuhl, Duitsland, 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 en Jens Eisert. Kwantumtomografie via gecomprimeerde detectie: foutgrenzen, steekproefcomplexiteit en efficiënte schatters. New Journal of Physics, 14 (9): 095022, september 2012. 10.1088/1367-2630/14/9/095022.
https://doi.org/10.1088/1367-2630/14/9/095022

[25] Paul W. Goldberg en Mark R. Jerrum. Het begrenzen van de vapnik-chervonenkis-dimensie van conceptklassen die zijn geparametreerd door reële getallen. Machine Learning, 18: 131–148, 1995. 10.1007/BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[26] Daniël Gottesman. Stabilisatorcodes en kwantumfoutcorrectie, 1997.

[27] Daniël Gottesman. De Heisenberg-weergave van kwantumcomputers, 1998.

[28] Venkatesan Guruswami en Prasad Raghavendra. Moeilijkheid bij het leren van halfruimten met ruis. 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 en Nengkun Yu. Voorbeeld-optimale tomografie van kwantumtoestanden. IEEE Transactions on Information Theory, pagina's 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 en John Preskill. Het voorspellen van veel eigenschappen van een kwantumsysteem op basis van zeer weinig metingen. Natuurfysica, oktober 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[32] Jonathan Katz. Opmerkingen over complexiteitstheorie Lezing 3. https://www.cs.umd.edu/ jkatz/complexity/f11/lecture3.pdf, 2011. URL https:///www.cs.umd. edu/ jkatz/complexity/f11/lecture3.pdf. Lezingsaantekeningen bij CS 652 — Complexiteitstheorie.
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. Kleinberg en E. Tardos. Algoritme ontwerp. Pearson Education, 2022. ISBN 9780132131087. URL https:///books.google.com/books?id=GORecgAACAAJ.
https:///books.google.com/books?id=GORecgAACAAAJ

[35] Adam Klivans. Het PAC-leermodel. https:///www.cs.utexas.edu/ klivans/f06lec2.pdf, 2005. URL https:///www.cs.utexas.edu/ klivans/f06lec2.pdf. Lezingsaantekeningen voor CS 395T Computationele leertheorie.
https:///www.cs.utexas.edu/~klivans/f06lec2.pdf

[36] Robert Koenig en John A. Smolin. Hoe u efficiënt een willekeurig clifford-groepselement selecteert. Journal of Mathematical Physics, 55 (12): 122202, december 2014. ISSN 1089-7658. 10.1063/1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

[37] Richard Kueng en David Gross. Qubit-stabilisatortoestanden zijn complexe projectieve 3-ontwerpen, 2015.

[38] Ching-Yi Lai en Hao-Chung Cheng. Kwantumcircuits van sommige t-poorten leren. IEEE Transactions on Information Theory, pagina's 1–1, 2022. 10.1109/TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

[39] Richard A. Laag. Algoritmen leren en testen voor de Clifford-groep. Fys. Rev. A, 80: 052314, november 2009. 10.1103/PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] Ashley Montanaro. Stabilisatietoestanden leren door Bell-sampling, 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 en John A Smolin. Privé-leren impliceert kwantumstabiliteit. In M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang en J. Wortman Vaughan, redacteuren, Advances in Neural Information Processing Systems, deel 34, pagina's 20503–20515. Curran Associates, Inc., 2021. URL https:///proceedings.neurips.cc/paper/2021/file/abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.
https://proceedings.neurips.cc/paper/2021/file/abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf

[44] Andrea Rocchetto. Stabilisatortoestanden zijn efficiënt PAC-leerbaar. 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. Polynomiale tijdalgoritmen voor priemfactorisatie en discrete logaritmen op een kwantumcomputer. SIAM Review, 41 (2): 303–332, 1999. 10.1137/S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

[46] Daniel R. Simon. Over de kracht van kwantumberekeningen. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

[47] Leslie G Valiant. Een theorie van het leerbare. Mededelingen van de ACM, 27 (11): 1134–1142, 1984. 10.1145/1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972

[48] Ewout Van Den Berg. Een eenvoudige methode voor het bemonsteren van willekeurige clifford-operatoren. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pagina's 54–59, 2021. 10.1109/QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[49] Mithuna Yoganathan. Een voorwaarde waaronder klassieke simuleerbaarheid een efficiënte staatsleerbaarheid impliceert, 2019.

[50] Huangjun Zhu. Multiqubit clifford-groepen zijn unitaire 3-ontwerpen. Fys. Rev. A, 96: 062336, december 2017. 10.1103/PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Geciteerd door

[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 en Theodore J. Yoder, "Optimale algoritmen voor het leren van kwantumfasetoestanden", arXiv: 2208.07851, (2022).

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

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2023-06-07 22:21:42). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On Crossref's geciteerde dienst er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2023-06-07 22:21:40).

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.

Door SEO aangedreven content en PR-distributie. Word vandaag nog versterkt.
EVM Financiën. Uniforme interface voor gedecentraliseerde financiën. Toegang hier.
Quantum Media Groep. IR/PR versterkt. Toegang hier.
PlatoAiStream. Web3 gegevensintelligentie. Kennis versterkt. Toegang hier.
Bron: https://quantum-journal.org/papers/q-2023-06-07-1036/

Tijdstempel: 7 June 2023

Tijdstempel: Jan 11, 2024

Clifford-circuits kunnen correct PAC worden geleerd als en alleen als $textsf{RP}=textsf{NP}$

Heruitgegeven door Plato

Abstract

► BibTeX-gegevens

► Referenties

Geciteerd door

Meer van Quantum Journaal

Energie-efficiënte kwantum-niet-sloopmeting met een spin-foton-interface

Seizoensinzending sluimer

Informatieoverdracht met continu variabele kwantumverwijderingskanalen

Verdeel-en-heers verificatiemethode voor lawaaierige kwantumberekening op middellange schaal

Bijna deterministische hybride generatie van willekeurige fotonische grafiektoestanden met behulp van een enkele kwantumzender en lineaire optica

Opkomende kwantumtoestandsontwerpen en biunitariteit in dual-unitaire circuitdynamica

Op afstand gebaseerde bronkwantificering voor sets kwantummetingen

Correlaties beperkt door samengestelde metingen

Tilted Hardy-paradoxen voor apparaatonafhankelijke willekeurextractie

Fermion-qudit-kwantumprocessors voor het simuleren van roosterijktheorieën met materie

Over Ons

Verticaal zoeken & Ai

Platform

Blijf verbonden

Account