양자 oracle 사용 및 정의

  • 아티클

oracle O$$는 다른 알고리즘에 대한 입력으로 사용되는 노출되지 않은 작업입니다. 종종 이러한 작업은 n비트 이진 입력을 사용하고 $$m$비트 이진 출력을 생성하는 클래식 함수 $f : \{0, 1\}^n \to \{0, 1\}^m$을 $사용하여 정의됩니다. 이렇게 하려면 특정 이진 입력 $x = (x_{0}, x_{1}, \dots, x_{n-1})$을 고려합니다. 큐비트 상태에 x=\ket{}}x_\ket{{0}}{\otimesx_x_\otimes{{1}}\otimes\cdots\ket{n-1}}$로 $\ket{\vec{레이블을 지정할 수 있습니다.

O x f(x\ket{=})}$가 되도록 $먼저 O\ket{$를 정의$하려고 시도할 수 있지만 이 메서드에는 몇 가지 문제가 있습니다. 첫째, $f$에는 다른 크기의 입력 및 출력($n \ne m$)이 있을 수 있으므로 $O$를 적용하면 레지스터의 큐비트 수가 변경됩니다. 둘째, $n = m$인 경우에도 함수가 반전될 수 없습니다. 일부 $x \ne y$에 대해 $f(x) = f(y)$이면 $O\ket{x}= O\ket{y}$이지만 $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$입니다. 즉, 인접 연산 $O^\dagger$을(를) 생성할 수 없으며, 오라클에는 인접 연산이 정의되어 있어야 합니다.

계산 기준 상태에 미치는 영향으로 oracle 정의

대답을 유지하기 위해 m$ 큐비트의 두 번째 레지스터$를 도입하여 이러한 두 가지 문제를 모두 처리할 수 있습니다. 그런 다음, 모든 계산 기준 상태에서 oracle의 효과를 정의합니다. 모든 x \0, 1\}^n$ 및 $y \in \{0, 1\}^m$,{\in$

$$\begin{\begin{align} O(\ket{x}\otimes\ket{y}) =\ket{x}\otimes\ket{y \oplus f(x)}. \end{align} $$

이제 $O = O^\dagger$ 를 생성하여 이전 문제를 모두 해결했습니다.

팁

$O = O^{\dagger}$임을 확인하기 위해 모든 $a, b \in{0, 1}$에 대해 $a \oplus b \oplus b = a$이므로 $O^2 =\mathbf{1}$임에 유의합니다. 결과는 $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$입니다.

중요한 점은 각 계산 기준 상태 $\ket{x}\ket{y}$에 대한 이 방법으로 oracle을 정의하는 것은 $O$가 다른 상태에 대해 작동하는 방법도 정의합니다. 이 동작은 모든 양자 연산과 마찬가지로 O$가 $작동하는 상태에서 선형이라는 사실에서 바로 뒤따릅니다. 예를 들어 H +}$ 및 $H=\ket{0}\ket{-}$=\ket{1}\ket{ 로 정의된 $Hadamard 작업을 고려합니다. H$가 +}$에서 $\ket{작동하는 방식을 $알고 싶다면 H$가 선형인 것을 $사용할 수 있습니다.

$$\begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}} H(\ket{0} + \ket{{1}) ={2}}\frac{1}{\sqrt{(H\ket{0} + H\ket{1}) \\& =\frac{1}{\sqrt{2}} (\ket{+} + \ket{{-}) =\frac12 ({0}\ket{ +{1}\ket{+ \ket{{0} -{1}\ket{ ) . =\ket{{0} \end{align} $$

oracle $O$를 정의할 때 n + m$ 큐비트의 모든 상태를 $\ket{\psi}$$다음과 같이 작성할 수 있습니다.

$$\begin{align}\ket{\psi}&앰프; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y}\end{\end{align}$$

여기서 $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$는 상태 $\ket{\psi}$의 계수를 나타냅니다. 그러므로

$$\begin{\begin{align}O \ket{\psi}& = O \sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m\alpha}(x, y) \ket{x\ket{}y\\&}amp; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) O \ket{x}\ket{y\\&}amp; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m\alpha}(x, y) \ket{x}\ket{y \oplus f(x)}. \end{align} $$

위상 Oracle

또는 O에 입력에 따라 단계를 적용하여 f$를 oracle $O$$로 인코딩$할 $수 있습니다. 예를 들어 O$ x(-1)^{f(x}=)}\ket{x}로 $$\begin{\begin{align} O\ket{를 정의$할 수 있습니다. \end{align} $$

위상 oracle이 처음에 계산 기반 상태 $\ket{x}$에서 레지스터 역할을 하는 경우 이 위상은 전역 위상이므로 관찰할 수 없습니다. 그러나 이러한 오라클은 중첩에 적용되거나 제어된 작업으로 적용되는 경우 강력한 리소스가 될 수 있습니다. 예를 들어 단일 큐비트 함수 $f$에 대한 위상 oracle $O_f$를 고려합니다. 그런 다음 + $$amp를 O_f\ket{.}=&\begin{align} O_f (\ket{0} +{1}\ket{ ) /\\&\sqrt{{2} amp; = ((-1)^{f(0)}\ket{0} + (-1)^{f(1)\ket{1}}) /&\sqrt{2}\\ amp; = (-1)^{f(0)}({0}\ket{ + (-1)^{f(1) - f(0){1}\ket{}) /\\{2}&\sqrt{ amp; = (-1)^{f(0)} Z^{f(0) - f(1)}\ket{+.} \end{align} $$

참고

$Z^{-1}=Z^{\dagger}=Z$이므로 $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}입니다.$

더 일반적으로 오라클의 두 보기를 모두 확장하여 단일 비트가 아닌 실제 숫자를 반환하는 클래식 함수를 나타낼 수 있습니다.

오라클을 구현하는 가장 좋은 방법은 지정된 알고리즘 내에서 이 오라클을 사용하는 방법에 따라 크게 달라집니다. 예를 들어 Deutsch-Jozsa 알고리즘은 첫 번째 방법으로 구현된 oracle을 사용하는 반면 Grover의 알고리즘은 두 번째 방법으로 구현된 oracle에 따라 달라집니다.

자세한 내용은 Gilyén et al. 1711.00465의 토론을 참조하세요.

다음 단계