문제 설정
숨겨진 문자열 s\in\{0,1\}^n가 있고, 함수는 입력과의 mod 2 내적을 반환합니다.
$$
f_s(x)=s\cdot x \pmod 2
$$고전적으로는 각 비트를 확인하려면 n번 질의가 필요합니다.
Phase oracle
출력 큐비트를 |-\rangle로 두면 오라클은 아래 phase를 붙입니다.
$$
U_f|x\rangle|-\rangle=(-1)^{s\cdot x}|x\rangle|-\rangle
$$Hadamard가 문자열을 꺼내는 이유
Hadamard transform의 핵심 항등식은 아래입니다.
$$
H^{\otimes n}|x\rangle
=
{1\over\sqrt{2^n}}\sum_z (-1)^{x\cdot z}|z\rangle
$$초기 균등중첩에 phase (-1)^{s\cdot x}가 붙은 상태는 다시 Hadamard를 걸면 정확히 |s\rangle로 갑니다.
$$
H^{\otimes n}
{1\over\sqrt{2^n}}\sum_x (-1)^{s\cdot x}|x\rangle
=|s\rangle
$$예제: s=101
s=101이면 함수는 f(x)=x_1\oplus x_3입니다. 오라클은 입력 x마다 (-1)^{x_1\oplus x_3}를 붙이고, 마지막 Hadamard가 이 phase pattern을 basis state |101\rangle로 변환합니다.
복잡도
오라클 질의는 1번입니다. 회로에는 입력 레지스터 앞뒤로 Hadamard가 들어가므로 O(n)개의 단일 큐비트 게이트가 필요합니다.
왜 정확히 s가 나오는가
마지막 상태의 |z\rangle 진폭을 직접 쓰면 아래입니다.
$$
{1\over2^n}\sum_x (-1)^{s\cdot x}(-1)^{x\cdot z}
=
{1\over2^n}\sum_x (-1)^{x\cdot(s\oplus z)}
$$z=s이면 모든 항이 1이어서 진폭은 1입니다. z\ne s이면 절반은 +1, 절반은 -1로 상쇄되어 진폭이 0입니다.
$$
\Pr(z)=
\begin{cases}
1 & z=s\\
0 & z\ne s
\end{cases}
$$회로 관점
이 알고리즘은 hidden string의 각 비트를 따로 묻는 대신, 모든 입력 x에 대한 parity 정보를 phase pattern으로 한 번에 새깁니다. 마지막 Hadamard는 그 phase pattern을 계산기저 문자열로 디코딩합니다.
오라클을 실제 회로로 만들기
f_s(x)=s\cdot x는 s_i=1인 입력 비트들만 출력 큐비트에 XOR하면 됩니다. bit oracle 형태로 쓰면 아래입니다.
$$
|x_1\dots x_n,y\rangle
\mapsto
|x_1\dots x_n,y\oplus(s_1x_1\oplus\cdots\oplus s_nx_n)\rangle
$$회로에서는 s_i=1인 선에서 target y로 CNOT을 하나씩 겁니다. 예를 들어 s=101이면 1번 큐비트와 3번 큐비트에서 출력 큐비트로 CNOT 두 개를 둡니다.
$$
y \mapsto y\oplus x_1\oplus x_3
$$출력 큐비트가 |-\rangle이면 각각의 CNOT이 해당 입력 비트가 1일 때 phase -1을 붙이는 효과를 냅니다. 여러 CNOT의 phase가 곱해져 최종적으로 (-1)^{s\cdot x}가 됩니다.
s=101의 phase table
3비트 전체 입력을 표로 쓰면 Hadamard가 무엇을 디코딩하는지 더 잘 보입니다.
| x | x_1\oplus x_3 | phase |
|---|---|---|
| 000 | 0 | +1 |
| 001 | 1 | -1 |
| 010 | 0 | +1 |
| 011 | 1 | -1 |
| 100 | 1 | -1 |
| 101 | 0 | +1 |
| 110 | 1 | -1 |
| 111 | 0 | +1 |
이 부호 패턴은 아무렇게나 생긴 패턴이 아니라 s=101이라는 주파수 성분 하나입니다. 마지막 H^{\otimes 3}는 이 부호 패턴을 계산기저 |101\rangle로 바꿉니다.
고전 질의와 비교
고전적으로는 e_i를 넣어야 s_i를 알 수 있습니다.
$$
f_s(e_i)=s\cdot e_i=s_i
$$따라서 숨겨진 문자열 전체를 확정하려면 n번 질의가 필요합니다. 양자 회로는 2^n개 입력을 “각각 계산해서 읽는” 것이 아니라, 모든 입력에 대한 parity 부호를 한 번에 만들고 그 부호 패턴의 Walsh-Hadamard spectrum을 읽습니다. 이 설명이 더 정확합니다.
Walsh-Hadamard spectrum 관점
Boolean 함수 f에 대해 부호 함수 \chi_f(x)=(-1)^{f(x)}를 생각하면, Bernstein-Vazirani는 \chi_f의 Hadamard spectrum을 한 번 측정하는 알고리즘입니다.
$$
\hat{\chi}(z)
=
{1\over 2^n}\sum_x (-1)^{f(x)}(-1)^{x\cdot z}
$$f(x)=s\cdot x이면 spectrum은 z=s에서만 1이고 나머지는 0입니다. 그래서 측정값이 확률적으로 분산되지 않고 정확히 s로 고정됩니다.