도이치 알고리즘

도이치 문제

f:{0, 1} -> {0, 1}

f는 둘 중 하나
1. 균형 함수: 입력 0과 1에 대해 출력이 다름. f(0) != f(1)
(입력과 출력이 같거나, 반전되는 둘 중 하나)
2. 불균형 함수(상수 함수): 모든 입력에 대해 출력이 같음. f(0) = f(1)

도이치 알고리즘 목표는 이 함수가 균형인지 불균형인지 결정하는 것

알고리즘 설명

1. 초기화

두 개의 큐비트
첫 번째 큐비트는 |0>, 두 번째 큐비트는 |1>로 초기화

2. 중첩

두 큐비트에 H 게이트 적용해서 중첩 상태 만듦.
첫 번째 큐비트는 루트2(|0> + |1>)
두 번째 큐비트는 루트2(|0> - |1>)로 변함

3. 함수 평가

양자 오라클로 f를 판별.
오라클은 첫 번째 큐비트를 입력으로 해서, 두 번째 큐비트에 XOR연산(CNOT)을 통해 반영

4. 다시 하다마르

첫 번째 큐비트에 다시 하다마르 게이트 적용

5. 측정

첫 번째 큐비트 측정
결과가 |0>이면 불균형 함수,
결과가 |1>이면 균형 함수

원리가 이해는 안 됨.

그로버 알고리즘

건초더미에서 바늘 찾기

문제

n개의 데이터가 들어 있는 데이터베이스에서 x를 찾기
비구조적 탐색 문제로, 고전 알고리즘의 시작 복잡도는 O(n)
근데 양자는 루트 N으로 해결 가능

풀이

1. 초기화: 모든 큐비트 0 상태로 초기화 후 중첩 생성
2. 오라클 함수(블랙박스)로 특정 조건을 만족하면 위상 변화 시키는 함수 적용. 해답을 음으로 변화.(아직 관측 전이며, 위상을 변화시킴)
3. 모든 상태 진폭 반전, 평균 진폭 주위로 해답 진폭 증폭(하다마르, 조건부 위상 반전, 다시 하다마르)
4. 대략 루트 N회 측정해서 가장 진폭이 큰 상태의 시점의 큐비트를 측정

오라클 함수 구현 예시

from qiskit import QuantumCircuit, Aer, execute
from qiskit.visualization import plot_histogram

# 오라클 함수 구현: 2에 해당하는 큐비트를 위상 변화 시킴
def oracle(qc, qubits):
    # "2"에 해당하는 상태는 |10>이므로, 첫 번째 큐비트는 1이고 두 번째 큐비트는 0이어야 합니다.
    # 이 상태를 반전시키기 위해 Z 게이트를 두 번째 큐비트에 적용합니다.
    # 하지만, Z 게이트는 직접적인 조건부 작업을 수행할 수 없으므로, CX 게이트를 사용하여 조건을 만듭니다.
    qc.cx(qubits[0], qubits[1])
    qc.cz(qubits[0], qubits[1])
    qc.cx(qubits[0], qubits[1])

# 2 큐비트 회로와 보조 큐비트(오라클의 출력을 위한) 초기화
qc = QuantumCircuit(3)

# 입력 큐비트에 하다마르 게이트 적용 (중첩 상태 생성)
qc.h([0, 1])

# 보조 큐비트를 |1> 상태로 설정 후 하다마르 게이트 적용
qc.x(2)
qc.h(2)

# 오라클 함수 적용
oracle(qc, [0, 1, 2])

# 회로 그리기
qc.draw(output='mpl')