단열 양자 계산

단열 양자 계산(AQC)은 계산을 하기^[1] 위해 단열 정리에 의존하는 양자 계산의 한 형태이며 양자 ^[2][3][4][5]어닐링과 밀접하게 관련되어 있습니다.

묘사

우선, (잠재적으로 복잡한) 해밀턴의 지면 상태가 관심 문제에 대한 해결책을 기술하는 해밀턴을 찾는다.다음으로 간단한 해밀턴을 가진 시스템을 준비하고 그라운드 상태로 초기화한다.마지막으로 단순 해밀턴식은 원하는 복잡한 해밀턴식으로 단열적으로 진화한다.단열정리에 의해 시스템은 그라운드 상태를 유지하므로, 마지막에 시스템 상태가 문제의 해답을 기술한다.단열 양자 컴퓨팅은 회로 ^[6]모델에서 기존의 양자 컴퓨팅과 다항식으로 동등한 것으로 나타났습니다.

단열 알고리즘의 시간 복잡도는 해밀턴의 에너지 고유값의 간격(스펙트럼 간격)에 의존하는 단열 진화를 완료하는 데 걸리는 시간입니다.시스템이 기저 상태에 새겨 둘 특히, 기저 상태와 H의 첫번째 여기 상태(t)사이의 에너지 갭{H(t)\displaystyle}는 언제는 스펙트럼 격차 작다는 Hamiltonian 시간에 t{\displaystyle지}.[7]진화할 수 있는 비율에는 상한선을 제공한다, 해밀토니안evolv야 한다.교육느리게.알고리즘 전체의 런타임은 다음과 같이 제한할 수 있습니다.

$({displaystyle T=O\left({\frac {1}{min}^{2}}\오른쪽)})$

${\displaystyle {여기}_{}}$서 g ${\displaystyle {\mathrm{mi}}_{}}$ n$${ $displaystyle$ $g_{min}$은${\displaystyle }$H$$( t $)$의 $최소{\displaystyle }$ 스펙트럼 간격입니다$.$

AQC는 에너지 완화 문제를 회피하기 위한 가능한 방법입니다.양자계는 그라운드 상태이기 때문에 외부와의 간섭으로 인해 더 낮은 상태로 이동할 수 없다.외부 에너지(즉, "욕조의 온도")가 지면 상태와 다음으로 높은 에너지 상태 사이의 에너지 간격보다 낮게 유지되면 시스템이 더 높은 에너지 상태로 갈 확률은 상대적으로 낮아집니다.따라서 시스템은 필요에 따라 단일 시스템 고유 상태를 유지할 수 있습니다.

단열 모델의 보편성 결과는 양자 복잡성과 QMA-하드 문제와 관련이 있다.k-local Hamiltonian은 k ≤ ^[8]2에 대해 QMA-완전하다. QMA-경도 결과는 다음과 같은 큐비트의 물리적으로 현실적인 격자 모델에 대해 알려져 있다.

${\displaystyle H=\sum _{i}h_{i}Z_{i}Z_{i}Z_{j}+\sum_{i}K^{i}X_{j}X_{j}}$

$여기$서${\displaystyle }$Z , ${\displaystyle X}${\$displaystyle$$$Z$,X}$는 Pauli 행렬 ${\displaystyle z_{}}$z , ${\displaystyle x_{}}$x {\$displaystyle$ \$sigma _{z$},\$sigma$ _${x$를 나타냅니다. 이러한 모델은 범용 단열 양자 계산에 사용됩니다.QMA-완전 문제에 대한 해밀턴식은 또한 큐비트의^[10] 2차원 그리드 또는 ^[11]입자당 12개의 상태를 가진 양자 입자 선에 작용하도록 제한될 수 있습니다.그러한 모델이 물리적으로 실현 가능한 것으로 판명되면, 범용 단열 양자 컴퓨터의 구성 요소를 형성하기 위해서도 사용될 수 있다.

실제로 계산 중에 문제가 발생합니다.해밀턴이 점차 변화함에 따라 여러 큐비트가 티핑 포인트에 가까울 때 흥미로운 부분(클래식과는 대조적으로 양자 행동)이 발생합니다.그라운드 상태(큐비트 방향의 1세트)가 첫 번째 에너지 상태(방향의 다른 배열)에 매우 가까워지는 것은 바로 이 시점입니다.약간의 에너지를 추가하면(외부 욕조에서 또는 해밀턴을 천천히 바꾼 결과) 시스템이 접지 상태에서 벗어나 계산을 망칠 수 있습니다.계산을 더 빨리 수행하려고 하면 외부 에너지가 증가합니다. 큐비트 수를 조정하면 티핑 포인트의 에너지 갭이 줄어듭니다.

만족도 문제에서의 단열 양자 계산

단열 양자 연산은 만족도 문제와 기타 조합 검색 문제를 해결합니다.구체적으로는 이러한 문제는 ${\displaystyle {C1\mathrm{}}_{}{c\mathrm{}}_{}}$ C2${\displaystyle c_{}}$ CM$C_$1$}\wedge C_{2}\wedge \cdots\wedge C_{M$을 $만족$하는 상태를 요구하고 있습니다.이 표현에는 C$(\$ C_{$M})$에 대해 M절의 충족성이 포함되어 $있습니다$.각 비트는 ${\displaystyle {변수x}_{}}$ j ${\displaystyle \{}$ {${\displaystyle 0}$ , ${\displaystyle 1}$ $}$ { { $displaystyle x$_ { $j$} \ $in$\ {$0$ , $1$\ } 。${\displaystyle {Ci}_{}}${ $displaystyle C$_ { $i$}는 ${\displaystyle {x\mathrm{}}_{}{}_{}}$, ${\displaystyle {x\mathrm{}}_{}}$2, ${\displaystyle ...,}$ ${\displaystyle x_{}}$n { $displaystyle x_{1}, x_dots, x_n$의 부울값 함수입니다.QAAi는 이 퀀텀을 사용하여 이 문제를 해결합니다.이니셜 해밀턴 $(\$로 시작합니다.

$\displaystyle H_{B}=H_{B_{1}}+H_{B_{2}}+\dots+H_{B_{M}}$

${\displaystyle {여기}_{}}$서 H B$$(\$displaystyle H_{B_{i})$는 ${\displaystyle C_{}}$ i$(\$ $절$에 대응하는 해밀토니안을 나타냅니다.보통 H ${\displaystyle {B{}_{}}_{}}$(\$displaystyle H_{B_{i})$의 선택은 다른 절에 의존하지 않으므로 각 비트의 총 횟수만 모든 절에 관련됩니다.다음으로 단열 진화를 거쳐 문제 $해밀턴{\displaystyle {}_{}}$ $(\$ H_${P$로 끝납니다.

${\displaystyle H_{P}=\sum \sum _{C}^{}H_{P,C}}$

${\displaystyle {여기}_{}}$서 H P${\displaystyle {}_{}}$,$$ (\$displaystyle H_{P,C})$는 C절의 만족스러운 해밀턴어입니다.

여기에는 다음과 같은 고유값입니다.

${\displaystyle h_{C}(z_{1C},z_{2C}\dots z_{nC})=sbegin{case}0&{\mbox{clause}}}C{\mbox{clause}}\1&{\mbox{clause}}}}C{\{\mbox{\mbox{\mbox{clioliolioliolioliolioliolioliores}}}}}}}}}}}}C{\case$

실행 시간 T에 의한 단열 진화의 간단한 경로의 경우 다음을 고려하십시오.

${\displaystyle H(t)=(1-t/T)H_{B}+(t/T)H_{P}}$

s ${\displaystyle =}$ ${\displaystyle t}$/$$ { $style$ s =$$t / T$\}$ $s{\displaystyle }$ have 。그러면,

$displaystyle$$s$$H_{B}+sH_{$$P$ 이것은 우리 알고리즘의 단열 진화 해밀턴입니다.

단열정리에 따르면 처음에 $해밀토니안{\displaystyle {}_{}}$ $({$의 그라운드 상태에서$$ 시작하여 단열과정을 거쳐 문제 $해밀토니안{\displaystyle {}_{}}$ $({$ H_${P$의 그라운드 상태로 끝납니다.

그런 다음 최종 상태에서 각 n 스핀의 z 성분을 측정합니다.${\displaystyle {이}_{}}$로 인해 z ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$2, ${\displaystyle \dots ,}$ ${\displaystyle z_{}}$n(\$displaystyle z_{1$},$z_{2},\dots,z_{$n$$}) $문자열$이 생성됩니다.이 문자열은 만족도 문제로 인해 발생할 가능성이 높습니다.실행 시간 T는 결과의 정확성을 보장하기에 충분히 길어야 합니다.단열정리에 따르면, T는${\displaystyle \theta {}_{}^{}}$ /$$ ${\displaystyle {mi}_{\mathrm{}}^{}}$ n$$2 {\$displaystyle$ \$varepsilon$ /$g_{\mathrm${min}$\}^\{$$2$}이다. ${\displaystyle {여기}_{}}$서 ${\displaystyle {\mathrm{g}}_{}}$ ${\displaystyle {\mathrm{mi}}_{}}$ ${\displaystyle \underset{}{n}}$ ${\displaystyle {=}_{}}$ ${\displaystyle \underset{}{min\mathrm{}}}$ ${\displaystyle \underset{}{0}{}_{}\underset{}{\le }}$ $)$ ${\displaystyle {}_{}\underset{}{}}$( ${\displaystyle s}$ ) { $displaystyle g_{\mathrm {min}$ } } = \ $q s_0$}d ^[12]상태

게이트 기반 양자 컴퓨팅과의 비교

단열 양자 컴퓨팅은 임의의 단일 연산을 구현하는 표준 게이트 기반의 양자 컴퓨팅과 동등합니다.그러나 게이트 기반 양자 디바이스의 매핑 과제는 논리 변수가 체인이 ^[13]아닌 단일 큐비트에만 매핑되기 때문에 양자 어닐러와 상당히 다르다.

D-Wave 양자 프로세서

D-Wave One은 최적화 ^[14][15]문제를 해결하기 위해 양자 어닐링을 사용한다고 주장하는 캐나다 회사 D-Wave Systems가 만든 장치이다.2011년 5월 25일,^[15] 록히드마틴은 약 1,000만 달러에 D-Wave One을 구입했다.2013년 5월, 구글은 512 큐비트 D-Wave ^[16]Two를 구입했다.

D-Wave 프로세서가 기존 프로세서보다 속도를 높일 수 있는지에 대한 질문은 아직 해결되지 않았습니다.퀀텀인공지능연구소(NASA), USC, ETH 취리히, 구글의 연구원들이 수행한 테스트는 2015년 현재 양자 ^[17][18][19]우위에 대한 증거가 없음을 보여준다.

메모들