양자워크

양자 걷기는 고전적인 무작위 걷기의 양자 유사점이다. 보행자가 특정 상태를 점유하고 상태 간의 확률적 전환으로 인해 무작위가 발생하는 기존의 무작위 보행과 대조적으로 양자 보행에서 임의성은 (1) 상태의 양자 중첩, (2) 무작위, 역전 가능한 단일 진화, (3) 상태 측정으로 인한 파동 함수의 붕괴를 통해 발생한다.

기존의 무작위 걷기와 마찬가지로 양자 걷기는 이산 시간과 연속 시간 모두에서 제형을 허용한다.

동기

양자 걷기는 무작위화된 알고리즘 설계에서 고전적인 무작위 걷기의 광범위한 사용에 의해 동기 부여되며, 여러 양자 알고리즘의 일부분이다. 일부 또는 언어적인 문제에서 양자 걷기는 어떤 고전 알고리즘보다 기하급수적인 속도를 제공한다.^[1][2] 양자 걷기는 또한 요소 고유성 문제,^[3] 삼각형 찾기 문제,^[4] 낸드 나무 평가와 같은 많은 실제적인 문제들에 대해 고전적인 알고리즘보다 다항식 속도를 제공한다.^[5] 잘 알려진 그로버 검색 알고리즘은 양자워크 알고리즘으로도 볼 수 있다.

고전적 무작위 보행과의 관계

양자 걷기는 고전적인 무작위 걷기와는 매우 다른 특징을 보인다. 특히, 그것들은 제한된 분포로 수렴되지 않으며 양자 간섭의 힘 때문에 그것들은 고전적인 등가물들보다 훨씬 더 빠르거나 느리게 확산될 수 있다.

연속시간

연속 시간 양자 걷기는 슈뢰딩거 방정식의 연속 공간 영역을 이산형 집합으로 대체할 때 발생한다. 즉, 연속체에서 전파되는 양자 입자 대신에, 유한하거나 카운트다운 무한할 수 있는$$ 일부 $그래프{\displaystyle }$G =${\displaystyle }$(${\displaystyle }$V ,${\displaystyle E}$ ) ${\displaystyle G=(V,E)}$의 정점 $집합{\displaystyle }$ V$${\$displaystyle V}$로 가능한 위치 상태 집합을 제한한다. 특정 조건에서 연속 시간 양자 걷기는 범용 양자 계산 모델을 제공할 수 있다.^[6]

비관계적 슈뢰딩거 역학관계

질량 m {\$displaystyle m}$이(가$)$ 무한 1차원 공간 영역에서 전파되는 비-상대적이며 스핀이 없는 자유 양자 입자의 역학을 생각해 보십시오. 입자의 움직임은 1차원 자유입자 슈뢰딩거 방정식을 만족하는$$파동함수 $\psi {\displaystyle }$: ${\displaystyle R\mathbb{}}$ ${\displaystyle \times }$ ${\displaystyle {\mathrm{R}}_{}}$≥ ${\displaystyle 0\mathbb{}{}_{}}$→ C ${\$에 $의해$ 완전히 설명된다.

${\displaystyle {\textbf{i}\hbar {\frac \\frac {\bar ^{2}}:{\frac {\hbar ^{2}}:{\frac {\frac ^{2}\frac }{}\competition x^{2}}:}}}}}}}}}}}}}}}$

여기서 $i{\displaystyle }$=${\displaystyle \sqrt{}}$- ${\displaystyle \sqrt{1}}$ ${\$ 및 $and$ ${\displaystyle \hbar }$은(는) Plank의 상수 감소된 것이다$$. Now suppose that only the spatial part of the domain is discretized, ${\displaystyle \mathbb {R} }$ being replaced with ${\displaystyle \mathbb {Z} _{\Delta x}\equiv \{\ldots ,-2\,\Delta x,-\Delta x,0,\Delta x,2\,\Delta x,\ldots \}}$ where ${\displaystyle \Del$$ta x}$은 입자가 차지할 수 있는 공간적 장소 사이의 분리다. 파동함수는 지도 $\psi {\displaystyle }$: ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {\Delta }_{}}$ x ${\displaystyle {}_{}}$ ${\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle 0_{}}$→ ${\displaystyle C\mathbb{}}$ ${\$ 0$}\mathb {C}}$이(가)가$$ 되고 두 번째 공간 부분파생물은 이산 라플라시안(laplacian)이 된다.

${\displaystyle {\frac {\partial ^{2}\psi }{\partial x^{2}}}\to {\frac {L_{\mathbb {Z} }\psi (j\,\Delta x,t)}{\Delta x^{2}}}\equiv {\frac {\psi \left((j+1)\,\Delta x,t\right)-2\psi \left(j\,\Delta x,t\right)+\psi \left((j-1)\,\Delta x,t\right)}{\델타 x^{2}}:}$

$Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle x_{}}$ ${\$ x$}$의 연속 시간 양자 보행에 대한 진화 방정식은 다음과 같다$$.

${\displaystyle {\textbf {i}{\frac {\partial t}{\psi}{\partial t}=-\omega _{\Delta x}L_{\mathb {Z}}\psi }}}$

여기서 ${\displaystyle {\Omega \mathrm{}}_{}}$ Δ ${\displaystyle x_{}}$≡${\displaystyle \hslash }$ / ${\displaystyle 2}$ m ${\displaystyle \Delta \mathrm{}}$ x ${\displaystyle {2\mathrm{}}^{}}$ ${\$ x$}\equiv \hbar /2m\,\Delta$ x$^{2}}$은 특성$$ 주파수다. This construction naturally generalizes to the case that the discretized spatial domain is an arbitrary graph ${\displaystyle G=(V,E)}$ and the discrete laplacian ${\displaystyle L_{\mathbb {Z} }}$is replaced by the graph Laplacian ${\displaystyle L_{G}\equiv D_{G}-A_{G}}$where ${\displaystyle D_{}}$ ${\displaystyle G_{}}$ ${\$와 $A{\displaystyle {}_{}}$ ${\displaystyle G_{}}$ ${\$는 각각 도 행렬과 인접 행렬이다. Common choices of graphs that show up in the study of continuous time quantum walks are the d-dimensional lattices ${\displaystyle \mathbb {Z} ^{d}}$, cycle graphs ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$, d-dimensional discrete tori ${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{$$d$ d차원 하이퍼큐브 $Q{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\daystyle$ \$mathb{Q}$^{$d}}$ 및 랜덤$$ 그래프.

이산 시간

이 구간은 확장이 필요하다. 덧셈으로 도와줘도 된다.(2009년 12월)

$Z{\displaystyle \mathbb{}}$ ${\$에 대한 이산 시간 양자 보행

이산 시간에서의 양자 보행의 진화는 (1) "코인 플립" 운영자와 (2) 반복적으로 적용되는 조건부 시프트 운영자의 두 가지 단일 운영자의 산물로 지정된다. 다음의 예는 여기에서 유익하다.^[7] 스핀-1/2도 자유도가 있는 입자가 이산형 부지의 선형 배열에서 전파된다고 상상해 보십시오. 이러한 사이트의 수가 셀 수 없이 무한하다면 상태 $공간$을 Z ${\$ {$Z}$}(으$)$로 식별한다$.$ 입자의 상태는 제품 상태로 설명될 수 있다.

${\displaystyle \PSI \rangele = s\rangele \otimes \psi \rangele }$

내부 스핀 상태로 구성됨

${\displaystyle s\rangle \in {H}_{C}=\좌측\{a_{\uparrow } {\uparrow }\\uparrow }\parrow }{\downarrow }} {\reangle :a_{\uparrow /\downarrow }\in {C}}}}}}\mathB}$

위치 상태

${\displaystyle \psi \langle \in {H}_{P}=\left\\\\\sum \mathb {Z}\nalpha _{x\in \mathb {Z}}\sum \{x\in \alpha _{x}{x}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

여기서 $H{\displaystyle {\mathcal{}}_{}}$ ${\displaystyle C_{}}$= ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$은 "코인 공간"이고$$ ${\displaystyle H_{}}$ P${\displaystyle {}_{}}$= ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$( ${\displaystyle Z\mathbb{}}$) ${\displaystyle {\mathcal {H}_{P}=\ell ^{2}(\mathb {Z} )$은 물리적 상태의 공간이다. 이 설정의$$ 제품 $\otimes {\displaystyle }$ ${\displaystyle\otimes }$은(는) Kronecker(텐서) 제품이다. 선상에서 양자 보행에 대한 조건부 시프트 운영자는 다음과 같이 주어진다.

${\displaystyle S= {\uparrow }\langle \langle {\uparrow }\otimes \sum \limits _{i} i+1\langle \langle i+}\\downarrow }\langle \limits _{i}}$

즉, 입자가 위로 회전하면 오른쪽으로 점프하고 아래로 회전하면 왼쪽으로 점프한다. 명시적으로 조건부 시프트 운영자는 다음과 같이 제품 상태에 대해 행동한다.

${\displaystyle S({\uparrow }\rangele \otimes i\rangle )= {\uparrow }\row }\time i+1\rangle }$

${\displaystyle S({\downarrow }\rangele \otimes i\rangle )= {\downarrow }\row \otimes i-1\rangle }$

If we first rotate the spin with some unitary transformation ${\displaystyle C:{\mathcal {H}}_{C}\to {\mathcal {H}}_{C}}$ and then apply ${\displaystyle S}$, we get a non-trivial quantum motion on ${\displaystyle \mathbb {Z} }$. A popular choice for such a transformation is the Hadamard gate $$${\displaystyle C}$= ${\displaystyle H}$ ${\displaystyle C=H}$은$($는) 표준 z 구성 요소 스핀 기준에 대해 행렬 표현을 가지고 있다.

${\displaystyle H={\frac {1}{\sqrt{2}}:{\begin{pmatrix}1&\;\;1\&#1&-1\end{pmatrix}}}}$

이러한 선택이 코인 플립 운영자에게 이루어질 때, 운영자 자체를 "하다마드 코인"이라고 하고, 그 결과 양자 걷기를 "하다마드 걷기"라고 한다. 워커가 원점 및 스핀업 상태에서 $초기화$된 경우$,$ Hadamard $Walk$ on Z {\displaystyle $\mathb {Z}$에 대한 Hadamard Walk의 단일 단계

${\displaystyle {\uparrow }\rangle \otimes 0\rangle \;\,{\overset {H}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}( {\uparrow }\rangle + {\downarrow }\rangle )\otimes 0\rangle \;\,{\overset {S}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}( {\uparrow }\rangle \otimes 1\rangle + {\downarrow }\rangle \otimes {-1}\rangle ).}$

이 지점에서 시스템 상태를 측정하면 위치 1에서 상향 회전 또는 위치 -1에서 하향 회전(두 가지 모두 확률 1/2)이 나타난다. 이 절차를 $반복$하는 것은 Z ${\$ {$Z}}$에서 고전적인 간단한 무작위 걷기와 일치할 것이다$.$ 비고전적 움직임을 관찰하기 위해 이 시점에서는 어떤 상태에서도 측정을 수행하지 않는다(따라서 파동 함수의 붕괴를 강제하지 않는다). 대신, 코인 플립 연산자와 스핀을 회전시키고 $조건부$로 S ${\displaystyle$ S$}$와 점프하는 절차를 반복한다$.$ 이렇게 하면 양자 상관관계가 보존되고 서로 다른 위치 상태가 간섭할 수 있다. 이는 오른쪽 그림에서 보듯이 고전적인 무작위 보행(가우스 분포)과는 확률을 크게 달리한다. 공간적으로는 분포가 대칭적이지 않다고 본다: 하다마드 동전은 동일한 확률로 위아래 스핀을 모두 내주지만, 초기 스핀이 is ${\displaystyle \{}$ { { { ${$ { {\$displaystyle {\uparrow }\rangele }$일 때 분포가 오른쪽으로 치우치는 경향이 있다$.$ 이러한 비대칭성은 전적으로 하다마드 동전이 취급하기 때문이다.${\displaystyle \uparrow }$ ${\displaystyle {\uparrow }\rangele }$ 및$$ ${\displaystyle \downarrow }$ ${\displaystyle${\$downarrow }\rangele }$ 상태 비대칭으로$$. 초기 상태가 선택되면 대칭 확률 분포가 발생한다.

${\displaystyle \PSI _{0}^{\text{symm}\rangele ={\frac {1}{\sqrt{1}}}}({\uparrow }\rangele +{\textbf}}{\downarrow }}}}}\otimes 0\rangele }}}}}}}}$

디라크 방정식

하나의 공간 차원에 대해 거대한 디락 연산자를 찾아낼 때 어떤 일이 일어나는지 생각해 보십시오. 대중용어가 없을 때, 우리는 좌뇌와 우뇌를 가지고 있다.^{[clarification needed]} 그들은 내부적인 자유도, "스핀" 또는 "코인"으로 특징지어질 수 있다. 우리가 매스 용어를 켤 때, 이것은 이 내부 "코인" 공간에서 회전하는 것에 해당한다. 양자 걷기는 시프트와 코인 오퍼레이터를 반복적으로 반복하는 것에 해당한다.

이것은 리처드 파인만의 1개의 공간과 1개의 시간 차원에 있는 전자 모델과 매우 흡사하다. 그는 지그재그로 가는 길을 요약했는데, 한 스핀(또는 동전)에 해당하는 좌회전 구간과 다른 스핀에 해당하는 우이동 구간을 합쳤다. 자세한 내용은 파인만 체커보드를 참조하십시오.

1차원 양자 보행에 대한 전이 확률은 (1) 고전적으로 허용되는 영역에서 점증적으로 진동하는 헤르미트 함수처럼 작용하며, (2) 전위^{[clarification needed]} 벽 주위의 에어리 함수에 의해 근사치되며, (3) 고전적으로 숨겨진 영역에서 기하급수적으로 붕괴한다.^[8]

참고 항목

• 경로 적분식

참조

추가 읽기

외부 링크

• 이산시간 양자워크의 수학적·물리적 기초에 관한 국제 워크숍
• 양자워크