Clifford-Schaltkreise können nur dann ordnungsgemäß PAC gelernt werden, wenn $textsf{RP}=textsf{NP}$

Neuauflage von Plato

Verfolger: 0

Institut für Informatik, University of Texas at Austin

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

Abstrakt

Ist es angesichts eines Datensatzes von Eingabezuständen, Messungen und Wahrscheinlichkeiten möglich, die mit einer Quantenschaltung verbundenen Messwahrscheinlichkeiten effizient vorherzusagen? Aktuelle Arbeiten von Caro und Datta [19] untersuchte das Problem des PAC-Lernens von Quantenschaltungen im informationstheoretischen Sinne und ließ Fragen zur Recheneffizienz offen. Eine Kandidatenklasse von Schaltkreisen, für die ein effizienter Lernender möglich gewesen wäre, waren insbesondere die Clifford-Schaltkreise, da der entsprechende Satz von Zuständen, die von solchen Schaltkreisen erzeugt werden und als Stabilisatorzustände bezeichnet werden, bekanntermaßen effizient PAC-lernbar ist [44]. Hier liefern wir ein negatives Ergebnis und zeigen, dass das ordnungsgemäße Lernen von CNOT-Schaltkreisen mit 1/ Poly($n$)-Fehler für klassische Lernende schwierig ist, es sei denn, $textsf{RP = NP}$, was die Möglichkeit starker Lernender unter der Standardkomplexitätstheorie ausschließt Annahmen. Als klassisches Analogon und Teilmenge der Clifford-Schaltkreise führt dies natürlich auch für Clifford-Schaltkreise zu einem Härteergebnis. Darüber hinaus zeigen wir, dass es, wenn $textsf{RP = NP}$ wäre, effiziente richtige Lernalgorithmen für CNOT- und Clifford-Schaltkreise geben würde. Mit ähnlichen Argumenten finden wir auch, dass ein effizienter echter Quantenlerner für solche Schaltkreise genau dann existiert, wenn $textsf{NP ⊆ RQP}$. Das Problem der Härte für unsachgemäßes Lernen oder $mathcal{O(1)}$-Fehler lassen wir für zukünftige Arbeiten offen.

► BibTeX-Daten

@article{Liang2023cliffordCircuitscan, doi = {10.22331/q-2023-06-07-1036}, url = {https://doi.org/10.22331/q-2023-06-07-1036}, Titel = {Clifford { Schaltkreise können genau dann {P}korrekt {PAC} {L}verdient werden, wenn {$textsf{RP}=textsf{NP}$}}, Autor = {Liang, Daniel}, Zeitschrift = {{Quantum}} , issn = {2521-327X}, verleger = {{Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften}}, Band = {7}, Seiten = {1036}, Monat = Juni, Jahr = {2023} }

► Referenzen

[1] Scott Aaronson. Die Lernbarkeit von Quantenzuständen. 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. Schattentomographie von Quantenzuständen. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Seite 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 und Daniel Gottesman. Verbesserte Simulation von Stabilisatorschaltungen. Physical Review 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 und AG White. Ancilla-unterstützte Quantenprozesstomographie. Physik. Rev. Lett., 90: 193601, Mai 2003. 10.1103/PhysRevLett.90.193601.
https://doi.org/ 10.1103/PhysRevLett.90.193601

[5] Martin Anthony und Peter L. Bartlett. Funktionslernen durch Interpolation. Combinatorics, Probability and Computing, 9 (3): 213–225, 2000. 10.1017/S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam und Ronald de Wolf. Gastkolumne: Ein Überblick über die Quantenlerntheorie. ACM SIGACT News, 48 (2): 41–67, 2017. 10.1145/3106700.3106710.
https: / / doi.org/ 10.1145 / 3106700.3106710

[7] Srinivasan Arunachalam und Ronald de Wolf. Optimale Quantenprobenkomplexität von Lernalgorithmen. In Ryan O'Donnell, Herausgeber, 32. Computational Complexity Conference (CCC 2017), Band 79 von Leibniz International Proceedings in Informatics (LIPIcs), Seiten 25:1–25:31, Dagstuhl, Deutschland, 2017. Schloss Dagstuhl–Leibniz-Zentrum für 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 und Henry Yuen. Quantenstatistisches Abfragelernen. arXiv-Vorabdruck 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 und Aarthi Sundaram. Quantenhärte des Lernens flacher klassischer Schaltkreise. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[10] Charles H. Bennett und Gilles Brassard. Quantenkryptographie: Verteilung öffentlicher Schlüssel und Münzwurf. Theoretical Computer Science, 560: 7–11, Dezember 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 und Stephen J. Wiesner. Kommunikation über Ein- und Zwei-Teilchen-Operatoren auf Einstein-Podolsky-Rosen-Zuständen. Physik. 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 und William K. Wootters. Teleportation eines unbekannten Quantenzustands über duale klassische und Einstein-Podolsky-Rosen-Kanäle. Physik. Rev. Lett., 70: 1895–1899, März 1993. 10.1103/PhysRevLett.70.1895.
https://doi.org/ 10.1103/PhysRevLett.70.1895

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

[14] Avrim Blum. Rechenhärte des Lernens. http:///www.cs.cmu.edu/ avrim/ML07/lect1007.pdf, 2015. URL http:///www.cs.cmu.edu/ avrim/ML07/lect1007 .pdf. Vorlesungsskript für CS 10-806 Grundlagen des maschinellen Lernens und der Datenwissenschaft.
http:///www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

[15] Avrim L. Blum und Ronald L. Rivest. Das Training eines neuronalen Netzwerks mit 3 Knoten ist np-vollständig. 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 und Manfred K. Warmuth. Lernbarkeit und die Vapnik-Chervonenkis-Dimension. J. ACM, 36 (4): 929–965, Okt. 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371

[17] Jonathan F. Buss, Gudmund S. Frandsen und Jeffrey O. Shallit. Die rechnerische Komplexität einiger Probleme der linearen 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. Binäre Klassifizierung mit klassischen Instanzen und Quantenlabels. Quantum Machine Intelligence, 3 (1), Mai 2021. 10.1007/s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[19] Matthias C. Caro und Ishaun Datta. Pseudodimension von Quantenschaltungen. 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 und Ping-Cheng Yeh. Die Lernbarkeit unbekannter Quantenmessungen. Quanteninfo. Comput., 16 (7–8): 615–656, Mai 2016. ISSN 1533-7146. 10.26421/QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] Isaac L. Chuang und MA Nielsen. Rezept zur experimentellen Bestimmung der Dynamik einer Quanten-Blackbox. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

[22] Kai-Min Chung und Han-Hsuan Lin. Beispielhafte effiziente Algorithmen zum Lernen von Quantenkanälen im PAC-Modell und das Problem der ungefähren Zustandsdiskriminierung. In Min-Hsiu Hsieh, Herausgeber, 16. Konferenz zur Theorie der Quantenberechnung, Kommunikation und Kryptographie (TQC 2021), Band 197 von Leibniz International Proceedings in Informatics (LIPIcs), Seiten 3:1–3:22, Dagstuhl, Deutschland, 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 und Shai Shalev-Shwartz. Komplexitätstheoretische Einschränkungen beim Lernen von DNFs. In Vitaly Feldman, Alexander Rakhlin und Ohad Shamir, Herausgeber, 29. Jahreskonferenz zur Lerntheorie, Band 49 von Proceedings of Machine Learning Research, Seiten 815–830, Columbia University, New York, New York, USA, 23.–26. Juni 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 und Jens Eisert. Quantentomographie mittels Compressed Sensing: Fehlergrenzen, Probenkomplexität und effiziente Schätzer. 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 und Mark R. Jerrum. Begrenzung der Vapnik-Chervonenkis-Dimension von durch reelle Zahlen parametrisierten Konzeptklassen. Machine Learning, 18: 131–148, 1995. 10.1007/BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[26] Daniel Gottesmann. Stabilisatorcodes und Quantenfehlerkorrektur, 1997.

[27] Daniel Gottesmann. Die Heisenberg-Darstellung von Quantencomputern, 1998.

[28] Venkatesan Guruswami und Prasad Raghavendra. Schwierigkeit, Halbräume mit Rauschen zu lernen. 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 und Nengkun Yu. Probenoptimale Tomographie von Quantenzuständen. IEEE Transactions on Information Theory, Seiten 1–1, 2017. ISSN 1557-9654. 10.1109/tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

[30] Nika Haghtalab. Vorlesung 9: Lernhärte. 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. Vorlesungsskript für CS6781 – Theoretische Grundlagen des maschinellen Lernens.
https:///www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf

[31] Hsin-Yuan Huang, Richard Kueng und John Preskill. Vorhersage vieler Eigenschaften eines Quantensystems aus sehr wenigen Messungen. Nature Physics, Okt. 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

[32] Jonathan Katz. Hinweise zur Komplexitätstheorie Vorlesung 3. https://www.cs.umd.edu/ jkatz/complexity/f11/lecture3.pdf, 2011. URL https://www.cs.umd. edu/ jkatz/complexity/f11/lecture3.pdf. Skript zur Vorlesung CS 652 – Komplexitätstheorie.
https:///www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf

[33] Michael Charitonow. Kryptografische Härte des verteilungsspezifischen Lernens. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC '93, Seite 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 und E. Tardos. Algorithmusdesign. Pearson Education, 2022. ISBN 9780132131087. URL https://books.google.com/books?id=GORecgAACAAJ.
https:///books.google.com/books?id=GORecgAACAAJ

[35] Adam Klivans. Das PAC-Lernmodell. https://www.cs.utexas.edu/ klivans/f06lec2.pdf, 2005. URL https://www.cs.utexas.edu/ klivans/f06lec2.pdf. Vorlesungsskript für CS 395T Computational Learning Theory.
https://www.cs.utexas.edu/~klivans/f06lec2.pdf

[36] Robert Koenig und John A. Smolin. So wählen Sie effizient ein beliebiges Clifford-Gruppenelement aus. Journal of Mathematical Physics, 55 (12): 122202, Dezember 2014. ISSN 1089-7658. 10.1063/1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

[37] Richard Kueng und David Gross. Qubit-Stabilisatorzustände sind komplexe projektive 3-Designs, 2015.

[38] Ching-Yi Lai und Hao-Chung Cheng. Quantenschaltkreise einiger T-Gatter lernen. IEEE Transactions on Information Theory, Seiten 1–1, 2022. 10.1109/TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

[39] Richard A. Low. Lern- und Testalgorithmen für die Clifford-Gruppe. Physik. Rev. A, 80: 052314, November 2009. 10.1103/PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] Ashley Montanaro. Lernen von Stabilisatorzuständen durch Bell-Sampling, 2017.

[41] Ryan O'Donnell und John Wright. Effiziente Quantentomographie. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, Seite 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 und John Wright. Effiziente Quantentomographie ii. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Seite 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 und John A. Smolin. Privates Lernen impliziert Quantenstabilität. In M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang und J. Wortman Vaughan, Herausgeber, Advances in Neural Information Processing Systems, Band 34, Seiten 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. Stabilisatorzustände sind effizient PAC-lernbar. 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. Polynomzeitalgorithmen zur Primfaktorzerlegung und diskreten Logarithmen auf einem Quantencomputer. SIAM Review, 41 (2): 303–332, 1999. 10.1137/S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

[46] Daniel R. Simon. Über die Kraft der Quantenberechnung. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

[47] Leslie G. Valiant. Eine Theorie des Lernbaren. 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. Eine einfache Methode zur Stichprobe zufälliger Clifford-Operatoren. Im Jahr 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), Seiten 54–59, 2021. 10.1109/QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[49] Mithuna Yoganathan. Eine Bedingung, unter der klassische Simulierbarkeit eine effiziente Zustandslernbarkeit impliziert, 2019.

[50] Huangjun Zhu. Multiqubit-Clifford-Gruppen sind einheitliche 3-Designs. Physik. Rev. A, 96: 062336, Dez. 2017. 10.1103/PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Zitiert von

[1] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd und Alioscia Hamma, „Lernen effizienter Decoder für quasi-chaotische Quantenscrambler“, arXiv: 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt und Theodore J. Yoder, „Optimale Algorithmen zum Lernen von Quantenphasenzuständen“, arXiv: 2208.07851, (2022).

[3] Anurag Anshu und Srinivasan Arunachalam, „Eine Umfrage zur Komplexität des Lernens von Quantenzuständen“, arXiv: 2305.20069, (2023).

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

On Der zitierte Dienst von Crossref Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-06-07 22:21:40).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

SEO-gestützte Content- und PR-Distribution. Holen Sie sich noch heute Verstärkung.
EVM-Finanzen. Einheitliche Schnittstelle für dezentrale Finanzen. Hier zugreifen.
Quantum Media Group. IR/PR verstärkt. Hier zugreifen.
PlatoAiStream. Web3-Datenintelligenz. Wissen verstärkt. Hier zugreifen.
Quelle: https://quantum-journal.org/papers/q-2023-06-07-1036/

Zeitstempel: 7. Juni 2023

Zeitstempel: Jan 11, 2024

Clifford-Schaltkreise können genau dann ordnungsgemäß PAC gelernt werden, wenn $textsf{RP}=textsf{NP}$

Neuauflage von Plato

Abstrakt

► BibTeX-Daten

► Referenzen

Zitiert von

Mehr von Quantenjournal

Energieeffiziente zerstörungsfreie Quantenmessung mit einer Spin-Photonen-Schnittstelle

Saisonaler Unterwerfungsschlaf

Informationsübertragung mit kontinuierlich variablen Quantenlöschkanälen

Divide-and-Conquer-Verifizierungsverfahren für verrauschte Quantenberechnungen im mittleren Maßstab

Nahezu deterministische Hybriderzeugung beliebiger photonischer Graphenzustände unter Verwendung eines einzelnen Quantenemitters und linearer Optik

Emergente Quantenzustandsdesigns und Biunitarität in der Dynamik dual-unitärer Schaltkreise

Distanzbasierte Ressourcenquantifizierung für Mengen von Quantenmessungen

Durch zusammengesetzte Messungen eingeschränkte Korrelationen

Gekippte Hardy-Paradoxe zur geräteunabhängigen Zufallsextraktion

Fermion-Qudit-Quantenprozessoren zur Simulation von Gittereichtheorien mit Materie

Über uns

Vertikale Suche & Ai

Plattform

Bleiben Sie in Verbindung

Konto