양자 지원 벡터 머신의 복잡성

양자 지원 벡터 머신의 복잡성

타임 스탬프 : 11 년 2024 월 9 일 오전 08:XNUMX
소스 노드 : 3057476

지안 젠티네타1,2, 아르네 톰센3,2, 데이비드 서터2, 스테판 워너2

1물리학 연구소, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – 취리히
3ETH 취리히 물리학과

이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.

추상

양자 지원 벡터 머신은 양자 회로를 사용하여 커널 기능을 정의합니다. 이 접근 방식은 특정 데이터 세트에 대해 알려진 기존 알고리즘에 비해 기하급수적인 속도 향상을 제공하는 것으로 나타났습니다. 이러한 모델의 훈련은 원시 또는 이중 공식을 통해 볼록 최적화 문제를 해결하는 것과 같습니다. 양자 역학의 확률적 특성으로 인해 훈련 ​​알고리즘은 통계적 불확실성의 영향을 받으며, 이는 복잡성에 큰 영향을 미칩니다. $O(M^{4.67}/varepsilon^2)$ 양자 회로 평가에서 이중 문제를 해결할 수 있음을 보여줍니다. 여기서 $M$은 데이터 세트의 크기를 나타내고 $varepsilon$은 이상적인 것과 비교한 솔루션 정확도를 나타냅니다. 이는 이론상으로만 얻을 수 있는 정확한 기대값의 결과입니다. 우리는 경험적으로 동기 부여된 가정 하에서 커널화된 원시 문제가 알려진 고전의 일반화를 사용하여 $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ 평가에서 대안적으로 해결될 수 있음을 증명합니다. 페가소스(Pegasos)라는 알고리즘. 수반되는 경험적 결과는 이러한 분석적 복잡성이 본질적으로 엄격하다는 것을 보여줍니다. 또한, 우리는 양자 지원 벡터 머신에 대한 변형 근사를 조사하고 그들의 경험적 훈련이 실험에서 훨씬 더 나은 확장성을 달성한다는 것을 보여줍니다.

주요 이미지: 커널 값 $k(mathbf{x}_i, mathbf{x}_j)$ 추정. 여기서 $mathcal{E}(mathbf{x}_i)$는 $mathbf{x 데이터로 매개변수화된 단위체를 나타냅니다. }_i$. 샷 수는 커널 추정의 정확성을 제어하는 ​​$R$로 제공됩니다.

인기 요약

양자 지원 벡터 머신은 가까운 미래에 분류 문제에 대한 양자 이점을 입증할 후보입니다. 아이디어는 (유용하길 바라는) 커널 함수가 고전적으로 평가하기 어려운 효율적인 양자 회로에 의해 제공된다는 것입니다. 양자 역학의 확률적 특성으로 인해 이러한 커널 기능은 통계적 불확실성의 영향을 받습니다. 이 연구에서는 이러한 불확실성(샷 노이즈라고도 함)이 분류 문제를 해결하기 위한 전반적인 계산 복잡성에 어떻게 영향을 미치는지 엄격하게 분석합니다.

► BibTeX 데이터

► 참고 문헌

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe 및 S. Lloyd. 양자 기계 학습. 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 및 JM Gambetta. 양자 강화 기능 공간을 사용한 지도 학습. Nature, 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 및 S. Woerner. 양자 신경망의 힘. 자연계산과학, 1(2020월), 10.1038. DOI: 43588/​s021-00084-1-XNUMX.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam 및 K. Temme. 지도형 기계 학습의 엄격하고 강력한 양자 속도 향상. 자연 물리학, 2021. DOI: 10.1038/​s41567-021-01287-z.
https : / /doi.org/ 10.1038 / s41567-021-01287-z

[5] S. 아론슨. 작은 글씨를 읽어보세요. 자연 물리학, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https : / /doi.org/ 10.1038 / nphys3272

[6] E. 탕. 추천 시스템을 위한 양자 영감을 받은 클래식 알고리즘입니다. 컴퓨팅 이론에 관한 제51회 연례 ACM SIGACT 심포지엄 진행 중, STOC 2019, 페이지 217–228, 뉴욕, 뉴욕, 미국, 2019. 컴퓨팅 기계 협회. DOI: 10.1145/​3313276.3316310.
https : / /doi.org/ 10.1145 / 3313276.3316310

[7] N.-H. 치아, A. 길옌, T. 리, H.-H. 린, E. 탕, C. 왕. 양자 기계 학습을 역양자화하기 위한 샘플링 기반 하위선형 하위 행렬 산술 프레임워크, 387-400페이지. 컴퓨팅 기계 협회(Association for Computing Machinery), 뉴욕, 뉴욕, 미국, 2020. 온라인 이용 가능: https:/​/​doi.org/​10.1145/​3357713.3384314.
https : / /doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti 및 X. Wu. 선형 및 커널 기반 분류기를 훈련하기 위한 하위선형 양자 알고리즘입니다. 기계 학습에 관한 국제 회의, 3815~3824페이지. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo 및 Z. Holmes. 양자 커널 방법의 지수적 집중 및 훈련 불가능성, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz 및 N. Srebro. SVM 최적화: 훈련 세트 크기에 대한 역의존성. 제25회 기계 학습에 관한 국제 컨퍼런스 진행, 페이지 928-935, 2008.

[11] A. 톰센. 양자 신경망과 양자 지원 벡터 머신을 비교합니다. 석사 논문, ETH Zurich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon 및 VN Vapnik. 최적 마진 분류자를 위한 훈련 알고리즘. 계산 학습 이론에 관한 제92회 연례 워크숍 진행, COLT '144, 페이지 152–1992, 뉴욕, 뉴욕, 미국, 10.1145. 컴퓨터 기계 협회. DOI: 130385.130401/​XNUMX.
https : / /doi.org/ 10.1145 / 130385.130401

[13] C. Cortes 및 V. Vapnik. 지원 벡터 네트워크. 기계 학습, 273~297페이지, 1995년.

[14] VN Vapnik. 통계적 학습 이론의 본질. 스프링거 사이언스+비즈니스 미디어, LLC, 2000.

[15] F. Pedregosaet al. Scikit-learn: Python의 기계 학습. Journal of Machine Learning Research, 12(85):2825–2830, 2011. 온라인 이용 가능: http:/​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd와 L. Vandenberghe. 볼록 최적화. 캠브리지 대학 출판부, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro 및 A. Cotter. Pegasos: SVM용 기본 추정 하위 기울기 솔버입니다. 수학적 프로그래밍, 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. 키스킷: 양자 컴퓨팅을 위한 오픈 소스 프레임워크, 2021. DOI: 10.5281/​zenodo.2573505.
https : / /doi.org/ 10.5281 / zenodo.2573505

[19] P. Rebentrost, M. Mohseni 및 S. Lloyd. 빅데이터 분류를 위한 양자 지원 벡터 머신. 물리적 검토 편지, 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, B. Schölkopf. 양자 커널의 유도 바이어스. M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang 및 JW Vaughan 편집자, 신경 정보 처리 시스템의 발전, 34권, 12661~12673페이지. Curran Associates, Inc., 2021. 온라인 이용 가능: 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é 및 C. Ciuti. 시끄러운 양자 커널 기계. 물리. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https : / /doi.org/10.1103/ PhysRevA.106.052421

[22] CJC 버지와 CJC 버지. 패턴 인식을 위한 지원 벡터 머신에 대한 튜토리얼입니다. 데이터 마이닝 및 지식 검색, 2:121–167, 1998. 온라인 이용 가능: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-Vector -패턴 인식을 위한 기계/​.
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 및 PJ Coles. 얕은 매개변수화된 양자 회로의 비용 함수 의존 불모의 고원. 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 및 Reiter, Florentin. 양자 분류기를 이용한 힉스 분석. EPJ 웹 컨퍼런스, 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 및 PJ Coles. 변이 양자 알고리즘. 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. McGibbornet al. Quadprog: 2022차 프로그래밍 솔버(Python). https://​/​github.com/​quadprog/​quadprog, XNUMX.
https://​/​github.com/​quadprog/​quadprog

[27] Y. 네스테로프. 볼록 최적화에 대한 입문 강의: 기본 과정. 적용된 최적화. 스프링거, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. 스폴. 효율적인 최적화를 위한 동시 섭동 방법 개요. John Hopkins APL Technical Digest, 19(4), 페이지 482-492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter 및 S. Woerner. 원고 코드 "양자 지원 벡터 머신의 복잡성". 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 및 JJ Meyer. 단기 양자 컴퓨터에서 양자 임베딩 커널을 훈련합니다. 물리. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https : / /doi.org/10.1103/ PhysRevA.106.042431

[31] R. Latała. 랜덤 행렬의 규범에 대한 일부 추정치입니다. 미국수학학회 회보, 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. Vershynin. 무작위 행렬의 비점근적 분석 소개. 압축 감지: 이론 및 응용, 페이지 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https : / /doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf 및 AJ Smola. 기계 학습의 커널 방법. 통계 연보, 36(3):1171–1220, 2008. DOI: 10.1214/009053607000000677.
https : / /doi.org/ 10.1214 / 009053607000000677

[34] JW 다니엘. 명확한 5차 계획법의 해의 안정성. 수학 프로그래밍, 1(41):53–1973, 10.1007. DOI: 01580110/​BFXNUMX.
https : / /doi.org/ 10.1007 / BF01580110

인용

[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 및 Fernando GSL Brandão, "양자 알고리즘: 애플리케이션 및 엔드투엔드 복잡성 조사", arXiv : 2310.03011, (2023).

[2] Maria Schuld와 Nathan Killoran, "Quantum Advantage가 양자 기계 학습의 올바른 목표입니까?", PRX 퀀텀 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik 및 Ofer Lahav, "은하 분류를 위한 양자 강화 지원 벡터 머신", RAS 기술 및 도구 2 1, 752(2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung, Chen-Yu Liu, "GPU 가속을 통한 대규모 항성 분류를 위한 양자 강화 지원 벡터 머신", arXiv : 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo 및 Zoë Holmes, "양자 커널 방법의 지수 집중 및 훈련 불가능성", arXiv : 2208.11060, (2022).

[6] 나카지 코헤이, 테즈카 히로유키, 야마모토 나오키, “신경 탄젠트 커널 체제의 양자 고전 하이브리드 신경망”, 양자 과학 및 기술 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo 및 Rudy Raymond, "단기 양자 장치에 대한 양자 기계 학습: 실제 응용 프로그램을 위한 감독 및 비지도 기법의 현재 상태", arXiv : 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs 및 Nico Piatkowski, "Shapley 값을 사용한 양자 회로 설명: 설명 가능한 양자 기계 학습을 향하여", arXiv : 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner 및 Giuseppe Carleo, "양자 기하 텐서 없는 변이 양자 시간 진화", arXiv : 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller 및 Stefan Woerner, "확률적 경사하강법을 사용한 양자 커널 정렬", arXiv : 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie 및 Tim Scanlon, "양자 강화 지원 벡터 머신을 사용하여 하전 입자 추적 세그먼트 재구성", arXiv : 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick 및 Thomas Ward, "회로 실행 런타임 모델 및 실제 데이터 세트 크기에서 양자 커널에 대한 의미", arXiv : 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler 및 Stefan Woerner, "노이즈 샘플에서 계산된 노이즈 없는 기대값의 증명 가능한 한계", arXiv : 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus 및 Stefano Mensa, "양자 커널 정렬을 위한 효율적인 매개변수 최적화: 변형 훈련의 하위 샘플링 접근 방식" , arXiv : 2401.02879, (2024).

위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2024-01-12 02:12:22). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.

On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2024-01-12 02:12:21).

이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.

타임 스탬프 :

더보기 양자 저널