변형 양자 알고리즘의 확률적 최적화 프로그램에 대한 대기 시간 고려 사항

변형 양자 알고리즘의 확률적 최적화 프로그램에 대한 대기 시간 고려 사항

소스 노드 : 2015562

매트 메니켈리1, 하윤수2, 매튜 오튼3

1수학 및 컴퓨터 과학 부서, Argonne National Laboratory, 9700 S. Cass Ave., Lemont, IL 60439
2Edward P. Fitts 산업 및 시스템 공학과, North Carolina State University, 915 Partners Way, Raleigh, NC 27601
3HRL 연구소, LLC, 3011 Malibu Canyon Road, Malibu, CA 90265

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

추상

시끄러운 중간 규모 양자 설정에서 두드러진 변형 양자 알고리즘은 기존 하드웨어에서 확률적 최적화 프로그램을 구현해야 합니다. 지금까지 대부분의 연구는 확률적 고전적 옵티마이저로서 확률적 그래디언트 반복에 기반한 알고리즘을 사용했습니다. 이 작업에서 우리는 대신 고전적인 결정론적 알고리즘의 동역학을 에뮬레이트하는 확률적 프로세스를 생성하는 확률적 최적화 알고리즘을 사용할 것을 제안합니다. 이 접근 방식은 반복당 샘플(샷) 복잡성이 더 커지는 대신 이론적으로 최악의 경우 반복 복잡성이 더 우수한 방법을 만듭니다. 우리는 이론적으로나 경험적으로 이 트레이드오프를 조사하고 확률적 최적화 프로그램의 선택에 대한 선호도가 대기 시간과 샷 실행 시간의 함수에 명시적으로 의존해야 한다고 결론을 내립니다.

변형 양자 알고리즘은 단기 양자 컴퓨터에서 실제 문제를 해결하기 위한 유망한 후보입니다. 그러나 이러한 알고리즘을 최적화하는 프로세스는 1) 양자 컴퓨터에서 반복 측정(샷)을 수행하고 2) 양자 회로 매개변수를 조정해야 하기 때문에 계산 비용이 많이 들 수 있습니다. 여기서 우리는 샷을 수행하는 최적화에 소요되는 시간이 회로 조정을 수행하는 최적화에 소요되는 시간이 지배적이라는 가정하에 설계된 SHOALS(SHOt Adaptive Line Search)라는 새로운 확률적 최적화 알고리즘을 제안합니다. 우리는 SHOALS가 이 설정에서 다른 확률적 최적화 알고리즘을 능가한다는 것을 보여줍니다. 반대로 샷 시간이 회로 전환 시간과 유사할 때 확률적 경사하강법 알고리즘이 더 효율적인 것으로 나타났습니다. 샷 시간, 회로 전환 시간 및 최적화 알고리즘의 효율성 간의 트레이드 오프를 고려하여 변형 양자 알고리즘의 총 실행 시간을 크게 줄일 수 있음을 보여줍니다.

► BibTeX 데이터

► 참고 문헌

[1] Benjamin P Lanyon, James D Whitfield, Geoff G Gillett, Michael E Goggin, Marcelo P Almeida, Ivan Kassal, Jacob D Biamonte, Masoud Mohseni, Ben J Powell, Marco Barbieri 등. "양자 컴퓨터에서 양자 화학을 향하여". 자연 화학 2, 106–111 (2010).
https : / / doi.org/ 10.1038 / nchem.483

[2] Ian C Cloët, Matthew R Dietrich, John Arrington, Alexei Bazavov, Michael Bishof, Adam Freese, Alexey V Gorshkov, Anna Grassellino, Kawtar Hafidi, Zubin Jacob 등. "핵 물리학 및 양자 정보 과학을 위한 기회"(2019). arXiv:1903.05453.
arXiv : 1903.05453

[3] Adam Smith, MS Kim, Frank Pollmann 및 Johannes Knolle. "현재 디지털 양자 컴퓨터에서 양자 다체 동역학 시뮬레이션". npj 양자 정보 5, 1–13(2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[4] Benjamin Nachman, Davide Provasoli, Wibe A de Jong, Christian W Bauer. "고에너지 물리 시뮬레이션을 위한 양자 알고리즘". 물리적 검토 편지 126, 062001(2021).
https : / /doi.org/10.1103/ PhysRevLett.126.062001

[5] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, Seth Lloyd. "양자 기계 학습". 자연 549, 195–202(2017).
https : / /doi.org/ 10.1038 / nature23474

[6] 로만 오루스, 사무엘 무겔, 엔리케 리자소. "금융을 위한 양자 컴퓨팅: 개요 및 전망". Physics 4, 100028 (2019)의 리뷰.
https : / /doi.org/ 10.1016 / j.revip.2019.100028

[7] 존 프레스킬. "NISQ 시대와 그 이후의 양자 컴퓨팅". 퀀텀 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[8] U Dorner, R Demkowicz-Dobrzanski, BJ Smith, JS Lundeen, W Wasilewski, K Banaszek 및 IA Walmsley. "최적의 양자 위상 추정". Physical Review Letters 102, 040403(2009).
https : / /doi.org/10.1103/ PhysRevLett.102.040403

[9] 존 프레스킬. "내결함성 양자 계산". 양자 계산 및 정보 소개. 페이지 213–269. 세계 과학 (1998).

[10] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio 등. "변량 양자 알고리즘". Nature Reviews Physics페이지 1–20(2021).
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[11] Peter JJ O'Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding 등 "분자 에너지의 확장 가능한 양자 시뮬레이션". 물리적 검토 X 6, 031007(2016).
https : / /doi.org/10.1103/ PhysRevX.6.031007

[12] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li 및 Simon C Benjamin. "변동 양자 시뮬레이션 이론". 퀀텀 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[13] 매튜 오튼, 크리스티안 L 코르테스, 스티븐 K 그레이. "대칭 보존 ansatzes를 사용한 잡음 복원성 양자 역학"(2019). arXiv:1910.06284.
arXiv : 1910.06284

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, Jay M Gambetta. "소분자 및 양자 자석을 위한 하드웨어 효율적인 변형 양자 고유 솔버". 자연 549, 242–246(2017).
https : / /doi.org/ 10.1038 / nature23879

[15] 미타라이 코스케, 네고로 마코토, 키타가와 마사히로, 후지이 케이스케 "양자 회로 학습". 물리적 검토 A 98, 032309(2018).
https : / /doi.org/10.1103/ PhysRevA.98.032309

[16] Matthew Otten, Imène R Goumiri, Benjamin W Priest, George F Chapline, Michael D Schneider. "성능 양자 커널과 함께 가우시안 프로세스를 사용한 양자 기계 학습"(2020). arXiv:2004.11280.
arXiv : 2004.11280

[17] Robert M Parrish, Edward G Hohenstein, Peter L McMahon, Todd J Martínez. "변형 양자 고유 해결사를 사용한 전자 전이의 양자 계산". 물리적 검토 편지 122, 230401(2019).
https : / /doi.org/10.1103/ PhysRevLett.122.230401

[18] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush 및 Jarrod R McClean. "모델을 사용하여 변형 양자 알고리즘에 대한 옵티마이저 개선". 양자 과학 및 기술 5, 044008(2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb6d9

[19] Jay Gambetta, WA Braff, A Wallraff, SM Girvin 및 RJ Schoelkopf. "연속 양자 비파괴 측정을 사용하여 큐비트의 최적 판독을 위한 프로토콜". Physical Review A 76, 012325(2007).
https : / /doi.org/10.1103/ PhysRevA.76.012325

[20] Susan M Clark, Daniel Lobser, Melissa C Revelle, Christopher G Yale, David Bossert, Ashlyn D Burch, Matthew N Chow, Craig W Hogle, Megan Ivory, Jessica Pehr 등 "양자 과학 컴퓨팅 개방형 사용자 테스트베드 엔지니어링". 양자 공학에 관한 IEEE 트랜잭션 2, 1–32(2021).
https : / / doi.org/ 10.1109 / TQE.2021.3096480

[21] Colin D Bruzewicz, John Chiaverini, Robert McConnell, Jeremy M Sage. "갇힌 이온 양자 컴퓨팅: 진보와 도전". 응용 물리학 리뷰 6, 021314(2019).
https : / /doi.org/ 10.1063 / 1.5088164

[22] Jonas M Kübler, Andrew Arrasmith, Lukasz Cincio, Patrick J Coles. "측정 검소한 변이 알고리즘을 위한 적응형 옵티마이저". 퀀텀 4, 263(2020).
https:/​/​doi.org/​10.22331/​q-2020-05-11-263

[23] 디데릭 P 킹마와 지미 바. "Adam: 확률적 최적화를 위한 방법"(2014). arXiv:1412.6980.
arXiv : 1412.6980

[24] Trygve Helgaker, Poul Jorgensen 및 Jeppe Olsen. "분자 전자 구조 이론". 존 와일리 & 선즈. (2014).
https : / /doi.org/ 10.1002 / 9781119019572

[25] 톰 스카울, 이오아니스 안토노글루, 데이비드 실버. "확률적 최적화를 위한 단위 테스트". Yoshua Bengio 및 Yann LeCun, 편집자, 학습 표현에 관한 2차 국제 회의, ICLR 2014, 캐나다 AB 밴프, 14년 16월 2014-2014일, Conference Track Proceedings. (1312.6055). URL: http://arxiv.org/abs/XNUMX.
arXiv : 1312.6055

[26] 힐랄 아시와 존 C 두치. "확률적 최적화에서 더 나은 모델의 중요성". 국립 과학 아카데미 절차 116, 22924–22930 (2019).
https : / /doi.org/ 10.1073 / pnas.1908018116

[27] Billy Jin, Katya Scheinberg 및 Miaolan Xie. "확률적 오라클을 기반으로 한 라인 검색을 위한 높은 확률 복잡성 범위"(2021). arXiv:2106.06454.
arXiv : 2106.06454

[28] Jose Blanchet, Coralia Cartis, Matt Menickelly 및 Katya Scheinberg. "슈퍼마팅게일을 통한 확률적 신뢰 영역 방법의 수렴률 분석". INFORMS 최적화 저널 1, 92–119(2019).
https://doi.org/10.1287/ijoo.2019.0016

[29] Courtney Paquette와 Katya Scheinberg. "예상 복잡도 분석을 통한 확률적 선 탐색 방법". 최적화에 관한 SIAM 저널 30, 349–376(2020).
https : / //doi.org/10.1137/ 18M1216250

[30] Albert S Berahas, Liyuan Cao, Katya Scheinberg. "잡음이 있는 일반 라인 탐색 알고리즘의 전역 수렴률 분석". 최적화에 관한 SIAM 저널 31, 1489–1518(2021).
https : / //doi.org/10.1137/ 19M1291832

[31] Coralia Cartis, Nicholas IM Gould 및 Ph L Toint. "가장 가파른 하강법의 복잡성에 대해, 비볼록 비제약 최적화 문제에 대한 Newton 및 정규화된 Newton의 방법". Siam 저널 최적화 20, 2833–2852(2010).
https : / /doi.org/ 10.1137 / 090774100

[32] Coralia Cartis, Nicholas IM Gould 및 Philippe L Toint. "매끄러운 비볼록 최소화를 위한 22차 및 미분 없는 알고리즘의 오라클 복잡성에 대해". 최적화에 관한 SIAM 저널 66, 86–2012(XNUMX).
https : / /doi.org/ 10.1137 / 100812276

[33] Yair Carmon, John C Duchi, Oliver Hinder, Aaron Sidford. "정지점을 찾기 위한 하한 I". 수학 프로그래밍 184, 71–120(2020).
https : / /doi.org/ 10.1007 / s10107-019-01406-y

[34] Yair Carmon, John C Duchi, Oliver Hinder, Aaron Sidford. ""유죄가 입증될 때까지 볼록": 볼록하지 않은 함수에 대한 경사 하강법의 무차원 가속". 기계 학습에 관한 국제 회의에서. 페이지 654–663. PMLR(2017).
https : / /doi.org/ 10.5555 / 3305381.3305449

[35] Chi Jin, Praneeth Nettrapalli, Michael I Jordan. "가속 경사하강법은 경사하강법보다 더 빨리 안장 지점을 탈출합니다." 학습 이론 회의에서. 페이지 1042–1085. PMLR(2018). URL: https:///proceedings.mlr.press/v75/ jin18a.html.
https://proceedings.mlr.press/v75/jin18a.html

[36] 사이드 가디미와 광후이 란. "비볼록 확률적 프로그래밍을 위한 확률적 23차 및 2341차 방법". SIAM 최적화 저널 2368, 2013–XNUMX (XNUMX).
https : / /doi.org/ 10.1137 / 120880811

[37] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth. "볼록하지 않은 확률적 최적화의 하한"(2019). arXiv:1912.02365.
arXiv : 1912.02365

[38] Cong Fang, Chris Junchi Li, Zhouchen Lin 및 Tong Zhang. "스파이더: 확률적 경로 통합 미분 추정기를 통한 최적에 가까운 비볼록 최적화". S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi 및 R. Garnett 편집자, Advances in Neural Information Processing Systems. 31권. Curran Associates, Inc.(2018). URL: https://proceedings.neurips.cc/paper/2018/file/1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​1543843a4723ed2ab08e18053ae6dc5b-Paper.pdf

[39] 타미야 시로와 야마사키 하야타. "확률적 경사선 베이지안 최적화: 매개변수화된 양자 회로 최적화에서 측정 샷 감소"(2021). arXiv:2111.07952.
https:/​/​doi.org/​10.1038/​s41534-022-00592-6
arXiv : 2111.07952

[40] 파스쿠알 조던과 유진 폴 위그너. "über das paulische äquivalenzverbot". Eugene Paul Wigner의 전집에서. 109~129쪽. 스프링거(1993).

[41] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac 및 Nathan Killoran. "양자 하드웨어에서 분석 기울기 평가". 물리적 검토 A 99, 032331(2019).
https : / /doi.org/10.1103/ PhysRevA.99.032331

[42] 이준호, William J Huggins, Martin Head-Gordon, K Birgitta Whaley. "양자 계산을 위한 일반화된 단일 결합 클러스터 파동 함수". 화학 이론 및 계산 저널 15, 311–324 (2018).
https : / /doi.org/ 10.1021 / acs.jctc.8b01004

[43] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, Jeremy L O'brien. "광양자 프로세서의 변이 고유치 솔버". 자연 커뮤니케이션 5, 1–7(2014). URL: https://doi.org/10.1038/ncomms5213.
https : / /doi.org/ 10.1038 / ncomms5213

[44] Ilya G Ryabinkin, Tzu-Ching Yen, Scott N Genin, Artur F Izmaylov. "큐빗 결합 클러스터 방법: 양자 컴퓨터에서 양자 화학에 대한 체계적인 접근". 화학 이론 및 계산 저널 14, 6317–6326(2018).
https : / /doi.org/ 10.1021 / acs.jctc.8b00932

[45] Ho Lun Tang, VO Shkolnikov, George S Barron, Harper R Grimsley, Nicholas J Mayhall, Edwin Barnes, Sophia E Economou. "qubit-ADAPT-VQE: 양자 프로세서에서 하드웨어 효율적인 응답을 구성하기 위한 적응형 알고리즘". PRX 퀀텀 2, 020310(2021).
https : / / doi.org/ 10.1103 / PRXQuantum.2.020310

[46] Dmitry A. Fedorov, Yuri Alexeev, Stephen K. Gray, Matthew Otten. "단일 선택적 결합 클러스터 방법". 퀀텀 6, 703(2022).
https:/​/​doi.org/​10.22331/​q-2022-05-02-703

[47] Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, Frederic T Chong. "$ o (n^3) $ 분자 해밀턴에 대한 변이 양자 고유 솔버의 측정 비용". 양자 공학에 관한 IEEE 트랜잭션 1, 1–24(2020).
https : / / doi.org/ 10.1109 / TQE.2020.3035814

[48] Ruobing Chen, Matt Menickelly, Katya Scheinberg. "트러스트 영역 방법과 무작위 모델을 사용한 확률적 최적화". 수학 프로그래밍 169, 447–487(2018).
https:/​/​doi.org/​10.1007/​s10107-017-1141-8

[49] Léon Bottou, Frank E Curtis, Jorge Nocedal. "대규모 기계 학습을 위한 최적화 방법". 시암 리뷰 60, 223–311(2018).
https : / //doi.org/10.1137/ 16M1080173

[50] 요엘 드로리와 오하드 샤미르. "확률적 경사하강법으로 정지점을 찾는 복잡성". 기계 학습에 관한 국제 회의에서. 페이지 2658–2667. PMLR(2020). URL: https://proceedings.mlr.press/v119/drori20a.html.
https://proceedings.mlr.press/v119/drori20a.html

[51] Cong Fang, Zhouchen Lin 및 Tong Zhang. "안장점에서 벗어나는 비볼록 SGD에 대한 날카로운 분석". 학습 이론 회의에서. 페이지 1192–1234. PMLR(2019). URL: https://proceedings.mlr.press/v99/fang19a.html.
https://proceedings.mlr.press/v99/fang19a.html

[52] S Reddi, Manzil Zaheer, Devendra Sachan, Satyen Kale 및 Sanjiv Kumar. "비볼록 최적화를 위한 적응 방법". 신경 정보 처리 시스템에 관한 32차 회의 진행(NIPS 2018). (2018). URL: https://proceedings.neurips.cc/paper/2018/file/90365351ccc7437a1309dc64e4db32a3-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2018/​file/​90365351ccc7437a1309dc64e4db32a3-Paper.pdf

[53] Léon Bottou와 Olivier Bousquet. "대규모 학습의 장단점". J. Platt, D. Koller, Y. Singer 및 S. Roweis 편집자, Advances in Neural Information Processing Systems. 20권. Curran Associates, Inc.(2007). URL: https://proceedings.neurips.cc/paper/2007/file/0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2007/​file/​0d3180d672e08b4c5312dcdafdf6ef36-Paper.pdf

[54] Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan, Marcus P da Silva, Robert S Smith. "변형 하이브리드 알고리즘에 최적화된 양자 고전 클라우드 플랫폼". 양자 과학 및 기술 5, 024003(2020).
https : / /doi.org/ 10.1088 / 2058-9565 / ab7559

[55] HJ Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac, Peter Zoller. "중립 원자를 사용한 양자 컴퓨팅". 현대 광학 저널 47, 415–451 (2000).
https : / /doi.org/ 10.1080 / 09500340008244052

[56] Sergey Bravyi, Jay M Gambetta, Antonio Mezzacapo, Kristan Temme. "페르미온성 해밀턴을 시뮬레이션하기 위해 큐비트 테이퍼링"(2017). arXiv:1701.08213.
arXiv : 1701.08213

[57] MD SAJID ANIS, Héctor Abraham, AduOffei, Rochisha Agarwal, Gabriele Agliardi, Merav Aharoni, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Sashwat Anagolum, Eli Arbel, Abraham Asfaw, Anish Athalye, Artur Avkhadiev 등 "Qiskit: 양자 컴퓨팅을 위한 오픈 소스 프레임워크"(2021).

[58] Ciyou Zhu, Richard H Byrd, Peihuang Lu, Jorge Nocedal. "알고리즘 778: L-BFGS-B: 대규모 경계 제약 최적화를 위한 Fortran 서브루틴". 수학적 소프트웨어(TOMS)에 대한 ACM 트랜잭션 23, 550–560(1997).
https : / /doi.org/ 10.1145 / 279232.279236

[59] 라구 볼라프라가다, 리처드 버드, 호르헤 노세달. "확률적 최적화를 위한 적응 샘플링 전략". SIAM 최적화 저널 28, 3312–3343(2018).
https : / //doi.org/10.1137/ 17M1154679

[60] Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, Ping Tak Peter Tang. "기계 학습을 위한 프로그레시브 일괄 처리 L-BFGS 방법". 기계 학습에 관한 국제 회의에서. 페이지 620–629. PMLR(2018). URL: https:/ / proceedings.mlr.press/ v80/ bollapragada18a.html.
https:/ / proceedings.mlr.press/ v80/ bollapragada18a.html

[61] Raghu Pasupathy, Peter Glynn, Soumyadip Ghosh, Fatemeh S Hashemi. "시뮬레이션 기반 재귀의 샘플링 속도". SIAM 최적화 저널 28, 45–73(2018).
https : / /doi.org/ 10.1137 / 140951679

[62] Andrew Arrasmith, Lukasz Cincio, Rolando D Somma, Patrick J Coles. "변형 알고리즘에서 샷 검소한 최적화를 위한 연산자 샘플링"(2020). arXiv:2004.06252.
arXiv : 2004.06252

[63] Yangyang Xu와 Wotao Yin. "볼록 및 비볼록 최적화를 위한 블록 확률적 그래디언트 반복". 최적화에 관한 SIAM 저널 25, 1686–1716 (2015).
https : / /doi.org/ 10.1137 / 140983938

인용

[1] Matt Menickelly, Stefan M. Wild, Miaolan Xie, "공통 난수가 없는 확률적 준뉴턴 방법", arXiv : 2302.09128, (2023).

[2] Kosuke Ito, "런타임 효율적인 변형 양자 알고리즘을 위한 대기 시간 인식 적응형 샷 할당", arXiv : 2302.04422, (2023).

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

가져올 수 없습니다 Crossref 인용 자료 마지막 시도 중 2023-03-16 18:30:43 : Crossref에서 10.22331 / q-2023-03-16-949에 대한 인용 데이터를 가져올 수 없습니다. DOI가 최근에 등록 된 경우 이는 정상입니다.

타임 스탬프 :

더보기 양자 저널