1QuSoft, 암스테르담, 네덜란드.
2네덜란드 암스테르담 대학.
3네덜란드 암스테르담 대학.
이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.
추상
브란 당과 스 보어 [14] 최근에 대략 정체되는 프로그램을 해결하기위한 양자 알고리즘을 제공했는데, 일부 영역에서는 문제의 $ n $ 차원과 제약의 $ m $ 차원에서 가장 가능한 고전적인 알고리즘보다 빠르지 만 다양한 측면에서 더 나쁘다. 다른 매개 변수. 이 백서에서는 알고리즘을 여러 가지 방법으로 개선하여 다른 매개 변수에 더 잘 의존합니다. 이를 위해 양자 알고리즘을위한 새로운 기술, 예를 들어 스파 스 해밀턴 (Sparse Hamiltonian)의 부드러운 기능을 효율적으로 구현하는 일반적인 방법과 일반화 된 최소 찾기 절차를 개발합니다.
또한 양자 SDP- 솔버에 대한 이러한 접근 방식에 대한 제한을 보여줍니다 (예 : 대칭이 많은 조합 최적화 문제). 마지막으로, 우리는 최악의 경우, 모든 맵 LPx 솔버 (SDP 솔버)의 복잡성이 $ mapprox n $와 같을 때 $ mn $로 선형으로 확장되어야 함을 보여주는 일반적인 하한을 증명합니다. 고전.
인기 요약
► BibTeX 데이터
► 참고 문헌
[1] Sanjeev Arora, Elad Hazan 및 Satyen Kale. 곱하기 가중치 업데이트 방법 : 메타 알고리즘 및 응용 프로그램. toc, 8 (6) : 121–164, 2012.
https : / /doi.org/ 10.4086 / toc.2012.v008a006
[2] Sanjeev Arora 및 Satyen Kale. 준정의 프로그램에 대한 조합 적, 기본 이중 접근. jacm, 63 (2) : 12 : 1–12 : 35, 2016. STOC'07의 이전 버전.
https : / /doi.org/ 10.1145 / 2837020
[3] 안드리 암바 이니스. 요소 구별을위한 양자 보행 알고리즘. siamjc, 37 (1) : 210–239, 2007. FOCS'04의 이전 버전. arXiv : quant-ph / 0311001 ?.
https : / /doi.org/ 10.1137 / S0097539705447311
arXiv : 퀀트 -PH / 0311001
[4] Joran van Apeldoorn과 András Gilyén. 응용 프로그램을 사용한 양자 SDP 해결 개선. icalp46th, 99 : 1–99 : 15, 2019 페이지. arXiv : 1804.05058 ?.
https : / /doi.org/10.4230/LIPIcs.ICALP.2019.99
arXiv : 1804.05058
[5] Joran van Apeldoorn과 András Gilyén. 제로섬 게임을위한 양자 알고리즘. arXiv : 1904.03180 ?, 2019.
arXiv : 1904.03180
[6] Joran van Apeldoorn, András Gilyén, Sander Gribling 및 Ronald de Wolf. 양자 SDP- 솔버 : 더 나은 상한 및 하한. focs58th, 403–414, 2017 페이지. arXiv : 1705.01843 ?.
https : / /doi.org/10.1109/FOCS.2017.44
arXiv : 1705.01843
[7] Joran van Apeldoorn, András Gilyén, Sander Gribling 및 Ronald de Wolf. 양자 오라클을 사용한 볼록 최적화. 양자, 4 : 220, 2020. arXiv : 1809.00643 ?.
https://doi.org/10.22331/q-2020-01-13-220
arXiv : 1809.00643
[8] 노가 알론과 조엘 H. 스펜서. 확률 적 방법. Wiley-Interscience, 2008 년 제 XNUMX 판.
https : / /doi.org/ 10.1002 / 0471722154
[9] Michel Boyer, Gilles Brassard, Peter Høyer 및 Alain Tapp. 양자 검색에 대한 엄격한 한계. Fortschritte der Physik, 46 (4–5) : 493–505, 1998. arXiv : quant-ph / 9605034 ?.
arXiv : 퀀트 -PH / 9605034
[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari 및 Rolando D. Somma. 잘린 Taylor 시리즈로 Hamiltonian 역학을 시뮬레이션합니다. prl, 114 (9) : 090502, 2015. arXiv : 1412.4687 ?.
https : / /doi.org/10.1103/ PhysRevLett.114.090502
arXiv : 1412.4687
[11] Dominic W. Berry, Andrew M. Childs 및 Robin Kothari. 모든 매개 변수에 거의 최적으로 의존하는 Hamiltonian 시뮬레이션. focs56th, 페이지 792–809, 2015. arXiv : 1501.01715 ?.
https : / /doi.org/10.1109/FOCS.2015.54
arXiv : 1501.01715
[12] Gilles Brassard, Peter Høyer, Michele Mosca 및 Alain Tapp. 양자 진폭 증폭 및 추정. 양자 계산 및 양자 정보 : 밀레니엄 볼륨, 현대 수학 시리즈 305 권, 53–74 페이지. AMS, 2002. arXiv : quant-ph / 0005055 ?.
https : / /doi.org/10.1090/conm/305/05215
arXiv : 퀀트 -PH / 0005055
[13] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore 및 Xiaodi Wu. 퀀텀 SDP 솔버 : 퀀텀 학습을위한 빠른 속도, 최적 성 및 응용 프로그램. icalp46th, 27 년 1 : 27–14 : 2019, arXiv : 1710.02581 ?.
https : / /doi.org/10.4230/LIPIcs.ICALP.2019.27
arXiv : 1710.02581
[14] Fernando GSL Brandão와 Krysta M. Svore. 반 정확한 프로그램을 해결하기위한 양자 속도 향상. focs58th, 페이지 415–426, 2017. arXiv : 1609.05537 ?.
https : / /doi.org/10.1109/FOCS.2017.45
arXiv : 1609.05537
[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li 및 Xiaodi Wu. 볼록 최적화를위한 양자 알고리즘 및 하한. 양자, 4 : 221, 2020. arXiv : 1809.01731 ?.
https://doi.org/10.22331/q-2020-01-13-221
arXiv : 1809.01731
[16] Richard Cleve, Artur Ekert, Chiara Macchiavello 및 Michele Mosca. 양자 알고리즘 재검토. rspa, 454 (1969) : 339–354, 1998. arXiv : quant-ph / 9708016 ?.
https : / /doi.org/ 10.1098 / rspa.1998.0164
arXiv : 퀀트 -PH / 9708016
[17] Andrew M. Childs, Robin Kothari 및 Rolando D. Somma. 정밀도에 기하 급수적으로 개선 된 선형 방정식 시스템의 양자 알고리즘. siamjc, 46 (6) : 1920–1950, 2017. arXiv : 1511.02306 ?.
https : / //doi.org/10.1137/ 16M1087072
arXiv : 1511.02306
[18] Anirban Narayan Chowdhury 및 Rolando D. Somma. Gibbs 샘플링 및 적중 시간 추정을위한 양자 알고리즘. qic, 17 (1 & 2) : 41–64, 2017. arXiv : 1603.02940 ?.
https : / /doi.org/ 10.26421 / QIC17.1-2
arXiv : 1603.02940
[19] Andrew M. Childs와 Nathan Wiebe. 단일 연산의 선형 조합을 사용한 해밀턴 시뮬레이션. qic, 12 (11 & 12) : 901–924, 2012. arXiv : 1202.5822 ?.
https : / /doi.org/ 10.26421 / QIC12.11-12
arXiv : 1202.5822
[20] 조지 B. 단치히. 선형 부등식에 종속되는 변수의 선형 함수 최대화. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, 339페이지
-347. John Wiley & Sons Inc., 뉴욕, 뉴욕, 1951.
[21] 크리스토프 뒤르와 피터 호이어. 최소값을 찾기위한 양자 알고리즘. arXiv : quant-ph / 9607014 ?, 1996.
arXiv : 퀀트 -PH / 9607014
[22] Christoph Dürr, Mark Heiligman, Peter Høyer 및 Mehdi Mhalla. 일부 그래프 문제의 양자 쿼리 복잡성. siamjc, 35 (6) : 1310–1328, 2006. ICALP'04의 이전 버전. arXiv : quant-ph / 0401091 ?.
https : / /doi.org/ 10.1137 / 050644719
arXiv : 퀀트 -PH / 0401091
[23] Martin Grötschel, László Lovász 및 Alexander Schrijver. 타원체 방법과 조합 최적화의 결과. 빗, 1 (2) : 169–197, 1981.
https : / /doi.org/ 10.1007 / BF02579273
[24] Martin Grötschel, László Lovász 및 Alexander Schrijver. 기하 알고리즘 및 조합 최적화. 1988 년 스프링거.
[25] 로브 그로버와 테리 루돌프. 효율적으로 통합 가능한 확률 분포에 해당하는 중첩을 만듭니다. arXiv : quant-ph / 0208112 ?, 2002.
arXiv : 퀀트 -PH / 0208112
[26] 로브 K. 그로버. 데이터베이스 검색을위한 빠른 양자 역학 알고리즘. stoc28th, 페이지 212–219, 1996. arXiv : quant-ph / 9605043 ?.
https : / /doi.org/ 10.1145 / 237814.237866
arXiv : 퀀트 -PH / 9605043
[27] 안드라 길리 엔, 위안 수, 광 하오 로우, 나단 위베. 양자 특이 값 변환 및 그 이상 : 양자 행렬 산술을위한 지수 개선. stoc51st, 페이지 193–204, 2019. arXiv : 1806.01838 ?.
https : / /doi.org/ 10.1145 / 3313276.3316366
arXiv : 1806.01838
[28] Michel X. Goemans와 David P. Williamson. 반정의 프로그래밍을 사용하여 최대 절단 및 만족도 문제에 대한 개선 된 근사 알고리즘. jacm, 42 (6) : 1115–1145, 1995. STOC'94의 이전 버전.
https : / /doi.org/ 10.1145 / 227683.227684
[29] Aram W. Harrow, Avinatan Hassidim 및 Seth Lloyd. 선형 방정식 시스템을위한 양자 알고리즘. prl, 103 (15) : 150502, 2009. arXiv : 0811.3171 ?.
https : / /doi.org/10.1103/ PhysRevLett.103.150502
arXiv : 0811.3171
[30] 셸비 킴멜. 양자 대적 (상한) cjtcs, 2013 : 4 : 1–14, 2013. ICALP'12의 이전 버전. arXiv : 1101.0797 ?.
https : / /doi.org/ 10.4086 / cjtcs.2013.004
arXiv : 1101.0797
[31] Subhash Khot, Guy Kindler, Elchanan Mossel 및 Ryan O'Donnell. MAX-CUT 및 기타 2 변수 CSP에 대한 최적의 근사치 결과? siamjc, 37 (1) : 319–357, 2007. FOCS'04의 이전 버전.
https : / /doi.org/ 10.1137 / S0097539705447372
[32] Iordanis Kerenidis와 Anupam Prakash. LP 및 SDP를위한 양자 내부 포인트 방법. arXiv : 1808.09266 ?, 2018.
arXiv : 1808.09266
[33] Guang Hao Low 및 Isaac L. Chuang. 양자 신호 처리에 의한 최적의 해밀턴 시뮬레이션. prl, 118 (1) : 010501, 2017. arXiv : 1606.02685 ?.
https : / /doi.org/10.1103/ PhysRevLett.118.010501
arXiv : 1606.02685
[34] Guang Hao Low 및 Isaac L. Chuang. qubitization에 의한 해밀턴 시뮬레이션. 퀀텀, 3 : 163, 2019. arXiv : 1610.06546 ?.
https://doi.org/10.22331/q-2019-07-12-163
arXiv : 1610.06546
[35] Yin Tat Lee, Aaron Sidford 및 Sam Chiu-wai Wong. 보다 빠른 절단면 방법과 조합 및 볼록 최적화에 대한 영향. focs56th, 1049–1065, 2015 페이지. arXiv : 1508.04874 ?.
https : / /doi.org/10.1109/FOCS.2015.68
arXiv : 1508.04874
[36] Michael A. Nielsen과 Isaac L. Chuang. 양자 계산 및 양자 정보. 케임브리지 대학 출판부, 2000.
https : / /doi.org/ 10.1017 / CBO9780511976667
[37] Y. Nesterov와 A. Nemirovski. 볼록 프로그래밍의 내부 포인트 다항식 알고리즘, 응용 수학에서의 SIAM 연구의 13 권. 산업 및 응용 수학 학회 (SIAM), 1994.
https : / /doi.org/ 10.1137 / 1.9781611970791
[38] David Poulin과 Pawel Wocjan. 양자 컴퓨터에서 양자 다체 시스템의 지상 상태를 준비합니다. prl, 102 (13) : 130503, 2009. arXiv : 0809.2705 ?.
https : / /doi.org/10.1103/ PhysRevLett.102.130503
arXiv : 0809.2705
[39] David Poulin과 Pawel Wocjan. 열 양자 깁스 상태에서 샘플링하고 양자 컴퓨터로 파티션 기능을 평가합니다. prl, 103 (22) : 220502, 2009. arXiv : 0905.2199 ?.
https : / /doi.org/10.1103/ PhysRevLett.103.220502
arXiv : 0905.2199
[40] 제임스 레네가 일반적인 볼록 최적화를위한 "효율적인"하위 그라데이션 방법. siamjc, 26 (4) : 2649–2676, 2016. arXiv : 1605.08712 ?.
https : / //doi.org/10.1137/ 15M1027371
arXiv : 1605.08712
[41] 제임스 레네가 쌍곡선 프로그래밍을위한 가속화 된 173 차 방법. 수학 프로그래밍, 1 (1) : 35–2019, 1512.07569. arXiv : XNUMX ?.
https : / /doi.org/ 10.1007 / s10107-017-1203-y
arXiv : 1512.07569
[42] Alexander Schrijver. 선형 및 정수 프로그래밍 이론. John Wiley & Sons, Inc., 미국 뉴욕 주 뉴욕, 1986 년.
[43] 피터 더블 류 양자 컴퓨터에서 소인수 분해 및 이산 로그를위한 다항식 시간 알고리즘. siamjc, 26 (5) : 1484–1509, 1997. FOCS'94의 이전 버전. arXiv : quant-ph / 9508027 ?.
https : / /doi.org/ 10.1137 / S0097539795293172
arXiv : 퀀트 -PH / 9508027
[44] Koji Tsuda, Gunnar Rätsch 및 Manfred K. Warmuth. 온라인 학습 및 Bregman 투영을위한 매트릭스 지수 형 그래디언트 업데이트. 기계 학습 연구 저널, 6 : 995–1018, 2005. NIPS'04의 이전 버전.
http : / /jmlr.csail.mit.edu/papers/volume6/tsuda05a/tsuda05a.pdf
[45] Manfred K. Warmuth와 Dima Kuzmin. 온라인 차이 최소화. Machine Learning, 87 (1) : 1–32, 2012. COLT'06의 이전 버전.
https://doi.org/10.1007/s10994-011-5269-0
인용
[1] András Gilyén, Yuan Su, Guang Hao Low 및 Nathan Wiebe,“Quantum 특이 값 변환 및 그 이상 : 양자 행렬 산술을위한 지수 개선”, arXiv : 1806.01838.
[2] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini 및 Leonard Wossnig,“Quantum machine learning : 고전적인 관점”, 런던 왕립 학회 시리즈 A 474 2209, 20170551 (2018)의 절차.
[3] Patrick Rebentrost와 Seth Lloyd,“Quantum 전산 금융 : 포트폴리오 최적화를위한 양자 알고리즘”, arXiv : 1811.03975.
[4] Joran van Apeldoorn과 András Gilyén,“제로섬 게임을위한 퀀텀 알고리즘”, arXiv : 1904.03180.
[5] András Gilyén, Srinivasan Arunachalam 및 Nathan Wiebe,“더 빠른 양자 구배 계산을 통한 양자 최적화 알고리즘 최적화”, arXiv : 1711.00465.
[6] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione 및 Seth Lloyd,“제한된 다항식 최적화를위한 양자 구배 하강 및 뉴턴의 방법”, arXiv : 1612.01789.
[7] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore 및 Xiaodi Wu,“Quantum SDP Solvers : 큰 속도 향상, 최적화 및 양자 학습에의 응용 프로그램”, arXiv : 1710.02581.
[8] Joran van Apeldoorn과 András Gilyén,“응용 프로그램을 사용한 Quantum SDP-Solving 개선”, arXiv : 1804.05058.
[9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin 및 Chunhao Wang,“샘플링 접근을 통해 낮은 순위의 반정의 프로그래밍을 해결하기위한 퀀텀에서 영감을 얻은 클래식 하위 선형 시간 알고리즘”, arXiv : 1901.03254.
[10] Simon Apers,“성장하는 종자 세트에 의한 퀀텀 워크 샘플링”, arXiv : 1904.11446.
[11] Joran van Apeldoorn, András Gilyén, Sander Gribling 및 Ronald de Wolf,“양자 oracles를 사용한 볼록 최적화”, arXiv : 1809.00643.
[12] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li 및 Xiaodi Wu,“볼록 최적화를위한 퀀텀 알고리즘 및 하한값”, arXiv : 1809.01731.
[13] Yimin Ge, Jordi Tura 및 J. Ignacio Cirac,“더 적은 큐빗으로 더 빠른 지상 상태 준비 및 고정밀 지상 에너지 추정”, arXiv : 1712.03193.
[14] Ivan Bardet와 Cambyse Rouzé,“비 원시적 양자 마르코프 반군에 대한 하이퍼 컨트리 러 빌리티 및 로그 소볼 레프 불평등과 디코 히 런스 비율 추정”, arXiv : 1803.05379.
[15] Ashley Montanaro,“분기 및 바운드 알고리즘의 퀀텀 속도 향상”, arXiv : 1906.10375.
[16] Johannes Bausch, Sathyawageeswar Subramanian 및 Stephen Piddock,“자연 언어 처리를위한 양자 검색 디코더”, arXiv : 1909.05023.
위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2020-02-14 09:28:14). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.
가져올 수 없습니다 Crossref 인용 자료 마지막 시도 중 2020-02-14 09:28:13 : Crossref에서 10.22331 / q-2020-02-14-230에 대한 인용 데이터를 가져올 수 없습니다. DOI가 최근에 등록 된 경우 이는 정상입니다.
이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.
