QuOne Lab, Phanous Research and Innovation Centre,이란 테헤란
이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.
추상
짧은 시간에 로컬 해밀턴의 진화는 로컬로 남아 있으므로 제한적일 것으로 예상됩니다. 이 백서에서는 로컬 시간 종속 Hamiltonians의 단시간 진화에 대한 몇 가지 제한 사항을 증명하여 이 직관을 검증합니다. 우리는 로컬 Hamiltonians의 단시간(최대 로그) 진화의 측정 출력 분포가 $concentrated$이고 $textit{isoperimetric inequality}$를 만족함을 보여줍니다. 결과의 명시적 적용을 보여주기 위해 $M$$small{AX}$$C$$small{UT}$ 문제를 연구하고 양자 어닐링에는 문제 크기에서 대수적으로 확장되는 런타임이 적어도 필요하다는 결론을 내립니다. $M$$small{AX}$$C$$small{UT}$에서 기존 알고리즘을 이겼습니다. 우리의 결과를 확립하기 위해, 우리는 또한 독립적인 관심을 가질 수 있는 시간 종속 해밀턴에 대해 작동하는 Lieb-Robinson 경계를 증명합니다.
인기 요약
► BibTeX 데이터
► 참고 문헌
[1] T. Kadowaki 및 H. Nishimori. 가로 Ising 모델의 양자 어닐링. 물리적 검토 E 58, 5355–5363(1998).
https : / /doi.org/10.1103/ PhysRevE.58.5355
[2] E. Farhi, J. Goldstone, S. Gutmann 및 M. Sipser. Adiabatic Evolution에 의한 양자 계산. arXiv:0001106 [quant-ph] (2000).
https:///doi.org/10.48550/arXiv.quant-ph/0001106
arXiv : 0001106
[3] T. 카토. 양자 역학의 단열 정리에 대해. 일본물리학회지 5, 435–439 (1950).
https : / /doi.org/10.1143/ JPSJ.5.435
[4] M. Born과 V. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik 51, 165–180(1928).
https : / /doi.org/ 10.1007 / BF01343193
[5] T. 알바쉬와 DA 라이다. 단열 양자 계산. Modern Physics 90, 015002(2018)의 리뷰.
https : / /doi.org/10.1103/ RevModPhys.90.015002
[6] I. 암탉과 FM Spedalieri. 제한된 최적화를 위한 양자 어닐링. 물리적 검토 적용 5, 034007(2016).
https : / /doi.org/10.1103/ PhysRevApplied.5.034007
[7] S. Puri, CK Andersen, AL Grimsmo 및 A. Blais. 모두 연결된 비선형 발진기를 사용한 양자 어닐링. 네이처 커뮤니케이션즈 8, 15785(2017).
https : / /doi.org/ 10.1038 / ncomms15785
[8] W. Lechner, P. Hauke 및 P. Zoller. 로컬 상호 작용에서 모두 연결되는 양자 어닐링 아키텍처. 사이언스 어드밴스 1, e1500838 (2015).
https : / /doi.org/10.1126/sciadv.1500838
[9] S. Jiang, KA Britt, AJ McCaskey, TS Humble 및 S. Kais. 소인수 분해를 위한 양자 어닐링. Scientific Reports 8, 17667 (2018).
https : / /doi.org/ 10.1038 / s41598-018-36058-z
[10] RY Li, R. Di Felice, R. Rohs 및 DA Lidar. 단순화된 전산 생물학 문제에 적용되는 양자 어닐링 대 고전 기계 학습. NPJ 양자 정보 4, 1–10(2018).
https://doi.org/10.1038/s41534-018-0060-8
[11] L. Stella, GE Santoro 및 E. Tosatti. 양자 어닐링에 의한 최적화: 간단한 경우로부터의 교훈. Physical Review B 72, 014303(2005).
https : / /doi.org/10.1103/ PhysRevB.72.014303
[12] O. Titiloye 및 A. Crispin. 그래프 착색 문제의 양자 어닐링. 이산 최적화 8, 376–384(2011).
https://doi.org/10.1016/j.disopt.2010.12.001
[13] A. 모트, J. 잡, J.-R. Vlimant, D. Lidar 및 M. Spiropulu. 기계 학습을 위한 양자 어닐링으로 Higgs 최적화 문제 해결. 자연 550, 375–379 (2017).
https : / /doi.org/ 10.1038 / nature24047
[14] KL Pudenz, T. Albash 및 D. A Lidar. 랜덤 Ising 문제에 대한 양자 어닐링 보정. 물리적 검토 A 91, 042302(2015).
https : / /doi.org/10.1103/ PhysRevA.91.042302
[15] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose 및 A. Aspuru-Guzik. 양자 어닐링에 의한 격자 단백질 모델의 저에너지 형태 찾기. 과학 보고서 2, 571(2012).
https : / /doi.org/ 10.1038 / srep00571
[16] KL Pudenz, T. Albash 및 D. A Lidar. 수백 큐비트로 오류가 수정된 양자 어닐링. 네이처 커뮤니케이션 5, 1–10(2014).
https : / /doi.org/ 10.1038 / ncomms4243
[17] R. Martoňák, GE Santoro 및 E. Tosatti. 순회 세일즈맨 문제의 양자 어닐링. Physical Review E 70, 057701(2004).
https : / /doi.org/10.1103/ PhysRevE.70.057701
[18] SH 아다치와 MP 헨더슨. 심층 신경망 훈련에 양자 어닐링 적용. arXiv:1510.06356 [quant-ph] (2015).
https:///doi.org/10.48550/arXiv.1510.06356
arXiv : 1510.06356
[19] M. W Johnson, et al. 제조된 스핀으로 양자 어닐링. 자연 473, 194–198 (2011).
https : / /doi.org/ 10.1038 / nature10012
[20] S. Boixo, T. Albash, FM Spedalieri, N. Chancellor 및 DA Lidar. 프로그래밍 가능한 양자 어닐링의 실험적 서명. 네이처 커뮤니케이션 4, 1–8(2013).
https : / /doi.org/ 10.1038 / ncomms3067
[21] AD King, et al. 프로그래밍 가능한 2000큐비트 Ising 체인의 일관된 양자 어닐링. arXiv:2202.05847 [quant-ph] (2022).
https:///doi.org/10.48550/arXiv.2202.05847
arXiv : 2202.05847
[22] B. Foxen, 외. 단기 양자 알고리즘을 위한 연속 125큐비트 게이트 세트 시연. 물리적 검토 편지 120504, 2020(XNUMX).
https : / /doi.org/10.1103/ PhysRevLett.125.120504
[23] K. Wright, et al. 11큐비트 양자 컴퓨터 벤치마킹. 네이처 커뮤니케이션 10, 1–6(2019).
https://doi.org/10.1038/s41467-019-13534-2
[24] EJ Crosson과 DA Lidar. 단열 양자 어닐링으로 양자 향상에 대한 전망. 네이처 리뷰 물리학 3, 466–489(2021).
https://doi.org/10.1038/s42254-021-00313-6
[25] E. Farhi, J. Goldstone 및 S. Gutmann. 양자 근사 최적화 알고리즘. arXiv:1411.4028 [quant-ph] (2014).
https:///doi.org/10.48550/arXiv.1411.4028
arXiv : 1411.4028
[26] E. Farhi, D. Gamarnik 및 S. Gutmann. Quantum Approximate Optimization Algorithm은 전체 그래프를 볼 필요가 있습니다: 최악의 사례. arXiv:2005.08747 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2005.08747
arXiv : 2005.08747
[27] E. Farhi, D. Gamarnik 및 S. Gutmann. Quantum Approximate Optimization Algorithm은 전체 그래프를 볼 필요가 있습니다: 일반적인 경우. arXiv:2004.09002 [quant-ph] (2020).
https:///doi.org/10.48550/arXiv.2004.09002
arXiv : 2004.09002
[28] S. Bravyi, A. Kliesch, R. Koenig 및 E. Tang. 대칭 보호에서 변이 양자 최적화의 장애물. 물리적 검토 편지 125, 260505(2020).
https : / /doi.org/10.1103/ PhysRevLett.125.260505
[29] S. Bravyi, D. Gosset 및 R. Movassagh. 양자 평균값에 대한 고전적인 알고리즘. 자연 물리학 17, 337–341 (2021).
https://doi.org/10.1038/s41567-020-01109-8
[30] S. Bravyi, A. Kliesch, R. Koenig 및 E. Tang. 대략적인 그래프 색상 지정을 위한 하이브리드 양자 고전 알고리즘. 퀀텀 6, 678(2022).
https://doi.org/10.22331/q-2022-03-30-678
[31] L. Eldar 및 AW Harrow. 기저 상태를 근사화하기 어려운 지역 해밀토니안. 2017년 컴퓨터 과학 기초(FOCS)에 관한 IEEE 58차 연례 심포지엄, 427–438(2017).
https : / /doi.org/10.1109/FOCS.2017.46
[32] LT Brady, CL Baldwin, A. Bapat, Y. Kharkov 및 AV Gorshkov. 양자 어닐링 및 양자 근사 최적화 알고리즘 문제의 최적 프로토콜. 물리적 검토 편지 126, 070505(2021).
https : / /doi.org/10.1103/ PhysRevLett.126.070505
[33] LT Brady, L. Kocia, P. Bienias, A. Bapat, Y. Kharkov 및 AV Gorshkov. 아날로그 양자 알고리즘의 동작. arXiv:2107.01218 [quant-ph] (2021).
https:///doi.org/10.48550/arXiv.2107.01218
arXiv : 2107.01218
[34] LC Venuti, D. D'Alessandro 및 DA Lidar. 폐쇄 및 개방 시스템의 양자 최적화를 위한 최적 제어. 물리적 검토 적용 16, 054023(2021).
https : / /doi.org/10.1103/ PhysRevApplied.16.054023
[35] AM Childs, Y. Su, MC Tran, N. Wiebe 및 S. Zhu. 정류자 스케일링에 따른 트로터 오차 이론. 물리적 검토 X 11, 011020(2021).
https : / /doi.org/10.1103/ PhysRevX.11.011020
[36] B. Nachtergaele, Y. Ogata 및 R. Sims. 양자 격자 시스템에서 상관 관계의 전파. 통계 물리학 저널 124, 1-13(2006).
https://doi.org/10.1007/s10955-006-9143-6
[37] B. Nachtergaele 및 R. Sims. Lieb-Robinson은 양자 다체 물리학의 경계를 넘습니다. 현대 수학 529, 141–176 (2010).
https : / /doi.org/10.1090/conm/529/10429
[38] S. Bravyi, MB Hastings 및 F. Verstraete. Lieb-robinson 범위와 상관 관계 및 위상 양자 순서 생성. Physical Review Letters 97, 050401(2006).
https : / /doi.org/10.1103/ PhysRevLett.97.050401
[39] C.-F. 첸과 A. 루카스. 그래프 이론의 연산자 성장 한계. 수학 물리학 385의 커뮤니케이션, 페이지 1273–1323(2021).
https://doi.org/10.1007/s00220-021-04151-6
[40] EH 리브와 DW 로빈슨. 양자 스핀 시스템의 유한군 속도. 수학 물리학 28, 251–257(1972)의 커뮤니케이션.
https : / /doi.org/ 10.1007 / BF01645779
[41] J. Haah, MB Hastings, R. Kothari 및 GH Low. 격자 해밀턴의 실시간 진화를 시뮬레이션하기 위한 양자 알고리즘. 컴퓨터 과학 기초(FOCS)에 관한 2018 IEEE 59차 연례 심포지엄, 350–360(2018).
https : / /doi.org/10.1109/FOCS.2018.00041
[42] A. Lubotzky, R. Phillips 및 P. Sarnak. 라마누잔 그래프. Combinatorica 8, 261–277 (1988).
https : / /doi.org/ 10.1007 / BF02126799
[43] B. 모하르. 등주 그래프 수. 조합 이론 저널, 시리즈 B 47, 274–291(1989).
https://doi.org/10.1016/0095-8956(89)90029-4
[44] AW Marcus, DA Spielman 및 N. Srivastava. Interlacing Families IV: 모든 크기의 Bipartite Ramanujan 그래프. 2015년 컴퓨터 과학 기초(FOCS)에 관한 IEEE 56차 연례 심포지엄, 1358–1377(2015).
https : / /doi.org/10.1109/FOCS.2015.87
[45] AW Marcus, DA Spielman 및 N. Srivastava. Interlacing Families IV: 모든 크기의 Bipartite Ramanujan 그래프. SIAM Journal on Computing 47, 2488–2509 (2018).
https:// / doi.org/ 10.1137/ 16M106176X
[46] C. 홀, D. 푸더, WF 사윈. 그래프의 Ramanujan 덮개. 수학의 발전 323, 367–410(2018).
https : / / doi.org/ 10.1016 / j.aim.2017.10.042
[47] MX Goemans 및 DP Williamson. 준정확 프로그래밍을 사용하여 최대 절단 및 만족 가능성 문제에 대한 근사 알고리즘이 개선되었습니다. ACM 저널 42, 1115–1145(1995).
https : / /doi.org/ 10.1145 / 227683.227684
[48] RD Somma, D. Nagaj 및 M. Kieferová. Quantum Annealing에 의한 Quantum Speedup. Physical Review Letters 109, 050501(2012).
https : / /doi.org/10.1103/ PhysRevLett.109.050501
[49] MB 헤이스팅스. 부호 문제가 없는 단열 양자 계산의 힘. 퀀텀 5, 597(2021).
https://doi.org/10.22331/q-2021-12-06-597
[50] A. Gilyén, MB Hastings 및 U. Vazirani. (하위)부호 문제가 없는 단열 양자 계산의 기하급수적 이점. 컴퓨팅 이론(STOC)에 관한 연례 ACM 심포지엄 절차, 1357–1369(2021).
https : / /doi.org/ 10.1145 / 3406325.3451060
[51] R. 바티아. 매트릭스 분석. 수학 대학원 텍스트. 스프링거 뉴욕(1996).
https://doi.org/10.1007/978-1-4612-0653-8
[52] R. 바티아. 양의 정부호 행렬. 프린스턴 대학 출판부, (2007).
https : / /doi.org/ 10.1515 / 9781400827787
[53] BD McKay, NC Wormald 및 B. Wysocka. 임의 일반 그래프의 짧은 주기. Combinatorics 11, 1–12 (2004)의 전자 저널.
https : / /doi.org/ 10.37236 / 1819
[54] F. Kardoš, D. Král 및 J. Volec. 둘레가 큰 큐빅 그래프와 랜덤 큐빅 그래프에서 최대 에지 컷. 랜덤 구조 및 알고리즘 41, 506–520 (2012).
https : / /doi.org/10.1002/rsa.20471
[55] D. Coppersmith, D. Gamarnik, MT Hajiaghayi 및 GB Sorkin. 임의 MAX SAT, 임의 MAX CUT 및 위상 전환. 무작위 구조 및 알고리즘 24, 502–545 (2004).
https : / /doi.org/10.1002/rsa.20015
[56] A. Dembo, A. Montanari 및 S. Sen. 희박한 무작위 그래프의 극단 절단. 확률 연대기 45, 1190–1217 (2017).
https:// / doi.org/ 10.1214/ 15-AOP1084
인용
[1] Giacomo De Palma, Milad Marvian, Cambyse Rouzé 및 Daniel Stilck França, "변형 양자 알고리즘의 한계: 양자 최적 전송 접근 방식", arXiv : 2204.03455.
위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2022-07-19 03:10:09). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.
On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2022-07-19 03:10:07).
이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.