그로버 알고리즘
덤프버전 :
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{ω} = \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된 임의의 데이터를 다음과 같은 공식으로 양자 중첩화한다.
||<tablealign=center><tablebordercolor=#eee,#2d2f34><bgcolor=#eee,#2d2f34> [math(\displaystyle |s\rangle = \dfrac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle)] ||
2. 아래와 같은 그로버 연속 법칙으로, 중첩화된 식에 오라클을 대입한 연산을 수행한다.
||<tablealign=center><tablebordercolor=#eee,#2d2f34><bgcolor=#eeeeee,#2d2f34> [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 θ=arcsin \left< s|ω \right> = arcsin \dfrac{1}{\sqrt{N}})]으로 가정할때,
[math(|s\rangle)]에 대한 초기 상태의 확률 진폭은 아래와 같이 정의된다.
[math(|s\rangle = cosθ|s’\rangle + 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의 여부에 따라 생략한다.
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. 참고문헌[편집]
이 문서의 내용 중 전체 또는 일부는 2023-11-14 20:52:12에 나무위키 그로버 알고리즘 문서에서 가져왔습니다.[1] 특징점을 가지는.