패리티 양자 최적화: 인코딩 제약

패리티 양자 최적화: 인코딩 제약

타임 스탬프 : 17 년 2023 월 5 일 오전 56시 XNUMX 분
소스 노드 : 2017978

마이케 드리브쇤1,2, 킬리안 엔더1,2, 유네스 자바마드1및 Wolfgang Lechner1,2

1Parity Quantum Computing GmbH, A-6020 인스부르크, 오스트리아
2인스브루크 대학교 이론 물리학 연구소, A-6020 인스브루크, 오스트리아

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

추상

제약 조건은 큰 에너지 페널티와 추가 큐비트 오버헤드로 구현되기 때문에 어려운 최적화 문제를 양자 장치에서 해결하기 더욱 어렵게 만듭니다. 스핀 인코딩의 대안으로 도입된 패리티 매핑은 스핀 변수의 곱을 인코딩하는 패리티 변수만을 사용하여 문제를 표현으로 변환합니다. 패리티 표현에서 교환 상호 작용과 단일 스핀 뒤집기 항을 결합할 때 임의의 $k$-body 항의 합과 곱에 대한 제약 조건을 XNUMX차원 양자 시스템에서 추가 오버헤드 없이 구현할 수 있습니다.

► BibTeX 데이터

► 참고 문헌

[1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann 등 "NP-완전 문제의 임의 인스턴스에 적용되는 양자 단열 진화 알고리즘". Science 292, 472–475 (2001).
https : / /doi.org/10.1126/ science.1057726

[2] David Allouche, Isabelle Andre, Sophie Barbe 등 "최적화 문제로서의 전산 단백질 설계". 인공 지능 212, 59–79 (2014).
https:// / doi.org/ 10.1016/ j.artint.2014.03.005

[3] Simon Gravel과 Veit Elser. "분할 및 동의: 제약 만족에 대한 일반적인 접근". 물리학 E 78, 036706(2008).
https : / /doi.org/10.1103/ PhysRevE.78.036706

[4] Florian Neukart, Gabriele Compostella, Christian Seidel 등 "양자 어닐러를 사용한 교통 흐름 최적화"(2017). arXiv:1708.01625.
arXiv : 1708.01625

[5] Eleanor G. Rieffel, Davide Venturelli, Bryan O'Gorman 등. "어려운 운영 계획 문제에 대한 양자 어닐러 프로그래밍 사례 연구". 양자정보처리 14(2015).
https : / /doi.org/ 10.1007 / s11128-014-0892-x

[6] Emmanuel Hebrard, Eoin O'Mahony, Barry O'Sullivan. "Numberjack의 제약 프로그래밍 및 조합 최적화". Andrea Lodi, Michela Milano 및 Paolo Toth 편집자, 조합 최적화 문제에 대한 제약 조건 프로그래밍의 AI 및 OR 기술 통합. 컴퓨터 과학 강의 노트. 스프링거(2010).
https:/​/​doi.org/​10.1007/​978-3-642-13520-0_22

[7] MW Johnson, MHS Amin, S. Gildert, 외. "제작된 스핀을 사용한 양자 어닐링". 자연 473 (2011).
https : / /doi.org/ 10.1038 / nature10012

[8] Pei Cao, Zhaoyan Fan, Robert X. Gao 및 Jiong Tang. "여러 하드 제약 조건이 있는 구성 최적화 문제 해결: 향상된 다목적 시뮬레이션 어닐링 접근법"(2017). arXiv:1706.03141.
arXiv : 1706.03141

[9] Frank Arute, Kunal Arya, Ryan Babbush 등 "프로그래밍 가능한 초전도 프로세서를 사용한 양자 우위". 자연 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[10] Hannes Bernien, Sylvain Schwartz, Alexander Keesling 등. "51 원자 양자 시뮬레이터에서 다체 동역학 조사". 자연 551, 579 EP – (2017).
https : / /doi.org/ 10.1038 / nature24622

[11] Jens Koch, Terri M. Yu, Jay Gambetta 등 “쿠퍼 쌍 상자에서 파생된 전하 비감지 큐비트 설계”. 물리학 A 76, 042319(2007).
https : / /doi.org/10.1103/ PhysRevA.76.042319

[12] M. Saffman, TG Walker 및 K. Mølmer. “리드버그 원자를 이용한 양자 정보”. 목사 모드. 물리학 82, 2313–2363 (2010).
https : / /doi.org/10.1103/ RevModPhys.82.2313

[13] Loic Henriet, Lucas Beguin, Adrien Signoles, 외. "중립 원자를 사용한 양자 컴퓨팅". 퀀텀 4(2020).
https:/​/​doi.org/​10.22331/​q-2020-09-21-327

[14] Immanuel Bloch, Jean Dalibard, Wilhelm Zwerger. “초저온 기체를 이용한 다물체 물리학”. 목사 모드. 물리학 80, 885–964 (2008).
https : / /doi.org/10.1103/ RevModPhys.80.885

[15] Zhengbing Bian, Fabian Chudak, Robert Brian Israel, 외. "결함 진단에 적용하여 제한된 최적화 문제를 양자 어닐링에 매핑". ICT 3의 프론티어(2016).
https://doi.org/10.3389/fict.2016.00014

[16] Adam Douglass, Andrew D. King, Jack Raymond. "양자 어닐러로 SAT 필터 구성". Marijn Heule 및 Sean Weaver, 편집자, 만족도 테스트의 이론 및 응용 – SAT 2015. Computer Science Cham 강의 노트(2015). 스프링거 인터내셔널 퍼블리싱.
https:/​/​doi.org/​10.1007/​978-3-319-24318-4_9

[17] 앤드류 루카스. "많은 NP 문제의 공식화". 앞쪽. 물리학 2, 5(2014).
https : / /doi.org/ 10.3389 / fphy.2014.00005

[18] 에드워드 파리, 제프리 골드스톤, 샘 거트만. "양자 근사 최적화 알고리즘"(2014). arXiv:1411.4028.
arXiv : 1411.4028

[19] 카도와키 타다시와 니시모리 히데토시. "횡방향 ising 모델의 양자 어닐링". 물리학 E 58, 5355–5363(1998).
https : / /doi.org/10.1103/ PhysRevE.58.5355

[20] Arnab Das와 Bikas K. Chakrabarti. "콜로키움: 양자 어닐링 및 아날로그 양자 계산". 목사 모드. 물리학 80, 1061–1081(2008).
https : / /doi.org/10.1103/ RevModPhys.80.1061

[21] Philipp Hauke, Helmut G. Katzgraber, Wolfgang Lechner 등 "양자 어닐링의 관점: 방법 및 구현". 물리학 83, 054401(2020)의 진행 상황에 대한 보고서.
https:/​/​doi.org/​10.1088/​1361-6633/​ab85b8

[22] 토마스 비스코실과 흐리스토 디제프. "양자 어닐러에 최적화 문제의 등식 제약 조건 포함". 알고리즘 12(2019).
https : / /doi.org/10.3390/ a12040077

[23] Itay Hen과 Federico M. Spedalieri. "제한된 최적화를 위한 양자 어닐링". 물리학 Rev. Applied 5, 034007(2016).
https : / /doi.org/10.1103/ PhysRevApplied.5.034007

[24] Itay Hen과 Marcelo S. Sarandy. "양자 어닐링에서 제한된 최적화를 위한 드라이버 해밀턴". 물리학 A 93, 062312(2016).
https : / /doi.org/10.1103/ PhysRevA.93.062312

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

[26] Kazuki Ikeda, Yuma Nakamura, Travis S. Humble. "간호사 스케줄링 문제에 대한 양자 어닐링의 적용". Scientific Reports 9, 12837 (2019).
https:/​/​doi.org/​10.1038/​s41598-019-49172-3

[27] Hirotaka Irie, Goragot Wongpaisarnsin, Masayoshi Terabe, et al. "시간, 상태 및 용량에 따른 차량 경로 문제의 양자 어닐링". Sebastian Feld와 Claudia Linnhoff-Popien, 편집자, 양자 기술 및 최적화 문제. 페이지 145–156. Computer Science Cham 강의 노트(2019). 스프링거 인터내셔널 퍼블리싱.
https:/​/​doi.org/​10.1007/​978-3-030-14082-3_13

[28] Tobias Stollenwerk, Bryan O'Gorman, Davide Venturelli 등. "항공 교통 관리를 위한 충돌 방지 최적 궤적에 적용되는 양자 어닐링". 지능형 교통 시스템에 관한 IEEE 거래 21, 285–297(2020).
https://doi.org/ 10.1109/ TITS.2019.2891235

[29] Itay Hen과 AP 영. "특정 만족 문제에 대한 양자 단열 알고리즘의 기하급수적 복잡성". 물리학 E 84, 061152(2011).
https : / /doi.org/10.1103/ PhysRevE.84.061152

[30] Hok K. Ng, Banavar Sridhar, Shon Grabbe. "바람이 불 때 여러 순항 고도로 항공기 궤적 최적화". 항공우주정보시스템 저널 11(2014).
https://doi.org/10.2514/1.I010084

[31] Eleanor Rieffel, Davide Venturelli, Minh Do, 외. "상전이에서 어려운 계획 문제의 매개변수화된 가족". 인공 지능 28에 관한 AAAI 회의 간행물(2014).
https : / / doi.org/ 10.1609 / aaai.v28i1.9044

[32] Davide Venturelli, Dominic JJ Marchand 및 Galo Rojo. "Job-Shop Scheduling의 양자 어닐링 구현"(2016). arXiv:1506.08479.
arXiv : 1506.08479

[33] 길리 로젠버그, 포야 하그네가다르, 필 고다드 등 "양자 어닐러를 사용한 최적의 거래 궤적 문제 해결". 신호 처리 10(2016)에서 선택된 주제에 대한 IEEE 저널.
https://doi.org/10.1109/JSTSP.2016.2574703

[34] 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

[35] Jeremy Cook, Stephan Eidenbenz, Andreas Bärtschi. "최대 k-꼭지점 커버에서 양자 교대 연산자 ansatz". 2020년 IEEE QCE(Quantum Computing and Engineering) 국제 컨퍼런스에서. 83~92쪽. (2020).
https : / / doi.org/ 10.1109 / QCE49297.2020.00021

[36] 볼프강 레흐너, 필립 하우케, 피터 졸러. "로컬 상호 작용에서 모두 연결되는 양자 어닐링 아키텍처". 과학. 고급 1, 1500838(2015).
https : / /doi.org/10.1126/sciadv.1500838

[37] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff 등 "패리티 양자 최적화: 컴파일러"(2021). arXiv:2105.06233.
arXiv : 2105.06233

[38] Michael Fellner, Kilian Ender, Roeland ter Hoeven 및 Wolfgang Lechner. "패리티 양자 최적화: 벤치마크"(2021). arXiv:2105.06240.
arXiv : 2105.06240

[39] 비키 최. "단열 양자 계산의 마이너 임베딩: I. 매개변수 설정 문제". 양자 정보 처리 7, 193–209(2008).
https:/​/​doi.org/​10.1007/​s11128-008-0082-9

[40] Walter Vinci, Tameem Albash, Gerardo Paz-Silva 등 "마이너 임베딩으로 양자 어닐링 보정". 물리학 A 92, 042310(2015).
https : / /doi.org/10.1103/ PhysRevA.92.042310

[41] 야마시로 유, 오쿠와 마사키, 니시모리 히데토시, 다니엘 A. 라이다. "완전히 연결된 $p$-spin 모델에 대한 역방향 어닐링의 역학". 물리학 A100, 052321(2019).
https : / /doi.org/10.1103/ PhysRevA.100.052321

[42] Tameem Albash와 Daniel A. Lidar. "단열 양자 계산". 목사 모드. 물리학 90, 015002(2018).
https : / /doi.org/10.1103/ RevModPhys.90.015002

[43] Rolando D. Somma, Daniel Nagaj, Mária Kieferová. "양자 어닐링에 의한 양자 속도 향상". 물리학 레트 목사 109, 050501(2012).
https : / /doi.org/10.1103/ PhysRevLett.109.050501

[44] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin 등 "양자 단열 알고리즘을 사용한 최적화를 위한 다양한 전략"(2014). arXiv:1401.7320.
arXiv : 1401.7320

[45] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo, Matthias Troyer. "Nonstoquastic hamiltonians 및 ising 스핀 유리의 양자 어닐링". 물리학 B95, 184416(2017).
https : / /doi.org/10.1103/ PhysRevB.95.184416

[46] 안드레아스 하트만과 볼프강 레흐너. "격자 게이지 단열 양자 컴퓨팅의 신속한 반단열 스윕". 새로운 J. Phys. 21, 043025(2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab14a0

[47] MHS 아민. "단열 정리의 일관성". 물리학 레트 목사 102, 220401(2009).
https : / /doi.org/10.1103/ PhysRevLett.102.220401

[48] Lukas M. Sieberer와 Wolfgang Lechner. "Ising 구성의 프로그래밍 가능한 중첩". 물리학 A 97, 052329(2018).
https : / /doi.org/10.1103/ PhysRevA.97.052329

[49] Andreas Bärtschi와 Stephan Eidenbenz. "딕케 상태의 결정론적 준비". 계산 이론의 기초에서. 126~139쪽. 스프링거 국제 출판(2019).
https:/​/​doi.org/​10.1007/​978-3-030-25027-0_9

[50] 볼프강 레흐너. "병렬 가능한 게이트를 사용한 양자 근사 최적화". 양자 공학에 관한 IEEE 트랜잭션 1, 1–6(2020).
https : / / doi.org/ 10.1109 / TQE.2020.3034798

[51] SE Anderson, KC Younge, G. Raithel. "광학 격자에 리드베리 원자를 가두는 것". 물리학 레트 목사 107, 263001 (2011).
https : / /doi.org/10.1103/ PhysRevLett.107.263001

[52] S. Ebadi, A. Keesling, M. Cain 등 "리드버그 원자 배열을 사용한 최대 독립 집합의 양자 최적화". 사이언스 376, 1209–1215(2022).
https://doi.org/10.1126/science.abo6587

[53] TM Graham, Y. Song, J. Scott, et al. "중립 원자 양자 컴퓨터의 다중 큐비트 얽힘 및 알고리즘". 자연 604, 457–462(2022).
https:/​/​doi.org/​10.1038/​s41586-022-04603-6

[54] Dolev Bluvstein, Harry Levine, Giulia Semeghini, 외. "얽힌 원자 배열의 일관된 전송을 기반으로 하는 양자 프로세서". 자연 604, 451–456(2022).
https:/​/​doi.org/​10.1038/​s41586-022-04592-6

[55] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng 등 "128체 리드버그 게이트를 통한 양자 최적화". 물리학 레트 목사 120503, 2022(XNUMX).
https : / /doi.org/10.1103/ PhysRevLett.128.120503

[56] Joseph W. Britton, Brian C. Sawyer, Adam C. Keith 등. "수백 개의 스핀이 있는 포획 이온 양자 시뮬레이터에서 엔지니어링된 484차원 Ising 상호 작용". 자연 2012 (XNUMX).
https : / /doi.org/ 10.1038 / nature10981

[57] JI Cirac 및 P. Zoller. "마이크로트랩 배열에 이온이 있는 확장 가능한 양자 컴퓨터". Nature 404, 579–581(2000).
https : / /doi.org/ 10.1038 / 35007021

[58] 뮤어 쿰프, 마이클 브라운넛, 라이너 블랫. "어드레서블 상호 작용이 있는 무선 주파수 이온 트랩의 13차원 배열". New Journal of Physics 073043, 2011 (XNUMX).
https:/​/​doi.org/​10.1088/​1367-2630/​13/​7/​073043

[59] Manuel Mielenz, Henning Kalis, Matthias Wittemer, 외. "7차원 양자 시뮬레이션에 적합한 개별 제어 이온 배열". 네이처 커뮤니케이션즈 11839, ncomms2016 (XNUMX).
https : / /doi.org/ 10.1038 / ncomms11839

[60] B Foxen, JY Mutus, E Lucero, 외. "Qubit 호환 초전도 상호 연결". Quantum Science and Technology 3, 014005 (2017).
https://doi.org/ 10.1088/ 2058-9565/ aa94fc

[61] Ming Gong, Shiyu Wang, Chen Zha 등 "Quantum은 프로그래밍 가능한 62차원 372큐비트 초전도 프로세서를 사용합니다." 사이언스 948, 952–2021(XNUMX).
https:// / doi.org/ 10.1126/ science.abg7812

[62] Tim Menke, William P. Banner, Thomas R. Bergamaschi 등 "초전도 큐비트 간의 조정 가능한 129체 상호 작용 시연". 물리학 레트 목사 220501, 2022(XNUMX).
https : / /doi.org/10.1103/ PhysRevLett.129.220501

[63] Nico W. Hendrickx, William IL Lawrie, Maximilian Russ 등. "591큐비트 게르마늄 양자 프로세서". 자연 580, 585–2021(XNUMX).
https:/​/​doi.org/​10.1038/​s41586-021-03332-6

[64] LMK Vandersypen, H. Bluhm, JS Clarke 등 "양자점과 도너의 스핀 큐비트 인터페이스 - 뜨겁고 밀도가 높으며 일관성이 있습니다." npj 양자 정보 3, 34 (2017).
https : / /doi.org/ 10.1038 / s41534-017-0038-y

[65] M. Veldhorst, HGJ Eenink, CH Yang 및 AS Dzurak. “스핀 기반 양자 컴퓨터를 위한 실리콘 CMOS 아키텍처”. 자연 통신 8, 1766 (2017).
https:/​/​doi.org/​10.1038/​s41467-017-01905-6

[66] Ruoyu Li, Luca Petit, David P. Franke, 외. "실리콘 양자점 큐비트용 크로스바 네트워크". 사이언스 어드밴스 4, eaar3960 (2018).
https://doi.org/10.1126/sciadv.abg9158

[67] JR Johansson, PD Nation, Franco Nori. "Qutip 2: 개방형 양자 시스템의 역학을 위한 Python 프레임워크". 컴퓨터 물리학 커뮤니케이션 184, 1234–1240 (2013).
https : / /doi.org/ 10.1016 / j.cpc.2012.11.019

[68] Tameem Albash, Walter Vinci 및 Daniel A. Lidar. "전대역 연결 방식 간의 시뮬레이션 양자 어닐링 비교". 물리학 A 94, 022327(2016).
https : / /doi.org/10.1103/ PhysRevA.94.022327

[69] 페르난도 파스타프스키와 존 프레스킬. "인코딩된 양자 어닐링에 대한 오류 수정". 물리학 A 93, 052325(2016).
https : / /doi.org/10.1103/ PhysRevA.93.052325

[70] Anita Weidinger, Glen Bigan Mbeng, Wolfgang Lechner. "양자 근사 최적화를 위한 오류 완화"(2023). arXiv:2301.05042.
arXiv : 2301.05042

[71] Sergey Bravyi, David P. DiVincenzo, Daniel Loss. "양자 다체 시스템을 위한 슈리퍼-볼프 변환". Annals of Physics 326, 2793–2826 (2011).
https : / /doi.org/ 10.1016 / j.aop.2011.06.004

인용

[1] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia 및 Yuri Alexeev, "금융을 위한 양자 컴퓨팅에 대한 조사", arXiv : 2201.02773, (2022).

[2] Sheir Yarkoni, Elena Raponi, Thomas Bäck 및 Sebastian Schmitt, "산업용 양자 어닐링: 소개 및 검토", 물리학 진행에 관한 보고서 85 10, 104001 (2022).

[3] Kilian Ender, Roeland ter Hoeven, Benjamin E. Niehoff, Maike Drieb-Schön, Wolfgang Lechner, "패리티 양자 최적화: 컴파일러", arXiv : 2105.06233, (2021).

[4] PV Sriluckshmy, Vicente Pina-Canelles, Mario Ponce, Manuel G. Algaba, Fedor Šimkovic 및 Martin Leib, "최적, 매개변수화된 다중 큐비트 Pauli 게이트의 하드웨어 기본 분해", arXiv : 2303.04498, (2023).

[5] Michael Fellner, Kilian Ender, Roeland ter Hoeven 및 Wolfgang Lechner, "패리티 양자 최적화: 벤치마크", arXiv : 2105.06240, (2021).

[6] Narendra N. Hegade, Koushik Paul, F. Albarrán-Arriagada, Xi Chen 및 Enrique Solano, "디지털화된 단열 양자 분해", 물리적 검토 A 104 5, L050403(2021).

[7] Federico Dominguez, Josua Unger, Matthias Traube, Barry Mant, Christian Ertler, Wolfgang Lechner, "Encoding-Independent Optimization Problem Formulation for Quantum Computing", arXiv : 2302.03711, (2023).

[8] R. Cumming 및 T. Thomas, "양자 컴퓨터를 사용하여 실제 문제 해결 - 오늘날 달성할 수 있는 것은 무엇입니까?", arXiv : 2211.13080, (2022).

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

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

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

타임 스탬프 :

더보기 양자 저널