1. 개요
그로버 알고리즘(Grover Algorithm)은 탐색 문제에 관한 기하학적 특성과 양자적 특성을 이용해 고전적 컴퓨터가 지수적인 시간 복잡도로 구현하는 탐색 문제를 다항 시간에 풀수 있도록 한 양자 알고리즘이다.그로버 알고리즘은 구조화되지 않은 탐색 문제를 오라클(검은 상자)라고 불리는 함수에 대입값을 집어넣어서 해에 대한 높은 확률을 산출하는데 [math(O\sqrt{N})]의 시간 복잡도를 가지도록 하는 목적이 있다는 면에서 중요하다.
인도의 컴퓨터 과학자 Lov Grover가 고안했다.
2. 알고리즘
2.1. 비구조적 탐색과 오라클
아래와 같은 함수를 하나 가정한뒤 임의의 x값을 한번 떠올리고 그것을 찾고자하는 상황을 가정하자.[math(f : (0,1…N-1)\to (0,1))]
다른 표현으로 말하자면, 이 함수는 N개의 데이터가 나열된 하나의 리스트이다.
그러면, 위 함수에서 input이 탐색 조건에 맞을 경우 [math(f(x)=1)]이 되고, 이 조건을 만족하는 데이터 x는 찾고자하는[1][math(ω)]에서만 참이 되는 상황일때, 계산적인 기저 상태의 [math(f(x))]에서 [math(ω)]를 찾는 연산을 수행해야한다. 이때 이를 수행하는 보조 연산 구조를 오라클(검은 상자)이라고 부르고, 아래와 같은 수반적인 선형 연산자로 정의한다.
[math( U_\text{ω}|x\rangle = \begin{cases} |x\rangle,\ (x=ω, f(x)=1) \\ -|x\rangle,\ (x\neω, f(x)=0)\end{cases})]
[math(U_\text{ω}|x\rangle = (-1)^{f(x)}|x\rangle)]
[math(U_\text{ω}|x\rangle = (-1)^{f(x)}|x\rangle)]
선형 연산자인 오라클은 아래와 같은 행렬식 표현도 존재한다.
[math(U_\text{ω} = \begin{pmatrix} (-1)^{f(0)} & 0 & \cdots & 0 \\ 0 & (-1)^{f(1)} & \cdots & 0 \\ \vdots & 0 & \ddots & 0 \\ 0 & 0 & \cdots & (-1)^{f(2^{n}-1)} \end{pmatrix})]
2.1.1. 대안?
위의 오라클은 데이터를 탐색하기 위해 함수로 정의된 리스트에 접근하는 양자 알고리즘의 표준과 살짝 거리가 있어, 원래의 오라클에 추가로 함숫값에 대한 선형적인 상태를 나타내는 오라클 [math(U_\text{f})]을 대안으로 사용하기도 한다. 이를 아다마르 게이트로 다른 오라클을 대안으로 사용될수 있음을 증명할수 있다.대안 오라클 f를 논리 회로의 부정 게이트와 논리합을 사용하여 정의하면,
[math(U_\text{f}|x\rangle|y\rangle = \begin{cases} |x\rangle| ¬ y\rangle,\ (x=ω, f(x)=1) \\ |x\rangle|y\rangle,\ (x\neω, f(x)=0)\end{cases})]
[math(U_\text{f}|x\rangle|y\rangle = |x\rangle|y \oplus f(x) \rangle)]
아다마르 게이트를 적용하면,
[math(\displaystyle U_\text{f}(|x\rangle \oplus |-\rangle)=\dfrac{(U_\text{f}|x\rangle|0\rangle-U_\text{f}|x\rangle|1\rangle)}{\sqrt{2}})]
= [math(\displaystyle \dfrac{(|x\rangle|0\rangle-|x\rangle|1 \oplus f(x)\rangle)}{\sqrt{2}})]
= [math(\displaystyle \begin{cases} \dfrac{-(|x\rangle|0\rangle+|x\rangle|1\rangle)}{\sqrt{2}},\ (x=ω, f(x)=1) \\ \\ \dfrac{(|x\rangle|0\rangle-|x\rangle|1\rangle)}{\sqrt{2}},\ (x\neω, f(x)=0)\end{cases})]
= [math((U_\text{f}|x\rangle) \oplus |-\rangle)]
그러므로, 대안 오라클 f가 양자 알고리즘에 적합하다는 증명이된다.
2.2. 구현
Grover Algorithm:
Input: 함숫값이 2진수로 정의되는 데이터 집합 x
Output: 탐색하고자 하는 데이터값 [math(ω)]
Procedure:
1. 아다마르 변환을 이용해 input된 임의의 데이터를 다음과 같은 공식으로 양자 중첩화한다.
2. 아래와 같은 그로버 연속 법칙으로, 중첩화된 식에 오라클을 대입한 연산을 수행한다.
3. 계산적 기저의 양자 상태를 측정해 특징적인 output을 얻는다. 단, 리스트의 다른 데이터들의 확률 진폭이 output의 확률 진폭과 비슷하면, 2번 단계로 되돌아가 다시 수행한다.
Input: 함숫값이 2진수로 정의되는 데이터 집합 x
Output: 탐색하고자 하는 데이터값 [math(ω)]
Procedure:
1. 아다마르 변환을 이용해 input된 임의의 데이터를 다음과 같은 공식으로 양자 중첩화한다.
| [math(\displaystyle |s\rangle = \dfrac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle)] |
2. 아래와 같은 그로버 연속 법칙으로, 중첩화된 식에 오라클을 대입한 연산을 수행한다.
| [math(U_\text{s}=2|s\rangle \langle s|-1)] |
3. 계산적 기저의 양자 상태를 측정해 특징적인 output을 얻는다. 단, 리스트의 다른 데이터들의 확률 진폭이 output의 확률 진폭과 비슷하면, 2번 단계로 되돌아가 다시 수행한다.
2.2.1. output의 기하적 탐색
output에 대한 양자 중첩 상태를 가지는 정보를 평면으로 전개하는 방법이 있다.x축이 모함수인 [math(|s’\rangle)], y축이 비구조적 탐색 문단에서 언급했던 임의의 데이터의 상태 [math(|ω\rangle)]로 구성된 평면과 [math(ω)]의 확률 진폭을 나타내는 [math(|s\rangle)]는 평면에서 위치로 나타낼수 있음을 정의하자,
위의 정의하에 그로버 알고리즘은 x축 위에 존재하는 [math(|s\rangle)]부터 탐색을 시작한다.
[math(\displaystyle θ=\operatorname{arcsin} \left< s|ω \right> = \operatorname{arcsin}\dfrac{1}{\sqrt{N}})]으로 가정할때,
[math(|s\rangle)]에 대한 초기 상태의 확률 진폭은 아래와 같이 정의된다.
[math(|s\rangle = \operatorname{cos}θ|s’\rangle + \operatorname{sin}θ|ω\rangle)]
이후에, 초기 값을 역수로 대응하는 값을 산출하는 오라클 [math(U_\text{f})]을 적용하면, [math(|s\rangle)]는 초기 확률진폭의 평면상의 위치에 x축에 대칭하는 음수의 [math(|s\rangle)]위치로 나타내어진다.
음수가 된 [math(|s\rangle)]에 대한 오라클 [math(U_\text{s})]을 아래와 같은 식을 적용하면,
[math(U_\text{s}=2|s\rangle \langle s|-1)]
이전의 초기값과 오라클을 적용한 값에 대하여 역수로 대응하는 값을 산출하므로, [math(|s\rangle)]의 확률 진폭은 2배가되고, output으로 확정할수 있다.
3. 인터프리팅
3.1. python(qiskit)
아래의 코드는 0000 오라클을 예시로한 코드로 0000을 제외한 나머지 15개의 오라클 준비 코드에서의 qc.x(q[n])는 오라클에 위치한 1의 여부에 따라 생략한다.#!syntax python
print('\nGrovers Algorithm')
print('------------------\n')
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute,IBMQ
import math
from qiskit.tools.monitor import job_monitor
IBMQ.enable_account('Enter API token')
provider = IBMQ.get_provider(hub='ibm-q')
pi = math.pi
q = QuantumRegister(4,'q')
c = ClassicalRegister(4,'c')
qc = QuantumCircuit(q,c)
print('\nInitialising Circuit...\n')
qc.h(q[0])
qc.h(q[1])
qc.h(q[2])
qc.h(q[3])
print('\nPreparing Oracle circuit....\n')
qc.x(q[0])
qc.x(q[1])
qc.x(q[2])
qc.x(q[3])
qc.cu1(pi/4, q[0], q[3])
qc.cx(q[0], q[1])
qc.cu1(-pi/4, q[1], q[3])
qc.cx(q[0], q[1])
qc.cu1(pi/4, q[1], q[3])
qc.cx(q[1], q[2])
qc.cu1(-pi/4, q[2], q[3])
qc.cx(q[0], q[2])
qc.cu1(pi/4, q[2], q[3])
qc.cx(q[1], q[2])
qc.cu1(-pi/4, q[2], q[3])
qc.cx(q[0], q[2])
qc.cu1(pi/4, q[2], q[3])
qc.x(q[0])
qc.x(q[1])
qc.x(q[2])
qc.x(q[3])
print('\nPreparing Amplification circuit....\n')
qc.h(q[0])
qc.h(q[1])
qc.h(q[2])
qc.h(q[3])
qc.x(q[0])
qc.x(q[1])
qc.x(q[2])
qc.x(q[3])
qc.cu1(pi/4, q[0], q[3])
qc.cx(q[0], q[1])
qc.cu1(-pi/4, q[1], q[3])
qc.cx(q[0], q[1])
qc.cu1(pi/4, q[1], q[3])
qc.cx(q[1], q[2])
qc.cu1(-pi/4, q[2], q[3])
qc.cx(q[0], q[2])
qc.cu1(pi/4, q[2], q[3])
qc.cx(q[1], q[2])
qc.cu1(-pi/4, q[2], q[3])
qc.cx(q[0], q[2])
qc.cu1(pi/4, q[2], q[3])
qc.x(q[0])
qc.x(q[1])
qc.x(q[2])
qc.x(q[3])
qc.h(q[0])
qc.h(q[1])
qc.h(q[2])
qc.h(q[3])
qc.barrier(q)
qc.measure(q[0], c[0])
qc.measure(q[1], c[1])
qc.measure(q[2], c[2])
qc.measure(q[3], c[3])
backend = provider.get_backend('ibmq_qasm_simulator')
print('\nExecuting job....\n')
job = execute(qc, backend, shots=100)
job_monitor(job)
counts = job.result().get_counts()
print('RESULT: ',counts,'\n')
print('Press any key to close')
input()4. 참고문헌
- https://qiskit.org/textbook/ch-algorithms/grover.html
- https://en.m.wikipedia.org/wiki/Grover%27s_algorithm
[1] 특징점을 가지는.