Grover의 검색 알고리즘의 이론

이 문서에서는 Grover의 알고리즘이 작동하도록 하는 수학적 원리에 대해 자세히 설명합니다.

수학 문제를 해결하기 위한 Grover 알고리즘의 실제 구현은 Grover의 검색 알고리즘 구현을 참조하세요.

문제의 설명

모든 검색 작업은 검색 항목 $x$를 허용하는 추상 함수 $f(x)$로 표현할 수 있습니다. 항목 $x$가 검색 작업의 솔루션인 경우 $f(x)=1$입니다. $x$ 항목이 솔루션이 아니면 $f(x)=0$입니다. 검색 문제는 $f(x_0)=1$과 같은 $x_0$ 항목을 찾는 것으로 구성됩니다.

Grover의 알고리즘이 해결하려는 작업은 다음과 같이 표현할 수 있습니다. 주어진 클래식 함수 $f(x):\{0,1\}^n \rightarrow\{0,1\}$, 여기서 $n$은 검색 공간의 비트 크기입니다. $f(x_0)=1$에 해당하는 입력 $x_0$을 찾습니다. 알고리즘의 복잡성은 $f(x)$ 함수 사용의 횟수로 측정됩니다. 일반적으로 최악의 시나리오에서 $N=2^n$인 경우 $f(x)$를 총 $N-1$번 평가해야 합니다. 모든 가능성을 시험해보세요. $N-1$ 요소 다음에는 마지막 요소여야 합니다. Grover의 양자 알고리즘은 이 문제를 훨씬 빠르게 해결할 수 있으므로 2차 속도를 제공합니다. 여기서 2차는 N에 비해 약 $\sqrt{$N$}$개의 평가만 필요하다는 것을 의미합니다.

알고리즘 개요

검색 작업에 적합한 항목이 $N=2^n$개 있고 각 항목에 $0$에서 $N-1$까지의 정수를 할당하여 인덱스된다고 가정합니다. 또한 $M$개의 서로 다른 유효한 입력이 있다고 가정합니다. 이는 $f(x)=1$에 해당하는 $M$개의 입력이 있음을 의미합니다. 알고리즘의 단계는 다음과 같습니다.

1. $\ket{0}$ 상태에서 초기화된 $n$개 큐비트의 레지스터로 시작합니다.
2. 레지스터의 각 큐비트에 $H$를 적용하여 레지스터를 균일한 중첩으로 준비합니다. $$|\text{register}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$
3. 다음 연산을 레지스터 $N_{\text{optimal}}$ 시간에 적용합니다.
   1. 솔루션 항목에 대해 $-1$의 조건부 위상 편이를 적용하는 위상 oracle $O_f$.
   2. 레지스터의 각 큐비트에 $H$ 적용.
   3. $\ket{0}$을 제외한 모든 계산 기반 상태로 $-1$의 조건부 위상 편이. $O_0$은 $\ket{0}$으로만 조건부 위상 편이를 나타내므로 유니터리 연산 $-O_0$으로 나타낼 수 있습니다.
   4. 레지스터의 각 큐비트에 $H$ 적용.
4. 확률이 매우 높은 솔루션인 항목의 인덱스를 가져오려면 레지스터를 측정합니다.
5. 유효한 솔루션인지 확인합니다. 그렇지 않은 경우 다시 시작합니다.

$N_\text{optimal}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{{2}\right\rfloor$는 레지스터를 측정하여 올바른 항목을 얻을 가능성을 최대화하는 최적의 반복 횟수입니다.

참고

3.b, 3.c 및 3.d 단계의 공동 적용은 일반적으로 문헌에서 Grover의 확산 연산자로 알려져 있습니다.

레지스터에 적용되는 전체 유니터리 연산은 다음과 같습니다.

$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{optimal}}}H^{\otimes n}$$

레지스터의 상태를 단계별로 수행합니다.

프로세스를 설명하기 위해 큐비트가 2개뿐이고 유효한 요소가 $\ket{01}인 간단한 경우에 대해 레지스터 상태의 수학적 변환을 수행해 보겠습니다.$

1. 레지스터는 state: $$|\text{register}\rangle=|00\rangle$$에서 시작합니다.

2. 각 큐비트에 $H$를 적용하면 레지스터의 상태가 다음으로 변환됩니다. $$|\text{register}\rangle=\frac{{1}{\sqrt{{4}}\sum_{i \in \{0,1\}^2}|i\rangle=\frac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$

3. 그런 다음, 위상 oracle이 get: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$에 적용됩니다.

4. 그런 다음 $H$는 각 큐비트에 대해 다시 작동하여 다음을 제공합니다. $$|\text{register}\rangle=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$$

5. 이제 조건부 위상 편이가 $\ket{00}$: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$를 제외한 모든 상태에 적용됩니다.

6. 마지막으로 첫 번째 Grover 반복은 $H$를 다시 get: $$|\text{register}\rangle=\ket{{01}$$에 적용함으로써 끝납니다.

   위의 단계를 따르면 단일 반복에서 유효한 항목을 찾을 수 있습니다. 나중에 볼 수 있듯이 N=4 및 단일 유효한 항목 $의 경우 N_\text{ 최적}=1$이기 때문입니다.

기하학적 설명

Grover의 알고리즘이 작동하는 이유를 확인하려면 기하학적 관점에서 알고리즘을 연구해보겠습니다. $\ket{\text{bad}}$를 검색 문제에 대한 솔루션이 아닌 모든 상태의 중첩이라고 가정합니다. $M$개의 유효한 솔루션이 있다고 가정합니다.

$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$

$\ket{\text{good}}$ 상태는 검색 문제에 대한 솔루션인 모든 상태의 중첩으로 정의됩니다.

$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$

good 및 bad는 항목이 유효하지 않거나 유효하지 않기 때문에 상호 배타적인 집합이므로 상태 $\ket{\text{good}}$ 및 $\ket{\text{bad}}$는 직교합니다. 두 상태 모두 벡터 공간에서 평면의 직교를 형성합니다. 이 평면을 사용하여 알고리즘을 시각화할 수 있습니다.

이제 $\ket{\psi}$이 $\ket{\text{good}}$ 및 $\ket{\text{bad}}$에 걸쳐있는 평면에 있는 임의의 상태라고 가정합니다. 해당 평면에 있는 모든 상태는 다음과 같이 표현될 수 있습니다.

$$\ket{\psi}=\alpha\ket{\text{good}} + \beta\ket{\text{bad}}$$

여기서 $\alpha$ 및 $\beta$은 실수입니다. 이제 리플렉션 연산자 $R_{\ket{\psi}}$을 소개하겠습니다. 여기서 $\ket{\psi}$는 평면에 있는 큐비트 상태입니다. 연산자는 다음과 같이 정의됩니다.

$$R_{\ket{\psi}}=2\ket{\psi}\bra{\psi}-\mathcal{I}$$

의 방향에 대한 리플렉션으로 기하학적으로 해석될 수 있기 때문에 $\ket{\psi}$$\ket{\psi}$에 대한 리플렉션 연산자라고 합니다. 이를 보려면 $\ket{\psi}$과 그 직교 보수 $\ket{\psi^{\perp}}$ 형식의 평면의 직교 기반을 사용합니다. 평면의 모든 상태 $\ket{\xi}$는 다음과 같은 기준으로 분해될 수 있습니다.

$$\ket{\xi}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$

$R_{\ket{\psi}}$ 연산자를 $\ket{\xi}$에 적용하는 경우:

$$R_{\ket{\psi}}\ket{\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$

연산자 $R_\ket{\psi}$은 $\ket{\psi}$에 직교하는 구성 요소를 반전하지만 $\ket{\psi}$ 구성 요소는 변경하지 않고 그대로 둡니다. 따라서 $R_\ket{\psi}$은 $\ket{\psi}$에 대한 리플렉션입니다.

Grover의 알고리즘은 모든 큐비트에 $H$를 처음 적용한 후 모든 상태의 균일한 중첩을 시작합니다. 이는 다음과 같이 작성될 수 있습니다.

$$\ket{\text{all}}=\sqrt{\frac{M}{N}}\ket{\text{good}} + \sqrt{\frac{N-M}{N}}\ket{\text{bad}}$$

따라서 상태는 평면에 있습니다. 동일한 중첩에서 측정할 때 올바른 결과를 얻을 확률은 모든}}}|^2=M/N$에 불과$|\braket{\text{}|{\text{합니다. 이는 임의 추측에서 기대하는 것입니다.

Oracle $O_f$는 검색 문제에 대한 솔루션에 부정적 단계를 추가합니다. 따라서 $\ket{\text{bad}}$ 축에 대한 리플렉션으로 작성할 수 있습니다.

$$O_f = R_{\ket{\text{bad}}}= 2\ket{\text{bad}}\bra{\text{bad}} - \mathcal{I}$$

마찬가지로 조건부 위상 편이 $O_0$은 상태 $\ket{0}$에 대한 반전된 리플렉션일 뿐입니다.

$$O_0 = R_{\ket{0}}= -2\ket{{0}\bra{0} + \mathcal{I}$$

이 사실을 알고 있으면 Grover 확산 연산 $-H^{\otimes n} O_0 H^{\otimes n}$이 $\ket{all}$ 상태에 대한 리플렉션이라는 것도 쉽게 확인할 수 있습니다. 다음을 수행하기만 하면 됩니다.

$$-H^{\otimes n} O_0 H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathcal{I}H^{\otimes n}= 2\ket{\text{all}}\bra{\text{all}} - \mathcal{I}= R_{\ket{\text{all}}}$$

Grover 알고리즘의 각 반복이 두 가지 리플렉션 $R_\ket{\text{bad}}$ 및 $R_\ket{\text{all}}$의 구상임을 증명했습니다.

각 Grover 반복의 결합된 효과는 각도 $2\theta$를 시계 반대 방향으로 회전하는 것입니다. 다행히 각도 $\theta$는 찾기가 쉽습니다. $\theta$는 $\ket{\text{all}}$과 $\ket{\text{bad}}$ 사이의 각도일 뿐이므로 스칼라 제품을 사용하여 각도를 찾을 수 있습니다. $\cos{\theta}=\braket{\text{all}|\text{bad}}$이므로 $\braket{\text{all}|\text{bad}}$를 계산해야 합니다. bad 및 good 측면에서 $\ket{\text{$\ket{\text{}}$$\ket{\text{all}}$}}$의 분해에서 다음을 따릅니다.

$$\theta = \arccos{\left(\braket{\text{all}|\text{bad}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)}$$

레지스터의 상태와 $\ket{\text{양호}}$ 한 상태 사이의 각도는 반복할 때마다 감소하여 유효한 결과를 측정할 확률이 높아질 수 있습니다. 이 확률을 계산하려면 좋은}|\text{register}}|^2$를 계산$|\braket{\text{하기만 하면 됩니다. $\ket{\text{good}}$과 $\ket{\text{register}}$$\gamma (k)$ 사이의 각도를 나타냅니다. 여기서 $k$는 반복 횟수입니다.

$$\gamma (k) =\frac{\pi}{2}-\theta -k2\theta =\frac{\pi}{{2} -(2k + 1) \theta $$

따라서 성공 확률은 다음과 같습니다.

$$P(\text{success}) = \cos^2(\gamma(k)) = \sin^2\left[(2k +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)\right]$$

최적 반복 횟수

성공 확률은 반복 횟수의 함수로 작성할 수 있으므로 성공 확률 함수를 대략 최대화하는 가장 작은 양의 정수를 계산하여 최적 반복 횟수 $N_{\text{optimal}}$을 찾을 수 있습니다.

$\sin^2{x}$가 $x=\frac{\pi}{2}$에 대해 첫 번째 최댓값에 도달합니다.

$$\frac{\pi}{{2}=(2k_{\text{optimal}} +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$$

다음 출력이 표시됩니다.

$$k_{\text{optimal}}=\frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2 =\frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N}\right)$$

마지막 단계에서 $\arccos \sqrt{1-x}=\sqrt{x} + O(x^{3/2})$.

따라서 N_\text{옵티멀}$을 $N_\text{optimal}\left=\lfloor \pi{4}\sqrt{\frac{}{N M}}}{-\frac{{1}{2}\right\rfloor$\frac{로 선택할 $수 있습니다.

복잡성 분석

이전 분석에서 유효한 항목을 찾기 위해 oracle $O_f$의 $O\left(\sqrt{\frac{N}{M}}\right)$ 쿼리가 필요합니다. 그러나 알고리즘을 시간 복잡성 측면에서 효율적으로 구현할 수 있나요? $O_0$은 $n$개의 비트에 대한 부울 연산 계산을 기반으로 하며 $O(n)$ 게이트를 사용하여 구현할 수 있는 것으로 알려져 있습니다. 또한 $n$개의 Hadamard 게이트의 두 계층도 있습니다. 따라서 두 구성 요소 모두는 반복당 $O(n)$개의 게이트만 필요합니다. $N=2^n$이므로 $O(n)=O(log(N))$를 따릅니다. 따라서 $O\left(\sqrt{\frac{N}{M}}\right)$ 반복과 반복당 $O(log(N))$개의 게이트가 필요한 경우, oracle 구현을 고려하지 않은 총 시간 복잡도는 $O\left(\sqrt{\frac{N}{M}}log(N)\right)$입니다.

알고리즘의 전반적인 복잡성은 궁극적으로 oracle $O_f$ 구현의 복잡성에 따라 달라집니다. 함수 평가가 기존 컴퓨터보다 양자 컴퓨터에서 훨씬 더 복잡한 경우, 기술적으로는 더 적은 수의 쿼리를 사용하더라도 전체 알고리즘 런타임은 양자 사례에서 더 길어질 것입니다.

참조

Grover 알고리즘에 대해 계속 학습하려는 경우 다음 원본에서 확인할 수 있습니다.

• Lov K. Grover의 원 문서
• 닐슨의 양자 검색 알고리즘 섹션, M. A. &앰프; 추앙, I. L. (2010). 양자 계산 및 양자 정보
• Arxiv.org의 Grover 알고리즘

다음 단계

• Quantum Intermediate Representation
• 벡터 및 행렬
• T 게이트 및 T 팩터리
• 다중 큐비트