양자 어닐링

Quantum annealing
그 외의 용도는, 어닐링(동음이의)을 참조하십시오.

양자 어닐링(QA)은 양자 변동을 사용하는 프로세스에 의해 주어진 후보 솔루션 세트(후보 상태)에 걸쳐 주어진 목적 함수의 전역 최소값을 찾는 최적화 프로세스입니다.양자 어닐링은 스핀 글라스의 접지 상태를 찾거나 이동 중인 세일즈맨 문제 등[1] 서치 공간이 국소 최소값이 많은 이산적인 문제(콤비노토리얼 최적화 문제)에 주로 사용됩니다."퀀텀 어닐링"이라는 용어는 1988년 B에 의해 처음 제안되었다.아폴로니, N. 세자 비앙키와 D.De Falco는 양자에서 영감을 얻은 고전 [2][3]알고리즘입니다.그것은 T. Kadowaki와 H에 의해 현재의 형태로 공식화되었다.양자 일관성이 없는 상상의 시간 변이체는 A. B. 피닐라, M. A. 고메즈, C에 의해 논의되었지만, "횡방향 이싱 모델에서 [4]양자 아닐링"의 니시모리(ja)는 논의되었다.세베니크와 J.D."Quantum annealing은 다차원 기능을 최소화하는 새로운 방법입니다."[5]에서 인형.

양자 어닐링은 동일한 가중치를 가진 모든 가능한 상태(후보 상태)의 양자 역학적 중첩에서 시작됩니다.그 후 시스템은 물리적 시스템의 자연스러운 양자역학적 진화인 시간에 의존하는 슈뢰딩거 방정식에 따라 진화한다.모든 후보 상태의 진폭은 상태 간의 양자 터널링을 일으키는 가로장의 시간 의존 강도에 따라 양자 병렬화를 실현하면서 계속 변화한다.횡단장의 변화 속도가 충분히 느리면 시스템은 순간 해밀턴의 지면 상태에 근접합니다(단열 양자 [6]계산 참조).횡단장의 변화율이 빨라지면 시스템은 일시적으로 그라운드 상태를 유지할 수 있지만 최종 문제 해밀턴의 그라운드 상태, 즉 디아바틱 양자 계산에서 [7][8]결론날 가능성이 높아진다.마침내 가로 필드가 꺼지고, 시스템은 원래의 최적화 문제에 대한 해결책에 대응하는 기존의 Ising 모델의 접지 상태에 도달했을 것으로 예상됩니다.무작위 자석에 대한 양자 어닐링의 성공에 대한 실험 시연은 최초 이론적 [9]제안 직후에 보고되었다.

모의 어닐링과의 비교

양자 어닐링은 QA의 터널링 필드 강도와 유사한 역할을 하는 "온도" 매개 변수인 시뮬레이션 어닐링과 비교할 수 있습니다.시뮬레이션 어닐링에서 온도는 단일 전류 상태에서 더 높은 "에너지" 상태로 이동할 확률을 결정합니다.양자 어닐링에서, 횡장의 강도는 모든 상태의 진폭을 병렬로 변화시키는 양자역학적 확률을 결정한다.분석적 및 수치적 증거는 양자 아닐링이 특정 조건 하에서 시뮬레이션 어닐링을 능가한다는 것을 시사한다(자세한 분석 및 [13]임의 타깃 해밀턴에 대한 양자 아닐링의 완전 해결 가능 모델 및 다른 계산 접근법의 비교 참조).

양자역학: 유추와 장점

Simple analogy describing the difference between Simulated Annealing and Quantum Annealing.
양자 어닐링(파란색 선)은 양자 터널링을 활용하여 글로벌 최소값을 구함으로써 에너지 환경을 효율적으로 횡단합니다.양자 어닐링은 Simulated Annealing(마젠타 라인)에 비해 큰 퍼포먼스를 발휘하여 이전에는 불가능하다고 생각되었던 대규모 최적화 문제를 해결할 수 있는 가능성을 열어줍니다.

터널링 장은 기본적으로 원래 유리의 고전적인 위치 에너지 부분과 이동하지 않는 운동 에너지 용어입니다.전체 과정은 양자 몬테카를로(또는 다른 확률적 기법)를 사용하여 컴퓨터에서 시뮬레이션될 수 있으며, 따라서 고전 유리의 바닥 상태를 찾기 위한 휴리스틱 알고리즘을 얻을 수 있다.

순수하게 수학적 목적 함수를 해제하는 경우, 문제의 변수는 고전적 자유도이며 비용 함수는 잠재적 에너지 함수(고전적 해밀턴)로 간주할 수 있다.그런 다음 터널링 필드(운동학적 부분)의 역할을 하기 위해 비환산 변수(즉, 원래 수학 문제의 변수와 0이 아닌 정류자를 갖는 변수)로 구성된 적절한 용어를 해밀턴에 인위적으로 도입해야 한다.그런 다음 위에서 설명한 대로 구성된 양자 해밀턴(원래 함수 + 비정류 부분)으로 시뮬레이션을 수행할 수 있다.여기서 비통전항 선택에는 선택지가 있으며 이에 따라 아닐의 효율이 좌우될 수 있다.

특히 잠재적 에너지(비용) 경관이 얕은 [14]국소 최소치를 둘러싼 매우 높고 얇은 장벽으로 구성되어 있는 경우에 양자 어닐링이 실제로 열 어닐링(시뮬레이션 어닐링)을 능가할 수 있다는 것은 이론적으로뿐만 아니라 실험적으로도 입증되었다.열 전이 확률(- T { e^ { - { \ } { k { } ） 와 의 Boltzmann 상수)는 장벽의 높이(스타일 \에만 의존하며, 장벽이 매우 높기 때문에 열변동이 이러한 국소적 최소값에서 시스템을 빼내기는 매우 어렵습니다.하지만 앞에서 1989년에 레이, Chakrabarti &amp에 의해;Chakrabarti,[1]는 양자 터널링 확률이 같은 장벽(격리에서 고려되)을 통해 장벽을 높이Δ{\Delta\displaystyle}뿐만 아니라 그것의 너비 w{w\displaystyle}및 약 e− Δ wΓ에 의해서 주어진다 따라 달라진다고 주장했다. {) e}} 여기서 \는 터널링 [15]필드입니다.양자 터널링이 있는 경우 폭w\를 이 추가 핸들은 큰 도움이 될 수 있습니다. 장벽이 충분히 얇다면( w\ ) 양자 변동은 시스템을 얕은 국소 최소값에서 확실히 끌어낼 수 있습니다. N 스핀 글라스의 경우 장벽 높이(\는N(\ N이 됩니다.w w의 일정한 값에 는, 안네 대신에 에 비례하는\t {을 얻을 수 있습니다.는eN( 어닐링의 경우 { e에 비례하며, 반면 w가1/ 1[16][17]만큼 감소하는 { n은 일 수 있습니다.

양자 컴퓨터에서는 이러한 시뮬레이션이 기존의 컴퓨터보다 훨씬 효율적이고 정확할 것으로 추측된다. 왜냐하면 손으로 추가할 필요 없이 터널링을 직접 수행할 수 있기 때문이다.더욱이, 더 전통적인 양자 알고리즘에서 사용된 양자 얽힘을 이용하는 데 필요한 엄격한 오류 제어 없이도 이를 수행할 수 있을 것이다.이에 대한 몇 가지 확인은 정확히 [18][19]해결 가능한 모델에서 찾을 수 있습니다.

이징 스핀 글라스에서의 양자 아닐링과 관련된 아이디어의 연대표:

  • 1989년 양자 변동은 터널링을 [1]사용하여 국소 최소(높지만 얇은 장벽이 있음)에서 벗어나 고전적인 이싱 스핀 글라스의 거친 에너지 환경을 탐색하는 데 도움이 될 수 있다는 아이디어가 제시되었다.
  • 1998년 양자 어닐링의 공식화 및 이싱 유리 [4]시스템에서 장점을 입증하는 수치 테스트
  • 1999년 LiHoYF 이싱 유리 [20]자석의 양자 어닐링에 대한 첫 번째 실험 시연.
  • 2011년 D-Wave [21]Systems가 제조 및 판매한 초전도 회로 양자 소둔기.

D-Wave 실장

상세정보 : D-Wave Systems computer컴퓨터 시스템 및 D-Wave Two
D-Wave Systems에 의해 제작되어 샘플 홀더에 장착 및 와이어 본딩된 칩의 사진.D-Wave One의 프로세서는 128개의 초전도 논리 소자를 사용하도록 설계되어 있습니다. 이 논리 소자는 제어 가능하고 조정 가능한 결합을 나타내며 연산을 수행합니다.

2011년, D-Wave Systems는 D-Wave One이라는 이름의 최초의 상업용 양자 어닐러를 발표했고,[21] 그 성능에 대한 논문을 네이처에 실었습니다.동사는, 이 시스템이 128 qubit 프로세서 [22]칩셋을 사용하고 있다고 주장하고 있습니다.2011년 5월 25일, D-Wave는 Lockheed Martin Corporation이 [23]D-Wave One 시스템 구매 계약을 체결했다고 발표했다.2011년 10월 28일 USC의 정보과학연구소는 록히드사의 D-Wave One을 인수했습니다.

2013년 5월, Google, NASA Ames 및 비영리 University Space Research Association의 컨소시엄이 D-Wave Systems로부터 512 큐비트의 [24][25]단열 양자 컴퓨터를 구입했다고 발표했다.일부 고전적인 어닐링 알고리즘과 비교하여 양자 어닐러로서의 성능에 대한 광범위한 연구가 이미 가능하다.[26]

2014년 6월, D-Wave는 컴퓨터 금융 회사 1QBit (1QBit)와 암 연구 그룹인 DNA-SEQ와 함께 양자 [27]하드웨어로 실제 문제를 해결하는 데 초점을 맞춘 새로운 양자 애플리케이션 생태계를 발표했습니다.1QBit의 연구개발 부문은 상업적으로 이용 가능한 양자 컴퓨터용 소프트웨어 애플리케이션을 생산하는 최초의 기업으로서 D-Wave의 양자 어닐링 프로세서에 초점을 맞추어 이들 프로세서가 실제 애플리케이션을 [28]해결하는 데 적합하다는 것을 성공적으로 입증했습니다.

얽힘에 대한 데모가 [29]발표되면서, D-Wave 기계가 모든 고전 컴퓨터에 대해 양자 속도 향상을 보여줄 수 있는지에 대한 의문은 여전히 풀리지 않고 있습니다.2014년 6월 사이언스에 발표된 연구는 "D-Wave 기계의 성능에 [30]대해 수행된 것 중 가장 철저하고 정확한 연구"와 "지금까지 가장 공정한 비교"로 설명되었으며 양자 속도 향상을 정의하고 측정하려고 시도했다.일부 정의는 경험적 테스트로 검증할 수 없는 반면, 다른 정의는 거짓이긴 하지만 성과 우위의 존재를 허용할 수 있기 때문에 제시되었다.이 [31]연구는 D-Wave 칩이 "양자 속도 향상"을 일으키지 않았으며 향후 실험에서 가능성을 배제하지 않았다.스위스 연방공과대학의 마티아스 트로이어가 이끄는 연구원들은 그들의 모든 실험 범위에 걸쳐 "양자 속도 증가"가 없다는 것을 발견했고, 실험의 하위 집합을 볼 때 결론적이지 않은 결과만 나왔다.그들의 연구는 "양자 가속 질문의 미묘한 본질"을 설명했다.추가 연구는[32] 이러한 테스트 지표와 평형 시스템에 대한 의존도를 더 잘 이해함으로써 양자 역학으로 인한 우위성을 놓쳤다.

양자 속도 향상과 관련된 많은 미해결 질문들이 있다.이전 섹션의 ETH 레퍼런스는 벤치마크 문제의 한 클래스에 대한 것입니다.양자 속도 상승이 발생할 수 있는 다른 종류의 문제가 있을 수 있습니다.구글, LANL, USC, 텍사스 A&M, D-Wave의 연구원들은 이러한 문제 수업을 [33]찾기 위해 열심히 일하고 있다.

2015년 12월, 구글은 D-Wave 2X가 일련의 하드 최적화 [34]문제에서 시뮬레이션 어닐링과 Quantum Monte Carlo를 최대 1억 배 이상 능가한다고 발표했다.

D-Wave의 아키텍처는 기존의 양자 컴퓨터와는 다릅니다.이것은 범용 양자 컴퓨터와 다항식으로 동등하다고 알려져 있지 않으며, 특히 쇼어의 알고리즘은 언덕을 오르는 [citation needed]과정이 아니기 때문에 쇼어의 알고리즘을 실행할 수 없다.쇼어의 알고리즘에는 범용 양자 컴퓨터가 필요합니다.D-Wave가 개최한 Qubits 2021 컨퍼런스에서 이 회사는 QAOA, VQE 등 다른 게이트 모델 알고리즘과 더불어 쇼르 알고리즘을 실행할 수 있는 최초의 범용 양자 컴퓨터 개발에 주력하고 있다고 발표했습니다[35].

"quantumannealing-based 알고리즘에 대한 여러 학문 분야에 걸치는 도입"[36]조합 최적화(NP하드)문제, 양자annealing-based 알고리즘의 일반적인 구조와 알고리즘의 이 종류의 max-SAT 및 최소 Multicut 문제, 같이 overvie의 인스턴스를 해결하는 것으로 두가지 예에 대한 소개를 제공한다.w의D-Wave Systems가 제조한 양자 어닐링 시스템.대규모 이산 연속 최적화 문제에 대한 하이브리드 양자 고전 알고리즘은 양자 [37]이점을 설명하기 위해 보고되었다.

레퍼런스

  1. ^ a b c Ray, P.; Chakrabarti, B. K.; Chakrabarti, A. (1989). "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations". Physical Review B. 39 (16): 11828–11832. Bibcode:1989PhRvB..3911828R. doi:10.1103/PhysRevB.39.11828. PMID 9948016.
  2. ^ Apolloni, Bruno; Cesa-Bianchi, Nicolo; De Falco, Diego (July 1988). "A numerical implementation of quantum annealing". Stochastic Processes, Physics and Geometry, Proceedings of the Ascona-Locarno Conference.
  3. ^ Apolloni, Bruno; Carvalho, Maria C.; De Falco, Diego (1989). "Quantum stochastic optimization". Stoc. Proc. Appl. 33 (2): 233–244. doi:10.1016/0304-4149(89)90040-9.
  4. ^ a b Kadowaki, T.; Nishimori, H. (1998). "Quantum annealing in the transverse Ising model". Phys. Rev. E. 58 (5): 5355. arXiv:cond-mat/9804280. Bibcode:1998PhRvE..58.5355K. doi:10.1103/PhysRevE.58.5355. S2CID 36114913. Archived from the original on 2013-08-11.
  5. ^ Finnila, A.B.; Gomez, M.A.; Sebenik, C.; Stenson, C.; Doll, J.D. (1994). "Quantum annealing: A new method for minimizing multidimensional functions". Chemical Physics Letters. 219 (5–6): 343–348. arXiv:chem-ph/9404003. Bibcode:1994CPL...219..343F. doi:10.1016/0009-2614(94)00117-0. S2CID 97302385.
  6. ^ Farhi, E.; Goldstone, J.; Gutmann, S.; Lapan, J.; Ludgren, A.; Preda, D. (2001). "A Quantum adiabatic evolution algorithm applied to random instances of an NP-Complete problem". Science. 292 (5516): 472–5. arXiv:quant-ph/0104129. Bibcode:2001Sci...292..472F. doi:10.1126/science.1057726. PMID 11313487. S2CID 10132718.
  7. ^ Crosson, Elizabeth, Farhi, Edward, Lin, Cedric, Lin, Han-Hsuan & Shor, Peter(2014)."양자 단열 알고리즘을 사용한 최적화를 위한 다른 전략." arXiv: 1401.7320
  8. ^ 무투크리슈난, 싯다르트, 알바시, 타밈 & 라이다르, 다니엘 A. (2015년)"Diabatic Trumps가 Quantum Optimization에서 단열할 때" arXiv:1505.01249
  9. ^ Brooke, J.; Bitko, D.; Rosenbaum, T. F.; Aeppli, G. (1999). "Quantum annealing of a disordered magnet". Science. 284 (5415): 779–81. arXiv:cond-mat/0105238. Bibcode:1999Sci...284..779B. doi:10.1126/science.284.5415.779. PMID 10221904. S2CID 37564720.
  10. ^ Morita, Satoshi; Nishimori, Hidetoshi (2008). "Mathematical foundation of quantum annealing". Journal of Mathematical Physics. 49 (12): 125210. arXiv:0806.1859. Bibcode:2008JMP....49l5210M. doi:10.1063/1.2995837. S2CID 13992889.
  11. ^ Santoro, Giuseppe E. & Tosatti, Erio (18 August 2006). "Optimization using quantum mechanics: quantum annealing through adiabatic evolution". Journal of Physics A. 39 (36): R393–R431. doi:10.1088/0305-4470/39/36/R01. S2CID 116931586.
  12. ^ Heim, B.; Rønnow, T. F.; Isakov, S. V.; Troyer, M. (2015). "Quantum versus classical annealing of Ising spin glasses". Science. 348 (6231): 215–217. arXiv:1411.5693. Bibcode:2015Sci...348..215H. doi:10.1126/science.aaa4170. PMID 25765071.
  13. ^ Yan, B.; Sinitsyn, N. A. (2022). "Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian". Nature Communications. 13: 2212. arXiv:2110.12354. Bibcode:2022NatCo..13.2212Y. doi:10.1038/s41467-022-29887-0. PMID 35468917. S2CID 248389790.
  14. ^ "Local Maxima and Minima, and, Absolute Maxima and Minima". Mathonline.
  15. ^ Das, A.; Chakrabarti, B. K. & Stinchcombe, R. B. (2005). "Quantum annealing in a kinetically constrained system". Phys. Rev. E. 72 (2): 026701. arXiv:cond-mat/0502167. Bibcode:2005PhRvE..72b6701D. doi:10.1103/PhysRevE.72.026701. PMID 16196745. S2CID 16466621. Archived from the original on 2014-01-13.
  16. ^ 예를 들어,
  17. ^ Das, A.; Chakrabarti, B. K. (2008). "Quantum Annealing and Analog Quantum Computation". Rev. Mod. Phys. 80 (3): 1061–1081. arXiv:0801.2193. Bibcode:2008RvMP...80.1061D. CiteSeerX 10.1.1.563.9990. doi:10.1103/RevModPhys.80.1061. S2CID 14255125.
  18. ^ Li, F.; Chernyak, V. Y. & Sinitsyn, N. A. (2018). "Quantum annealing and thermalization: insights from integrability". Physical Review Letters. 121 (19): 190601. arXiv:1804.00371. Bibcode:2018arXiv180400371L. doi:10.1103/PhysRevLett.121.190601. PMID 30468584. S2CID 53594139.
  19. ^ Yan, B.; Sinitsyn, N. A. (2022). "Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian". Nature Communications. 13. arXiv:2110.12354. Bibcode:2022NatCo..13.2212Y. doi:10.1038/s41467-022-29887-0. S2CID 248389790.
  20. ^ Brooke, J.; Bitko, D.; Rosenbaum, T. F. & Aeppli, G. (30 April 1999). "Quantum Annealing of a Disordered Magnet". Science. 284 (5415): 779–781. Bibcode:1999Sci...284..779B. doi:10.1126/science.284.5415.779. PMID 10221904. S2CID 37564720.
  21. ^ a b Johnson, M. W.; Amin, M. H. S.; Gildert, S.; et al. (2011). "Quantum annealing with manufactured spins". Nature. 473 (7346): 194–8. Bibcode:2011Natur.473..194J. doi:10.1038/nature10012. PMID 21562559. S2CID 205224761.
  22. ^ "Learning to program the D-Wave One". D-Wave Systems blog. Archived from the original on July 23, 2011. Retrieved 11 May 2011.
  23. ^ "D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation". D-Wave. 2011-05-25. Archived from the original on July 23, 2011. Retrieved 2011-05-30.
  24. ^ Jones, N. (2013). "Google and NASA snap up quantum computer". Nature News. doi:10.1038/nature.2013.12999. S2CID 57405432.
  25. ^ Smelyanskiy, Vadim N., Rieffel, Eleanor G., Knysh, Sergey I., Williams, Colin P., Johnson, Mark W., Tom, Murray C., Macready, William G. & Pudenz, Kristen L.(2012)."우주탐사의 하드 컴퓨팅 문제에 대한 단기 양자 컴퓨팅 접근법", arXiv: 1204.2821
  26. ^ Boixo, S.; Rønnow, T. F.; Isakov, S. V.; Wang, Z.; Wecker, D.; Lidar, D. A.; Martinis, J. M.; Troyer, M. (2014). "Evidence for quantum annealing with more than one hundred qubits". Nature Physics. 10 (3): 218–224. arXiv:1304.4595. Bibcode:2014NatPh..10..218B. doi:10.1038/nphys2900. S2CID 8031023.
  27. ^ "D-Wave Systems Building Quantum Application Ecosystem, Announces Partnerships with DNA-SEQ Alliance and 1QBit". D-Wave Systems. Retrieved 22 June 2014.
  28. ^ "1QBit Research". 1QBit. Archived from the original on 19 June 2014. Retrieved 22 June 2014.
  29. ^ Lanting, T.; Przybysz, A. J.; Smirnov, A. Yu.; Spedalieri, F. M.; et al. (2014-05-29). "Entanglement in a quantum annealing processor". Physical Review X. 4 (2): 021041. arXiv:1401.3500. Bibcode:2014PhRvX...4b1041L. doi:10.1103/PhysRevX.4.021041. S2CID 19235104.
  30. ^ Helmut Katzgraber, (2014년 1월)에서 인용.
  31. ^ Cho, Adrian (20 June 2014). "Quantum or not, controversial computer yields no speedup". Science. 344 (6190): 1330–1331. Bibcode:2014Sci...344.1330C. doi:10.1126/science.344.6190.1330. PMID 24948715.
  32. ^ Amin, Mohammad H., "준정 양자 아닐러에서의 양자 속도 향상 연구" arXiv:1503.04216
  33. ^ Steiger, Damian; Heim, Bettina; Rønnow, Troels; Troyer, Matthias (October 22, 2015). Huckridge, David A.; Ebert, Reinhard; Gruneisen, Mark T.; Dusek, Miloslav; Rarity, John G. (eds.). "Performance of quantum annealing hardware". Proceedings of SPIE (Electro-Optical and Infrared Systems: Technology and Applications XII; and Quantum Information Science and Technology). Electro-Optical and Infrared Systems: Technology and Applications XII; and Quantum Information Science and Technology. 9648: 964816. Bibcode:2015SPIE.9648E..16S. doi:10.1117/12.2202661. S2CID 57916974.
  34. ^ "When can Quantum Annealing win?". Research Blog. Retrieved 2016-01-21.
  35. ^ D-Wave Systems (2021-10-05). "D-Wave's Next-Generation Roadmap: Bringing Clarity to Practical Quantum Computing". Medium. Retrieved 2021-11-12.
  36. ^ Venegas-Andraca, Salvador E.; Cruz-Santos, William; McGeoch, Catherine; Lanzagorta, Marco (2018). "A cross-disciplinary introduction to quantum annealing-based algorithms". Contemporary Physics. 59 (2): 174–196. arXiv:1803.03372. Bibcode:2018ConPh..59..174V. doi:10.1080/00107514.2018.1450720. S2CID 118974781.
  37. ^ Ajagekar, Akshay; Humble, Travis; You, Fengqi (2020-01-04). "Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems". Computers & Chemical Engineering. 132: 106630. arXiv:1910.13045. doi:10.1016/j.compchemeng.2019.106630. ISSN 0098-1354.

추가 정보