위상·간섭과 Grover 탐색¶

진폭 파형 모델¶

n개 큐비트의 순수상태에는 2ⁿ개 계산 기저 상태에 대한 복소 진폭이 있다. 양자 회로는 정규화를 보존하면서 이 진폭 배열을 변환하고, 측정 확률은 각 진폭 크기의 제곱이다.

이 모델은 “모든 경우를 동시에 계산한다”보다 정확하지만 두 가지 보정이 필요하다.

진폭에는 크기와 위상이 있다.
계산 이득에는 유용한 간섭을 만드는 알고리즘과 문제 구조가 필요하다.

고전 상태벡터 시뮬레이터는 2ⁿ개 진폭을 실제 메모리에 저장한다. 50큐비트만 되어도 약 10¹⁵개이므로 일반적인 완전 상태벡터 시뮬레이션은 매우 어렵다. 고전 난이도는 큐비트 수와 함께 텐서 네트워크나 안정자 기법을 적용할 수 있는 회로 구조로 평가한다.

Grover의 두 연산¶

정답이 하나인 N개 후보의 균등 중첩에서 초기 진폭은 s=1/√N이다.

오라클: 정답 상태의 진폭 부호를 뒤집는다. 확률은 변하지 않는다.
확산 연산: 모든 진폭을 평균에 대해 반사한다.

첫 오라클 뒤의 평균은 다음과 같다.

\[ m=s\frac{N-2}{N} \]

확산 a → 2m-a를 적용하면 정답 진폭은 2m+s, 즉 큰 N에서 약 3s가 된다. 각 오답 진폭은 아주 조금 감소한다. 정답이 얻은 확률은 많은 오답이 조금씩 내놓은 확률의 합과 정확히 일치한다.

회전으로 보는 Grover¶

정답 방향을 |w>, 모든 오답의 균등 결합을 |s'>로 잡으면 전체 과정은 2차원 평면의 회전이다.

초기 각도 θ는 sinθ=1/√N
오라클과 확산은 각각 반사
두 반사의 합성은 매 반복 2θ 회전
k회 뒤 정답 확률은 sin²((2k+1)θ)

작은 θ에서 θ≈1/√N이므로 최적 반복 수는 대략 다음과 같다.

\[ k\approx\frac{\pi}{4}\sqrt N \]

최적점을 지나도 회전은 계속되므로 성공 확률은 다시 낮아진다. 이것이 과회전(over-rotation) 이다.

N	θ	첫 최적 반복	성공 확률
4	30.00°	1	100%
8	20.70°	2	94.53%
16	14.48°	3	96.13%
32	10.18°	4	99.92%
64	7.18°	6	99.66%

4자리 PIN 사례¶

0000–9999의 후보를 14큐비트 공간 2¹⁴=16,384에 넣고 정답 하나를 표시한다고 하자. 초기 진폭은 1/128=0.0078125다.

단계	정답 진폭	정답 확률
초기	0.0078125	약 0.0061%
오라클 1회	-0.0078125	약 0.0061%
확산까지 1회	약 0.02344	약 0.055%
50회	약 0.7097	약 50.4%
100회	거의 1	약 99.99998%

질의 횟수만 보면 고전 평균 약 5,000회에 비해 약 100회다. 그러나 현실의 비용은 오라클 호출 한 번이 무엇인지에 달려 있다.

오라클의 실제 비용¶

오라클은 후보를 판별하는 함수를 결맞고 가역적으로 구현한 회로다.

실제 공격에는 인증 로직을 가역적인 양자 오라클로 구현하는 별도 비용이 든다.
해시를 검사하려면 해시 계산 전체를 가역 양자 회로로 만들고 보조 큐비트를 정리해야 한다.
실제 4자리 PIN은 작은 탐색 공간보다 시도 횟수 제한과 장치 보안으로 보호된다.

이 예시는 진폭 증폭과 오라클 비용을 동시에 가르치는 사례다.

Grover가 만능이 아닌 이유¶

Grover는 효율적인 결맞은 판별 회로가 있는 비정형 탐색에 일반적인 제곱근 가속을 준다. 그러나 다음 한계가 있다.

2¹⁰⁰ 후보가 2⁵⁰회로 줄어도 여전히 거대하다.
전체 실행 이득은 질의 횟수와 오라클 구현 비용을 함께 반영해 평가한다.
데이터 적재와 결과 검증, 오류 정정과 고전 전후처리를 포함해야 한다.
Grover형 검증 오라클은 비정형 탐색 알고리즘에 적용한다.

Shor와 양자 시뮬레이션은 다른 구조다¶

알고리즘	이용하는 구조	얻는 정보
Grover	판별 오라클과 진폭 증폭	표시된 후보의 위치
Shor	모듈러 함수의 주기성과 QFT	인수분해로 이어지는 주기
양자 시뮬레이션	해밀토니안의 동역학·스펙트럼	에너지·시간 변화·관측량

NP는 후보 해답을 고전적으로 다항시간에 검증할 수 있는 결정 문제의 부류다. 효율적 검증자를 Grover 오라클로 만들면 일반적인 제곱근 탐색을 적용할 수 있다. 이때 복잡도는 지수적 탐색의 제곱근 수준으로 남는다.

양자 화학에서는 결과의 정확성을 검증하고 신뢰를 구축하는 방법이 별도의 중요한 연구 과제가 된다.

측정과 재실행¶

Grover는 하나의 후보값을 측정한다. 후보는 고전 검증으로 확인하고, 실패하면 다시 실행한다. 성공까지 필요한 실행 횟수가 확률적으로 달라진다.

정답 개수를 모를 때는 양자 카운팅, BBHT 방식이나 고정점 진폭 증폭 같은 변형을 고려한다. 입문 강의에서는 “최적점을 모르면 과회전할 수 있다”는 사실까지만 다룬다.

진폭 증폭의 일반형¶

Grover 탐색은 진폭 증폭(amplitude amplification)의 특수한 경우다. 초기상태 A|0>에서 좋은 상태의 전체 확률을 a라고 하면 상태를 두 성분으로 쓸 수 있다.

\[ A|0\rangle=\sin\theta|good\rangle+ \cos\theta|bad\rangle, \qquad \sin^2\theta=a \]

한 번의 Grover 연산은 이 평면에서 상태를 2θ만큼 회전시킨다. k회 뒤 좋은 상태의 확률은 다음과 같다.

\[ \sin^2((2k+1)\theta) \]

초기 성공확률이 a이면 필요한 반복 횟수는 O(1/√a)다. 고전적인 독립 재시도는 평균 O(1/a)회가 필요하다. 이 비교는 초기상태 준비 A, 좋은 상태 판별, 두 연산의 역연산을 모두 결맞게 구현할 수 있다는 조건 위에서 성립한다.

질의 복잡도와 실제 실행 시간¶

알고리즘 논문은 종종 오라클 호출 횟수인 질의 복잡도를 분석한다. 시스템 평가는 다음 항목을 더한다.

\[ T_{total}=T_{prepare}+k(T_{oracle}+T_{diffusion}) +T_{measure}+T_{verify}+T_{retry} \]

T_prepare: 데이터와 초기상태 준비
T_oracle: 가역 판별 회로와 보조 큐비트 정리
T_diffusion: 진폭 반사 연산
T_measure: 반복 측정과 통계 수집
T_verify: 출력의 고전 검증
T_retry: 실패확률에 따른 재실행

오류내성 계산에서는 각 논리 연산이 오류 정정 주기와 연결된다. 비-Clifford 게이트에 필요한 magic state 생산 공장은 전체 물리 큐비트와 시간을 크게 늘릴 수 있다. 제곱근 질의 이득이 벽시계 시간과 비용의 이득으로 이어지는지는 이 총합으로 판단한다.

위상 추정과의 연결¶

많은 양자 알고리즘은 유니터리 U의 고유상태 |u>에 대해 \(U|u\rangle=e^{2\pi i\phi}|u\rangle\)를 만족하는 위상 φ를 추정한다. 제어된 U 연산으로 위상을 보조 레지스터에 기록하고 역양자 푸리에 변환으로 비트열을 얻는 방식이다.

Shor 알고리즘에서는 모듈러 지수함수의 주기를, 양자 화학에서는 해밀토니안의 에너지 고유값을 위상으로 바꿔 읽는다. 이 구조는 높은 정밀도에서 긴 결맞은 회로와 많은 비-Clifford 자원을 요구하므로 오류내성 장비의 대표 장기 워크로드로 분류된다.

이전: 큐비트·게이트·측정 · 심화 과정 홈 · 다음: 텐서곱과 얽힘