Bit oracle
가장 표준적인 오라클은 아래입니다.
$$
U_f|x,y\rangle=|x,y\oplus f(x)\rangle
$$이 형태는 항상 reversible입니다. 입력 x가 보존되고 target에 함수값만 XOR로 기록되기 때문입니다.
Phase oracle
출력 큐비트를 |-\rangle로 준비하면 bit oracle은 phase oracle이 됩니다.
$$
U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle
$$Grover, Deutsch-Jozsa, Bernstein-Vazirani에서 이 변환이 반복됩니다.
Reversible embedding
고전 함수 g(x)가 비가역이어도 아래처럼 만들면 reversible합니다.
$$
|x,0\rangle\mapsto |x,g(x)\rangle
$$하지만 중간 계산값 garbage가 남을 수 있습니다.
$$
|x,0,0\rangle\mapsto |x,g(x),\mathrm{garbage}(x)\rangle
$$Uncomputation
garbage를 남기면 간섭이 깨집니다. 계산, 결과 복사, 역계산 순서로 지웁니다.
$$
|x,0,0\rangle
\xrightarrow{compute}
|x,g(x),h(x)\rangle
\xrightarrow{copy}
|x,g(x),h(x),g(x)\rangle
\xrightarrow{compute^{-1}}
|x,0,0,g(x)\rangle
$$예제: AND oracle
AND는 Toffoli로 구현됩니다.
$$
|a,b,y\rangle\mapsto |a,b,y\oplus ab\rangle
$$이 패턴을 조합하면 Boolean formula oracle을 만들 수 있습니다. 비용은 AND/OR/NOT을 reversible gate로 바꾸는 과정에서 결정됩니다.
bit oracle에서 phase oracle로 바꾸기
출력 큐비트를 |-\rangle로 준비하는 trick은 오라클 설계의 기본 문법입니다.
$$
|-\rangle={|0\rangle-|1\rangle\over\sqrt2}
$$f(x)=0이면 출력은 그대로입니다.
$$
|y\oplus0\rangle \quad\Rightarrow\quad |-\rangle
$$f(x)=1이면 출력 큐비트에 X가 걸립니다. 그런데 X|-\rangle=-|-\rangle이므로 입력 레지스터에 phase가 붙은 것처럼 보입니다.
$$
U_f|x\rangle|-\rangle
=
(-1)^{f(x)}|x\rangle|-\rangle
$$이렇게 출력 큐비트는 계산 결과를 담는 레지스터가 아니라 phase를 입력 쪽에 되돌려주는 도구가 됩니다.
Boolean formula oracle 예시
예를 들어 아래 함수를 생각합니다.
$$
f(a,b,c)=(a\land b)\oplus c
$$reversible하게 구현하려면 먼저 ancilla t에 a\land b를 계산합니다.
$$
|a,b,c,y,0\rangle
\xrightarrow{\mathrm{CCX}_{a,b\to t}}
|a,b,c,y,ab\rangle
$$그 다음 t와 c를 target y에 XOR합니다.
$$
|a,b,c,y,ab\rangle
\mapsto
|a,b,c,y\oplus ab\oplus c,ab\rangle
$$마지막으로 Toffoli를 한 번 더 적용해 t를 0으로 되돌립니다.
$$
|a,b,c,y\oplus f(a,b,c),ab\rangle
\xrightarrow{\mathrm{CCX}_{a,b\to t}}
|a,b,c,y\oplus f(a,b,c),0\rangle
$$이 마지막 uncompute가 없으면 ancilla가 입력과 얽힌 채 남습니다. Grover 같은 간섭 알고리즘에서는 이 garbage가 정답/오답 진폭의 깔끔한 반사를 방해합니다.
garbage가 왜 위험한가
오라클이 아래처럼 동작한다고 해봅니다.
$$
|x\rangle|0\rangle
\mapsto
(-1)^{f(x)}|x\rangle|g(x)\rangle
$$겉으로는 phase가 붙었지만, 서로 다른 x가 서로 다른 g(x)를 남기면 입력 레지스터끼리 더 이상 같은 공간에서 간섭하지 못합니다. 진폭의 합과 상쇄는 같은 basis state에 도달한 경로끼리 일어납니다. garbage가 남으면 경로가 서로 다른 꼬리표를 달고 흩어지는 셈입니다.
따라서 오라클 설계의 기본 원칙은 “필요한 결과만 남기고 나머지는 원래대로 돌린다”입니다. compute-copy-uncompute 패턴은 이 원칙을 회로로 적은 것입니다.
오라클 문서에 남길 항목
- 입력 레지스터와 target 레지스터 정의
- 사용한 ancilla 수와 초기값
- bit oracle인지 phase oracle인지
- garbage가 최종적으로 0으로 돌아오는지
- Toffoli, CX, controlled phase 수
- 오라클 한 번의 depth와 전체 알고리즘 반복 횟수