Cliffordin piirit voidaan oppia kunnolla PAC:na jos ja vain jos $textsf{RP}=textsf{NP}$

Julkaissut Platon

seuraajia: 0

Tietojenkäsittelytieteen laitos, Texasin yliopisto Austinissa

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Onko mahdollista ennustaa tehokkaasti kvanttipiiriin liittyvät mittaustodennäköisyydet, kun otetaan huomioon syötetilojen, mittausten ja todennäköisyyksien tietojoukko? Caron ja Dattan viimeaikainen työ [19] tutki PAC-oppimisen kvanttipiirien ongelmaa informaatioteoreettisessa mielessä jättäen avoimia kysymyksiä laskennan tehokkuudesta. Erityisesti yksi ehdokas piirien luokka, jolle tehokas oppija olisi voinut olla mahdollista, oli Clifford-piirit, koska tällaisten piirien generoimat vastaavat tilat, joita kutsutaan stabilointitiloiksi, tiedetään olevan tehokkaasti PAC-opetettavissa [44]. Tässä annamme negatiivisen tuloksen, joka osoittaa, että CNOT-piirien asianmukainen oppiminen 1/ poly($n$) -virheellä on vaikeaa klassisille oppijoille, ellei $textsf{RP = NP}$, mikä sulkee pois vahvojen oppijoiden mahdollisuuden standardin monimutkaisuusteoreettisen mukaan. oletuksia. Klassisena Clifford-piirien analogina ja osajoukkona tämä johtaa luonnollisesti myös Clifford-piirien kovuustulokseen. Lisäksi näytämme, että jos $textsf{RP = NP}$, niin CNOT- ja Clifford-piireille olisi olemassa tehokkaat oikeat oppimisalgoritmit. Samanlaisilla argumenteilla huomaamme myös, että tehokas oikea kvanttioppija tällaisille piireille on olemassa, jos ja vain jos $textsf{NP ⊆ RQP}$. Jätämme avoimeksi virheellisen oppimisen kovuuden ongelman tai $mathcal{O(1)}$ virheen tulevaan työhön.

► BibTeX-tiedot

@article{Liang2023cliffordcircuitscan, doi = {10.22331/q-2023-06-07-1036}, url = {https://doi.org/10.22331/q-2023-06-07-1036}, otsikko { = {Clifford C}piirit voidaan {P}oikeasti {PAC} {L}ansaita jos ja vain, jos {$textsf{RP}=textsf{NP}$}}, kirjoittaja = {Liang, Daniel}, päiväkirja = {{Kvantti}} , issn = {2521-327X}, julkaisija = {{Verein zur F{"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volyymi = {7}, sivut = {1036}, kuukausi = kesä, vuosi = {2023}
}

► Viitteet

[1] Scott Aaronson. Kvanttitilojen opittavuus. 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] Scott Aaronson. Kvanttitilojen varjotomografia. Teoksessa Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, sivu 325–338, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355599. 10.1145/3188745.3188802.
https: / / doi.org/ 10.1145 / +3188745.3188802

[3] Scott Aaronson ja Daniel Gottesman. Stabilisaattoripiirien parannettu simulointi. Physical Review 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 ja A. G. White. Ancilla-avusteinen kvanttiprosessitomografia. Phys. Rev. Lett., 90: 193601, toukokuu 2003. 10.1103/PhysRevLett.90.193601.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[5] Martin Anthony ja Peter L. Bartlett. Toimintojen oppiminen interpoloinnista. Combinatorics, Probability and Computing, 9 (3): 213–225, 2000. 10.1017/S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam ja Ronald de Wolf. Vieraskolumni: Tutkimus kvanttioppimisteoriasta. ACM SIGACT News, 48 (2): 41–67, 2017. 10.1145/3106700.3106710.
https: / / doi.org/ 10.1145 / +3106700.3106710

[7] Srinivasan Arunachalam ja Ronald de Wolf. Oppimisalgoritmien optimaalinen kvanttinäytteen monimutkaisuus. Teoksessa Ryan O'Donnell, toimittaja, 32nd Computational Complexity Conference (CCC 2017), Leibniz International Proceedings in Informatics (LIPIcs) osa 79, sivut 25:1–25:31, Dagstuhl, Saksa, 2017. Schloss Dagstuhl-Ztrumennib 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 ja Henry Yuen. Kvanttitilastokyselyn oppiminen. 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 ja Aarthi Sundaram. Kvanttikovuus matalien klassisten piirien oppimisessa. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[10] Charles H. Bennett ja Gilles Brassard. Kvanttisalaus: Julkisen avaimen jakelu ja kolikoiden heittäminen. Teoreettinen tietojenkäsittelytiede, 560: 7–11, joulukuu 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 ja Stephen J. Wiesner. Viestintä yhden ja kahden hiukkasen operaattorien kautta einstein-podolsky-rosen-tiloissa. Phys. Rev. Lett., 69: 2881–2884, marraskuu 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 ja William K. Wootters. Teleportoidaan tuntematon kvanttitila kahden klassisen ja Einstein-podolsky-rosen-kanavan kautta. Phys. Rev. Lett., 70: 1895–1899, maaliskuu 1993. 10.1103/PhysRevLett.70.1895.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[13] Ethan Bernstein ja Umesh Vazirani. Kvanttien monimutkaisuusteoria. SIAM Journal of Computing, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[14] Avrim Blum. Oppimisen laskennallinen kovuus. http:///www.cs.cmu.edu/ avrim/ML07/lect1007.pdf, 2015. URL http:///www.cs.cmu.edu/ avrim/ML07/lect1007 .pdf. Luentomuistiinpanot CS 10-806:n koneoppimisen ja tietotieteen perusteet.
http:///www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

[15] Avrim L. Blum ja Ronald L. Rivest. 3-solmun hermoverkon koulutus on np-täydellinen. Neural Networks, 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 ja Manfred K. Warmuth. Oppittavuus ja vapnik-chervonenkis-ulottuvuus. J. ACM, 36 (4): 929–965, lokakuu 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / +76359.76371

[17] Jonathan F Buss, Gudmund S Frandsen ja Jeffrey O Shallit. Joidenkin lineaarialgebran tehtävien laskennallinen monimutkaisuus. 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. Binääriluokitus klassisilla esiintymillä ja kvanttileimoilla. Quantum Machine Intelligence, 3 (1), toukokuu 2021. 10.1007/s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[19] Matthias C. Caro ja Ishaun Datta. Kvanttipiirien pseudoulottuvuus. Quantum Machine Intelligence, 2 (2), marraskuu 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 ja Ping-Cheng Yeh. Tuntemattomien kvantimittausten opittavuus. Kvantti Info. Comput., 16 (7–8): 615–656, toukokuu 2016. ISSN 1533-7146. 10.26421/QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] Isaac L. Chuang ja MA Nielsen. Resepti kvanttimustan laatikon dynamiikan kokeelliselle määrittämiselle. Journal of Modern Optics, 44 (11-12): 2455-2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / +09500349708231894

[22] Kai-Min Chung ja Han-Hsuan Lin. Esimerkki tehokkaista algoritmeista kvanttikanavien oppimiseen PAC-mallissa ja likimääräisen tilan erotteluongelmasta. Teoksessa Min-Hsiu Hsieh, toimittaja, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), julkaisun Leibniz International Proceedings in Informatics (LIPIcs) osa 197, sivut 3:1–3:22, Dagstuhl, Saksa, 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 ja Shai Shalev-Shwartz. Monimutkaisuusteoreettiset rajoitukset dnf:n oppimiseen. Teoksessa Vitaly Feldman, Alexander Rakhlin ja Ohad Shamir, toimittajat, 29th Annual Conference on Learning Theory, Proceedings of Machine Learning Researchin osa 49, sivut 815–830, Columbia University, New York, New York, USA, 23.–26. kesäkuuta 2016 PMLR. URL-osoite https:///proceedings.mlr.press/v49/daniely16.html.
https:///proceedings.mlr.press/v49/daniely16.html

[24] Steven T Flammia, David Gross, Yi-Kai Liu ja Jens Eisert. Kvanttitomografia pakatun tunnistuksen kautta: virherajat, näytteen monimutkaisuus ja tehokkaat estimaattorit. New Journal of Physics, 14 (9): 095022, syyskuu 2012. 10.1088/1367-2630/14/9/095022.
https://doi.org/10.1088/1367-2630/14/9/095022

[25] Paul W. Goldberg ja Mark R. Jerrum. Reaaliluvuilla parametroitujen käsiteluokkien vapnik-chervonenkis-ulottuvuuden rajoittaminen. Machine Learning, 18: 131–148, 1995. 10.1007/BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[26] Daniel Gottesman. Stabilisaattorikoodit ja kvanttivirheen korjaus, 1997.

[27] Daniel Gottesman. Kvanttitietokoneiden Heisenberg-esitys, 1998.

[28] Venkatesan Guruswami ja Prasad Raghavendra. Kovaus puolivälien oppimiseen kohinalla. 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 ja Nengkun Yu. Kvanttitilojen näyteoptimaalinen tomografia. IEEE Transactions on Information Theory, sivut 1–1, 2017. ISSN 1557-9654. 10.1109/tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

[30] Nika Haghtalab. Luento 9: Oppimisen kovuus. 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. Luentomuistiinpanot CS6781:lle - Koneoppimisen teoreettiset perusteet.
https:///www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf

[31] Hsin-Yuan Huang, Richard Kueng ja John Preskill. Kvanttijärjestelmän monien ominaisuuksien ennustaminen hyvin harvoista mittauksista. Nature Physics, lokakuu 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[32] Jonathan Katz. Huomautuksia kompleksisuusteoriasta, luento 3. https://www.cs.umd.edu/ jkatz/complexity/f11/lecture3.pdf, 2011. URL https://www.cs.umd. edu/ jkatz/complexity/f11/lecture3.pdf. Luentomuistiinpanot CS 652:lle — Kompleksisuusteoria.
https:///www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf

[33] Mikael Kharitonov. Jakelukohtaisen oppimisen kryptografinen kovuus. Teoksessa Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, sivu 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 ja E. Tardos. Algoritmin suunnittelu. Pearson Education, 2022. ISBN 9780132131087. URL https:///books.google.com/books?id=GORecgAACAAJ.
https:///books.google.com/books?id=GORecgAACAAJ

[35] Adam Klivans. PAC-oppimismalli. https:///www.cs.utexas.edu/ klivans/f06lec2.pdf, 2005. URL https://www.cs.utexas.edu/ klivans/f06lec2.pdf. CS 395T:n laskennallisen oppimisen teorian luentomuistiinpanot.
https:///www.cs.utexas.edu/~klivans/f06lec2.pdf

[36] Robert Koenig ja John A. Smolin. Kuinka valita tehokkaasti mielivaltainen clifford-ryhmäelementti. Journal of Mathematical Physics, 55 (12): 122202, joulukuu 2014. ISSN 1089-7658. 10.1063/1.4903507.
https: / / doi.org/ 10.1063 / +1.4903507

[37] Richard Kueng ja David Gross. Qubitin stabilointitilat ovat monimutkaisia projektiivisia 3-malleja, 2015.

[38] Ching-Yi Lai ja Hao-Chung Cheng. Joidenkin t-porttien kvanttipiirien oppiminen. IEEE Transactions on Information Theory, sivut 1–1, 2022. 10.1109/TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

[39] Richard A. Low. Oppimis- ja testausalgoritmit clifford-ryhmälle. Phys. Rev. A, 80: 052314, marraskuu 2009. 10.1103/PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] Ashley Montanaro. Stabilisaattorin tilojen oppiminen Bell-samplingin mukaan, 2017.

[41] Ryan O'Donnell ja John Wright. Tehokas kvanttitomografia. Julkaisussa Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, sivu 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 ja John Wright. Tehokas kvanttitomografia ii. Julkaisussa Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, sivu 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 ja John A Smolin. Yksityinen oppiminen merkitsee kvanttivakautta. Julkaisussa M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang ja J. Wortman Vaughan, toimittajat, Advances in Neural Information Processing Systems, osa 34, sivut 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. Stabilisaattoritilat ovat tehokkaasti PAC-opetettavissa. 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. Polynomiaikaiset algoritmit alkutekijöiden jakoa ja diskreettejä logaritmeja varten kvanttitietokoneella. SIAM Review, 41 (2): 303–332, 1999. 10.1137/S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

[46] Daniel R. Simon. Kvanttilaskennan tehosta. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

[47] Leslie G Valiant. Opittavan teoria. Communications of the ACM, 27 (11): 1134–1142, 1984. 10.1145/1968.1972.
https: / / doi.org/ 10.1145 / +1968.1972

[48] Ewout Van Den Berg. Yksinkertainen menetelmä satunnaisten Clifford-operaattoreiden otamiseen. Vuonna 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), sivut 54–59, 2021. 10.1109/QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[49] Mithuna Yoganathan. Edellytys, jossa klassinen simulaatio merkitsee tehokasta tilan opittavuutta, 2019.

[50] Huangjun Zhu. Multiqubit clifford -ryhmät ovat yhtenäisiä 3-malleja. Phys. Rev. A, 96: 062336, joulukuu 2017. 10.1103/PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Viitattu

[1] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd ja Alioscia Hamma, "Tehokkaiden dekoodereiden oppiminen quasi-chaotic quantum scramblersille". arXiv: 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt ja Theodore J. Yoder, "Optimaaliset algoritmit kvanttivaihetilojen oppimiseen", arXiv: 2208.07851, (2022).

[3] Anurag Anshu ja Srinivasan Arunachalam, "Tutkimus kvanttitilojen oppimisen monimutkaisuudesta", arXiv: 2305.20069, (2023).

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2023-06-07 22:21:42). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteeraama palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2023-06-07 22:21:40).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

SEO-pohjainen sisällön ja PR-jakelu. Vahvista jo tänään.
EVM Finance. Hajautetun rahoituksen yhtenäinen käyttöliittymä. Pääsy tästä.
Quantum Media Group. IR/PR vahvistettu. Pääsy tästä.
PlatoAiStream. Web3 Data Intelligence. Tietoa laajennettu. Pääsy tästä.
Lähde: https://quantum-journal.org/papers/q-2023-06-07-1036/

Aikaleima: Kesäkuu 7, 2023

Aikaleima: Jan 11, 2024

Clifford Circuits voidaan oppia kunnolla PAC:lla, jos ja vain jos $textsf{RP}=textsf{NP}$

Julkaissut Platon

Abstrakti

► BibTeX-tiedot

► Viitteet

Viitattu

Lisää aiheesta Quantum Journal

Energiatehokas kvanttipurkumittaus spin-fotoni-rajapinnalla

Kausittainen lähettämisen uni

Tiedonsiirto jatkuvasti muuttuvilla kvanttipoistokanavilla

Jaa ja hallitse -todennusmenetelmä meluiseen keskimittakaavaiseen kvanttilaskentaan

Miltei deterministinen hybridigenerointi mielivaltaisten fotonisten graafien tilojen avulla käyttämällä yhtä kvanttiemitteriä ja lineaarista optiikkaa

Kehittyvät kvanttitilasuunnittelut ja biunitaarisuus kaksoisyksikköpiirin dynamiikassa

Etäisyyteen perustuva resurssien kvantifiointi kvanttimittaussarjoille

Komposiittimittausten rajoittamat korrelaatiot

Kallistuvia Hardy-paradokseja laiteriippumattoman satunnaisuuden erottamiseen

Fermion-qudit-kvanttiprosessorit hilateorioiden simulointiin aineen kanssa

Tietoa Meistä

Pystysuuntainen haku ja Ai

foorumi

Pysy yhteydessä

Tili