Los circuitos de Clifford se pueden aprender correctamente en PAC si y solo si $textsf{RP}=textsf{NP}$

Los circuitos de Clifford se pueden aprender correctamente en PAC si y solo si $textsf{RP}=textsf{NP}$

Marca de tiempo: 7 de junio de 2023 6:07 a.m.
Nodo de origen: 2706854

Daniel Liang

Departamento de Ciencias de la Computación, Universidad de Texas en Austin

¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.

Resumen

Dado un conjunto de datos de estados de entrada, mediciones y probabilidades, ¿es posible predecir de manera eficiente las probabilidades de medición asociadas con un circuito cuántico? Trabajo reciente de Caro y Datta [19] estudió el problema de los circuitos cuánticos de aprendizaje de PAC en un sentido teórico de la información, dejando preguntas abiertas sobre la eficiencia computacional. En particular, una clase candidata de circuitos para los que un aprendiz eficiente podría haber sido posible fue la de los circuitos de Clifford, ya que se sabe que el conjunto correspondiente de estados generados por dichos circuitos, llamados estados estabilizadores, se pueden aprender de manera eficiente con PAC.44]. Aquí proporcionamos un resultado negativo, que muestra que el aprendizaje adecuado de los circuitos CNOT con error 1/ poly($n$) es difícil para los estudiantes clásicos a menos que $textsf{RP = NP}$, descartando la posibilidad de estudiantes fuertes bajo la teoría de complejidad estándar suposiciones Como el análogo clásico y el subconjunto de los circuitos de Clifford, esto también conduce naturalmente a un resultado de dureza para los circuitos de Clifford. Además, mostramos que si $textsf{RP = NP}$ entonces existirían algoritmos de aprendizaje adecuados y eficientes para los circuitos CNOT y Clifford. Con argumentos similares, también encontramos que existe un aprendiz cuántico adecuado eficiente para tales circuitos si y solo si $textsf{NP ⊆ RQP}$. Dejamos abierto el problema de la dureza por aprendizaje inadecuado o error $mathcal{O(1)}$ para trabajos futuros.

► datos BibTeX

► referencias

[ 1 ] Scott Aaronson. La capacidad de aprendizaje de los estados cuánticos. Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería, 463 (2088): 3089–3114, 2007. 10.1098/rspa.2007.0113.
https: / / doi.org/ 10.1098 / rspa.2007.0113

[ 2 ] Scott Aaronson. Tomografía de sombra de estados cuánticos. En Actas del 50º Simposio Anual ACM SIGACT sobre Teoría de la Computación, STOC 2018, páginas 325–338, Nueva York, NY, EE. UU., 2018. Asociación de Maquinaria de Computación. ISBN 9781450355599. 10.1145/3188745.3188802.
https: / / doi.org/ 10.1145 / 3188745.3188802

[ 3 ] Scott Aaronson y Daniel Gottesman. Simulación mejorada de circuitos estabilizadores. Revisión física 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 y AG White. Tomografía de proceso cuántico asistida por Ancilla. Física. Rev. Lett., 90: 193601, mayo de 2003. 10.1103/​PhysRevLett.90.193601.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[ 5 ] Martín Antonio y Peter L. Bartlett. Aprendizaje de funciones por interpolación. Combinatorics, Probability and Computing, 9 (3): 213–225, 2000. 10.1017/​S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[ 6 ] Srinivasan Arunachalam y Ronald de Wolf. Columna invitada: Una encuesta sobre la teoría del aprendizaje cuántico. 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 y Henry Yuen. Aprendizaje de consultas estadísticas cuánticas. Preimpresión de 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 y Aarthi Sundaram. Dureza cuántica del aprendizaje de circuitos clásicos poco profundos. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[ 10 ] Charles H. Bennett y Gilles Brassard. Criptografía cuántica: distribución de claves públicas y lanzamiento de monedas. Informática teórica, 560: 7–11, diciembre de 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 y Stephen J. Wiesner. Comunicación a través de operadores de una y dos partículas en estados de einstein-podolsky-rosen. física Rev. Lett., 69: 2881–2884, noviembre de 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 y William K. Wootters. Teletransportación de un estado cuántico desconocido a través de canales duales clásicos y einstein-podolsky-rosen. física Rev. Lett., 70: 1895–1899, marzo de 1993. 10.1103/​PhysRevLett.70.1895.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[ 13 ] Ethan Bernstein y Umesh Vazirani. Teoría de la complejidad cuántica. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[ 14 ] Avrim Blum. Dureza computacional del aprendizaje. http:/​/​www.cs.cmu.edu/​ avrim/​ML07/​lect1007.pdf, 2015. URL http:/​/​www.cs.cmu.edu/​ avrim/​ML07/​lect1007 .pdf. Apuntes de clase para CS 10-806 Fundamentos de aprendizaje automático y ciencia de datos.
http://​/​www.cs.cmu.edu/​~avrim/​ML07/​lect1007.pdf

[ 15 ] Avrim L. Blum y Ronald L. Rivest. El entrenamiento de una red neuronal de 3 nodos es np-completo. Redes neuronales, 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 y Manfred K. Warmuth. Learnability y la dimensión vapnik-chervonenkis. J. ACM, 36 (4): 929–965, octubre de 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371

[ 17 ] Jonathan F Buss, Gudmund S Frandsen y Jeffrey O Shallit. La complejidad computacional de algunos problemas de álgebra lineal. 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 ] Matías C. Caro. Clasificación binaria con instancias clásicas y etiquetas cuánticas. Quantum Machine Intelligence, 3 (1), mayo de 2021. 10.1007/​s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[ 19 ] Matthias C. Caro e Ishaun Datta. Pseudo-dimensión de circuitos cuánticos. Quantum Machine Intelligence, 2 (2), noviembre de 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 y Ping-Cheng Yeh. La capacidad de aprendizaje de medidas cuánticas desconocidas. Información cuántica. Comput., 16 (7–8): 615–656, mayo de 2016. ISSN 1533-7146. 10.26421/QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[ 21 ] Isaac L. Chuang y MA Nielsen. Prescripción para la determinación experimental de la dinámica de una caja negra cuántica. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

[ 22 ] Kai-Min Chung y Han-Hsuan Lin. Ejemplo de algoritmos eficientes para el aprendizaje de canales cuánticos en el modelo PAC y el problema de discriminación de estado aproximado. En Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volumen 197 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 3:1–3:22, Dagstuhl, Alemania, 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 y Jens Eisert. Tomografía cuántica mediante sensado comprimido: límites de error, complejidad de la muestra y estimadores eficientes. New Journal of Physics, 14 (9): 095022, septiembre de 2012. 10.1088/1367-2630/14/9/095022.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​9/​095022

[ 25 ] Paul W. Goldberg y Mark R. Jerrum. Acotando la dimensión vapnik-chervonenkis de las clases de conceptos parametrizadas por números reales. Aprendizaje automático, 18: 131–148, 1995. 10.1007/BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[ 26 ] Daniel Gottesmann. Códigos estabilizadores y corrección de errores cuánticos, 1997.

[ 27 ] Daniel Gottesmann. La representación de Heisenberg de las computadoras cuánticas, 1998.

[ 28 ] Venkatesan Guruswami y Prasad Raghavendra. Dificultad de aprendizaje de semiespacios con ruido. 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 y Nengkun Yu. Tomografía muestra-óptima de estados cuánticos. IEEE Transactions on Information Theory, páginas 1 y 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 y John Preskill. Predecir muchas propiedades de un sistema cuántico a partir de muy pocas medidas. Nature Physics, octubre de 2020. 10.1038/​s41567-020-0932-7.
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[ 32 ] Jonathan Katz. Notas sobre la conferencia de teoría de la complejidad 3. https:/​/​www.cs.umd.edu/​ jkatz/​complexity/​f11/​lecture3.pdf, 2011. URL https:/​/​www.cs.umd. edu/​jkatz/​complexity/​f11/​lecture3.pdf. Apuntes de clase para CS 652 — Teoría de la complejidad.
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 y E. Tardos. Diseño de algoritmos. Pearson Education, 2022. ISBN 9780132131087. URL https:/​/​books.google.com/​books?id=GORecgAACAAJ.
https://​/​books.google.com/​books?id=GORecgAACAAJ

[ 35 ] Adam Klivans. El modelo de aprendizaje PAC. https:/​/​www.cs.utexas.edu/​klivans/​f06lec2.pdf, 2005. URL https:/​/​www.cs.utexas.edu/​klivans/​f06lec2.pdf. Notas de clase para CS 395T Teoría del aprendizaje computacional.
https:/​/​www.cs.utexas.edu/​~klivans/​f06lec2.pdf

[ 36 ] Robert Koenig y John A. Smolin. Cómo seleccionar de manera eficiente un elemento de grupo de Clifford arbitrario. Journal of Mathematical Physics, 55 (12): 122202, diciembre de 2014. ISSN 1089-7658. 10.1063/1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

[ 37 ] Richard Kueng y David Gross. Los estados del estabilizador Qubit son 3 diseños proyectivos complejos, 2015.

[ 38 ] Ching-Yi Lai y Hao-Chung Cheng. Aprendizaje de circuitos cuánticos de algunas puertas t. IEEE Transactions on Information Theory, páginas 1 y 1, 2022. 10.1109/​TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

[ 39 ] Richard A. Bajo. Algoritmos de aprendizaje y prueba para el grupo Clifford. física Rev. A, 80: 052314, noviembre de 2009. 10.1103/PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[ 40 ] Ashley Montanaro. Estados estabilizadores del aprendizaje por muestreo de Bell, 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 y John A. Smolin. El aprendizaje privado implica estabilidad cuántica. En M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang y J. Wortman Vaughan, editores, Advances in Neural Information Processing Systems, volumen 34, páginas 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. Los estados del estabilizador se pueden aprender de manera eficiente mediante PAC. Información y computación cuánticas, 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. Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica. Revista SIAM, 41 (2): 303–332, 1999. 10.1137/​S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

[ 46 ] Daniel R. Simón. Sobre el poder de la computación cuántica. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/​S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

[ 47 ] Leslie G Valiente. Una teoria de lo aprendible. Comunicaciones de la ACM, 27 (11): 1134–1142, 1984. 10.1145/​1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972

[ 48 ] Ewout Van Den Berg. Un método simple para muestrear operadores de Clifford aleatorios. En 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), páginas 54–59, 2021. 10.1109/​QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[ 49 ] Mithuna Yoganathan. Una condición bajo la cual la simulabilidad clásica implica una capacidad de aprendizaje de estado eficiente, 2019.

[ 50 ] Huangjun Zhu. Los grupos clifford multiqubit son 3 diseños unitarios. física Rev. A, 96: 062336, diciembre de 2017. 10.1103/​PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Citado por

[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 y Theodore J. Yoder, "Algoritmos óptimos para aprender estados de fase cuántica", arXiv: 2208.07851, (2022).

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

Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2023-06-07 22:21:42). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.

On Servicio de citaciones de Crossref no se encontraron datos sobre las obras citadas (último intento 2023-06-07 22:21:40).

Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.

Sello de tiempo:

Mas de Diario cuántico