그로버 알고리즘

양자 컴퓨팅에서 **그로버 탐색 알고리즘**은 **양자 탐색 알고리즘**으로도 알려져 있으며, 특정 출력값을 생성하는 블랙박스 함수의 고유 입력을 높은 확률로 찾는 비정형 탐색을 위한 양자 알고리즘이다. 이 함수는 함수의 정의역 크기를 N이라고 할 때 O(\sqrt{N})번만 평가하면 된다. 이 알고리즘은 1996년 로브 그로버에 의해 고안되었다.s2cid=207198067 고전적 계산에서 유사한 문제는 O(N)의 쿼리 복잡도를 가지는데(즉, 함수를 O(N)번 평가해야 한다: 평균적으로 N/2 단계를 거쳐 모든 입력 값을 하나씩 시도하는 것보다 더 나은 접근 방식은 없다). 찰스 H. 베넷, 이선 번스타인, 질 브라사르, 그리고 우메시 바지라니는 문제에 대한 어떤 양자 해결책도 함수를 \Omega(\sqrt{N})번 평가해야 함을 증명했으며, 따라서 그로버 탐색 알고리즘은 점근적으로 최적이다.arxiv=quant-ph/9701001 NP-완전 문제에 대한 고전적 알고리즘은 지수적으로 많은 단계를 요구하며, 그로버 탐색 알고리즘은 비정형 탐색에 대한 고전적 해결책에 비해 기껏해야 제곱근 속도 향상을 제공하므로, 그로버 탐색 알고리즘 자체만으로는 NP-완전 문제에 대한 다항 시간 해결책을 제공하지 못함을 시사한다 (지수 함수의 제곱근은 여전히 다항 함수가 아닌 지수 함수이기 때문이다).pages=276–305 고전적 알고리즘에 비해 지수적 속도 향상을 제공할 수 있는 다른 양자 알고리즘과 달리, 그로버 탐색 알고리즘은 제곱근 속도 향상만을 제공한다. 그러나 N이 클 때 제곱근 속도 향상조차도 상당하며, 그로버 탐색 알고리즘은 광범위한 알고리즘의 속도를 높이는 데 적용될 수 있다. 그로버 탐색 알고리즘은 128비트 대칭 암호화 키를 약 264회 반복으로, 256비트 키를 약 2128회 반복으로 무차별 대입할 수 있다. 그러나 그로버 탐색 알고리즘이 기존 고전적 알고리즘에 비해 암호화에 대한 위험을 크게 증가시키지는 않을 수 있다.isbn = 978-3-642-12928-5
# 응용과 한계
그로버 탐색 알고리즘은 진폭 증폭과 같은 변형과 함께 광범위한 알고리즘의 속도를 높이는 데 사용될 수 있다.isbn = 0-89791-962-9arxiv=quant-ph/0504012language=en 특히, 완전 탐색을 서브루틴으로 포함하는 NP-완전 문제 알고리즘은 그로버 탐색 알고리즘에 의해 속도가 향상될 수 있다. 3SAT에 대한 최악의 경우 복잡도 측면에서 현재 이론적으로 가장 좋은 알고리즘이 그러한 예시이다. 일반적인 제약 충족 문제도 그로버 탐색 알고리즘으로 제곱근 속도 향상을 보인다.url-access=subscription 이러한 알고리즘은 그로버 탐색 알고리즘이 명시적 함수(예: 비트 집합이 3SAT 인스턴스를 만족하는지 확인하는 함수)와 함께 적용되므로 입력이 오라클 형태로 주어질 필요가 없다. 그러나 그로버 탐색 알고리즘이 이러한 문제에 대한 최상의 실제 알고리즘의 속도를 높일 수 있는지는 불분명하다. 그로버 탐색 알고리즘은 양자 쿼리 복잡도에서 원소 구별성arxiv=quant-ph/0311001과 충돌 문제를 포함한 블랙박스 문제에 대해 증명 가능한 속도 향상을 제공할 수 있다isbn = 978-3-540-64275-6 (브라사르-호이어-탭 알고리즘으로 해결). 이러한 유형의 문제에서 오라클 함수 f는 데이터베이스로 취급되며, 목표는 이 함수에 대한 양자 쿼리를 가능한 한 적게 사용하는 것이다.
## 암호학
그로버 탐색 알고리즘은 본질적으로 함수 역산의 과제를 해결한다. 대략적으로 말하면, 양자 컴퓨터에서 평가될 수 있는 함수 y = f(x)가 있다면, 그로버 탐색 알고리즘은 y가 주어졌을 때 x를 계산할 수 있게 해준다. 결과적으로, 그로버 탐색 알고리즘은 충돌 공격 및 원상 공격을 포함한 대칭 키 암호에 대한 여러 종류의 무차별 대입 공격에 광범위한 점근적 속도 향상을 제공한다.oclc=318545517 그러나 예를 들어, 폴라드 로 알고리즘은 그로버 탐색 알고리즘보다 SHA-2에서 충돌을 더 효율적으로 찾을 수 있으므로 이것이 반드시 가장 효율적인 알고리즘은 아닐 수 있다.pages=105–117
## 한계
그로버의 원래 논문은 이 알고리즘을 데이터베이스 탐색 알고리즘으로 설명했으며, 이 설명은 여전히 흔하다. 이 비유에서 데이터베이스는 해당 입력으로 인덱싱된 모든 함수의 출력 테이블이다. 그러나 이 데이터베이스는 명시적으로 표현되지 않는다. 대신, 오라클이 인덱스로 항목을 평가하기 위해 호출된다. 전체 데이터베이스 항목을 하나씩 읽고 그러한 표현으로 변환하는 것은 그로버 탐색보다 훨씬 오래 걸릴 수 있다. 이러한 효과를 설명하기 위해 그로버 알고리즘은 방정식을 풀거나 제약 조건을 만족시키는 것으로 볼 수 있다. 이러한 응용 프로그램에서 오라클은 제약 조건을 확인하는 방법이며 탐색 알고리즘과 관련이 없다. 이러한 분리는 일반적으로 알고리즘 최적화를 방지하는 반면, 기존 탐색 알고리즘은 종종 이러한 최적화에 의존하고 완전 탐색을 피한다. 다행히도, 많은 제약 충족 및 최적화 문제에 대해 빠른 그로버 오라클 구현이 가능하다.s2cid=258236417 그로버 알고리즘의 속도 향상을 구현하는 데 있어 주요 장벽은 달성된 2차 속도 향상이 근시일 내 양자 컴퓨터의 큰 오버헤드를 극복하기에는 너무 미미하다는 것이다.doi-access=free 그러나 더 나은 하드웨어 성능을 가진 차세대 오류 내성 양자 컴퓨터는 실제 데이터 인스턴스에 대해 이러한 속도 향상을 실현할 수 있을 것이다.
# 문제 설명
그로버 알고리즘의 입력으로, 함수 f\colon \\{0,1,\ldots,N-1\\} \to \\{0,1\\}가 있다고 가정하자. "비정형 데이터베이스" 비유에서, 도메인은 데이터베이스에 대한 인덱스를 나타내며, 1=f(x) = 1은 x가 가리키는 데이터가 검색 기준을 만족할 때에만 해당된다. 또한 우리는 오직 하나의 인덱스만이 1=f(x) = 1을 만족하며, 이 인덱스를 ω라고 부른다. 우리의 목표는 ω를 식별하는 것이다. 우리는 유니터리 작용소 Uω 형태로 서브루틴(때때로 오라클이라고 불림)을 사용하여 f에 접근할 수 있으며, Uω는 다음과 같이 작동한다: \begin{cases} U_\omega |x\rang = -|x\rang & \text{for } x = \omega \text{, that is, } f(x) = 1, \\\ U_\omega |x\rang = |x\rang & \text{for } x \ne \omega \text{, that is, } f(x) = 0. \end{cases} 이는 n = \lceil \log_{2} N \rceil 큐비트를 가진 양자 레지스터가 제공하는 N-차원 상태 공간 \mathcal{H}를 사용한다. 이는 종종 다음과 같이 쓰여진다: U_\omega|x\rang = (-1)^{f(x)}|x\rang. 그로버 탐색 알고리즘은 Uω를 O(\sqrt{N})번 적용하여 최소 1/2의 확률로 ω를 출력한다. 이 확률은 그로버 탐색 알고리즘을 여러 번 실행함으로써 임의로 크게 만들 수 있다. ω가 발견될 때까지 그로버 탐색 알고리즘을 실행하면, 기대되는 적용 횟수는 평균적으로 두 번만 실행되므로 여전히 O(\sqrt{N})이다.
## 대안 오라클 정의
이 섹션에서는 위 오라클 U_\omega를 오라클 U_f와 비교한다. Uω는 함수 f에 대한 표준 양자 오라클과 다르다. 이 표준 오라클은 여기서 Uf로 표기되며, 보조 큐비트 시스템을 사용한다. 연산은 보조 시스템의 f(x) 값에 따라 주 시스템에서 NOT 게이트 반전 연산을 나타낸다. \begin{cases} U_f |x\rang |y\rang = |x\rang |\neg y\rang & \text{for } x = \omega \text{, that is, } f(x) = 1, \\\ U_f |x\rang |y\rang = |x\rang |y\rang & \text{for } x \ne \omega \text{, that is, } f(x) = 0, \end{cases} 또는 간단히, U_f |x\rang |y\rang = |x\rang |y \oplus f(x)\rang. 이러한 오라클은 일반적으로 역계산을 사용하여 구현된다. 만약 Uf가 오라클로 주어진다면, Uω도 구현할 수 있다. Uω는 보조 큐비트가 상태 |-\rang = \frac1{\sqrt2}\big(|0\rang - |1\rang\big) = H|1\rang에 있을 때 Uf와 같기 때문이다. \begin{align} U_f \big( |x\rang \otimes |-\rang \big) &= \frac1{\sqrt2} \left( U_f |x\rang |0\rang - U_f |x\rang |1\rang \right)\\\ &= \frac1{\sqrt2} \left(|x\rang |0 \oplus f(x)\rang - |x\rang |1 \oplus f(x)\rang \right)\\\ &= \begin{cases} \frac1{\sqrt2} \left(-|x\rang |0\rang + |x\rang |1\rang\right) & \text{if } f(x) = 1, \\\ \frac1{\sqrt2} \left( |x\rang |0\rang - |x\rang |1\rang \right) & \text{if } f(x) = 0 \end{cases} \\\ &= (U_\omega |x\rang) \otimes |-\rang \end{align} 따라서 어떤 오라클이 주어지든 그로버 탐색 알고리즘은 실행될 수 있다. Uf가 주어지면, 우리는 |-\rang 상태에 있는 추가 큐비트를 유지하고 Uω 대신 Uf를 적용해야 한다.
# 알고리즘
그로버 탐색 알고리즘의 양자 회로 표현 그로버 탐색 알고리즘의 단계는 다음과 같다. # 모든 상태에 대한 균일 중첩으로 시스템을 초기화한다.