맞춤형 믹서를 사용한 웜 스타트 QAOA는 낮은 회로 깊이에서 Goemans-Williamson의 Max-Cut을 수렴하고 계산적으로 능가함을 입증했습니다.

맞춤형 믹서를 사용한 웜 스타트 QAOA는 낮은 회로 깊이에서 Goemans-Williamson의 Max-Cut을 수렴하고 계산적으로 능가함을 입증했습니다.

루벤 테이트1, 자이 문드라2, 브라이언 가드3, 그렉 몰러3스와티 굽타4

1CCS-3 정보 과학, Los Alamos National Laboratory, Los Alamos, NM 87544, USA
2조지아 공과 대학, 애틀랜타, GA 30332, 미국
3조지아 기술 연구소, 애틀랜타, GA 30332, 미국
4슬론 경영대학원, 매사추세츠 공과대학, 케임브리지, MA 02142, 미국

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

추상

우리는 Farhi 등의 QAOA(Quantum Approximate Optimization Algorithm)를 일반화합니다. (2014)은 시작 상태가 혼합 해밀턴의 가장 여기된 상태가 되도록 해당 믹서를 사용하여 임의의 분리 가능한 초기 상태를 허용합니다. 우리는 가중치 그래프에서 Max-Cut을 시뮬레이션하여 $QAOA-warmest$라고 부르는 이 버전의 QAOA를 시연합니다. 우리는 Max-Cut의 준정의 프로그램에 대한 해의 무작위 투영을 사용하여 얻은 $2$ 및 $3$ 차원 근사치를 사용하여 시작 상태를 $warm-start$로 초기화하고 Warm-start 종속 $custom 믹서$를 정의합니다. 우리는 이러한 웜 스타트가 음수가 아닌 에지 가중치를 갖는 그래프에 대해 $0.658$ 차원의 경우 $2$, $0.585$ 차원의 경우 $3$의 상수 인자 근사값으로 QAOA 회로를 초기화하여 이전에 알려진 사소한 방법을 개선한다는 것을 보여줍니다( 즉, 표준 초기화의 경우 $0.5$) 최악의 경우 $p=0$입니다. 실제로 이러한 요인은 더 높은 회로 깊이에서 Max-Cut에 대해 달성된 근사치를 하한으로 설정합니다. 왜냐하면 분리 가능한 초기 상태를 갖는 QAOA-warmest가 $prightarrow infty$와 같은 단열 한계 하에서 Max-Cut에 수렴한다는 것을 보여주기 때문입니다. 그러나 Warm-Start의 선택은 Max-Cut으로의 수렴 속도에 큰 영향을 미치며, 우리는 Warm-Start가 기존 접근 방식에 비해 더 빠른 수렴을 달성한다는 것을 경험적으로 보여줍니다. 또한 수치 시뮬레이션에서는 표준 QAOA, 고전적인 Goemans-Williamson 알고리즘 및 $1148$ 그래프(최대 $11$ 노드) 및 깊이 $p=8의 인스턴스 라이브러리에 대한 맞춤형 믹서가 없는 웜 스타트 QAOA에 비해 더 높은 품질 컷을 보여줍니다. $. 우리는 또한 QAOA-warmest가 Farhi 등의 표준 QAOA보다 성능이 우수하다는 것을 보여줍니다. 현재 IBM-Q 및 Quantinuum 하드웨어에 대한 실험에서.

QAOA(양자 근사 최적화 알고리즘)는 조합 최적화를 위한 하이브리드 양자-고전 기술로, 어떤 기존 최적화 도구보다 더 강력할 것으로 예상됩니다. 이 연구에서 우리는 Max-Cut으로 알려진 기본적인 조합 최적화 문제에 대한 잠재력을 예시합니다. 여기서 가능한 최고의 고전 알고리즘은 Goemans 및 Williamson(GW)의 알고리즘입니다. 우리는 수정된 혼합 연산자를 사용하여 QAOA에 고전적으로 얻은 웜 스타트를 도입하고 이것이 GW보다 성능이 우수하다는 것을 계산적으로 보여줌으로써 이를 달성합니다. 우리는 양자 단열 컴퓨팅과의 연결을 유지하기 위해 양자 알고리즘을 적절하게 수정합니다. 우리는 이론을 논의하고 우리 접근 방식의 가능성을 보여주는 수치 및 실험적 증거를 제공합니다.

► BibTeX 데이터

► 참고 문헌

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

[2] 아람 W. 해로우(Aram W. Harrow)와 애슐리 몬타나로(Ashley Montanaro). “양자 계산의 우위”. 자연 549, 203–209 (2017).
https : / /doi.org/ 10.1038 / nature23458

[3] 에드워드 파리, 제프리 골드스톤, 샘 구트만. “양자 근사 최적화 알고리즘”(2014).

[4] 이안 더닝, 스와티 굽타, 존 실버홀츠. “언제 가장 잘 작동합니까? Max-Cut 및 QUBO에 대한 휴리스틱의 체계적인 평가”. INFORMS 컴퓨팅 저널 30(2018).
https : / /doi.org/ 10.1287 / ijoc.2017.0798

[5] 미셸 X 괴만스(Michel X Goemans)와 데이비드 P 윌리엄슨(David P Williamson). "반정의 프로그래밍을 사용하여 최대 절단 및 만족 문제에 대한 개선된 근사 알고리즘". ACM 저널(JACM) 42, 1115–1145(1995).
https : / /doi.org/ 10.1145 / 227683.227684

[6] 사무엘 뷰러와 레나토 DC 몬테이로. “낮은 순위 인수분해를 통해 준정부호 프로그램을 풀기 위한 비선형 계획법 알고리즘”. 수학적 프로그래밍 95, 329–357 (2003).
https:/​/​doi.org/​10.1007/​s10107-002-0352-8

[7] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz 등 “퀴스킷: 양자 컴퓨팅을 위한 오픈 소스 프레임워크”(2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard 및 Eugene Tang. “QAOA는 좋은 클래식 스트링에서 시작하여 막히게 됩니다”(2022).

[9] Daniel J. Egger, Jakub Mareček, Stefan Woerner. “웜 스타트 양자 최적화”. 양자 5, 479(2021).
https:/​/​doi.org/​10.22331/​q-2021-06-17-479

[10] Stefan H Sack, Raimel A Medina, Richard Kueng 및 Maksym Serbyn. “개선이 보장된 양자 근사 최적화 알고리즘의 재귀 탐욕적 초기화”. 실제 검토 A 107, 062404(2023).
https : / /doi.org/10.1103/ PhysRevA.107.062404

[11] 스테판 H 색(Stefan H Sack)과 막심 세르빈(Maksym Serbyn). “양자 근사 최적화 알고리즘의 양자 어닐링 초기화”. 양자 5, 491(2021).
https:/​/​doi.org/​10.22331/​q-2021-07-01-491

[12] Leo Zhou, 왕성타오, 최순원, Hannes Pichler, Mikhail D Lukin. “양자 근사 최적화 알고리즘: 단기 장치의 성능, 메커니즘 및 구현”. 실제 리뷰 X 10, 021067(2020).
https : / /doi.org/10.1103/ PhysRevX.10.021067

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski 및 Travis S Humble. “가중 maxcut의 양자 근사 최적화를 위한 매개변수 전송”. 양자 컴퓨팅의 ACM 거래 4, 1–15(2023).
https : / /doi.org/ 10.1145 / 3584706

[14] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev 및 Ilya Safro. “무작위 그래프 간 최적의 QAOA 매개변수 전송 가능성”. 2021년 IEEE 양자 컴퓨팅 및 엔지니어링 국제 컨퍼런스(QCE)에서. 171~180페이지. IEEE(2021).
https : / / doi.org/ 10.1109 / QCE52317.2021.00034

[15] Johannes Weidenfeller, Lucia C Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner 및 Daniel J Egger. “초전도 큐비트 기반 하드웨어에서 양자 근사 최적화 알고리즘의 확장”. 양자 6, 870(2022).
https:/​/​doi.org/​10.22331/​q-2022-12-07-870

[16] Phillip C Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis 및 Travis S Humble. “단기 하드웨어에 대한 양자 근사 최적화 확장”. 과학 보고서 12, 12388(2022).
https : / /doi.org/ 10.1038 / s41598-022-14767-w

[17] 지안 지아코모 게레스키(Gian Giacomo Guerreschi)와 앤 Y 마츠우라(Anne Y Matsuura). “max-cut을 위한 QAOA는 양자 속도 향상을 위해 수백 큐비트가 필요합니다.” 과학 보고서 9, 1–7(2019).
https:/​/​doi.org/​10.1038/​s41598-019-43176-9

[18] 찰스 무사, 앙리 칼란드라, 베드란 둔코. “양자냐 아니냐: 단기 양자 최적화에서 알고리즘 선택을 향하여”. 양자 과학 및 기술 5, 044009(2020).
https:/​/​doi.org/​10.1088/​2058-9565/​abb8e5

[19] 콜린 캠벨과 에드워드 달. “최고 수준의 QAOA”. 2022년 IEEE 19차 소프트웨어 아키텍처 동반자 국제 컨퍼런스(ICSA-C). 141~146페이지. IEEE(2022).
https:/​/​doi.org/​10.1109/​ICSA-C54293.2022.00035

[20] 레베카 허먼, 로나 트레퍼트, 제임스 오스트로스키, 필립 C 랏쇼, 트래비스 S 험블, 조지 시옵시스. “QAOA의 그래프 구조가 maxcut에 미치는 영향”. 양자 정보 처리 20, 1–21(2021).
https:/​/​doi.org/​10.1007/​s11128-021-03232-8

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke ​​및 Daniel J Egger. "압착 및 양자 근사 최적화"(2022).

[22] 루슬란 셰이둘린, 스튜어트 해드필드, 태드 호그, 일리아 사프로. “고전적인 대칭과 양자 근사 최적화 알고리즘”. 양자 정보 처리 20, 1–28(2021).
https:/​/​doi.org/​10.1007/​s11128-021-03298-4

[23] 조나단 워츠(Jonathan Wurtz)와 피터 러브(Peter Love). "Maxcut 양자 근사 최적화 알고리즘 성능은 p> 1에 대해 보장됩니다." 실제 검토 A 103, 042612(2021).
https : / /doi.org/10.1103/ PhysRevA.103.042612

[24] 에드워드 파리, 제프리 골드스톤, 샘 구트만. “고정 큐비트 아키텍처를 위한 양자 알고리즘”(2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang. “대칭 보호로 인한 변형 양자 최적화의 장애물”. 실제 검토 편지 125, 260505(2020).
https : / /doi.org/10.1103/ PhysRevLett.125.260505

[26] 에드워드 파리(Edward Farhi), 데이비드 가마르닉(David Gamarnik), 샘 구트만(Sam Gutmann). “양자 근사 최적화 알고리즘은 전체 그래프를 보아야 합니다: 일반적인 경우”(2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang. “대략적인 그래프 색상을 위한 하이브리드 양자-고전 알고리즘”. 양자 6, 678(2022).
https:/​/​doi.org/​10.22331/​q-2022-03-30-678

[28] 매튜 B 헤이스팅스. "고전 및 양자 제한 깊이 근사 알고리즘"(2019).

[29] 쿠날 마르와하. "로컬 클래식 max-cut 알고리즘은 둘레가 큰 일반 그래프에서 $ p= 2$ QAOA보다 성능이 뛰어납니다." 양자 5, 437(2021).
https:/​/​doi.org/​10.22331/​q-2021-04-20-437

[30] 보아스 바락과 쿠날 마르와하. "높은 둘레 그래프의 최대 절단을 위한 고전적 알고리즘 및 양자 제한"(2021).
https : / /doi.org/10.4230/ LIPIcs.ITCS.2022.14

[31] 루벤 테이트, 마지드 파라디, 크레스턴 헤롤드, 그렉 몰러, 스와티 굽타. “QAOA를 위한 SDP 초기화 웜 스타트를 통해 클래식과 양자 연결”. 양자 컴퓨팅에 대한 ACM 거래(2022).
https : / /doi.org/ 10.1145 / 3549554

[32] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli 및 Rupak Biswas. “양자 근사 최적화 알고리즘에서 양자 교대 연산자 ansatz까지”. 알고리즘 12(2019).
https : / /doi.org/10.3390/ a12020034

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy 및 Eleanor G. Rieffel. "$xy$ 믹서: 양자 교대 연산자 ansatz에 대한 분석 및 수치 결과". 물리. A 101, 012320(2020).
https : / /doi.org/10.1103/ PhysRevA.101.012320

[34] Linghua Zhu, Ho Lun Tang, George S. Barron, FA Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes 및 Sophia E. Economou. “양자 컴퓨터에서 조합 문제를 해결하기 위한 적응형 양자 근사 최적화 알고리즘”. 물리. 연구 4, 033029(2022).
https : / /doi.org/10.1103/ PhysRevResearch.4.033029

[35] 안드레아스 바르치(Andreas Bärtschi)와 스테판 아이덴벤츠(Stephan Eidenbenz). "QAOA용 Grover 믹서: 믹서 설계에서 상태 준비로 복잡성 이동". 2020년 IEEE QCE(양자 컴퓨팅 및 엔지니어링 국제 컨퍼런스)에서. 72~82페이지. IEEE(2020).
https : / / doi.org/ 10.1109 / QCE49297.2020.00020

[36] 장 지앙(Zhang Jiang), 엘레노어 G 리펠(Eleanor G Rieffel), 왕 지후이(Zhihui Wang). “횡장을 사용한 그로버의 비구조적 검색을 위한 최적에 가까운 양자 회로”. 물리적 검토 A 95, 062317 (2017).
https : / /doi.org/10.1103/ PhysRevA.95.062317

[37] 러브 케이 그로버. "데이터베이스 검색을 위한 빠른 양자 역학 알고리즘". 컴퓨팅 이론에 관한 제212회 연례 ACM 심포지엄의 절차에서. 219~1996쪽. (XNUMX).
https : / /doi.org/ 10.1145 / 237814.237866

[38] 인 장(Yin Zhang), 사무엘 뷰러(Samuel Burer), 레나토 DC 몬테이로(Renato DC Monteiro). "max-cut 및 기타 이진 2차 프로그램에 대한 랭크 12 완화 휴리스틱". 최적화에 관한 SIAM 저널 503, 521–2001(XNUMX).
https : / /doi.org/ 10.1137 / S1052623400382467

[39] 송 메이, 테오도르 미시아키에비츠, 안드레아 몬타나리, 로베르토 임부제이로 올리베이라. "그로텐디크 부등식을 통한 동기화 및 maxcut 문제에 대한 SDPS 해결". 학습 이론 회의에서. 1476~1515페이지. PMLR(2017).
https://​/​doi.org/​10.48550/​arXiv.1703.08729

[40] 오자스 파렉(Ojas Parekh)과 케빈 톰슨(Kevin Thompson). "양수 항을 갖는 2-로컬 양자 해밀턴에 대한 최적의 제품 상태 근사치"(2022). arXiv:2206.08342.
arXiv : 2206.08342

[41] 루벤 테이트와 스와티 굽타. “시큐베”. GitHub 저장소(2021). URL: https:/​/​github.com/​swati1729/​CI-QuBe.
https://​/​github.com/​swati1729/​CI-QuBe

[42] 하워드 칼로프. "Goemans-Williamson MAX-CUT 알고리즘은 얼마나 좋은가요?" 컴퓨팅에 관한 SIAM 저널 29, 336–350(1999).
https : / /doi.org/ 10.1137 / S0097539797321481

[43] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo 등 “평면 초전도 프로세서의 비평면 그래프 문제에 대한 양자 근사 최적화”. 자연 물리학 17, 332-336 (2021).
https : / /doi.org/ 10.1038 / s41567-020-01105-y

[44] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay 및 Jay M. Gambetta. “멀티큐비트 실험에서 측정 오류 완화”. 물리. A 103, 042605(2021).
https : / /doi.org/10.1103/ PhysRevA.103.042605

[45] 조지 S. 배런과 크리스토퍼 J. 우드. "변형 양자 알고리즘에 대한 측정 오류 완화"(2020).

[46] 마틴 아바디, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, 라팔 요제포윅즈, 루카스 카이저, 만주나스 쿠들루르, 조쉬 레벤버그, 단델리온 마네, 라자트 몬가, 셰리 무어, 데릭 머레이, 크리스 올라, 마이크 슈스터, 조나단 슐렌스, 베노이트 스타이너, 일리아 서츠케버, 쿠날 탈와르, 폴 터커, 빈센트 반후케, 비제이 바수데반 , Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu 및 Xiaoqiang Zheng. "TensorFlow: 이기종 시스템에서의 대규모 기계 학습"(2015).

[47] Diederik P. Kingma와 지미 바. “Adam: 확률론적 최적화 방법”(2014).

[48] 로저 플레처. "실용적인 최적화 방법(2판)". 존 와일리 앤 선즈. 뉴욕, 뉴욕, 미국 (1987).
https : / /doi.org/ 10.1002 / 9781118723203

[49] MJD 파월. “선형 보간을 통해 목적 함수와 제약 함수를 모델링하는 직접 검색 최적화 방법”입니다. 최적화 및 수치 분석의 발전 275, 51–67(1994).
https:/​/​doi.org/​10.1007/​978-94-015-8330-5_4

[50] Alan J. Laub. “과학자 및 엔지니어를 위한 매트릭스 분석”. 91권. 시암. (2005).
https : / /doi.org/ 10.1137 / 1.9780898717907

[51] 게오르그 프로베니우스. “Ueber matrizen aus nicht negativen elementen”. Sitzungsberichte der Königlich Preussischen Akademie der WissenschaftenPages 456–477 (1912).

[52] A. 카베(Kaveh)와 H. 라하미(Rahami). “그래프 곱의 고유 분해를 위한 통합 방법”. 생물의학 응용 공학의 수치적 방법에 대한 커뮤니케이션 21, 377–388 (2005).
https://doi.org/10.1002/cnm.753

[53] 사이먼 스파카판. "그래프의 데카르트 곱의 연결성". 응용 수학 편지 21, 682-685 (2008).
https : / / doi.org/ 10.1016 / j.aml.2007.06.010

[54] 야체크 곤지오(Jacek Gondzio)와 안드레아스 그로테이(Andreas Grothey). "대규모 병렬 아키텍처에서 109개의 의사결정 변수를 사용하여 비선형 재무 계획 문제 해결". 모델링 및 시뮬레이션에 대한 WIT 거래 43(2006).
https : / / doi.org/ 10.2495 / CF060101

[55] 팬 RK 정. “분광 그래프 이론”. 92권. 미국 수학 Soc. (1997).
https : / / doi.org/ 10.1090 / cbms / 092

[56] MA Nielsen과 IL Chuang. “양자계산과 양자정보: 10주년 기념판”. 케임브리지 대학 출판부, 뉴욕. (2011).
https : / /doi.org/ 10.1017 / CBO9780511976667

[57] Vincent R. Pascuzzi, Andre He, Christian W. Bauer, Wibe A. de Jong, Benjamin Nachman. “양자 게이트 오류 완화를 위한 계산적으로 효율적인 제로 노이즈 추정”. 실제 검토 A 105, 042406(2022).
https : / /doi.org/10.1103/ PhysRevA.105.042406

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala 및 Kristan Temme. "시끄러운 양자 프로세서에서 희소 Pauli-lindblad 모델을 사용한 확률적 오류 제거". 자연 물리학페이지 1–6(2023).
https:/​/​doi.org/​10.1038/​s41567-023-02042-2

[59] 네이선 크리스록(Nathan Krislock), 제롬 말릭(Jérôme Malick), 프레데릭 루팽(Frédéric Roupin). "BiqCrunch: 이진 43차 문제를 해결하기 위한 준정의 분기 및 경계 방법". 수학 소프트웨어의 ACM 거래 2017(XNUMX).
https : / /doi.org/ 10.1145 / 3005345

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer 및 Matt McGinnis. "해밍 그래프, 존슨 그래프 및 고전 매개변수를 사용하는 기타 거리 정규 그래프의 최소 고유값". 조합 이론 저널, 시리즈 B 133, 88–121 (2018).
https : / / doi.org/ 10.1016 / j.jctb.2018.04.005

[61] 도널드 커누스. “조합 행렬”. 이산 수학에 관한 선정 논문(2000).
https:/​/​doi.org/​10.1016/​S0898-1221(04)90150-2

인용

[1] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner 및 Daniel J. Egger, "초전도 큐비트 기반 하드웨어에서 양자 근사 최적화 알고리즘의 확장", 퀀텀 6, 870 (2022).

[2] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun 및 Marco Pistoia, "초기 상태와 믹서 간의 정렬로 제한된 포트폴리오 최적화를 위한 QAOA 성능이 향상됩니다.", arXiv : 2305.03857, (2023).

[3] V. Vijendran, Aritra Das, Dax Enshan Koh, Syed M. Assad 및 Ping Koy Lam, "저심도 양자 최적화를 위한 표현 Ansatz", arXiv : 2302.04479, (2023).

[4] Andrew Vlasic, Salvatore Certo 및 Anh Pham, "Grover의 검색 알고리즘 보완: 진폭 억제 구현", arXiv : 2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele 및 Procolo Lucignano, "디지털화-항당뇨병 QAOA의 수렴: 회로 깊이 대 자유 매개변수", arXiv : 2307.14079, (2023).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble 및 Creston D. Herold, "양자 근사 최적화에 적용된 전역 Mølmer-Sørensen 상호 작용의 노이즈 모델링", 물리적 검토 A 107 6, 062406 (2023).

[7] Guoming Wang, "고전적으로 강화된 양자 최적화 알고리즘", arXiv : 2203.13936, (2022).

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

On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2023-09-27 01:31:17).

타임 스탬프 :

더보기 양자 저널