La complejidad de las máquinas de vectores de soporte cuánticos

La complejidad de las máquinas de vectores de soporte cuánticos

Marca de tiempo: 11 de enero de 2024 9:08 a. M.
Nodo de origen: 3057476

Gian Gentinetta1,2, Arne Thomsen3,2, David Sutter2y Stefan Woerner2

1Instituto de Física, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – Zúrich
3Departamento de Física, ETH Zurich

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

Resumen

Las máquinas cuánticas de vectores de soporte emplean circuitos cuánticos para definir la función del núcleo. Se ha demostrado que este enfoque ofrece una aceleración exponencial demostrable en comparación con cualquier algoritmo clásico conocido para ciertos conjuntos de datos. El entrenamiento de dichos modelos corresponde a la resolución de un problema de optimización convexo ya sea mediante su formulación primaria o dual. Debido a la naturaleza probabilística de la mecánica cuántica, los algoritmos de entrenamiento se ven afectados por la incertidumbre estadística, lo que tiene un impacto importante en su complejidad. Mostramos que el problema dual se puede resolver en $O(M^{4.67}/varepsilon^2)$ evaluaciones de circuitos cuánticos, donde $M$ denota el tamaño del conjunto de datos y $varepsilon$ la precisión de la solución en comparación con el ideal. resultado de valores esperados exactos, lo cual sólo se puede obtener en teoría. Demostramos, bajo un supuesto motivado empíricamente, que el problema primario kernelizado puede resolverse alternativamente en evaluaciones $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ empleando una generalización de un clásico conocido. Algoritmo llamado Pegasos. Los resultados empíricos que lo acompañan demuestran que estas complejidades analíticas son esencialmente estrictas. Además, investigamos una aproximación variacional a las máquinas cuánticas de vectores de soporte y demostramos que su entrenamiento heurístico logra un escalamiento considerablemente mejor en nuestros experimentos.

Imagen destacada: Estimación del valor del kernel $k(mathbf{x}_i, mathbf{x}_j)$, donde $mathcal{E}(mathbf{x}_i)$ denota un unitario parametrizado por los datos $mathbf{x }_i$. El número de disparos viene dado por $R$, que controla la precisión de la estimación del núcleo.

Resumen popular

Las máquinas cuánticas de vectores de soporte son candidatas a demostrar una ventaja cuántica en un futuro próximo para los problemas de clasificación. La idea es que una función nuclear (con suerte útil) viene dada por un circuito cuántico eficiente que clásicamente es difícil de evaluar. Debido a la naturaleza probabilística de la mecánica cuántica, estas funciones del núcleo se ven afectadas por la incertidumbre estadística. En este trabajo, analizamos rigurosamente cómo esta incertidumbre (también llamada ruido de disparo) impacta la complejidad computacional general para resolver el problema de clasificación.

► datos BibTeX

► referencias

[ 1 ] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe y S. Lloyd. Aprendizaje automático cuántico. Naturaleza, 549(7671):195–202, 2017. DOI: 10.1038/​naturaleza23474.
https: / / doi.org/ 10.1038 / nature23474

[ 2 ] V. Havlíček, AD Córcoles, K. Temme, AW Harrow, A. Kandala, JM Chow y JM Gambetta. Aprendizaje supervisado con espacios de funciones mejorados cuánticamente. Naturaleza, 567(7747):209–212, 2019. DOI: 10.1038/​s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[ 3 ] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli y S. Woerner. El poder de las redes neuronales cuánticas. Nature Computational Science, 1 (junio de 2020). DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[ 4 ] Y. Liu, S. Arunachalam y K. Temme. Una aceleración cuántica rigurosa y robusta en el aprendizaje automático supervisado. Física de la Naturaleza, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[ 5 ] S. Aaronson. Lea la letra pequeña. Física de la naturaleza, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[ 6 ] E.Tang. Un algoritmo clásico de inspiración cuántica para sistemas de recomendación. En Actas del 51.º Simposio Anual ACM SIGACT sobre Teoría de la Computación, STOC 2019, páginas 217–228, Nueva York, NY, EE. UU., 2019. Association for Computing Machinery. DOI: 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310

[ 7 ] NUEVA HAMPSHIRE. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang y C. Wang. Marco aritmético de matriz sublineal de bajo rango basado en muestreo para descuantificar el aprendizaje automático cuántico, páginas 387–400. Association for Computing Machinery, Nueva York, NY, EE. UU., 2020. Disponible en línea: https:/​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[ 8 ] T. Li, S. Chakrabarti y X. Wu. Algoritmos cuánticos sublineales para entrenar clasificadores lineales y basados ​​en kernel. En Conferencia internacional sobre aprendizaje automático, páginas 3815–3824. PMLR, 2019.

[ 9 ] S. Thanasilp, S. Wang, M. Cerezo y Z. Holmes. Concentración exponencial e inentrenabilidad en métodos de núcleo cuántico, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[ 10 ] S. Shalev-Shwartz y N. Srebro. Optimización SVM: dependencia inversa del tamaño del conjunto de entrenamiento. Actas de la 25ª Conferencia Internacional sobre Aprendizaje Automático, páginas 928–935, 2008.

[ 11 ] A. Thomsen. Comparación de redes neuronales cuánticas y máquinas de vectores de soporte cuánticos. Tesis de maestría, ETH Zurich, 2021-09-06. DOI: 20.500.11850/​527559.

[ 12 ] BE Boser, IM Guyon y VN Vapnik. Un algoritmo de entrenamiento para clasificadores de margen óptimos. En Actas del Quinto Taller Anual sobre Teoría del Aprendizaje Computacional, COLT '92, páginas 144–152, Nueva York, NY, EE. UU., 1992. Asociación de Maquinaria de Computación. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[ 13 ] C. Cortés y V. Vapnik. Redes de vectores de soporte. En Machine Learning, páginas 273–297, 1995.

[ 14 ] VN Vapnik. La naturaleza de la teoría del aprendizaje estadístico. Springer Science + Business Media, LLC, 2000.

[ 15 ] F. Pedregosa et al. Scikit-learn: aprendizaje automático en Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Disponible en línea: http:/​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[ 16 ] S. Boyd y L. Vandenberghe. Optimizacion convexa. Prensa de la Universidad de Cambridge, 2004.

[ 17 ] S. Shalev-Shwartz, Y. Singer, N. Srebro y A. Cotter. Pegasos: solucionador de subgradiente estimado primario para SVM. Programación matemática, 127(1):3–30, 2011. DOI: 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[ 18 ] MDS Anis et al. Qiskit: un marco de código abierto para la computación cuántica, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[ 19 ] P. Rebentrost, M. Mohseni y S. Lloyd. Máquina de vectores de soporte cuántico para clasificación de big data. Cartas de revisión física, 113(3):1–5, 2014. DOI: 10.1103/​PhysRevLett.113.130503.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[ 20 ] J. Kübler, S. Buchholz y B. Schölkopf. El sesgo inductivo de los núcleos cuánticos. En M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang y JW Vaughan, editores, Advances in Neural Information Processing Systems, volumen 34, páginas 12661–12673. Curran Associates, Inc., 2021. Disponible en línea: https:/​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf

[ 21 ] V. Heyraud, Z. Li, Z. Denis, A. Le Boité y C. Ciuti. Máquinas de núcleo cuántico ruidosas. Física. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[ 22 ] CJC Burges y CJC Burges. Un tutorial sobre máquinas de vectores de soporte para el reconocimiento de patrones. Minería de datos y descubrimiento de conocimientos, 2:121–167, 1998. Disponible en línea: https:/​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -máquinas-para-reconocimiento-de-patrones/​.
https:/​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-recognition/​

[ 23 ] M. Cerezo, A. Sone, T. Volkoff, L. Cincio y PJ Coles. Mesetas estériles dependientes de la función de costos en circuitos cuánticos parametrizados poco profundos. Comunicaciones de la naturaleza, 12(1):1791, 2021. DOI: 10.1038/​s41467-021-21728-w.
https: / / doi.org/ 10.1038 / s41467-021-21728-w

[ 24 ] Belis, Vasilis, González-Castillo, Samuel, Reissel, Christina, Vallecorsa, Sofia, Combarro, Elías F., Dissertori, Günther y Reiter, Florentin. Análisis de Higgs con clasificadores cuánticos. EPJ Web Conf., 251:03070, 2021. DOI: 10.1051/​epjconf/​202125103070.
https: / / doi.org/ 10.1051 / epjconf / 202125103070

[ 25 ] M. Cerezo, A. Arrasmith, R. Babbush, SC Benjamin, S. Endo, K. Fujii, JR McClean, K. Mitarai, X. Yuan, L. Cincio y PJ Coles. Algoritmos cuánticos variacionales. Nature Reviews Physics, 3(9):625–644, 2021. DOI: 10.1038/​s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[ 26 ] R. McGibborn et al. quadprog: solucionador de programación cuadrática (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[ 27 ] Y. Nésterov. Conferencias introductorias sobre optimización convexa: un curso básico. Optimización aplicada. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[ 28 ] J. Spall. Una descripción general del método de perturbación simultánea para una optimización eficiente. Compendio técnico de John Hopkins APL, 19 (4), páginas 482–492, 1998.

[ 29 ] G. Gentinetta, A. Thomsen, D. Sutter y S. Woerner. Código del manuscrito “La complejidad de las máquinas de vectores de soporte cuánticos”. 2022. DOI: https://​/​doi.org/​10.5281/​zenodo.6303725.
https: / / doi.org/ 10.5281 / zenodo.6303725

[ 30 ] T. Hubregtsen, D. Wierichs, E. Gil-Fuster, P.-JHS Derks, PK Faehrmann y JJ Meyer. Entrenamiento de núcleos de incrustación cuántica en computadoras cuánticas a corto plazo. Física. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[ 31 ] R. Latała. Algunas estimaciones de normas de matrices aleatorias. Actas de la Sociedad Matemática Estadounidense, 133(5):1273–1282, 2005. DOI: 10.1090/​s0002-9939-04-07800-1.
https:/​/​doi.org/​10.1090/​s0002-9939-04-07800-1

[ 32 ] R. Vershinin. Introducción al análisis no asintótico de matrices aleatorias. Detección comprimida: teoría y aplicaciones, páginas 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[ 33 ] T. Hofmann, B. Schölkopf y AJ Smola. Métodos kernel en aprendizaje automático. Annals of Statistics, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[ 34 ] JW Daniel. Estabilidad de la solución de programas cuadráticos definidos. Programación matemática, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Citado por

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang y Fernando GSL Brandão, “Algoritmos cuánticos: un estudio de aplicaciones y complejidades de un extremo a otro”, arXiv: 2310.03011, (2023).

[2] Maria Schuld y Nathan Killoran, "¿Es Quantum Advantage el objetivo correcto para el aprendizaje automático cuántico?", PRX Cuántico 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik y Ofer Lahav, “Una máquina de vectores de soporte mejorada cuánticamente para la clasificación de galaxias”, Técnicas e Instrumentos RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung y Chen-Yu Liu, “Máquina de vectores de soporte mejorada cuánticamente para clasificación estelar a gran escala con aceleración de GPU”, arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo y Zoë Holmes, “Concentración exponencial y falta de entrenamiento en métodos de núcleo cuántico”, arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka y Naoki Yamamoto, “Redes neuronales híbridas clásicas cuánticas en el régimen del núcleo tangente neuronal”, Ciencia y tecnología cuántica 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo y Rudy Raymond, "Aprendizaje automático cuántico en dispositivos cuánticos a corto plazo: estado actual de las técnicas supervisadas y no supervisadas para aplicaciones del mundo real", arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs y Nico Piatkowski, "Explicación de circuitos cuánticos con valores de Shapley: hacia un aprendizaje automático cuántico explicable", arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner y Giuseppe Carleo, “Evolución del tiempo cuántico variacional sin el tensor geométrico cuántico”, arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller y Stefan Woerner, "Alineación del núcleo cuántico con descenso de gradiente estocástico", arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie y Tim Scanlon, “Reconstrucción de segmentos de seguimiento de partículas cargadas con una máquina de vectores de soporte mejorada cuánticamente”, arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick y Thomas Ward, “Un modelo para el tiempo de ejecución de circuitos y sus implicaciones para núcleos cuánticos en tamaños de conjuntos de datos prácticos”, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler y Stefan Woerner, “Límites demostrables para valores esperados libres de ruido calculados a partir de muestras ruidosas”, arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus y Stefano Mensa, “Optimización eficiente de parámetros para la alineación del núcleo cuántico: un enfoque de submuestreo en el entrenamiento variacional” , arXiv: 2401.02879, (2024).

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

On Servicio citado por Crossref no se encontraron datos sobre las obras citadas (último intento 2024-01-12 02:12:21).

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