양자 담금질

**양자 담금질** 또는 **양자 어닐링**(Quantum annealing, **QA**)은 양자 요동을 이용한 과정을 통해 주어진 후보 해 집합(후보 상태)에서 주어진 목표 함수의 전역 최솟값을 찾는 최적화 과정이다. 양자 담금질은 탐색 공간이 조합 최적화 문제와 같이 많은 극소점을 가진 이산 공간이거나, 스핀 유리의 바닥 상태를 찾거나, 최대 절단, 그래프 색칠, 충족 가능성, 외판원 문제와 같은 다양한 문제를 인코딩할 수 있는 QUBO 문제를 해결하는 데 주로 사용된다. "양자 담금질"이라는 용어는 1988년 B. 아폴로니, N. 체사 비안키, D. 드 팔코가 양자 영감을 받은 고전 알고리즘으로 처음 제안했다. 1994년 A. B. 핀닐라, M. A. 고메스, C. 세베니크, J. D. 돌이 양자 결맞음이 없는 허수 시간 변형에 대해 논의했지만, 현재의 형태는 1998년 T. 가도와키와 H. 니시모리(ja)에 의해 정립되었다.

양자 담금질은 모든 가능한 상태(후보 상태)의 양자역학적 중첩에서 동일한 가중치로 시작한다. 그런 다음 시스템은 물리적 시스템의 자연적인 양자역학적 진화인 시간에 따라 달라지는 슈뢰딩거 방정식을 따른다. 모든 후보 상태의 진폭은 시간에 따라 달라지는 횡단 필드의 강도에 따라 계속 변하여 양자 병렬 처리를 실현한다. 횡단 필드는 상태 간 또는 본질적으로 피크를 통한 양자 터널링을 유발한다. 횡단 필드의 변화율이 충분히 느리면 시스템은 순간 해밀토니언의 바닥 상태에 가깝게 유지된다(또한 단열 양자 계산 참조). 횡단 필드의 변화율이 가속되면 시스템은 일시적으로 바닥 상태를 벗어날 수 있지만 최종 문제 해밀토니언의 바닥 상태에 도달할 가능성이 더 높아진다. 즉, 비단열 양자 계산이다. 횡단 필드는 마침내 꺼지고, 시스템은 원래 최적화 문제의 해에 해당하는 고전 이징 모형의 바닥 상태에 도달할 것으로 예상된다. 무작위 자석에 대한 양자 담금질 성공의 실험적 시연은 초기 이론적 제안 직후 보고되었다. 양자 담금질은 많은 NP-완전 문제 해결에서 제곱근 속도 향상을 위한 빠른 그로버 오라클을 제공하는 것으로도 입증되었다.

## 담금질 기법과의 비교
양자 담금질은 양자 담금질의 터널링 필드 강도와 유사한 역할을 하는 "온도" 매개변수를 가진 담금질 기법과 비교할 수 있다. 담금질 기법에서 온도는 단일 현재 상태에서 더 높은 "에너지" 상태로 이동할 확률을 결정한다. 양자 담금질에서 횡단 필드의 강도는 모든 상태의 진폭을 병렬로 변경할 양자역학적 확률을 결정한다. 분석적 및 수치적 증거는 특정 조건에서 양자 담금질이 담금질 기법보다 우수함을 시사한다(하이엠 등과 양자 담금질의 임의 대상 해밀토니언에 대한 완전히 해결 가능한 모형 및 다양한 계산 방식의 비교를 위한 옌과 시니친 참조).

## 양자 역학: 유추와 장점
섬네일|upright=1.5|alt=담금질 기법과 양자 담금질의 차이를 설명하는 간단한 비유.|양자 담금질(파란색 선)은 양자 터널링을 활용하여 전역 최솟값을 찾아 에너지 지형을 효율적으로 탐색한다. 양자 담금질은 담금질 기법(자홍색 선)에 비해 상당한 성능 우위를 제공하여 이전에 불가능하다고 생각되었던 대규모 최적화 문제를 해결할 수 있는 잠재력을 열어준다.
터널링 필드는 기본적으로 원래 유리의 고전적 퍼텐셜 에너지 부분과 교환하지 않는 운동 에너지 항이다. 전체 과정은 양자 몬테카를로(또는 다른 확률적 기술)를 사용하여 컴퓨터에서 시뮬레이션될 수 있으므로 고전적 유리의 바닥 상태를 찾는 휴리스틱 알고리즘을 얻을 수 있다.

순수하게 수학적인 목적 함수를 담금질하는 경우, 문제의 변수를 고전적인 자유도로 간주하고 비용 함수를 퍼텐셜 에너지 함수(고전 해밀토니언)로 간주할 수 있다. 그런 다음 원래 수학적 문제의 변수와 0이 아닌 교환자를 갖는 변수(즉, 교환하지 않는 변수)로 구성된 적절한 항을 해밀토니언에 인위적으로 도입하여 터널링 필드(운동 부분)의 역할을 수행해야 한다. 그런 다음 위에서 설명한 대로 구성된 양자 해밀토니니언(원래 함수 + 비교환 부분)으로 시뮬레이션을 수행할 수 있다. 여기서 비비교환 항을 선택하는 데 선택의 여지가 있으며 담금질의 효율성은 이에 따라 달라질 수 있다.

양자 담금질은 특정 경우, 특히 퍼텐셜 에너지(비용) 지형이 얕은 지역 최솟값을 둘러싸는 매우 높지만 얇은 장벽으로 구성된 경우에 열 담금질(담금질 기법)보다 우수하다는 것이 실험적으로나 이론적으로 입증되었다. 열 전이 확률(T는 온도, k_B는 볼츠만 상수인 e^{-\frac{\Delta}{k_B T}}에 비례)은 장벽의 높이 \Delta에만 의존하기 때문에 매우 높은 장벽의 경우 열 요동이 시스템을 그러한 지역 최솟값에서 벗어나게 하는 것은 극히 어렵다. 그러나 1989년 레이, 차크라바티, 차크라바티가 일찍이 주장했듯이, 동일한 장벽을 통한 양자 터널링 확률(단독으로 고려됨)은 장벽의 높이 \Delta뿐만 아니라 너비 w에도 의존하며 대략 e^{-\frac{\sqrt{\Delta} w}{\Gamma}}로 주어진다. 여기서 \Gamma는 터널링 필드이다. 양자 터널링이 있는 경우 너비 w를 통한 이 추가 제어는 큰 도움이 될 수 있다. 장벽이 충분히 얇으면(즉, w \ll \sqrt{\Delta}), 양자 요동은 시스템을 얕은 지역 최솟값에서 확실히 벗어나게 할 수 있다. N-스핀 유리에서 장벽 높이 \Delta는 N 정도가 된다. w가 상수 값인 경우 담금질 시간은 e^{\sqrt{N}}에 비례하고(열 담금질의 경우 e^N에 비례하는 \tau 대신), w 가 1/\sqrt{N}로 감소하는 경우에는 \tau가 N에 무관하게 될 수도 있다.

양자 컴퓨터에서 이러한 시뮬레이션은 고전 컴퓨터에서 수행되는 것보다 훨씬 효율적이고 정확할 것으로 예상되는데, 이는 터널링을 수동으로 추가할 필요 없이 직접 수행할 수 있기 때문이다. 더욱이, 더 전통적인 양자 알고리즘에 사용되는 양자 얽힘을 활용하는 데 필요한 엄격한 오류 제어 없이도 이를 수행할 수 있을 것이다. 이에 대한 일부 확인은 정확히 해결 가능한 모델에서 발견된다.

이징 스핀 유리에서 양자 담금질과 관련된 아이디어의 타임라인:
*1989년: 양자 요동이 터널링을 사용하여 지역 최솟값(높지만 얇은 장벽이 있는)을 탈출함으로써 고전 이징 스핀 유리의 험한 에너지 지형을 탐색하는 데 도움이 될 수 있다는 아이디어가 제시됨;
*1998년: 양자 담금질의 공식화 및 이징 유리 시스템에서의 장점을 시연하는 수치적 테스트;
*1999년: LiHoYF 이징 유리 자석에서 양자 담금질의 첫 실험적 시연;
*2011년: D-웨이브 시스템에 의해 초전도 회로 양자 담금질 기계가 제작 및 판매됨.

## D-웨이브 구현

[섬네일|[D-웨이브 시스템이 제작한 칩의 사진으로, 샘플 홀더에 장착되고 와이어 본딩되었다. D-웨이브 원의 프로세서는 128개의 초전도 논리 요소를 사용하여 제어 가능하고 조정 가능한 결합으로 작업을 수행하도록 설계되었다.]]

2011년, D-웨이브 시스템은 D-Wave One이라는 이름으로 시장에 첫 상용 양자 담금질기를 발표하고 그 성능에 대한 논문을 네이처에 게재했다. 이 회사는 이 시스템이 128 큐비트 프로세서 칩셋을 사용한다고 주장한다. 2011년 5월 25일, D-Wave는 록히드 마틴 기업이 D-Wave One 시스템을 구매하는 계약을 체결했다고 발표했다. 2011년 10월 28일 서던캘리포니아 대학교 (USC)의 정보과학연구소는 록히드 마틴의 D-Wave One을 인도받았다.

2013년 5월, 구글, NASA 에임스 및 비영리 우주연구 대학연합 컨소시엄이 512큐비트의 D-Wave 시스템으로부터 단열 양자 컴퓨터를 구매했다고 발표되었다. 일부 고전 담금질 알고리즘과 비교하여 양자 담금질기로서의 성능에 대한 광범위한 연구가 가능하다.

2014년 6월, D-Wave는 계산 금융 회사인 1QB 인포메이션 테크놀로지스(1QBit) 및 암 연구 그룹인 DNA-SEQ와 함께 양자 하드웨어를 사용하여 실제 문제를 해결하는 데 중점을 둘 새로운 양자 애플리케이션 생태계를 발표했다. 상업적으로 이용 가능한 양자 컴퓨터용 소프트웨어 응용 프로그램을 생산하는 데 전념하는 최초의 회사로서 1QBit의 연구 개발 부서는 D-Wave의 양자 담금질 프로세서에 중점을 두었으며 이러한 프로세서가 실제 응용 프로그램을 해결하는 데 적합함을 입증했다.

양자 얽힘에 대한 시연이 발표되었음에도 불구하고, D-Wave 머신이 모든 고전 컴퓨터에 비해 양자 우월성을 시연할 수 있는지 여부는 여전히 미해결로 남아 있다. 2014년 6월 사이언스에 발표된 연구는 "D-Wave 머신의 성능에 대해 수행된 가장 철저하고 정확한 연구일 가능성이 높다"고 묘사되었고 "가장 공정한 비교"로, 양자 속도 향상을 정의하고 측정하려고 시도했다. 일부는 경험적 테스트로 확인할 수 없는 반면, 다른 일부는 위조되었음에도 불구하고 성능 이점의 존재를 허용할 수 있으므로 여러 정의가 제시되었다. 연구 결과 D-Wave 칩은 "양자 속도 향상을 생산하지 못했으며" 미래 테스트에서의 가능성도 배제하지 않았다. 취리히 연방 공과대학교의 마티아스 트로이어가 이끄는 연구진은 전체 테스트 범위에서 "양자 속도 향상"을 발견하지 못했으며, 테스트의 부분 집합을 살펴보았을 때만 결론을 내릴 수 없는 결과를 얻었다. 그들의 연구는 "양자 속도 향상 질문의 미묘한 본질"을 보여주었다. 추가 연구는 이러한 테스트 지표와 평형 시스템에 대한 의존성에 대한 이해를 발전시켜 양자 역학으로 인한 이점의 어떤 징후도 놓치지 않도록 했다.

양자 속도 향상에 관해서는 많은 미해결 질문이 있다. 이전 섹션의 ETH 참조는 벤치마크 문제의 한 클래스에 불과하다. 잠재적으로 양자 속도 향상이 발생할 수 있는 다른 문제 클래스가 있을 수 있다. 구글, LANL, USC, 텍사스 A&M, D-웨이브의 연구원들은 그러한 문제 클래스를 찾기 위해 노력하고 있다.

2015년 12월, 구글은 D-웨이브 2X가 어려운 최적화 문제 집합에서 담금질 기법과 양자 몬테카를로를 최대 100,000,000배까지 능가한다고 발표했다.

D-Wave의 아키텍처는 전통적인 양자 컴퓨터와 다르다. 보편적인 양자 컴퓨터와 다항식적으로 동일하지 않은 것으로 알려져 있으며, 특히 쇼어 알고리즘을 실행할 수 없는데, 쇼어 알고리즘은 양자 담금질 아키텍처에서는 현재 사용할 수 없는 정밀한 게이트 연산과 양자 푸리에 변환을 필요로 하기 때문이다. 쇼어 알고리즘은 보편적인 양자 컴퓨터를 필요로 한다. D-Wave가 주최한 Qubits 2021 컨퍼런스에서 회사가 QAOA 및 VQE와 같은 다른 게이트 모델 알고리즘 외에 쇼어 알고리즘을 실행할 수 있는 최초의 보편적인 양자 컴퓨터를 개발하고 있다고 발표했다.

"양자 담금질 기반 알고리즘에 대한 다학제적 소개"는 NP-난해 조합 최적화 문제, 양자 담금질 기반 알고리즘의 일반적인 구조, 최대 SAT(최대 만족 가능 문제) 및 최소 멀티컷 문제 사례를 해결하기 위한 두 가지 알고리즘 예제, 그리고 D-Wave Systems가 제조한 양자 담금질 시스템에 대한 개요를 제시한다. 대규모 이산-연속 최적화 문제를 위한 하이브리드 양자-고전 알고리즘은 양자 우월성을 보여주기 위해 보고되었다.

## 각주

## 더 읽어보기
*
*
*
*
*
*
*
*

분류:양자 알고리즘
분류:최적화 알고리즘 및 방법