제한된 다항식 이진 최적화를위한 Grover 적응 형 검색

타임 스탬프 : 8 년 2021 월 10 일 오전 04:XNUMX
소스 노드 : 806213

오스틴 길리엄1, 스테판 워너2및 콘스탄틴 곤치울레아1

1JP 모건 체이스 (JPMorgan Chase)
2IBM Quantum, IBM Research – 취리히

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

추상

본 논문에서는 CPBO(Constrained Polynomial Binary Optimization) 문제에 대한 GAS(Grover Adaptive Search) 문제, 특히 QUBO(Quadratic Unconstrained Binary Optimization) 문제를 특수 사례로 논의합니다. GAS는 무차별 대입 검색에 비해 조합 최적화 문제에 대해 XNUMX차 속도 향상을 제공할 수 있습니다. 그러나 이를 위해서는 특정 검색 기준을 충족하는 문제와 기국을 나타내는 효율적인 오라클의 개발이 필요합니다. 일반적으로 이는 양자 산술을 사용하여 달성할 수 있지만 이는 Toffoli 게이트 및 필요한 앤실라 큐비트 측면에서 비용이 많이 들고 단기적으로는 불가능할 수 있습니다. 이 작업에서 우리는 GAS 알고리즘을 사용하여 CPBO 문제를 해결하기 위해 효율적인 오라클을 구성하는 방법을 개발합니다. 우리는 실제 양자 하드웨어에서 얻은 시뮬레이션과 실험 결과를 사용하여 이러한 접근 방식과 포트폴리오 최적화 문제, 즉 QUBO에 대한 잠재적인 속도 향상을 보여줍니다. 그러나 우리의 접근 방식은 제한된 최적화 문제뿐만 아니라 더 높은 수준의 다항식 목적 함수에도 적용됩니다.

주요 이미지: 두 번의 반복에 대한 GAS의 출력 확률은 Grover 연산자의 각 임계값 $y$ 및 $r$ 적용을 사용하여 실제 양자 하드웨어에서 실행됩니다. 유효한 측정 결과는 파란색으로 표시되고, 유효하지 않은 측정 결과는 회색으로 표시됩니다.

인기 요약

본 논문에서는 CPBO(Constrained Polynomial Binary Optimization) 문제에 대한 GAS(Grover Adaptive Search) 문제, 특히 QUBO(Quadratic Unconstrained Binary Optimization) 문제를 특수 사례로 논의합니다. GAS는 무차별 대입 검색에 비해 조합 최적화 문제에 대해 XNUMX차 속도 향상을 제공할 수 있습니다. 그러나 이를 위해서는 특정 검색 기준을 충족하는 문제와 기국을 나타내는 효율적인 오라클의 개발이 필요합니다. 일반적으로 이는 양자 산술을 사용하여 달성할 수 있지만 이는 Toffoli 게이트 및 필요한 앤실라 큐비트 측면에서 비용이 많이 들고 단기적으로는 불가능할 수 있습니다. 이 작업에서 우리는 GAS 알고리즘을 사용하여 CPBO 문제를 해결하기 위해 효율적인 오라클을 구성하는 방법을 개발합니다. 우리는 실제 양자 하드웨어에서 얻은 시뮬레이션과 실험 결과를 사용하여 이러한 접근 방식과 포트폴리오 최적화 문제, 즉 QUBO에 대한 잠재적인 속도 향상을 보여줍니다. 그러나 우리의 접근 방식은 제한된 최적화 문제뿐만 아니라 더 높은 수준의 다항식 목적 함수에도 적용됩니다.

► BibTeX 데이터

► 참고 문헌

[1] 러브 K. 그로버. 데이터베이스 검색을 위한 빠른 양자 역학 알고리즘입니다. 컴퓨팅 이론에 관한 제96회 연례 ACM 심포지엄 진행, STOC '212, 페이지 219-1996, 뉴욕, 뉴욕, 미국, 0. ACM. ISBN 89791-785-5-10.1145. 237814.237866/​XNUMX.
https : / /doi.org/ 10.1145 / 237814.237866

[2] 피터 W. 쇼어. 양자 컴퓨터의 소인수분해 및 이산 로그를 위한 다항식 시간 알고리즘입니다. SIAM 컴퓨팅 저널, 26(5): 1484-1509, 1997년 1095월. ISSN 7111-10.1137. 0097539795293172/sXNUMX.
https : / /doi.org/ 10.1137 / s0097539795293172

[3] BP Lanyon, JD Whitfield, GG Gillett, ME Goggin, MP Almeida, I. Kassal, JD Biamonte, M. Mohseni, BJ Powell, M. Barbieri 등 양자 컴퓨터의 양자 화학을 향하여. 자연 화학, 2(2): 106–111, 2010년 1755월. ISSN 4349-10.1038. 483/​nchem.XNUMX.
https : / / doi.org/ 10.1038 / nchem.483

[4] 아람 W. 해로우(Aram W. Harrow), 아비나탄 하시딤(Avinatan Hassidim), 세스 로이드(Seth Lloyd). 선형 방정식 시스템을 위한 양자 알고리즘. 실제 검토 서한, 103(15), 2009년 1079월. ISSN 7114-10.1103. 103.150502/physrevlett.XNUMX.
https : / //doi.org/10.1103/ physrevlett.103.150502

[5] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio 및 Patrick J. Coles. 가변 양자 선형 솔버, 2020. URL https : / / arxiv.org/ abs / 1909.05820.
arXiv : 1909.05820

[6] 패트릭 레벤트로스트, 브라제시 굽트, 토마스 R. 브롬리. 양자 계산 금융: 금융 파생상품의 몬테카를로 가격 책정. 물리. A, 98: 022321, 2018년 10.1103월. 98.022321/​PhysRevA.XNUMX.
https : / /doi.org/10.1103/ PhysRevA.98.022321

[7] 스테판 워너(Stefan Woerner)와 다니엘 J. 에거(Daniel J. Egger). 양자 위험 분석. npj Quantum Information, 5: 15, 2019. 10.1038/​s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[8] DJ Egger, R. Garcia Gutierrez, J. Cahue Mestre 및 S. Woerner. 양자컴퓨터를 이용한 신용위험 분석. 컴퓨터에서의 IEEE 트랜잭션, 1~1페이지, 2020. 10.1109/​TC.2020.3038063.
https : / /doi.org/10.1109/ TC.2020.3038063

[9] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen 및 Stefan Woerner. 양자 컴퓨터를 사용한 옵션 가격 책정. Quantum, 4: 291, 2020년 2521월. ISSN 327-10.22331X. 2020/q-07-06-291-XNUMX.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291

[10] 에드워드 파리, 제프리 골드스톤, 샘 구트만. 양자 근사 최적화 알고리즘, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv : 1411.4028

[11] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man Hong Yung, Xiao Qi Zhou, Peter J. Love, Alán Aspuru-Guzik 및 Jeremy L. O'Brien. 광자 양자 프로세서의 변형 고유값 솔버. Nature Communications, 5: 4213, 2014. ISSN 20411723. 10.1038/​ncomms5213.
https : / /doi.org/ 10.1038 / ncomms5213

[12] 자코모 난니치니. 조합 최적화를 위한 하이브리드 양자-고전적 변이 휴리스틱 성능. 물리적 검토 E, 99: 013304, 2019년 10.1103월. 99.013304/​PhysRevE.XNUMX.
https : / /doi.org/10.1103/ PhysRevE.99.013304

[13] 파나기오티스 Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli 및 Stefan Woerner. cvar를 사용하여 변이 양자 최적화를 개선합니다. Quantum, 4: 256, 2020년 2521월. ISSN 327-10.22331X. 2020/q-04-20-256-XNUMX.
https:/​/​doi.org/​10.22331/​q-2020-04-20-256

[14] L. Braine, DJ Egger, J. Glick 및 S. Woerner. 거래 결제에 적용되는 혼합 바이너리 최적화를 위한 양자 알고리즘. 양자 공학에 관한 IEEE 거래, 2: 1–8, 2021. 10.1109/​TQE.2021.3063635.
https : / / doi.org/ 10.1109 / TQE.2021.3063635

[15] 앤드류 M 차일즈, 에드워드 파리, 존 프레스킬. 단열 양자 계산의 견고성. 물리적 검토 A, 65(1): 012322, 2001. 10.1103/​PhysRevA.65.012322.
https : / /doi.org/10.1103/ PhysRevA.65.012322

[16] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk 등 제조된 스핀을 이용한 양자 어닐링. Nature, 473 (7346): 194–198, 2011. 10.1038/nature10012.
https : / /doi.org/ 10.1038 / nature10012

[17] 크리스토프 뒤르(Christoph Dürr)와 피터 회이어(Peter Høyer). 최소값을 찾기 위한 양자 알고리즘, 1996. URL https:/​/​arxiv.org/​abs/​Quant-ph/​9607014.
arXiv : 퀀트 -PH / 9607014

[18] D. Bulger, WP Baritompa 및 GR Wood. Grover의 양자 알고리즘을 사용하여 순수 적응 검색을 구현합니다. 최적화 이론 및 응용 저널, 116(3): 517–529, 2003년 1573월. ISSN 2878-10.1023. 1023061218864/A:XNUMX.
https : / /doi.org/ 10.1023 / A : 1023061218864

[19] WP Baritompa, DW Bulger 및 GR Wood. Grover의 양자 알고리즘이 전역 최적화에 적용되었습니다. SIAM J. on Optimization, 15(4): 1170–1184, 2005년 1052월. ISSN 6234-10.1137. 040605072/XNUMX.
https : / /doi.org/ 10.1137 / 040605072

[20] Austin Gilliam, Charlene Venci, Sreraman Muralidharan, Vitaliy Dorum, Eric May, Rajesh Narasimhan 및 Constantin Gonciulea. 효율적인 양자 컴퓨팅을 위한 기본 패턴, 2019. URL https:/​/​arxiv.org/​abs/​1907.11513.
arXiv : 1907.11513

[21] 토마스 G. 드레이퍼. 양자 컴퓨터에 대한 추가, 2000. URL https:/​/​arxiv.org/​abs/​Quant-ph/​0008033.
arXiv : 퀀트 -PH / 0008033

[22] 로만 오루스, 사무엘 무겔, 엔리케 리자소. 금융을 위한 양자 컴퓨팅: 개요 및 전망. 물리학 리뷰, 4: 100028, 2019년 2405월. ISSN 4283-10.1016. 2019.100028/j.revip.XNUMX.
https : / /doi.org/ 10.1016 / j.revip.2019.100028

[23] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner 및 Elena Yndurain. 금융을 위한 양자 컴퓨팅: 최첨단 및 미래 전망. 양자 공학에 관한 IEEE 거래, 1: 1–24, 2020a. ISSN 2689-1808. 10.1109/tqe.2020.3030314.
https : / / doi.org/ 10.1109 / tqe.2020.3030314

[24] 패트릭 레벤트로스트와 세스 로이드. 양자 컴퓨터 금융: 포트폴리오 최적화를 위한 양자 알고리즘, 2018. URL https:/​/​arxiv.org/​abs/​1811.03975.
arXiv : 1811.03975

[25] 다비데 벤투렐리(Davide Venturelli)와 알렉세이 콘드라티예프(Alexei Kondratyev). 포트폴리오 최적화 문제에 대한 역양자 어닐링 접근법. 양자 기계 지능, 1, 2019. 10.1007/​s42484-019-00001-w.
https : / /doi.org/ 10.1007 / s42484-019-00001-w

[26] Daniel J. Egger, Jakub Marecek, Stefan Woerner. 웜 스타트 양자 최적화, 2020b. URL https:/​/​arxiv.org/​abs/​2009.10095.
arXiv : 2009.10095

[27] 헥터 아브라함 외. 알. Qiskit: 양자 컴퓨팅을 위한 오픈 소스 프레임워크입니다. 2019. 10.5281/​zenodo.2562110.
https : / /doi.org/ 10.5281 / zenodo.2562110

[28] 미셸 모스카. 고유벡터 분석을 통한 양자 검색, 계산 및 진폭 증폭. In Proceedings of Randomized Algorithms, Workshop of Mathematical Foundations of Computer Science, 페이지 90–100, 1998. URL https:/​/​eccc.weizmann.ac.il/​/​resources/​pdf/​moscafi.pdf.
https:/​/​eccc.weizmann.ac.il/​/​resources/​pdf/​moscafi.pdf

[29] Gilles Brassard, Peter Hoyer, Michele Mosca 및 Alain Tapp. 양자 진폭 증폭 및 추정. 현대수학, 305, 2002. 10.1090/​conm/​305.
https : / /doi.org/10.1090/conm/ 305

[30] 스즈키 요히치, 우노 슌페이, 루디 레이먼드, 다나카 토모키, 오노데라 타미야, 야마모토 나오키. 위상 추정 없이 진폭 추정. 양자 정보 처리, 19(2), 2020년 1573월. ISSN 1332-10.1007. 11128/s019-2565-2-XNUMX.
https:/​/​doi.org/​10.1007/​s11128-019-2565-2

[31] 스콧 아론슨과 패트릭 Rall. 양자 근사 계산이 단순화되었습니다. 알고리즘의 단순성에 관한 심포지엄, 24~32페이지, 2020년 10.1137월. 1.9781611976014.5/​XNUMX.
https : / /doi.org/ 10.1137 / 1.9781611976014.5

[32] Michel Boyer, Gilles Brassard, Peter Høyer 및 Alain Tapp. 양자 검색의 경계가 엄격합니다. Fortschritte der Physik, 46(4-5): 493–505, 1998년 1521월. ISSN 3978-10.1002. 1521/(SICI)3978-199806(46)4:5/​493<493::AID-PROP3.0>2.CO;XNUMX-P.
[33] 벤하민 바란과 마르코스 비야그라. 다중 목표 최적화 Grover 적응형 검색, 191~211페이지. 스프링거 국제 출판, 참, 2019. ISBN 978-3-319-99648-6. 10.1007/​978-3-319-99648-6_11.
https:/​/​doi.org/​10.1007/​978-3-319-99648-6_11

[34] 남윤성, 유안수, 드미트리 마슬로프. o(n log(n)) t 게이트를 사용한 대략적인 양자 푸리에 변환. npj Quantum Information, 6 (1), 2020년 2056월. ISSN 6387-10.1038. 41534/s020-0257-5-XNUMX.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[35] 스티븐 A. 쿠카로, 토마스 G. 드레이퍼, 사무엘 A. 쿠틴, 데이비드 페트리 몰튼. 새로운 양자 리플 캐리 추가 회로, 2004. URL https:/​/​arxiv.org/​abs/​Quant-ph/​0410184.
arXiv : 퀀트 -PH / 0410184

[36] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains 및 Krysta M. Svore. 로그 깊이 양자 캐리-예측 가산기입니다. 양자 정보. Comput., 6(4): 351–369, 2006년 1533월. ISSN 7146-10.26421. 6.4/​QIC5-4-XNUMX.
https : / / doi.org/ 10.26421 / QIC6.4-5-4

[37] 크레이그 기 드니. 양자 추가 비용을 절반으로 줄입니다. Quantum, 2:74, 2018 년 2521 월. ISSN 327-10.22331X. 2018 / q-06-18-74-XNUMX.
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[38] Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation 및 Jay M. Gambetta. 무작위 모델 회로를 사용하여 양자 컴퓨터를 검증합니다. 실제 검토 A, 100(3), 2019년 2469월. ISSN 9934-10.1103. 100.032328/physreva.XNUMX.
https : / /doi.org/10.1103/ physreva.100.032328

[39] A. Dewes, FR Ong, V. Schmitt, R. Lauro, N. Boulant, P. Bertet, D. Vion 및 D. Esteve. 개별 싱글샷 큐비트 판독 기능을 갖춘 108트랜스몬 프로세서의 특성화. 물리. Lett., 057002: 2012, 10.1103년 108.057002월. XNUMX/​PhysRevLett.XNUMX.
https : / /doi.org/10.1103/ PhysRevLett.108.057002

[40] 스반테 얀슨. 감마 유형의 순간과 브라운니안 최고 프로세스 영역. 확률. 설문조사, 7: 1–52, 2010. 10.1214/10-PS160.
https:/​/​doi.org/​10.1214/​10-PS160

[41] 마이클 A. 닐슨과 아이작 L. 추앙. 양자 계산 및 양자 정보: 10주년 기념판. Cambridge University Press, 뉴욕, 뉴욕, 미국, 10판, 2011. ISBN 1107002176, 9781107002173. 10.1017/​CBO9780511976667.
https : / /doi.org/ 10.1017 / CBO9780511976667

인용

[1] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner 및 Elena Yndurain, "금융을 위한 양자 컴퓨팅: 최신 기술 및 미래 전망", arXiv : 2006.14510.

[2] Claudio Gambella 및 Andrea Simonetto, "클래식 및 양자 컴퓨터의 혼합 바이너리 최적화를 위한 다중 블록 ADMM 휴리스틱", arXiv : 2001.02069.

[3] Austin Gilliam, Marco Pistoia 및 Constantin Gonciulea, "Grover 알고리즘의 일반화된 버전을 사용하여 양자 검색 최적화", arXiv : 2005.06468.

[4] Austin Gilliam, Marco Pistoia 및 Constantin Gonciulea, "양자 오라클의 정식 구성", arXiv : 2006.10656.

[5] Austin Gilliam, Marco Pistoia 및 Constantin Gonciulea, "그로버 알고리즘의 이항 버전으로 양자 검색 최적화", arXiv : 2007.10894.

[6] Julien Gacon, Christa Zoufal, Giuseppe Carleo 및 Stefan Woerner, "양자 피셔 정보의 동시 섭동 확률 적 근사", arXiv : 2103.09232.

[7] Sayantan Pramanik, M Girish Chandra, Shampa Sarkar 및 Manoj Nambiar, “수정된 Grover 알고리즘을 사용한 근사 위상 검색 및 고유 추정”, arXiv : 2012.11497.

[8] 장수연, Steven Herbert, Sofia Vallecorsa, Elías F. Combarro 및 Ross Duncan, "고에너지 물리학의 이중 매개변수화된 양자 회로 GAN 모델", arXiv : 2103.15470.

[9] Marika Svensson, Martin Andersson, Mattias Grönkvist, Pontus Vikstål, Devdatt Dubhashi, Giulia Ferrini 및 Göran Johansson, "분기 및 가격을 양자 알고리즘과 결합하여 대규모 정수 선형 프로그램을 해결하는 경험적 방법", arXiv : 2103.15433.

[10] Yidong Liao, Min-Hsiu Hsieh 및 Chris Ferrie, "양자 신경망 훈련을위한 양자 최적화", arXiv : 2103.17047.

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

On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2021-04-10 02:42:03).

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

출처 : https://quantum-journal.org/papers/q-2021-04-08-428/

타임 스탬프 :

더보기 양자 저널