Les circuits de Clifford peuvent être correctement appris PAC si et seulement si $textsf{RP}=textsf{NP}$

Republié par Platon

Suiveurs: 0

Département d'informatique, Université du Texas à Austin

Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.

Abstract

Étant donné un ensemble de données d'états d'entrée, de mesures et de probabilités, est-il possible de prédire efficacement les probabilités de mesure associées à un circuit quantique ? Travaux récents de Caro et Datta [19] ont étudié le problème des circuits quantiques d'apprentissage PAC dans un sens théorique de l'information, laissant ouvertes les questions d'efficacité de calcul. En particulier, une classe candidate de circuits pour lesquels un apprentissage efficace aurait pu être possible était celle des circuits de Clifford, puisque l'ensemble correspondant d'états générés par de tels circuits, appelés états stabilisateurs, sont connus pour être efficacement apprenables par PAC [44]. Ici, nous fournissons un résultat négatif, montrant que l'apprentissage correct des circuits CNOT avec une erreur 1/ poly($n$) est difficile pour les apprenants classiques à moins que $textsf{RP = NP}$, excluant la possibilité d'apprenants forts sous la théorie de la complexité standard hypothèses. En tant qu'analogue classique et sous-ensemble des circuits Clifford, cela conduit naturellement à un résultat de dureté pour les circuits Clifford également. De plus, nous montrons que si $textsf{RP = NP}$ alors il existerait des algorithmes d'apprentissage appropriés et efficaces pour les circuits CNOT et Clifford. Par des arguments similaires, nous trouvons également qu'un apprenant quantique propre et efficace pour de tels circuits existe si et seulement si $textsf{NP ⊆ RQP}$. Nous laissons ouvert le problème de la dureté pour un apprentissage incorrect ou une erreur $mathcal{O(1)}$ pour des travaux futurs.

► Données BibTeX

@article{Liang2023cliffordcircuitscan, doi = {10.22331/q-2023-06-07-1036}, url = {https://doi.org/10.22331/q-2023-06-07-1036}, titre = {Clifford { Les circuits peuvent être {P}correctement {PAC} {L}gagnés si et seulement si {$textsf{RP}=textsf{NP}$}}, author = {Liang, Daniel}, journal = {{Quantum}} , issn = {2521-327X}, éditeur = {{Verein zur F{"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1036}, mois = juin, année = {2023}
}

► Références

Scott Aaronson. L'apprentissage des états quantiques. Actes de la 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

Scott Aaronson. Tomographie d'ombre d'états quantiques. Dans Actes du 50e symposium annuel ACM SIGACT sur la théorie de l'informatique, STOC 2018, pages 325–338, New York, NY, États-Unis, 2018. Association for Computing Machinery. ISBN 9781450355599. 10.1145/3188745.3188802.
https: / / doi.org/ 10.1145 / 3188745.3188802

Scott Aaronson et Daniel Gottesman. Simulation améliorée des circuits stabilisateurs. Examen physique A, 70 (5) : 052328, 2004. 10.1103/physreva.70.052328.
https: / / doi.org/ 10.1103 / physreva.70.052328

J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O'Brien, M. A. Nielsen et A. G. White. Tomographie des processus quantiques assistée par Ancilla. Phys. Rev. Lett., 90 : 193601, mai 2003. 10.1103/PhysRevLett.90.193601.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

Martin Anthony et Peter L. Bartlett. Fonction d'apprentissage par interpolation. Combinatorics, Probability and Computing, 9 (3): 213–225, 2000. 10.1017/S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

Srinivasan Arunachalam et Ronald de Wolf. Chronique d'invité : Une enquête sur la théorie de l'apprentissage quantique. ACM SIGACT News, 48 (2): 41–67, 2017. 10.1145/3106700.3106710.
https: / / doi.org/ 10.1145 / 3106700.3106710

Srinivasan Arunachalam et Ronald de Wolf. Complexité optimale des échantillons quantiques des algorithmes d’apprentissage. Dans Ryan O'Donnell, éditeur, 32e Computational Complexity Conference (CCC 2017), volume 79 de Leibniz International Proceedings in Informatics (LIPIcs), pages 25 :1–25 :31, Dagstuhl, Allemagne, 2017. Schloss Dagstuhl–Leibniz-Zentrum pour l'informatique. ISBN978-3-95977-040-8. 10.4230/LIPIcs.CCC.2017.25.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.25

Srinivasan Arunachalam, Alex B Grilo et Henry Yuen. Apprentissage de requêtes statistiques quantiques. 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

Srinivasan Arunachalam, Alex Bredariol Grilo et Aarthi Sundaram. Dureté quantique de l'apprentissage des circuits classiques peu profonds. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

Charles H. Bennett et Gilles Brassard. Cryptographie quantique : distribution de clés publiques et tirage au sort. Informatique théorique, 560 : 7–11, décembre 2014. ISSN 0304-3975. 10.1016/j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

Charles H. Bennett et Stephen J. Wiesner. Communication via des opérateurs à une et deux particules sur les états d'einstein-podolsky-rosen. Phys. Rev. Lett., 69 : 2881–2884, novembre 1992. 10.1103/PhysRevLett.69.2881.
https: / / doi.org/ 10.1103 / PhysRevLett.69.2881

Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres et William K. Wootters. Téléportation d'un état quantique inconnu via deux canaux classiques et einstein-podolsky-rosen. Phys. Rev. Lett., 70 : 1895–1899, mars 1993. 10.1103/PhysRevLett.70.1895.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

Ethan Bernstein et Umesh Vazirani. Théorie de la complexité quantique. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

Avrim Blum. Dureté computationnelle de l'apprentissage. http://www.cs.cmu.edu/ avrim/ML07/lect1007.pdf, 2015. URL http://www.cs.cmu.edu/ avrim/ML07/lect1007 .pdf. Notes de cours pour CS 10-806 Fondements de l'apprentissage automatique et de la science des données.
http:///www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

Avrim L. Blum et Ronald L. Rivest. La formation d'un réseau de neurones à 3 nœuds est np-complète. Réseaux neuronaux, 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

Anselm Blumer, A. Ehrenfeucht, David Haussler et Manfred K. Warmuth. Apprentissage et dimension vapnik-chervonenkis. J. ACM, 36 (4): 929–965, octobre 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371

Jonathan F Buss, Gudmund S Frandsen et Jeffrey O Shallit. La complexité de calcul de certains problèmes d'algèbre linéaire. 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

Matthias C.Caro. Classification binaire avec instances classiques et étiquettes quantiques. Quantum Machine Intelligence, 3 (1), mai 2021. 10.1007/s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

Matthias C. Caro et Ishaun Datta. Pseudo-dimension des circuits quantiques. Quantum Machine Intelligence, 2 (2), novembre 2020. ISSN 2524-4914. 10.1007/s42484-020-00027-5.
https://doi.org/10.1007/s42484-020-00027-5

Hao-Chung Cheng, Min-Hsiu Hsieh et Ping-Cheng Yeh. L'apprentissage de mesures quantiques inconnues. Informations quantiques. 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

Isaac L. Chuang et MA Nielsen. Prescription pour la détermination expérimentale de la dynamique d'une boîte noire quantique. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

Kai-Min Chung et Han-Hsuan Lin. Exemples d'algorithmes efficaces pour l'apprentissage des canaux quantiques dans le modèle PAC et le problème de discrimination d'état approximatif. In Min-Hsiu Hsieh, rédacteur en chef, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 de Leibniz International Proceedings in Informatics (LIPics), pages 3:1–3:22, Dagstuhl, Allemagne, 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

Amit Daniely et Shai Shalev-Shwartz. Limites théoriques de la complexité sur l'apprentissage des DNF. Dans Vitaly Feldman, Alexander Rakhlin et Ohad Shamir, éditeurs, 29th Annual Conference on Learning Theory, volume 49 de Proceedings of Machine Learning Research, pages 815-830, Columbia University, New York, New York, États-Unis, 23-26 juin 2016. .PMLR. URL https:///proceedings.mlr.press/v49/daniely16.html.
https:///proceedings.mlr.press/v49/daniely16.html

Steven T Flammia, David Gross, Yi-Kai Liu et Jens Eisert. Tomographie quantique par détection compressée : limites d'erreur, complexité de l'échantillon et estimateurs efficaces. New Journal of Physics, 14 (9): 095022, septembre 2012. 10.1088/1367-2630/14/9/095022.
https://doi.org/10.1088/1367-2630/14/9/095022

Paul W. Goldberg et Mark R. Jerrum. Limitation de la dimension vapnik-chervonenkis des classes de concepts paramétrées par des nombres réels. Apprentissage automatique, 18 : 131–148, 1995. 10.1007/BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

Daniel Gottesman. Codes de stabilisation et correction d'erreur quantique, 1997.

Daniel Gottesman. La représentation d'Heisenberg des ordinateurs quantiques, 1998.

Venkatesan Guruswami et Prasad Raghavendra. Dureté d'apprentissage des demi-espaces avec du bruit. SIAM Journal on Computing, 39 (2): 742–765, 2009. 10.1137/070685798.
https: / / doi.org/ 10.1137 / 070685798

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu et Nengkun Yu. Tomographie optimale d'échantillons d'états quantiques. IEEE Transactions on Information Theory, pages 1–1, 2017. ISSN 1557-9654. 10.1109/tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

Nika Haghtalab. Conférence 9 : Dureté de l'apprentissage. 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. Notes de cours pour CS6781 - Fondements théoriques de l'apprentissage automatique.
https:///www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf

Hsin-Yuan Huang, Richard Kueng et John Preskill. Prédire de nombreuses propriétés d'un système quantique à partir de très peu de mesures. Nature Physics, octobre 2020. 10.1038/s41567-020-0932-7.
https://doi.org/10.1038/s41567-020-0932-7

Jonathan Katz. Notes sur la théorie de la complexité Conférence 3. https://www.cs.umd.edu/ jkatz/complexity/f11/lecture3.pdf, 2011. URL https://www.cs.umd. edu/jkatz/complexity/f11/lecture3.pdf. Notes de cours pour CS 652 — Théorie de la complexité.
https:///www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf

Michel Kharitonov. Dureté cryptographique de l'apprentissage spécifique à la distribution. Dans Actes du vingt-cinquième symposium annuel de l'ACM sur la théorie de l'informatique, STOC '93, pages 372-381, New York, NY, États-Unis, 1993. Association for Computing Machinery. ISBN0897915917/10.1145.
https: / / doi.org/ 10.1145 / 167088.167197

J. Kleinberg et E. Tardos. Conception d'algorithmes. Pearson Education, 2022. ISBN 9780132131087. URL https://books.google.com/books?id=GORecgAACAAJ.
https:///books.google.com/books?id=GORecgAACAAJ

Adam Klivan. Le modèle d'apprentissage PAC. https://www.cs.utexas.edu/klivans/f06lec2.pdf, 2005. URL https://www.cs.utexas.edu/klivans/f06lec2.pdf. Notes de cours pour la théorie de l'apprentissage informatique CS 395T.
https:///www.cs.utexas.edu/~klivans/f06lec2.pdf

Robert Koenig et John A. Smolin. Comment sélectionner efficacement un élément arbitraire du groupe Clifford. Journal of Mathematical Physics, 55 (12): 122202, décembre 2014. ISSN 1089-7658. 10.1063/1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

Richard Kueng et David Gross. Les états du stabilisateur de Qubit sont des 3-designs projectifs complexes, 2015.

Ching-Yi Lai et Hao-Chung Cheng. Apprentissage des circuits quantiques de certaines portes t. IEEE Transactions on Information Theory, pages 1–1, 2022. 10.1109/TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

Richard A. Low. Algorithmes d'apprentissage et de test pour le groupe Clifford. Phys. Rév. A, 80 : 052314, novembre 2009. 10.1103/PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

Ashley Montanaro. Apprentissage des états stabilisateurs par échantillonnage Bell, 2017.

Ryan O'Donnell et John Wright. Tomographie quantique efficace. Dans Actes du quarante-huitième symposium annuel de l'ACM sur la théorie de l'informatique, STOC '16, pages 899-912, New York, NY, États-Unis, 2016. Association for Computing Machinery. ISBN 9781450341325. 10.1145/2897518.2897544.
https: / / doi.org/ 10.1145 / 2897518.2897544

Ryan O'Donnell et John Wright. Tomographie quantique efficace ii. Dans Actes du 49e Symposium annuel ACM SIGACT sur la théorie de l'informatique, STOC 2017, pages 962-974, New York, NY, États-Unis, 2017. Association for Computing Machinery. ISBN 9781450345286. 10.1145/3055399.3055454.
https: / / doi.org/ 10.1145 / 3055399.3055454

Yihui Quek, Srinivasan Arunachalam et John A Smolin. L'apprentissage privé implique une stabilité quantique. Dans M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang et J. Wortman Vaughan, éditeurs, Advances in Neural Information Processing Systems, volume 34, pages 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

Andrea Rocchetto. Les états du stabilisateur sont efficacement apprenables par PAC. Information et calcul quantiques, 18 (7-8) : 541–552, 2018. 10.26421/qic18.7-8-1.
https: / / doi.org/ 10.26421 / qic18.7-8-1

Peter W. Shor. Algorithmes en temps polynomial pour la factorisation en nombres premiers et les logarithmes discrets sur un ordinateur quantique. Revue SIAM, 41 (2): 303–332, 1999. 10.1137/S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

Daniel R. Simon. Sur la puissance du calcul quantique. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

Leslie G Vaillant. Une théorie de l'apprenable. Communications de l'ACM, 27 (11): 1134–1142, 1984. 10.1145/1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972

Ewout Van Den Berg. Une méthode simple pour échantillonner des opérateurs de clifford aléatoires. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 54–59, 2021. 10.1109/QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

Mithuna Yoganathan. Une condition dans laquelle la simulabilité classique implique une capacité d'apprentissage efficace de l'état, 2019.

Huangjun Zhu. Les groupes de clifford multiqubits sont des 3-designs unitaires. Phys. Rév. A, 96 : 062336, décembre 2017. 10.1103/PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Cité par

[1] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd et Alioscia Hamma, "Apprentissage de décodeurs efficaces pour les brouilleurs quantiques quasi-chaotiques", arXiv: 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt et Theodore J. Yoder, "Algorithmes optimaux pour l'apprentissage des états de phase quantique", arXiv: 2208.07851, (2022).

[3] Anurag Anshu et Srinivasan Arunachalam, "Une enquête sur la complexité de l'apprentissage des états quantiques", arXiv: 2305.20069, (2023).

Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2023-06-07 22:21:42). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.

On Service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2023-06-07 22:21:40).

Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.

Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
Financement EVM. Interface unifiée pour la finance décentralisée. Accéder ici.
Groupe de médias quantiques. IR/PR amplifié. Accéder ici.
PlatoAiStream. Intelligence des données Web3. Connaissance Amplifiée. Accéder ici.
La source: https://quantum-journal.org/papers/q-2023-06-07-1036/

Horodatage: Le 7 juin 2023

Horodatage: Le 11 janvier 2024

Les circuits Clifford peuvent être correctement appris PAC si et seulement si $textsf{RP}=textsf{NP}$

Republié par Platon

Abstract

► Données BibTeX

► Références

Cité par

Plus de Journal quantique

Mesure de non-démolition quantique économe en énergie avec une interface spin-photon

Sommeil de soumission saisonnier

Transmission d'informations avec des canaux d'effacement quantique variables continus

Méthode de vérification diviser pour mieux régner pour le calcul quantique bruyant à échelle intermédiaire

Génération hybride quasi-déterministe d'états de graphes photoniques arbitraires à l'aide d'un seul émetteur quantique et d'une optique linéaire

Conceptions d'états quantiques émergents et biunitarité dans la dynamique des circuits dual-unitaires

Quantification des ressources basée sur la distance pour des ensembles de mesures quantiques

Corrélations contraintes par des mesures composites

Paradoxes de Hardy inclinés pour l'extraction aléatoire indépendante du périphérique

Processeurs quantiques Fermion-qudit pour simuler les théories de jauge sur réseau avec la matière

À propos de nous

Recherche verticale et Ai

Plateforme

Restez à l'affût

Compte