그로버 알고리즘

양자 컴퓨팅에서 그로버 탐색 알고리즘은 양자 탐색 알고리즘으로도 알려져 있으며, 특정 출력값을 생성하는 블랙박스 함수의 고유 입력을 높은 확률로 찾는 비정형 탐색을 위한 양자 알고리즘이다. 이 함수는 함수의 정의역 크기를 $N$이라고 할 때 $O({\sqrt {N}})$번만 평가하면 된다. 이 알고리즘은 1996년 로브 그로버에 의해 고안되었다.

고전적 계산에서 유사한 문제는 $O(N)$의 쿼리 복잡도를 가지는데(즉, 함수를 $O(N)$번 평가해야 한다: 평균적으로 $N/2$ 단계를 거쳐 모든 입력 값을 하나씩 시도하는 것보다 더 나은 접근 방식은 없다).

찰스 H. 베넷, 이선 번스타인, 질 브라사르, 그리고 우메시 바지라니는 문제에 대한 어떤 양자 해결책도 함수를 $\Omega ({\sqrt {N}})$번 평가해야 함을 증명했으며, 따라서 그로버 탐색 알고리즘은 점근적으로 최적이다. NP-완전 문제에 대한 고전적 알고리즘은 지수적으로 많은 단계를 요구하며, 그로버 탐색 알고리즘은 비정형 탐색에 대한 고전적 해결책에 비해 기껏해야 제곱근 속도 향상을 제공하므로, 그로버 탐색 알고리즘 자체만으로는 NP-완전 문제에 대한 다항 시간 해결책을 제공하지 못함을 시사한다 (지수 함수의 제곱근은 여전히 다항 함수가 아닌 지수 함수이기 때문이다).

고전적 알고리즘에 비해 지수적 속도 향상을 제공할 수 있는 다른 양자 알고리즘과 달리, 그로버 탐색 알고리즘은 제곱근 속도 향상만을 제공한다. 그러나 $N$이 클 때 제곱근 속도 향상조차도 상당하며, 그로버 탐색 알고리즘은 광범위한 알고리즘의 속도를 높이는 데 적용될 수 있다. 그로버 탐색 알고리즘은 128비트 대칭 암호화 키를 약 2⁶⁴회 반복으로, 256비트 키를 약 2¹²⁸회 반복으로 무차별 대입할 수 있다. 그러나 그로버 탐색 알고리즘이 기존 고전적 알고리즘에 비해 암호화에 대한 위험을 크게 증가시키지는 않을 수 있다.

응용과 한계

그로버 탐색 알고리즘은 진폭 증폭과 같은 변형과 함께 광범위한 알고리즘의 속도를 높이는 데 사용될 수 있다. 특히, 완전 탐색을 서브루틴으로 포함하는 NP-완전 문제 알고리즘은 그로버 탐색 알고리즘에 의해 속도가 향상될 수 있다. 3SAT에 대한 최악의 경우 복잡도 측면에서 현재 이론적으로 가장 좋은 알고리즘이 그러한 예시이다. 일반적인 제약 충족 문제도 그로버 탐색 알고리즘으로 제곱근 속도 향상을 보인다. 이러한 알고리즘은 그로버 탐색 알고리즘이 명시적 함수(예: 비트 집합이 3SAT 인스턴스를 만족하는지 확인하는 함수)와 함께 적용되므로 입력이 오라클 형태로 주어질 필요가 없다. 그러나 그로버 탐색 알고리즘이 이러한 문제에 대한 최상의 실제 알고리즘의 속도를 높일 수 있는지는 불분명하다.

그로버 탐색 알고리즘은 양자 쿼리 복잡도에서 원소 구별성과 충돌 문제를 포함한 블랙박스 문제에 대해 증명 가능한 속도 향상을 제공할 수 있다 (브라사르-호이어-탭 알고리즘으로 해결). 이러한 유형의 문제에서 오라클 함수 f는 데이터베이스로 취급되며, 목표는 이 함수에 대한 양자 쿼리를 가능한 한 적게 사용하는 것이다.

암호학

그로버 탐색 알고리즘은 본질적으로 함수 역산의 과제를 해결한다. 대략적으로 말하면, 양자 컴퓨터에서 평가될 수 있는 함수 $y=f(x)$가 있다면, 그로버 탐색 알고리즘은 $y$가 주어졌을 때 $x$를 계산할 수 있게 해준다. 결과적으로, 그로버 탐색 알고리즘은 충돌 공격 및 원상 공격을 포함한 대칭 키 암호에 대한 여러 종류의 무차별 대입 공격에 광범위한 점근적 속도 향상을 제공한다. 그러나 예를 들어, 폴라드 로 알고리즘은 그로버 탐색 알고리즘보다 SHA-2에서 충돌을 더 효율적으로 찾을 수 있으므로 이것이 반드시 가장 효율적인 알고리즘은 아닐 수 있다.

한계

그로버의 원래 논문은 이 알고리즘을 데이터베이스 탐색 알고리즘으로 설명했으며, 이 설명은 여전히 흔하다. 이 비유에서 데이터베이스는 해당 입력으로 인덱싱된 모든 함수의 출력 테이블이다. 그러나 이 데이터베이스는 명시적으로 표현되지 않는다. 대신, 오라클이 인덱스로 항목을 평가하기 위해 호출된다. 전체 데이터베이스 항목을 하나씩 읽고 그러한 표현으로 변환하는 것은 그로버 탐색보다 훨씬 오래 걸릴 수 있다. 이러한 효과를 설명하기 위해 그로버 알고리즘은 방정식을 풀거나 제약 조건을 만족시키는 것으로 볼 수 있다. 이러한 응용 프로그램에서 오라클은 제약 조건을 확인하는 방법이며 탐색 알고리즘과 관련이 없다. 이러한 분리는 일반적으로 알고리즘 최적화를 방지하는 반면, 기존 탐색 알고리즘은 종종 이러한 최적화에 의존하고 완전 탐색을 피한다. 다행히도, 많은 제약 충족 및 최적화 문제에 대해 빠른 그로버 오라클 구현이 가능하다.

그로버 알고리즘의 속도 향상을 구현하는 데 있어 주요 장벽은 달성된 2차 속도 향상이 근시일 내 양자 컴퓨터의 큰 오버헤드를 극복하기에는 너무 미미하다는 것이다. 그러나 더 나은 하드웨어 성능을 가진 차세대 오류 내성 양자 컴퓨터는 실제 데이터 인스턴스에 대해 이러한 속도 향상을 실현할 수 있을 것이다.

문제 설명

그로버 알고리즘의 입력으로, 함수 $f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}$가 있다고 가정하자. "비정형 데이터베이스" 비유에서, 도메인은 데이터베이스에 대한 인덱스를 나타내며, f(x) = 1은 x가 가리키는 데이터가 검색 기준을 만족할 때에만 해당된다. 또한 우리는 오직 하나의 인덱스만이 f(x) = 1을 만족하며, 이 인덱스를 ω라고 부른다. 우리의 목표는 ω를 식별하는 것이다.

우리는 유니터리 작용소 U_ω 형태로 서브루틴(때때로 오라클이라고 불림)을 사용하여 f에 접근할 수 있으며, U_ω는 다음과 같이 작동한다:

$${\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}$$

이는 $n=\lceil \log _{2}N\rceil$ 큐비트를 가진 양자 레지스터가 제공하는 $N$-차원 상태 공간 ${\mathcal {H}}$를 사용한다. 이는 종종 다음과 같이 쓰여진다:

$$U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .$$

그로버 탐색 알고리즘은 U_ω를 $O({\sqrt {N}})$번 적용하여 최소 1/2의 확률로 ω를 출력한다. 이 확률은 그로버 탐색 알고리즘을 여러 번 실행함으로써 임의로 크게 만들 수 있다. ω가 발견될 때까지 그로버 탐색 알고리즘을 실행하면, 기대되는 적용 횟수는 평균적으로 두 번만 실행되므로 여전히 $O({\sqrt {N}})$이다.

대안 오라클 정의

이 섹션에서는 위 오라클 $U_{\omega }$를 오라클 $U_{f}$와 비교한다.

U_ω는 함수 f에 대한 표준 양자 오라클과 다르다. 이 표준 오라클은 여기서 U_f로 표기되며, 보조 큐비트 시스템을 사용한다. 연산은 보조 시스템의 f(x) 값에 따라 주 시스템에서 NOT 게이트 반전 연산을 나타낸다.

$${\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0,\end{cases}}$$

또는 간단히,

$$U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .$$

이러한 오라클은 일반적으로 역계산을 사용하여 구현된다.

만약 U_f가 오라클로 주어진다면, U_ω도 구현할 수 있다. U_ω는 보조 큐비트가 상태 $|-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle$에 있을 때 U_f와 같기 때문이다.

$${\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|x\rangle |1\rangle \right)\\&={\frac {1}{\sqrt {2}}}\left(|x\rangle |0\oplus f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)\\&={\begin{cases}{\frac {1}{\sqrt {2}}}\left(-|x\rangle |0\rangle +|x\rangle |1\rangle \right)&{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)&{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}$$

따라서 어떤 오라클이 주어지든 그로버 탐색 알고리즘은 실행될 수 있다. U_f가 주어지면, 우리는 $|-\rangle$ 상태에 있는 추가 큐비트를 유지하고 U_ω 대신 U_f를 적용해야 한다.

알고리즘

그로버 탐색 알고리즘의 양자 회로 표현

그로버 탐색 알고리즘의 단계는 다음과 같다.

1. 모든 상태에 대한 균일 중첩으로 시스템을 초기화한다.

$|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .$

1. 다음 "그로버 반복"을 $r(N)$번 수행한다.
   1. 연산자 $U_{\omega }$를 적용한다.
   2. 그로버 확산 연산자 $U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I$를 적용한다.
2. 결과 양자 상태를 계산 기저에서 측정한다.

올바르게 선택된 $r$ 값에 대해, N ≫ 1일 때 출력은 1에 가까운 확률로 $|\omega \rangle$가 된다. 분석 결과 $r(N)$의 최종 값은 $r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }$을 만족한다.

이 알고리즘의 단계를 구현하는 것은 큐비트 수에 비례하는 게이트 수로 가능하다. 따라서 이 알고리즘의 게이트 복잡도는 $O(\log(N)r(N))$ 또는 반복당 $O(\log(N))$이다.

기하학적 증명

그로버 탐색 알고리즘의 첫 번째 반복에 대한 기하학적 해석을 보여주는 그림. 상태 벡터 $|s\rangle$가 표시된 것처럼 대상 벡터 $|\omega \rangle$를 향해 회전한다.

그로버 탐색 알고리즘은 각 단계 후 양자 상태가 2차원 부분 공간에 머무른다는 관찰에 따라 기하학적 해석을 갖는다. $|s\rangle$와 $|\omega \rangle$에 의해 생성되는 평면을 고려하자. 동등하게, $|\omega \rangle$와 수직 켓 $\textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle$에 의해 생성되는 평면을 고려하자.

그로버 탐색 알고리즘은 부분 공간에 놓인 초기 켓 $|s\rangle$로 시작한다. 연산자 $U_{\omega }$는 $|s'\rangle$와 $|\omega \rangle$에 의해 생성되는 평면의 벡터에 대해 $|\omega \rangle$에 수직인 초평면에서 반사이다. 즉, $|s'\rangle$에 대한 반사로 작동한다. 이는 $U_{\omega }$를 하우스홀더 반사 형태로 작성함으로써 알 수 있다.

$$U_{\omega }=I-2|\omega \rangle \langle \omega |.$$

연산자 $U_{s}=2|s\rangle \langle s|-I$는 $|s\rangle$를 통한 반사이다. 두 연산자 $U_{s}$와 $U_{\omega }$는 $|s'\rangle$와 $|\omega \rangle$에 의해 생성되는 평면의 상태를 평면의 상태로 변환한다. 따라서 그로버 탐색 알고리즘은 전체 알고리즘 동안 이 평면에 머무른다.

각 그로버 반복 단계의 연산자 $U_{s}U_{\omega }$가 상태 벡터를 $\theta =2\arcsin {\tfrac {1}{\sqrt {N}}}$만큼 회전시킨다는 것은 쉽게 확인할 수 있다. 따라서 충분한 반복을 통해 초기 상태 $|s\rangle$에서 원하는 출력 상태 $|\omega \rangle$로 회전할 수 있다. 초기 켓은 $|\omega \rangle$에 수직인 상태에 가깝다.

$$\langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.$$

기하학적으로, $|s\rangle$와 $|s'\rangle$ 사이의 각도 $\theta /2$는 다음과 같이 주어진다.

$$\sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.$$

상태 벡터가 $|\omega \rangle$에 가까워졌을 때 멈춰야 한다. 그 후의 반복은 상태 벡터를 $|\omega \rangle$에서 멀어지게 하여 올바른 답을 얻을 확률을 감소시킨다. 올바른 답을 측정할 정확한 확률은 다음과 같다.

$$\sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),$$

여기서 r은 그로버 반복 횟수(정수)이다. 따라서 거의 최적의 측정을 얻는 가장 빠른 시간은 $r\approx \pi {\sqrt {N}}/4$이다.

대수적 증명

대수적 분석을 완성하기 위해 $U_{s}U_{\omega }$를 반복적으로 적용할 때 어떤 일이 발생하는지 알아야 한다. 이를 수행하는 자연스러운 방법은 행렬의 고유값 분석을 통하는 것이다. 전체 계산 동안 알고리즘의 상태는 $s$와 $\omega$의 선형 결합이라는 점에 주목하자. $\{|s\rangle ,|\omega \rangle \}$로 생성되는 공간에서 $U_{s}$와 $U_{\omega }$의 작용을 다음과 같이 쓸 수 있다.

${\begin{aligned}U_{s}:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\\U_{\omega }:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\end{aligned}}$

따라서 $\{|\omega \rangle ,|s\rangle \}$ 기저(이는 직교 기저도, 전체 공간의 기저도 아니다)에서 $U_{\omega }$ 다음에 $U_{s}$를 적용하는 $U_{s}U_{\omega }$의 작용은 다음 행렬로 주어진다.

$$U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.$$

이 행렬은 매우 편리한 조르당 표준형을 가지고 있다. $t=\arcsin(1/{\sqrt {N}})$라고 정의하면,

$$U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}$$

여기서 $M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.$

따라서 r-번째 행렬 거듭제곱(r번 반복에 해당)은 다음과 같다.

$$(U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.$$

이 형태를 사용하여 삼각 함수 항등식을 통해 이전 섹션에서 언급된 r번의 반복 후 ω를 관찰할 확률을 계산할 수 있다.

$$\left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).$$

또는, 최적에 가까운 구별 시간이 2rt와 −2rt 각도가 가능한 한 멀리 떨어져 있을 때, 즉 $2rt\approx \pi /2$ 또는 $r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4$일 때라고 합리적으로 상상할 수 있다. 그러면 시스템은 다음 상태에 있게 된다.

$$[|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.$$

간단한 계산을 통해 관찰 결과가 $O\left({\frac {1}{N}}\right)$의 오차로 올바른 답인 ω를 산출함을 알 수 있다.

확장 및 변형

여러 개의 일치하는 항목

 진폭 증폭 문서에 이 부분의 추가 정보가 있습니다.

만약 일치하는 항목이 1개가 아니라 k개라면, 동일한 알고리즘이 작동하지만 반복 횟수는 ${\textstyle {\frac {\pi }{4}}{N^{1/2}}}$ 대신 ${\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}$여야 한다.

k를 알 수 없는 경우를 처리하는 여러 가지 방법이 있다. 간단한 해결책은 상수 계수까지 최적으로 작동한다: k 값을 점진적으로 줄여가면서 그로버 탐색 알고리즘을 반복적으로 실행한다. 예를 들어, 일치하는 항목이 발견될 때까지 t번째 반복에서 $k=N,N/2,N/4,\ldots$와 같이 $k=N/2^{t}$를 취한다.

충분히 높은 확률로, 일부 상수 c에 대해 $t=\log _{2}(N/k)+c$ 반복으로 표시된 항목이 발견될 것이다. 따라서 총 반복 횟수는 최대

$${\frac {\pi }{4}}{\Big (}1+{\sqrt {2}}+{\sqrt {4}}+\cdots +{\sqrt {\frac {N}{k2^{c}}}}{\Big )}=O{\big (}{\sqrt {N/k}}{\big )}.$$

k를 알 수 없는 경우의 또 다른 접근 방식은 양자 계수 알고리즘을 통해 사전에 이를 도출하는 것이다.

만약 $k=N/2$ (또는 $N=2$로 실행되는 기존의 단일 표시 상태 그로버 알고리즘)이라면, 알고리즘은 증폭을 제공하지 않을 것이다. 만약 $k>N/2$라면, k가 증가함에 따라 해를 얻는 데 필요한 반복 횟수가 증가하기 시작할 것이다. 반면에, 만약 $k\geq N/2$라면, 단일 무작위 입력 선택에 대한 고전적인 확인 오라클 실행은 정답을 줄 가능성이 더 높다.

이 알고리즘의 변형은 충돌 문제를 해결하는 데 사용된다.

양자 부분 탐색

그로버와 라다크리슈난은 2004년에 그로버 탐색 알고리즘의 변형인 양자 부분 탐색을 설명했다. 부분 탐색에서는 대상 항목의 정확한 주소를 찾는 것이 아니라 주소의 처음 몇 자리 숫자에만 관심이 있다. 동등하게, 검색 공간을 블록으로 "나누고" "대상 항목이 어느 블록에 있는가?"라고 묻는 것으로 생각할 수 있다. 많은 응용 분야에서, 대상 주소에 원하는 정보가 포함되어 있다면 이러한 검색만으로도 충분한 정보를 제공한다. 예를 들어, L. K. 그로버가 제시한 예시를 사용하면, 학급 석차별로 정리된 학생 목록이 있을 때, 학생이 하위 25%, 25–50%, 50–75% 또는 75–100% 백분위수에 속하는지에만 관심이 있을 수 있다.

부분 탐색을 설명하기 위해, 각각 $b=N/K$ 크기의 $K$개 블록으로 분리된 데이터베이스를 고려한다. 부분 탐색 문제는 더 쉽다. 고전적으로 우리가 취할 접근 방식을 고려해 보자 – 무작위로 하나의 블록을 선택한 다음 나머지 블록(집합론적 언어에서는 보완)을 통해 일반적인 검색을 수행한다. 대상을 찾지 못하면, 검색하지 않은 블록에 있다는 것을 알 수 있다. 평균 반복 횟수는 $N/2$에서 $(N-b)/2$로 줄어든다.

그로버 탐색 알고리즘은 ${\textstyle {\frac {\pi }{4}}{\sqrt {N}}}$번의 반복을 필요로 한다. 부분 탐색은 블록 수 $K$에 따라 달라지는 수치적 요인만큼 더 빠를 것이다. 부분 탐색은 $n_{1}$번의 전역 반복과 $n_{2}$번의 지역 반복을 사용한다. 전역 그로버 연산자는 $G_{1}$로, 지역 그로버 연산자는 $G_{2}$로 지정된다.

글로벌 그로버 연산자는 블록에 작용한다. 기본적으로 다음과 같이 주어진다.

1. 전체 데이터베이스에 $j_{1}$번 표준 그로버 반복을 수행한다.
2. $j_{2}$번 지역 그로버 반복을 수행한다. 지역 그로버 반복은 각 블록에 대한 그로버 반복의 직접 합이다.
3. 한 번의 표준 그로버 반복을 수행한다.

$j_{1}$과 $j_{2}$의 최적 값은 그로버와 라다크리슈난의 논문에서 논의된다. 또한, "해상도"의 다른 수준에서 연속적인 부분 탐색을 적용하면 어떻게 되는지 궁금할 수도 있다. 이 아이디어는 블라디미르 코레핀과 쉬에 의해 자세히 연구되었으며, 그들은 이를 이진 양자 탐색이라고 불렀다. 그들은 이것이 단일 부분 탐색을 수행하는 것보다 실제로 더 빠르지 않음을 증명했다.

최적성

그로버 탐색 알고리즘은 부상수 요인까지 최적이다. 즉, 연산자 U_ω만을 사용하여 데이터베이스에 접근하는 어떤 알고리즘도 그로버 탐색 알고리즘만큼 최소 $1-o(1)$ 비율의 U_ω를 적용해야 한다. k개의 일치하는 항목에 대한 그로버 탐색 알고리즘의 확장, π(N/k)^1/2/4 또한 최적이다. 이 결과는 양자 계산의 한계를 이해하는 데 중요하다.

만약 그로버 탐색 문제가 U_ω를 $\log ^{c}N$번 적용하여 해결될 수 있었다면, NP 문제를 그로버 유형 탐색 문제로 변환함으로써 NP가 BQP에 포함된다는 것을 의미할 것이다. 그로버 탐색 알고리즘의 최적성은 양자 컴퓨터가 NP-완전 문제를 다항 시간 내에 해결할 수 없으며, 따라서 NP가 BQP에 포함되지 않는다는 것을 시사한다.

비지역 숨은 변수 양자 컴퓨터의 한 종류는 $N$개 항목 데이터베이스의 검색을 최대 $O({\sqrt[{3}]{N}})$ 단계 내에 구현할 수 있음이 밝혀졌다. 이는 그로버 탐색 알고리즘이 걸리는 $O({\sqrt {N}})$ 단계보다 빠르다.

같이 보기

• 진폭 증폭
• 브라사르-호이어-탭 알고리즘 (충돌 문제 해결용)
• 쇼어 알고리즘 (인수분해용)
• 양자 워크 탐색

각주

• Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769–777, 2001. Pedagogical review of the algorithm and its history.
• Grover L.K.: QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today The Sciences, July/August 1999, pp. 24–30.
• Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
• What's a Quantum Phone Book?, Lov Grover, Lucent Technologies

외부 링크

• 데이비 와이비럴. “양자 회로 시뮬레이터”. 2017년 1월 16일에 원본 문서에서 보존된 문서. 2017년 1월 13일에 확인함. 
• 크레이그 기드니 (2013년 3월 5일). “그로버의 양자 탐색 알고리즘”. 2020년 11월 17일에 원본 문서에서 보존된 문서. 2013년 3월 8일에 확인함. 
• 프랑수아 슈바르첸트루버 (2013년 5월 18일). “그로버 알고리즘”. 
• 알렉산더 프로코페냐. “그로버 탐색 알고리즘을 구현하는 양자 회로”. 울프럼 알파. 
• “양자 계산 이론”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• 로베르토 마에스트레 (2018년 5월 11일). “R 및 C로 구현된 그로버 알고리즘”. 《깃허브》. 
• 베른하르트 외머. “QCL - 양자 컴퓨터를 위한 프로그래밍 언어”. 2022년 4월 30일에 확인함. /qcl-0.6.4/lib/grover.qcl에 구현됨