이진 최적화 문제에 대한 큐비트 효율적인 인코딩 방식

플라톤에 의해 재발행

팔로워 : 0

벤자민 탄¹, 마크 앙투안 레몬 드¹, 수파넛 타나실프¹, 지라 왓 탕파 니타 논¹및 Dimitris G. Angelakis^1,2

¹싱가포르 국립 대학교 양자 기술 센터, 3 Science Drive 2, 싱가포르 117543
²그리스 하니아 크레타 기술 대학교 전기 및 컴퓨터 공학부 73100

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

추상

$ mathcal O (log n_c) $ 큐 비트 수에 $ n_c $ 클래식 변수로 구성된 문제를 구현할 수있는 64 차 비 제약 이진 최적화 문제를 해결하기위한 변이 양자 알고리즘 세트를 제안하고 분석합니다. 기본 인코딩 체계는 관련된 큐 비트의 수를 점진적으로 증가시킴으로써 변이 양자 상태에 의해 포착 된 고전적 변수들 간의 상관 관계를 체계적으로 증가시킬 수 있습니다. 먼저 모든 상관 관계가 무시되는 가장 간단한 한계를 조사합니다. 즉, 양자 상태가 통계적으로 독립적 인 고전 변수 만 설명 할 수있는 경우입니다. 이 최소 인코딩을 적용하여 $ 7 $ 큐 비트를 사용하는 $ 42 $ 클래식 변수로 구성된 일반 문제 인스턴스의 대략적인 솔루션을 찾습니다. 다음으로, 고전적 변수 사이의 8 체 상관 관계가 어떻게 변이 양자 상태에 통합 될 수 있는지, 그리고 근사 솔루션의 품질을 개선 할 수있는 방법을 보여줍니다. 우리는 문제의 특정 토폴로지를 이용하는 $ XNUMX $ 큐 비트만을 사용하여 $ XNUMX $-변수 Max-Cut 문제를 푸는 예를 제공합니다. 최첨단 양자 플랫폼에서 사용할 수있는 제한된 리소스를 고려할 때 이러한 사례를 효율적으로 최적화 할 수 있는지 분석합니다. 마지막으로 확률 분포의 표현성을 다 물체 상관 관계로 확장하기위한 일반적인 프레임 워크를 제시합니다.

주요 이미지 : 우리의 인코딩 체계는 큐 비트를 사용하여 QUBO 문제에서 고전적 변수의 하위 그룹 간의 고전적 상관 관계를 포착하여 더 적은 큐 비트로 근사 솔루션을 찾을 수 있도록합니다. 인코딩 체계는 캡처 할 상관 관계의 양과 문제를 해결하는 데 필요한 큐 비트 수에 유연성을 제공합니다.

[포함 된 콘텐츠]

► BibTeX 데이터

@article {Tan2021qubitefficient, doi = {10.22331 / q-2021-05-04-454}, URL = {https://doi.org/10.22331/q-2021-05-04-454}, 제목 = {Qubit- 바이너리 최적화 문제를위한 효율적인 인코딩 체계}, 작성자 = {Tan, Benjamin 및 Lemonde, Marc-Antoine 및 Thanasilp, Supanut 및 Tangpanitanon, Jirawat 및 Angelakis, Dimitris G.}, journal = {{Quantum}}, issn = {2521- 327X}, 게시자 = {{Verein zur F {“{o}} rderung des Open Access Publizierens in den Quantenwissenschaften}}, 볼륨 = {5}, 페이지 = {454}, 월 = 2021 월, 연도 = {XNUMX} }

► 참고 문헌

[1] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva 및 Colm A. Ryan. 단일 보정 된 펄스로 xy 얽힘 게이트 구현. Nature Electronics, 3 (12) : 744–750, 2020 년 2520 월. ISSN 1131-10.1038. 41928 / s020-00498-1-XNUMX.
https://doi.org/10.1038/s41928-020-00498-1

[2] Tameem Albash 및 Daniel A. Lidar. 단열 양자 계산. Rev. Mod. Phys., 90 : 015002, 2018 년 10.1103 월. 90.015002 / RevModPhys.XNUMX.
https : / /doi.org/10.1103/ RevModPhys.90.015002

[3] Arya K. Babbush R. et al. Arute, F. 프로그래밍 가능한 초전도 프로세서를 사용하는 양자 우월. Nature, 574 (7779) : 505–510, 2019. 10.1038 / s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5

[4] Bela Bauer, Sergey Bravyi, Mario Motta 및 Garnet Kin-Lic Chan. 양자 화학 및 양자 재료 과학을위한 양자 알고리즘. 화학 검토, 120 (22) : 12685–12717, 2020 년 1520 월. ISSN 6890-10.1021. 9 / acs.chemrev.00829bXNUMX.
https : / /doi.org/ 10.1021 / acs.chemrev.9b00829

[5] Andreas Bengtsson, Pontus Vikstål, Christopher Warren, Marika Svensson, Xiu Gu, Anton Frisk Kockum, Philip Krantz, Christian Križan, Daryoush Shiri, Ida-Maria Svensson 및 et al. 양자 근사 최적화 알고리즘에 대한 더 큰 회로 깊이로 성공 확률이 향상되었습니다. Physical Review Applied, 14 (3), 2020 년 2331 월. ISSN 7019-10.1103. 14.034010 / physrevapplied. XNUMX.
https : / /doi.org/10.1103/ physrevapplied.14.034010

[6] Lee Braine, Daniel J Egger, Jennifer Glick 및 Stefan Woerner. 거래 정산에 적용되는 혼합 바이너리 최적화를위한 양자 알고리즘. arXiv 사전 인쇄 arXiv : 1910.05788, 2019.
arXiv : 1910.05788

[7] Fernando GSL Brandão, Aram W. Harrow 및 Michał Horodecki. 로컬 랜덤 양자 회로는 대략적인 다항식 설계입니다. 수학 물리학 커뮤니케이션, 346 (2) : 397–434, 2016. ISSN 14320916. 10.1007 / s00220-016-2706-8.
https://doi.org/10.1007/s00220-016-2706-8

[8] Colin D. Bruzewicz, John Chiaverini, Robert McConnell 및 Jeremy M. Sage. 갇힌 이온 양자 컴퓨팅 : 진보와 도전. Applied Physics Reviews, 6 (2) : 021314, 2019. 10.1063 / 1.5088164.
https : / /doi.org/ 10.1063 / 1.5088164

[9] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio 및 Patrick J. Coles. 얕은 매개 변수화 된 양자 회로에서 비용 함수 의존 불모의 고원. Nature Communications, 12 (1), 2021 년 2041 월. ISSN 1723-10.1038. 41467 / s021-21728-XNUMX-w.
https : / /doi.org/ 10.1038 / s41467-021-21728-w

[10] Brian Coyle, Daniel Mills, Vincent Danos 및 Elham Kashefi. 타고난 우월성 : 양자 적 이점과 타고난 기계의 훈련. npj Quantum Information, 6 (1), 2020 년 2056 월. ISSN 6387-10.1038. 41534 / s020-00288-9-XNUMX.
https://doi.org/10.1038/s41534-020-00288-9

[11] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu 및 Dacheng Tao. 매개 변수화 된 양자 회로의 표현력. Physical Review Research, 2 (3), 2020 년 2643 월. ISSN 1564-10.1103 2.033125 / physrevresearch.XNUMX.
https : / / doi.org/ 10.1103 / physrevresearch.2.033125

[12] Suguru Endo, Zhenyu Cai, Simon C. Benjamin 및 Xiao Yuan. 하이브리드 양자 고전 알고리즘 및 양자 오류 완화. 일본 물리 학회지, 90 (3) : 032001, 2021 년 1347 월. ISSN 4073-10.7566. 90.032001 / jpsj.XNUMX.
https : / //doi.org/10.7566/ jpsj.90.032001

[13] Edward Farhi, Jeffrey Goldstone 및 Sam Gutmann. 양자 근사치 최적화 알고리즘. arXiv 사전 인쇄 arXiv : 1411.4028, 2014a.
arXiv : 1411.4028

[14] Edward Farhi, Jeffrey Goldstone 및 Sam Gutmann. 경계 발생 제약 문제에 적용된 양자 근사 최적화 알고리즘입니다. arXiv 사전 인쇄 arXiv : 1412.6062, 2014b.
arXiv : 1412.6062

[15] Edward Farhi, Jeffrey Goldstone, Sam Gutmann 및 Leo Zhou. 무한 크기의 양자 근사 최적화 알고리즘 및 sherrington-kirkpatrick 모델. arXiv 사전 인쇄 arXiv : 1910.08187, 2019.
arXiv : 1910.08187

[16] Dimitris Fouskakis와 David Draper. 확률 적 최적화 : 검토. 국제 통계 검토, 70 (3) : 315–349, 2002. 10.1111 / j.1751-5823.2002.tb00174.x.
https : / /doi.org/ 10.1111 / j.1751-5823.2002.tb00174.x

[17] F. Glover M. Lewis ZP Lü HB Wang Y. Wang G. Kochenberger, JK Hao. 제약이없는 이진 28 차 계획법 문제 : 조사. 조합 최적화 저널, 1 (58) : 81–2014, 10.1007. 10878 / s014-9734-0-XNUMX.
https://doi.org/10.1007/s10878-014-9734-0

[18] Michael R Garey와 David S Johnson. 컴퓨터와 난치성, 174 권. freeman San Francisco, 1979.
https : / / dl.acm.org/ doi / book / 10.5555 / 574848

[19] Lov K. Grover. 양자 역학은 건초 더미에서 바늘을 찾는 데 도움이됩니다. Phys. Rev. Lett., 79 : 325–328, 1997 년 10.1103 월. 79.325 / PhysRevLett.XNUMX.
https : / /doi.org/10.1103/ PhysRevLett.79.325

[20] LLC 구로 비 최적화. Gurobi 최적화 기 참조 매뉴얼, 2020. URL http : / / www.gurobi.com.
http : / / www.gurobi.com

[21] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo 및 et al. 평면 초전도 프로세서에서 비평면 그래프 문제의 양자 근사 최적화. Nature Physics, 17 (3) : 332–336, 2021 년 1745 월. ISSN 2481-10.1038. 41567 / s020-01105-XNUMX-y.
https : / /doi.org/ 10.1038 / s41567-020-01105-y

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

[23] Richard M. Karp. 조합 문제 사이의 감소 가능성, 85-103 페이지. Springer US, Boston, MA, 1972. ISBN 978-1-4684-2001-2. 10.1007 / 978-1-4684-2001-2_9.
https://doi.org/10.1007/978-1-4684-2001-2_9

[24] Nathan Killoran, Thomas R. Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada 및 Seth Lloyd. 연속 가변 양자 신경망. Phys. Rev. Research, 1 : 033063, 2019 년 10.1103 월. 1.033063 / PhysRevResearch.XNUMX.
https : / /doi.org/10.1103/ PhysRevResearch.1.033063

[25] Tjalling C. Koopmans 및 Martin Beckmann. 할당 문제 및 경제 활동의 위치. 계량 경제학, 25 (1) : 53–76, 1957. ISSN 00129682, 14680262. 10.2307 / 1907742.
https : / /doi.org/ 10.2307 / 1907742

[26] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo 등 연속 게이트 세트로 심층 양자 최적화 알고리즘의 성능을 개선합니다. PRX Quantum, 1 (2), 2020 년 2691 월. ISSN 3399-10.1103. 1.020304 / prxquantum.XNUMX.
https : / / doi.org/ 10.1103 / prxquantum.1.020304

[27] Jose I. Latorre. 이미지 압축 및 얽힘. arXiv 사전 인쇄 arXiv : 0510031, 2005.
arXiv : 퀀트 -PH / 0510031

[28] Wim Lavrijsen, Ana Tudor, Juliane Müller, Costin Iancu 및 Wibe de Jong. 시끄러운 중간 규모 양자 장치를위한 클래식 옵티 마이저. arXiv 사전 인쇄 arXiv : 2004.03004, 2020. 10.1109 / QCE49297.2020.00041.
https : / / doi.org/ 10.1109 / QCE49297.2020.00041
arXiv : 2004.03004

[29] 볼프강 레 흐너, 필립 하우 크, 피터 졸러. 로컬 상호 작용에서 올-투-올 연결을 제공하는 양자 어닐링 아키텍처. Science Advances, 1 (9) : 1–6, 2015. ISSN 23752548. 10.1126 / sciadv.1500838.
https : / /doi.org/10.1126/sciadv.1500838

[30] 해리 마코 위츠. 포트폴리오 선택. 금융 저널, 7 (1) : 77–91, 1952. 10.2307 / 2975974.
https : / /doi.org/ 10.2307 / 2975974

[31] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin 및 Xiao Yuan. 양자 전산 화학. Rev. Mod. Phys., 92 : 015003, 2020 년 10.1103 월 92.015003 / RevModPhys.XNUMX.
https : / /doi.org/10.1103/ RevModPhys.92.015003

[32] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin 및 Xiao Yuan. 양자 전산 화학. 현대 물리학 리뷰, 92 (1), 2020 년 1539 월 b. ISSN 0756-10.1103. 92.015003 / revmodphys.XNUMX.
https : / /doi.org/10.1103/ revmodphys.92.015003

[33] Jarrod R McClean, Jonathan Romero, Ryan Babbush 및 Alán Aspuru-Guzik. 변이 하이브리드 양자-고전 알고리즘의 이론. New Journal of Physics, 18 (2) : 023023, 2016 년 10.1088 월. 1367 / 2630-18 / 2 / 023023 / XNUMX.
https://doi.org/10.1088/1367-2630/18/2/023023

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush 및 Hartmut Neven. 양자 신경망 훈련 환경의 불모의 고원. Nature Communications, 9 (1) : 4812, 2018. 10.1038 / s41467-018-07090-4.
https://doi.org/10.1038/s41467-018-07090-4

[35] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, Abhinav Kandala, Antonio Mezzacapo, Peter Müller, Walter Riess, Gian Salis, John Smolin, Ivano Tavernelli 및 Kristan Temme. 단기 양자 장치에서 변형 알고리즘을 사용한 양자 최적화. Quantum Science and Technology, 3 (3) : 030503, 2018 년 10.1088 월. 2058 / 9565-822 / aabXNUMX.
https : / /doi.org/ 10.1088 / 2058-9565 / aab822

[36] JS Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, CB Osborn, A. Papageorge , EC Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, EA Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, WJ Zeng, A. Hudson, Blake R. Johnson, M. Reagor, MP da Silva 및 C. Rigetti. 하이브리드 양자 컴퓨터에서 비지도 머신 러닝. arXiv 사전 인쇄 arXiv : 1712.05771, 2017.
arXiv : 1712.05771

[37] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin 등 갇힌 이온 양자 시뮬레이터를 사용하여 장거리 ising 모델의 양자 근사 최적화. National Academy of Sciences의 회보, 117 (41) : 25396–25401, Oct 2020. ISSN 1091-6490. 10.1073 / pnas. 2006373117.
https : / /doi.org/ 10.1073 / pnas.2006373117

[38] 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 (1) : 4213, 2014. 10.1038 / ncomms5213.
https : / /doi.org/ 10.1038 / ncomms5213

[39] M. 파월. 미분없는 최적화를위한 알고리즘보기. 수학 오늘, 43, 01 2007.

[40] 존 프리 스킬. NISQ 시대와 그 이후의 양자 컴퓨팅. Quantum, 2:79, 2018 년 2521 월. ISSN 327-10.22331X. 2018 / q-08-06-79-XNUMX.
https://doi.org/10.22331/q-2018-08-06-79

[41] Xiaogang Qiang, Xiaoqi Zhou, Jianwei Wang, Callum M. Wilkes, Thomas Loke, Sean O'Gara, Laurent Kling, Graham D. Marshall, Raffaele Santagati, Timothy C. Ralph, Jingbo B. Wang, Jeremy L. O'Brien, Mark G. Thompson 및 Jonathan CF Matthews. 임의의 12 큐 비트 처리를 구현하는 대규모 실리콘 양자 광자. Nature Photonics, 9 (534) : 539–2018, 10.1038. 41566 / s018-0236-XNUMX-y.
https : / /doi.org/ 10.1038 / s41566-018-0236-y

[42] Arthur G. Rattew, Shaohan Hu, Marco Pistoia, Richard Chen 및 Steve Wood. 도메인에 구애받지 않고 노이즈에 강한 하드웨어 효율적인 진화형 변이 양자 고유 솔버입니다. arXiv 사전 인쇄 arXiv : 1910.09694, 2019.
arXiv : 1910.09694

[43] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar 및 Matthias Troyer. 양자 속도 향상을 정의하고 감지합니다. 과학, 345 (6195) : 420–424, 2014. ISSN 0036-8075. 10.1126 / science.1252319.
https : / /doi.org/10.1126/ science.1252319

[44] M Saffman. 원자 큐 비트 및 리드 버그 상호 작용을 사용한 양자 컴퓨팅 : 진행 상황과 과제. Journal of Physics B : Atomic, Molecular and Optical Physics, 49 (20) : 202001, oct 2016. 10.1088 / 0953-4075 / 49 / 20 / 202001.
https://doi.org/10.1088/0953-4075/49/20/202001

[45] Peter W. Shor. 양자 컴퓨터에서 소인수 분해 및 이산 로그를위한 다항식 시간 알고리즘. SIAM Journal on Computing, 26 (5) : 1484–1509, 1997. 10.1137 / S0097539795293172.
https : / /doi.org/ 10.1137 / S0097539795293172

[46] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush 및 Jarrod R McClean. 모델을 사용하여 변형 양자 알고리즘에 대한 최적화 도구를 개선합니다. Quantum Science and Technology, 5 (4) : 044008, 2020 년 2058 월. ISSN 9565-10.1088. 2058 / 9565-6 / abb9dXNUMX.
https://doi.org/10.1088/2058-9565/abb6d9

[47] IBM Quantum 팀. https : / / quantum-computing.ibm.com에서 검색 함. Ibmq, 2020 년.
https : / / quantum-computing.ibm.com

[48] G Wendin. 초전도 회로를 사용한 양자 정보 처리 : 검토. 물리학 진척 보고서, 80 (10) : 106001, 2017 년 10.1088 월. 1361 / 6633-7 / aa1eXNUMXa.
https://doi.org/10.1088/1361-6633/aa7e1a

[49] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt 및 Kristel Michielsen. 양자 근사치 최적화 알고리즘 벤치마킹. 양자 정보 처리, 19 (7), 2020 년 1573 월. ISSN 1332-10.1007. 11128 / s020-02692-8-XNUMX.
https://doi.org/10.1007/s11128-020-02692-8

[50] 스티븐 J. 라이트. 연속 최적화 (비선형 및 선형 프로그래밍). Nicholas J. Higham, Mark R. Dennis, Paul Glendinning, Paul A. Martin, Fadil Santosa, Jared Tanner, 편집자, The Princeton Companion to Applied Mathematics, 4 장, 281–293 페이지. 프린스턴 대학 출판부, 프린스턴, 2015.

[51] Leo Zhou, Sheng-Tao Wang, 최순원, Hannes Pichler, Mikhail D. Lukin. 양자 근사치 최적화 알고리즘 : 성능, 메커니즘 및 단기 장치의 구현. Physical Review X, 10 (2), 2020 년 2160 월. ISSN 3308-10.1103. 10.021067 / physrevx.XNUMX.
https : / /doi.org/10.1103/ physrevx.10.021067