A complexidade das máquinas de vetores de suporte quântico

A complexidade das máquinas de vetores de suporte quântico

Carimbo de data / hora: 11 de janeiro de 2024 9h08
Nó Fonte: 3057476

Gian Gentineta1,2, Arne Thomsen3,2, David Suter2e Stefan Woerner2

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

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

Máquinas de vetores de suporte quântico empregam circuitos quânticos para definir a função do kernel. Foi demonstrado que esta abordagem oferece uma aceleração exponencial comprovável em comparação com qualquer algoritmo clássico conhecido para determinados conjuntos de dados. O treinamento de tais modelos corresponde à resolução de um problema de otimização convexa seja via sua formulação primal ou dual. Devido à natureza probabilística da mecânica quântica, os algoritmos de treinamento são afetados pela incerteza estatística, o que tem um grande impacto na sua complexidade. Mostramos que o problema dual pode ser resolvido em avaliações de circuitos quânticos $O(M^{4.67}/varepsilon^2)$, onde $M$ denota o tamanho do conjunto de dados e $varepsilon$ a precisão da solução comparada ao ideal resultam de valores esperados exatos, que só podem ser obtidos em teoria. Provamos sob uma suposição empiricamente motivada que o problema primal kernelizado pode alternativamente ser resolvido em $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ avaliações empregando uma generalização de um clássico conhecido algoritmo chamado Pegasos. Os resultados empíricos que acompanham demonstram que estas complexidades analíticas são essencialmente restritas. Além disso, investigamos uma aproximação variacional para máquinas de vetores de suporte quântico e mostramos que seu treinamento heurístico atinge um escalonamento consideravelmente melhor em nossos experimentos.

Imagem em destaque: Estimativa do valor do kernel $k(mathbf{x}_i, mathbf{x}_j)$, onde $mathcal{E}(mathbf{x}_i)$ denota um unitário parametrizado pelos dados $mathbf{x }_i$. O número de disparos é dado por $R$ que controla a precisão da estimativa do kernel.

Resumo popular

Máquinas quânticas de vetores de suporte são candidatas a demonstrar uma vantagem quântica em um futuro próximo para problemas de classificação. A ideia é que uma função kernel (esperançosamente útil) seja dada por um circuito quântico eficiente que é classicamente difícil de avaliar. Devido à natureza probabilística da mecânica quântica, tais funções centrais são afetadas pela incerteza estatística. Neste trabalho, analisamos rigorosamente como essa incerteza (também chamada de ruído de tiro) impacta a complexidade computacional geral para resolver o problema de classificação.

► dados BibTeX

► Referências

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe e S. Lloyd. Aprendizado de máquina quântica. Nature, 549(7671):195–202, 2017. DOI: 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / nature23474

[2] V. Havlíček, AD Córcoles, K. Temme, AW Harrow, A. Kandala, JM Chow e JM Gambetta. Aprendizagem supervisionada com espaços de recursos aprimorados por quantum. Natureza, 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 e S. Woerner. O poder das redes neurais quânticas. Nature Computational Science, 1(junho), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam e K. Temme. Uma aceleração quântica rigorosa e robusta em aprendizado de máquina supervisionado. Física da Natureza, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Leia as letras miúdas. Nature Physics, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Tang. Um algoritmo clássico de inspiração quântica para sistemas de recomendação. Em Anais do 51º Simpósio Anual ACM SIGACT sobre Teoria da Computação, STOC 2019, páginas 217–228, Nova York, NY, EUA, 2019. Association for Computing Machinery. DOI: 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310

[7] N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang e C. Wang. Estrutura aritmética de matriz sublinear de baixa classificação baseada em amostragem para desquantização do aprendizado de máquina quântica, páginas 387–400. Association for Computing Machinery, Nova York, NY, EUA, 2020. Disponível on-line: https:///​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti e X. Wu. Algoritmos quânticos sublineares para treinamento de classificadores lineares e baseados em kernel. Na Conferência Internacional sobre Aprendizado de Máquina, páginas 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo e Z. Holmes. Concentração exponencial e intreinabilidade em métodos de kernel quântico, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz e N. Srebro. Otimização SVM: Dependência inversa do tamanho do conjunto de treinamento. Anais da 25ª Conferência Internacional sobre Aprendizado de Máquina, páginas 928–935, 2008.

[11] A. Thomsen. Comparando redes neurais quânticas e máquinas de vetores de suporte quântico. Dissertação de mestrado, ETH Zurique, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon e VN Vapnik. Um algoritmo de treinamento para classificadores de margem ótima. Em Anais do Quinto Workshop Anual sobre Teoria de Aprendizagem Computacional, COLT '92, páginas 144–152, Nova York, NY, EUA, 1992. Association for Computing Machinery. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] C. Cortes e V. Vapnik. Redes de vetores de suporte. Em Machine Learning, páginas 273–297, 1995.

[14] VN Vapnik. A natureza da teoria de aprendizagem estatística. Springer Science+Business Media, LLC, 2000.

[15] F.Pedregosa et al. Scikit-learn: aprendizado de máquina em Python. Journal of Machine Learning Research, 12(85):2825–2830, 2011. Disponível on-line: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd e L. Vandenberghe. Otimização Convexa. Imprensa da Universidade de Cambridge, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro e A. Cotter. Pegasos: Solucionador de subgradiente estimado primordial para SVM. Programação 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: uma estrutura de código aberto para computação quântica, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] P. Rebentrost, M. Mohseni e S. Lloyd. Máquina de vetores de suporte quântico para classificação de big data. Physical Review Letters, 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 e B. Schölkopf. O viés indutivo dos kernels quânticos. Em M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang e JW Vaughan, editores, Advances in Neural Information Processing Systems, volume 34, páginas 12661–12673. Curran Associates, Inc., 2021. Disponível on-line: 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é e C. Ciuti. Máquinas de kernel quântico barulhentas. Física. Rev.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges e CJC Burges. Um tutorial sobre máquinas de vetores de suporte para reconhecimento de padrões. Data Mining and Knowledge Discovery, 2:121–167, 1998. Disponível online: https://www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -máquinas-para-reconhecimento de padrões/​.
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 e PJ Coles. Platôs estéreis dependentes da função de custo em circuitos quânticos rasos parametrizados. Nature Communications, 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 e Reiter, Florentin. Análise de Higgs com classificadores quâ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 e PJ Coles. Algoritmos quânticos variacionais. 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 programação quadrática (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Aulas introdutórias sobre otimização convexa: um curso básico. Otimização Aplicada. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Uma Visão Geral do Método de Perturbação Simultânea para Otimização Eficiente. John Hopkins APL Technical Digest, 19(4), páginas 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter e S. Woerner. Código para o manuscrito “A complexidade das máquinas de vetores de suporte quântico”. 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 e JJ Meyer. Treinamento de kernels de incorporação quântica em computadores quânticos de curto prazo. Física. Rev.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Algumas estimativas de normas de matrizes aleatórias. Anais da Sociedade Americana de Matemática, 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. Introdução à análise não assintótica de matrizes aleatórias. Sensor Comprimido: Teoria e Aplicações, páginas 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf e AJ Smola. Métodos de kernel em aprendizado de máquina. Anais de Estatística, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniel. Estabilidade da solução de programas quadráticos definidos. Programação 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 e Fernando GSL Brandão, “Algoritmos quânticos: Um levantamento de aplicações e complexidades ponta a ponta”, arXiv: 2310.03011, (2023).

[2] Maria Schuld e Nathan Killoran, “A vantagem quântica é o objetivo certo para o aprendizado de máquina quântica?”, PRX Quantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik e Ofer Lahav, “Uma máquina de vetores de suporte aprimorada quântica para classificação de galáxias”, Técnicas e Instrumentos RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung e Chen-Yu Liu, “Máquina de vetor de suporte aprimorada por quantum para classificação estelar em grande escala com aceleração de GPU”, arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo e Zoë Holmes, “Concentração exponencial e intreinabilidade em métodos de kernel quântico”, arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka e Naoki Yamamoto, “Redes neurais híbridas clássicas quânticas no regime de kernel tangente neural”, Ciência e Tecnologia Quântica 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo e Rudy Raymond, “Aprendizado de máquina quântica em dispositivos quânticos de curto prazo: estado atual de técnicas supervisionadas e não supervisionadas para aplicações do mundo real”, arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs e Nico Piatkowski, “Explicando Circuitos Quânticos com Valores Shapley: Rumo ao Aprendizado de Máquina Quântica Explicável”, arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner e Giuseppe Carleo, “Evolução Variacional do Tempo Quântico sem o Tensor Geométrico Quântico”, arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller e Stefan Woerner, “Alinhamento do Kernel Quântico com Descida Gradiente Estocástica”, arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie e Tim Scanlon, “Reconstruindo segmentos de trilha de partículas carregadas com uma máquina de vetor de suporte aprimorada quântica”, arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick e Thomas Ward, “Um modelo para tempo de execução de execução de circuito e suas implicações para kernels quânticos em tamanhos práticos de conjuntos de dados”, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler e Stefan Woerner, “Limites prováveis ​​para valores de expectativa livres de ruído calculados a partir de amostras ruidosas”, arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus e Stefano Mensa, “Otimização eficiente de parâmetros para alinhamento de kernel quântico: uma abordagem de subamostragem em treinamento variacional” , arXiv: 2401.02879, (2024).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2024-01-12 02:12:22). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2024-01-12 02:12:21).

Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.

Carimbo de hora:

Mais de Diário Quântico