Grover의 검색 알고리즘의 이론
이 문서에서는 Grover 알고리즘이 작동하게 하는 수학 원칙에 대한 자세한 이론적 설명을 찾을 수 있습니다.
수학 문제를 해결하기 위한 Grover 알고리즘의 실제 구현은 Grover의 검색 알고리즘 구현을 참조하세요.
문제 설명
Grover 알고리즘은 구조화되지 않은 데이터 검색(또는 검색 문제)에 대한 솔루션을 가속화하여 클래식 알고리즘보다 적은 단계로 검색을 실행합니다. 모든 검색 작업은 검색 항목 $x$를 허용하는 추상 함수 $f(x)$로 표현할 수 있습니다. 항목 $x$가 검색 작업의 솔루션인 경우 $f(x)=1$입니다. $x$ 항목이 솔루션이 아니면 $f(x)=0$입니다. 검색 문제는 f(x_0)=1$과 같은 $x_0$ 항목을 $찾는 것으로 구성됩니다.
실제로 지정된 값 $x$ 가 유효한 솔루션인지 여부를 확인할 수 있는 모든 문제(따옴표; & 예 또는 문제&따옴표 없음;) 검색 문제의 관점에서 공식화 할 수 있습니다. 예는 다음과 같습니다.
- 부울 만족도 문제: 부울 값 $집합 x$ 는 지정된 부울 수식을 충족하는 해석(변수에 값 할당)입니까?
- 여행 세일즈맨 문제: x$가 모든 도시를 연결하는 가장 짧은 루프를 설명하나요$?
- 데이터베이스 검색 문제: 데이터베이스 테이블에 레코드 $x$가 포함되어 있나요?
- 정수 팩터리화 문제: 고정 숫자 N$이 숫자 $$x$로 나눌 수 있나요?
Grover의 알고리즘이 해결하려는 작업은 다음과 같이 표현할 수 있습니다. 주어진 클래식 함수 $f(x):\{0,1\}^n \rightarrow\{0,1\}$, 여기서 $n$은 검색 공간의 비트 크기입니다. $f(x_0)=1$에 해당하는 입력 $x_0$을 찾습니다. 알고리즘의 복잡성은 $f(x)$ 함수 사용의 횟수로 측정됩니다. 고전적으로 최악의 시나리오 $에서는 f(x)$ 를 총 $N-1$ 번 평가해야 합니다. 여기서 $N=2^n$은 모든 가능성을 시험해 봅니다. N-1$ 요소 후에$는 마지막 요소여야 합니다. Grover의 양자 알고리즘은 이 문제를 훨씬 빠르게 해결할 수 있으므로 2차 속도를 제공합니다. 여기서 이차는 N에 비해 N}$ 평가만 $\sqrt{필요하다는 것을 $$의미합니다.
알고리즘 개요
$검색 작업에 적합한 N2=^n$개의 항목이 있고 각 항목에 0$에서 $N-1$로 정수로 할당하여 인덱스$라고 가정합니다. 또한 $M$개의 서로 다른 유효한 입력이 있다고 가정합니다. 이는 $f(x)=1$에 해당하는 $M$개의 입력이 있음을 의미합니다. 알고리즘의 단계는 다음과 같습니다.
- $\ket{0}$ 상태에서 초기화된 $n$개 큐비트의 레지스터로 시작합니다.
- 레지스터의 각 큐비트에 $H$를 적용하여 레지스터를 균일한 중첩으로 준비합니다. $$|\text{register}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$
- 등록 N_ 최적}}$ 시간에 다음 작업을 적용합니다.${\text{
- 단계 oracle$은$ 솔루션 항목에 대해 -1$의 $조건부 위상 이동을 적용하는 O_f.
- 레지스터의 각 큐비트에 H$를 적용$합니다.
- $\ket{0}$을 제외한 모든 계산 기반 상태로 $-1$의 조건부 위상 편이. $O_0$은 $\ket{0}$으로만 조건부 위상 편이를 나타내므로 유니터리 연산 $-O_0$으로 나타낼 수 있습니다.
- 레지스터의 각 큐비트에 H$를 적용$합니다.
- 레지스터를 측정하여 확률이 매우 높은 솔루션인 항목의 인덱스 가져오기
- 유효한 솔루션인지 확인합니다. 그렇지 않은 경우 다시 시작합니다.
$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}인 간단한 경우에 대해 레지스터 상태의 수학적 변환을 수행해 보겠습니다.$
레지스터는 00 등록 상태에서 $$|\text{}\rangle=|시작됩니다.\rangle$$
각 큐비트에 $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})$$
그런 다음, 위상 oracle이 get: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$에 적용됩니다.
그런 다음 $H$는 각 큐비트에 대해 다시 작동하여 다음을 제공합니다. $$|\text{register}\rangle=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$$
이제 조건부 위상 편이가 $\ket{00}$: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$를 제외한 모든 상태에 적용됩니다.
마지막으로 첫 번째 Grover 반복은 $H$를 다시 get: $$|\text{register}\rangle=\ket{{01}$$에 적용함으로써 끝납니다.
위의 단계를 수행하면 유효한 항목이 단일 반복에서 발견됩니다. 나중에 볼 수 있듯이 N=4 및 단일 유효한 항목 $이 N_\text{ 최적}=1$이기 때문입니다.
기하학적 설명
Grover의 알고리즘이 작동하는 이유를 확인하려면 기하학적 관점에서 알고리즘을 연구해보겠습니다. 검색 문제에 대한 해결책이 아닌 모든 상태의 중첩을 잘못}}$ 하자$\ket{\text{. M$ 유효한 솔루션이 있다고 $가정합니다.
$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$
정상 상태는 $\ket{\text{}}$ 검색 문제의 해결 방법인 모든 상태의 중첩으로 정의됩니다.
$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$
항목이 유효하고 유효하지 않기 때문에 양수 및 불량은 상호 배타적 집합이므로 양}}$수 및 $\ket{\text{불량}}$ 상태는 $\ket{\text{직교 상태입니다. 두 상태 모두 벡터 공간에서 평면의 직교 기초를 형성합니다. 이 평면을 사용하여 알고리즘을 시각화할 수 있습니다.
이제 선과 악에 걸친 $\ket{\text{비행기에 사는 임의의 상태라고 가정해 보겠습니다$\ket{\psi}$.}}$$\ket{\text{}}$ 해당 평면에 있는 모든 상태는 다음과 같이 표현할 수 있습니다.
$$\ket{\psi}=\alpha\ket{\text{good}} + \beta\ket{\text{bad}}$$
$\beta$ 여기서 $\alpha$ 실수입니다. 이제 리플렉션 연산자 $R_{\ket{\psi}}$ 소개해 보겠습니다. 여기서 $\ket{\psi}$ 는 평면에 있는 큐비트 상태입니다. 연산자는 다음과 같이 정의됩니다.
$${\ket{\psi}}=R_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}}$ \xi}$에 적용하는 $\ket{경우:
$$R_{\ket{\psi}}\ket{\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$
연산$자는 구성 요소 직교를 반전할 $\ket{\psi}$ R_\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{리플렉션으로 작성할 수 있습니다.
$$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{대한 리플렉션인지 쉽게 확인할 수 있습니다. 다음을 수행합니다.
$$-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_bad}}$ 및 $R_\ket{\text{\ket{\text{all}}$의 구성임을 입증했습니다.
각 Grover 반복의 결합된 효과는 각도 $2\theta$의 시계 반대 방향으로 회전하는 것입니다. 다행히 각도 $\theta$는 찾기가 쉽습니다. $\theta$는 $\ket{\text{all}}$과 $\ket{\text{bad}}$ 사이의 각도일 뿐이므로 스칼라 제품을 사용하여 각도를 찾을 수 있습니다. \cos\theta}=\braket{\text{가 모두}|\text{잘못된 것으로 알려져 $있으므로 모든}|\text{나쁜}}$}}$ 값을 계산$\braket{\text{해야 합니다.{ 나쁜 $\ket{\text{}}$}}$ 좋은 측면에서 모두}}$의 $\ket{\text{$\ket{\text{분해에서, 그것은 다음과 같습니다 :
$$\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 \frac{\pi{4}\sqrt{\frac{}{N}{M}}-\frac{{1}{2}\right\rfloor$로 선택할 $수 있습니다.
복잡성 분석
이전 분석에서 유효한 항목을 찾기 위해 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 알고리즘에 대한 학습을 계속하려면 다음 원본 중에서 확인할 수 있습니다.
- 로브 케이 그로버의 오리지널 논문
- 닐슨의 양자 검색 알고리즘 섹션, M. A. &앰프; 추앙, I. L. (2010). 양자 계산 및 양자 정보.
- Arxiv.org Grover 알고리즘