1Alfred Rényi 수학 연구소
2어도비 리서치
3워싱턴 대학
이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.
추상
우리는 낮은 순위 행렬[Wossnig, Zhao, and Prakash, Physical Review Letters'09]에 대한 양자 행렬 반전 알고리즘[Harrow, Hassidim, and Lloyd, Physical Review Letters'18]과 유사한 선형 회귀에 대한 고전적인 알고리즘을 제공합니다. 입력 행렬 $A$는 QRAM 기반 상태 준비에 적용 가능한 데이터 구조에 저장됩니다.
즉, Mathbb의 $b와 함께 특정 효율적인 $ell_2$-norm 중요도 샘플링 쿼리를 지원하는 6이 아닌 최소 특이값 $sigma$와 함께 mathbb{C}^{mtimes n}$에 $A가 있다고 가정합니다. {C}^m$. 그런 다음, mathbb{C}^n$의 일부 $x에 대해 $|x – A^+b| leq varepsilon|A^+b|$, 계산 기반에서 $|xrangle$의 측정값을 출력하고 $tilde{mathcal{O}}big(frac{ |A|_{수학{F}}^6|A|^12}{sigma^{4}varepsilon^6}큰)$ 및 $tilde{수학{O}}큰(frac{|A|_{수학 {F}}^2|A|^8}{sigma^4varepsilon^16}big)$ 시간입니다. 이것은 적어도 $frac{|A|^{16}}{sigma^{2}varepsilon^20}$ [Chia, Gilyén, Li, Lin, Tang 및 Wang, STOC'12]. 결과적으로 우리는 양자 컴퓨터가 이 QRAM 데이터 구조 설정 및 관련 설정에서 선형 회귀에 대해 최대 XNUMX배의 속도 향상을 달성할 수 있음을 보여줍니다. 우리의 작업은 스케치 알고리즘 및 최적화의 기술을 양자 영감 문헌에 적용합니다. 이전 작업과 달리 이것은 미래의 양자 컴퓨터와 비교하기 위해 양자에서 영감을 받은 설정에서 고전 회귀의 실현 가능한 구현으로 이어질 수 있는 유망한 방법입니다.
주요 이미지: 이 작업에서 달성한 알고리즘의 복잡성과 함께 Chia, Gilyén, Li, Lin, Tang, Wang이 작성한 양자 영감 선형 회귀(초록에 설명된 대로)를 위한 이전 최고의 알고리즘의 계산 복잡성. 두 알고리즘 모두 보다 일반적인 설정에서 작동하지만(이전 작업은 보다 강력한 회귀 개념에 적용할 수 있으며 이 작업은 정규화를 지원함) 이 설정으로 제한해도 비교에 큰 영향을 미치지 않습니다.
인기 요약
► BibTeX 데이터
► 참고 문헌
[1] 존 프리스킬. “NISQ 시대와 그 이후의 양자 컴퓨팅”. 양자 2, 79(2018). arXiv:1801.00862.
https://doi.org/10.22331/q-2018-08-06-79
arXiv : 1801.00862
[2] 앤드류 M 차일즈. "시뮬레이션에 의한 방정식 풀이". 자연 물리학 5, 861–861(2009).
https : / /doi.org/ 10.1038 / nphys1473
[3] 스콧 아론슨. "작은 글씨를 읽으십시오". 자연 물리학 11, 291–293(2015).
https : / /doi.org/ 10.1038 / nphys3272
[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe 및 Seth Lloyd. "양자 머신 러닝". 네이처 549, 195–202 (2017). arXiv:1611.09347.
https : / /doi.org/ 10.1038 / nature23474
arXiv : 1611.09347
[5] Aram W. Harrow, Avinatan Hassidim 및 Seth Lloyd. "선형 방정식 시스템을 위한 양자 알고리즘". Physical Review Letters 103, 150502(2009). arXiv:0811.3171.
https : / /doi.org/10.1103/ PhysRevLett.103.150502
arXiv : 0811.3171
[6] András Gilyén, Yuan Su, Guang Hao Low 및 Nathan Wiebe. "양자 특이값 변환 및 그 이상: 양자 행렬 산술의 기하급수적 개선". 제 51회 ACM 컴퓨팅 이론 심포지엄(STOC)의 절차에서. 193~204페이지. (2019). arXiv:1806.01838.
https : / /doi.org/ 10.1145 / 3313276.3316366
arXiv : 1806.01838
[7] 비토리오 지오바네티, 세스 로이드, 로렌조 맥콘. "양자 랜덤 액세스 메모리". Physical Review Letters 100, 160501(2008). arXiv:0708.1879.
https : / /doi.org/10.1103/ PhysRevLett.100.160501
arXiv : 0708.1879
[8] 아누팜 프라카시. "선형 대수 및 기계 학습을 위한 양자 알고리즘". 박사 논문. 버클리 캘리포니아 대학교. (2014). URL: www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.pdf.
https:///www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.pdf
[9] Nai-Hui Chia, Andras Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang. "양자 기계 학습을 역양자화하기 위한 샘플링 기반 하위 선형 하위 행렬 산술 프레임워크". 컴퓨팅 이론(STOC)에 관한 제52회 ACM 심포지엄의 절차에서. 387~400페이지. (2020). arXiv:1910.06151.
https : / /doi.org/ 10.1145 / 3357713.3384314
arXiv : 1910.06151
[10] Iordanis Kerenidis와 Anupam Prakash. "양자 추천 시스템". 제8회 혁신 이론 컴퓨터 과학 컨퍼런스(ITCS)의 회보에서. 페이지 49:1–49:21. (2017). arXiv:1603.08675.
https : / /doi.org/10.4230/ LIPIcs.ITCS.2017.49
arXiv : 1603.08675
[11] 에윈 탕. "추천 시스템을 위한 양자 기반 고전 알고리즘". 제 51회 ACM 컴퓨팅 이론 심포지엄(STOC)의 절차에서. 217~228페이지. (2019). arXiv:1807.04271.
https : / /doi.org/ 10.1145 / 3313276.3316310
arXiv : 1807.04271
[12] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, Anupam Prakash. "q-means: 비지도 머신 러닝을 위한 양자 알고리즘". 신경 정보 처리 시스템의 발전. 32권. (2019). arXiv:1812.03584.
arXiv : 1812.03584
[13] Iordanis Kerenidis와 Anupam Prakash. "선형 시스템 및 최소 제곱에 대한 양자 경사 하강법". 물리적 검토 A 101, 022316(2020). arXiv:1704.04992.
https : / /doi.org/10.1103/ PhysRevA.101.022316
arXiv : 1704.04992
[14] 다니엘 더보비치, 마크 허브스터, 피터 마운트니, 시몬 세베리니, 나이리 어셔, 레너드 보스니그. "양자 선형 시스템 알고리즘: 입문서"(2018). arXiv:1802.08227.
arXiv : 1802.08227
[15] Leonard Wossnig, Zhikuan Zhao, Anupam Prakash. "조밀한 행렬을 위한 양자 선형 시스템 알고리즘". Physical Review Letters 120, 050502(2018). arXiv:1704.06174.
https : / /doi.org/10.1103/ PhysRevLett.120.050502
arXiv : 1704.06174
[16] 패트릭 레벤트로스트, 마수드 모세니, 세스 로이드. "빅 데이터 분류를 위한 양자 지원 벡터 머신". Physical Review Letters 113, 130503(2014). arXiv:1307.0471.
https : / /doi.org/10.1103/ PhysRevLett.113.130503
arXiv : 1307.0471
[17] Shantanav Chakraborty, András Gilyén 및 Stacey Jeffery. "블록으로 인코딩된 행렬의 힘: 더 빠른 해밀턴 시뮬레이션을 통한 개선된 회귀 기술". Automata, 언어 및 프로그래밍에 관한 제46회 국제 콜로키움(ICALP)의 회보에서. 33:1–33:14 페이지. (2019). arXiv:1804.01973.
https : / /doi.org/10.4230/LIPIcs.ICALP.2019.33
arXiv : 1804.01973
[18] Nai-Hui Chia, Andras Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, Chunhao Wang. "차원에 대한 로그 의존성을 갖는 하위 선형 방정식 시스템을 풀기 위한 양자에서 영감을 받은 알고리즘". 알고리즘 및 계산에 관한 제31회 국제 심포지엄(ISAAC)의 절차에서. 페이지 47:1–47:17. (2020). arXiv:1811.04852 및 1811.04909(통합).
https:// / doi.org/ 10.4230/ LIPIcs.ISAAC.2020.47
arXiv:1811.04852 및 1811.04909
(병합)
[19] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan 및 Seth Lloyd. "실제 양자에서 영감을 받은 알고리즘". 퀀텀 4, 307(2020). arXiv:1905.10415.
https://doi.org/10.22331/q-2020-08-13-307
arXiv : 1905.10415
[20] 에윈 탕. "양자 주성분 분석은 상태 준비 가정으로 인해 기하급수적인 속도 향상을 달성합니다." Physical Review Letters 127, 060503(2021). arXiv:1811.00414.
https : / /doi.org/10.1103/ PhysRevLett.127.060503
arXiv : 1811.00414
[21] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, Leonard Wossnig. "양자 기계 학습: 고전적 관점". 왕립학회 회보 A: 수리, 물리 및 공학 과학 474, 20170551(2018). arXiv:1707.08561.
https : / /doi.org/ 10.1098 / rspa.2017.0551
arXiv : 1707.08561
[22] Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, Priyaa Varshinee Srinivasan. "버킷 여단 양자 RAM의 견고성". New Journal of Physics 17, 123010(2015). arXiv:1502.03450.
https://doi.org/10.1088/1367-2630/17/12/123010
arXiv : 1502.03450
[23] 네하 굽타와 아론 시드포드. "효율적인 학습을 위한 수치 희소성 활용: 더 빠른 고유 벡터 계산 및 회귀". 신경 정보 처리 시스템의 발전. 페이지 5269–5278. (2018). arXiv:1811.10866.
arXiv : 1811.10866
[24] Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian. "매트릭스 게임을 위한 조정 방법". 2020년 IEEE 61번째 연례 컴퓨터 과학 기초 심포지엄(FOCS). 283~293페이지. IEEE(2020). arXiv:2009.08447.
https:///doi.org/10.1109/focs46700.2020.00035
arXiv : 2009.08447
[25] 세바스티앙 부벡. "볼록 최적화: 알고리즘과 복잡성". 기계 학습의 기초 및 동향 8, 231–357(2015). arXiv:1405.4980.
https : / /doi.org/ 10.1561 / 2200000050
arXiv : 1405.4980
[26] Roy Frostig, Rong Ge, Sham Kakade, Aaron Sidford. "비정규화: 경험적 위험 최소화를 위한 근사적 근접점 및 더 빠른 확률론적 알고리즘". 기계 학습에 관한 국제 회의에서. 2540-2548 페이지. (2015). arXiv:1506.07512.
arXiv : 1506.07512
[27] 프란시스 바흐와 에릭 물린. "기계 학습을 위한 확률적 근사 알고리즘의 비점근적 분석". 신경 정보 처리 시스템의 발전. 451~459페이지. (2011). URL: http:///papers.nips.cc/paper/4316-non-asymptotic-analysis-of-stochastic-approximation-algorithms-for-machine-learning.pdf.
http:///papers.nips.cc/paper/4316-non-asymptotic-analysis-of-stochastic-approximation-algorithms-for-machine-learning.pdf
[28] András Gilyén, Seth Lloyd, Ewin Tang. "차원에 대한 로그 의존성을 갖는 양자에서 영감을 받은 낮은 순위 확률적 회귀"(2018). arXiv:1811.04909.
arXiv : 1811.04909
[29] Nai-Hui Chia, Han-Hsuan Lin 및 Chunhao Wang. "하위 선형 시스템을 해결하기 위한 양자에서 영감을 받은 하위 선형 클래식 알고리즘"(2018). arXiv:1811.04852.
arXiv : 1811.04852
[30] 데이비드 P. 우드럽 "수치 선형 대수학을 위한 도구로서의 스케치". 이론적 컴퓨터 과학의 기초 및 동향 10, 1–157(2014).
https : / /doi.org/ 10.1561 / 0400000060
[31] Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin 및 David P. Woodruff. "무작위 수치 선형 대수학의 양자 영감 알고리즘"(2020). arXiv:2011.04125.
arXiv : 2011.04125
[32] 창펑 샤오와 애슐리 몬타나로. "선형 시스템을 풀기 위한 더 빠른 양자 영감 알고리즘"(2021). arXiv:2103.10309.
arXiv : 2103.10309
[33] 토마스 스트로머와 로만 베르쉬닌. "지수 수렴을 사용한 무작위 Kaczmarz 알고리즘". 푸리에 분석 및 응용 저널 15, 262–278(2008). arXiv:math/0702226.
https://doi.org/10.1007/s00041-008-9030-4
arXiv : 수학 / 0702226
[34] 디아나 니델, 네이선 스레브로, 레이첼 워드. "확률적 경사 하강법, 가중 샘플링 및 무작위 Kaczmarz 알고리즘". 수학 프로그래밍 155, 549–573(2015). arXiv:1310.5715.
https://doi.org/10.1007/s10107-015-0864-7
arXiv : 1310.5715
[35] Petros Drineas, Ravi Kannan 및 Michael W Mahoney. "행렬 II에 대한 고속 몬테카를로 알고리즘: 행렬에 대한 낮은 순위 근사값 계산". 컴퓨팅에 관한 SIAM 저널 36, 158–183(2006).
https : / /doi.org/ 10.1137 / S0097539704442696
인용
[1] Quynh T. Nguyen, Bobak T. Kiani, Seth Lloyd, "계층적 행렬을 사용하는 밀집 및 전체 순위 커널에 대한 양자 알고리즘", arXiv : 2201.11329.
[2] Benjamin A. Cordier, Nicolas PD Sawaya, Gian G. Guerreschi 및 Shannon K. McWeeney, "양자 이점의 환경에서 생물학 및 의학", arXiv : 2112.00760.
[3] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis 및 Anupam Prakash, "양자 금융의 전망과 과제", arXiv : 2011.06492.
[4] Amirhossein Nourbakhsh, Mark Nicholas Jones, Kaur Kristjuhan, Deborah Carberry, Jay Karon, Christian Beenfeldt, Kyarash Shahriari, Martin P. Andersson, Mojgan A. Jadidi, Seyed Soheil Mansouri, "양자 컴퓨팅: 기초, 추세 및 전망 화학 및 생화학 엔지니어", arXiv : 2201.02823.
[5] Xiao-Ming Zhang, Tongyang Li 및 Xiao Yuan, "최적 회로 깊이를 사용한 양자 상태 준비: 구현 및 응용", arXiv : 2201.11495.
[6] Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun 및 Patrick Rebentrost, "최적화된 Hadamard 테스트를 사용한 치우친 선형 시스템을 위한 양자 고전 알고리즘", 물리적 검토 A 103 4, 042422 (2021).
[7] Iordanis Kerenidis 및 Anupam Prakash, "부분공간 상태를 사용한 양자 기계 학습", arXiv : 2202.00054.
[8] Changpeng Shao와 Ashley Montanaro, "선형 시스템을 풀기 위한 더 빠른 양자 영감 알고리즘", arXiv : 2103.10309.
[9] Patrick Rall, "위상, 에너지 및 진폭 추정을위한 더 빠른 일관된 양자 알고리즘", arXiv : 2103.09717.
[10] Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin 및 David P. Woodruff, "무작위 수치 선형 대수학의 양자 영감 알고리즘", arXiv : 2011.04125.
[11] Armando Bellante, Alessandro Luongo 및 Stefano Zanero, "데이터 표현 및 분석을 위한 양자 알고리즘", arXiv : 2104.08987.
[12] Daniel Chen, Yekun Xu, Betis Baheri, Samuel A. Stein, Chuan Bi, Ying Mao, Qiang Quan 및 Shuai Xu, "저속 특징 분석을 위한 양자 영감 고전 알고리즘", arXiv : 2012.00824.
[13] Sevag Gharibian 및 François Le Gall, "양자 특이값 변환 역양자화: 경도 및 양자 화학 및 양자 PCP 추측에 대한 응용", arXiv : 2111.09079.
[14] Chenyi Zhang, Jiaqi Leng, Tongyang Li, "안장점에서 탈출하기 위한 양자 알고리즘", arXiv : 2007.10253.
[15] Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, Kazuyoshi Yoshino, "양자 진폭 추정에 의한 선형 회귀 및 볼록 최적화로의 확장", 물리적 검토 A 104 2, 022430 (2021).
[16] Franco D. Albareti, Thomas Ankenbrand, Denis Bieri, Esther Hänggi, Damian Lötscher, Stefan Stettler 및 Marcel Schöngens, "금융 산업을 위한 양자 컴퓨팅의 구조적 조사", arXiv : 2204.10026.
[17] Ebrahim Ardeshir-Larijani, "양자 영감 알고리즘의 매개변수화 복잡성", arXiv : 2112.11686.
[18] Shantanav Chakraborty, Aditya Morolia 및 Anurudh Peduri, "양자 정규화 최소 제곱", arXiv : 2206.13143.
위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2022-06-30 13:00:28). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.
가져올 수 없습니다 Crossref 인용 자료 마지막 시도 중 2022-06-30 13:00:26 : Crossref에서 10.22331 / q-2022-06-30-754에 대한 인용 데이터를 가져올 수 없습니다. DOI가 최근에 등록 된 경우 이는 정상입니다.
이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.
