숨겨진 비트열 $s$를 한 번의 오라클 질의로 찾는 알고리즘입니다. Deutsch-Jozsa보다 더 직접적으로 Hadamard 변환의 의미를 보여줍니다.
## 문제 설정 {#problem}
숨겨진 문자열 $s\in\{0,1\}^n$가 있고, 함수는 입력과의 mod 2 내적을 반환합니다.
$$
f_s(x)=s\cdot x \pmod 2
$$
고전적으로는 각 비트를 확인하려면 n번 질의가 필요합니다.
## Phase oracle {#phase}
출력 큐비트를 $|-\rangle$로 두면 오라클은 아래 phase를 붙입니다.
$$
U_f|x\rangle|-\rangle=(-1)^{s\cdot x}|x\rangle|-\rangle
$$
## Hadamard가 문자열을 꺼내는 이유 {#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 {#example}
$s=101$이면 함수는 $f(x)=x_1\oplus x_3$입니다. 오라클은 입력 $x$마다 $(-1)^{x_1\oplus x_3}$를 붙이고, 마지막 Hadamard가 이 phase pattern을 basis state $|101\rangle$로 변환합니다.
## 복잡도 {#complexity}
오라클 질의는 1번입니다. 회로에는 입력 레지스터 앞뒤로 Hadamard가 들어가므로 $O(n)$개의 단일 큐비트 게이트가 필요합니다.
## 왜 정확히 s가 나오는가 {#why-exact}
마지막 상태의 $|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}
$$
## 회로 관점 {#circuit-view}
이 알고리즘은 hidden string의 각 비트를 따로 묻는 대신, 모든 입력 $x$에 대한 parity 정보를 phase pattern으로 한 번에 새깁니다. 마지막 Hadamard는 그 phase pattern을 계산기저 문자열로 디코딩합니다.
## 오라클을 실제 회로로 만들기 {#oracle-build}
$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 {#table-s101}
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$로 바꿉니다.
## 고전 질의와 비교 {#classical-comparison}
고전적으로는 $e_i$를 넣어야 $s_i$를 알 수 있습니다.
$$
f_s(e_i)=s\cdot e_i=s_i
$$
따라서 숨겨진 문자열 전체를 확정하려면 $n$번 질의가 필요합니다. 양자 회로는 $2^n$개 입력을 “각각 계산해서 읽는” 것이 아니라, 모든 입력에 대한 parity 부호를 한 번에 만들고 그 부호 패턴의 Walsh-Hadamard spectrum을 읽습니다. 이 설명이 더 정확합니다.
## Walsh-Hadamard spectrum 관점 {#linear-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$로 고정됩니다.