Entendendo os oráculos quânticos
Um oráculo, $O$, é uma operação não exposta que é usada como entrada para outro algoritmo. Freqüentemente, essas operações são definidas usando uma função $clássica f : \{0, 1\}^n \to \{0, 1\}^m$, que recebe uma $entrada binária de n$ bits e produz uma $saída binária de m-bits$. Para fazer isso, considere uma entrada binária específica $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Você pode rotular estados de qubit como $\ket{\vec{x=\ket{}}x_{0}}\ket{{\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{n-1.}}$
Você pode primeiro tentar definir $O$ para que $O\ket{x=}\ket{f(x),}$ mas esse método tem alguns problemas. Primeiro, $f$ pode ter um tamanho diferente de entrada e saída ($n \ne m$), de modo que a aplicação $de O$ alteraria o número de qubits no registro. Em segundo lugar, mesmo se n m, a função pode não ser invertível: se $f(x) = f(y)$ para algum $x \ne y$, então $O\ket{x}= O\ket{y}$ mas $O^\dagger O\ket{x}\ne O^\dagger O\ket{y.}$$= $ Isso significa que você não pode construir a operação $adjunta O^\dagger$, e os oráculos precisam ter um adjunto definido para eles.
Definir um Oracle pelo seu efeito nos estados da base computacional
Você pode lidar com esses dois problemas introduzindo um segundo registro de $m$ qubits para manter a resposta. Em seguida, defina o efeito do oráculo em todos os estados de base computacional: para todos x $\0, 1\}^n$ e $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} $$
Agora $O = O^\dagger$ por construção e você resolveu os dois problemas anteriores.
Dica
Para ver que $O = O^{\dagger}$, observe que $O^2 =\mathbf{1}$ já que $a \oplus b \oplus b = a$ para todo $a, b \in{0, 1}$. Como resultado, $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.
É importante ressaltar que definir um Oracle dessa maneira para cada estado de base computacional $\ket{x}\ket{y}$ também define como o $O$ age para qualquer outro estado. Esse comportamento decorre imediatamente do fato de que $O$, como todas as operações quânticas, é linear no estado em que atua. Considere a operação de Hadamard, por exemplo, que é definida $H \ket{0}=\ket{+}$ e $H \ket{1}=\ket{-}$. Se você deseja saber como $H$ atua em $\ket{+}$, você pode usar que $H$ é linear,
$$\begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}} H(\ket{0} + \ket{{1})\frac{1}{\sqrt{={2}} (H\ket{0} + H\ket{1})&\\ amp; =\frac{1}{\sqrt{2}} (\ket{+} + \ket{{-}) =\frac12 ({0}\ket{ +{1} \ket{+ \ket{{0} -{1}\ket{ ) . =\ket{{0} \end{align} $$
Ao definir o oráculo $O$, você pode usar da mesma forma que qualquer estado $\ket{\psi}$ em $n + m$ qubits pode ser escrito como
$$\begin{\begin{align}\ket{\psi}& =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y}. \end{align} $$
Aqui, $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ representa os coeficientes do estado $\ket{\psi}$. Assim,
$$\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}\\& =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) O \ket{x}\ket{y}\\& =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y \oplus f(x)}. \end{align} $$
Fase Oracle
Como alternativa, você pode codificar $f$ em um oráculo $O$ aplicando uma fase com base na entrada para $O$. Por exemplo, você pode definir $O$ de tal forma que\begin{$$\begin{align} O \ket{x=} (-1)^{f(x)}\ket{x.} \end{align} $$
Se uma fase Oracle age em um registro inicialmente em um estado de base computacional $\ket{x}$, essa fase é uma fase global e, portanto, não observável. Mas esse oráculo pode ser um recurso poderoso se aplicado a uma superposição ou como uma operação controlada. Por exemplo, considere uma fase Oracle $O_f$ para uma função $f$ de qubit única. Em seguida, $$\begin{align} O_f \ket{+}& = O_f (\ket{0} +{1}\ket{ ) /\\&\sqrt{{2} amp; = ((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}) / \sqrt{2}\\& = (-1)^{f(0)} (\ket{{0} + (-1)^{f(1) - f(0){1}\ket{}) /\\{2}&\sqrt{ amp; = (-1)^{f(0)} Z^{f(0) - f(1)}\ket{+.} \end{align} $$
Observação
Observe que $Z^{-1}=Z^{\dagger}=Z$ e, portanto, $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$
De forma mais geral, ambas as visões de oráculos podem ser ampliadas para representar funções clássicas, que retornam números reais em vez de apenas um único bit.
A escolha da melhor maneira de implementar um oráculo depende muito de como esse oráculo deve ser usado em um determinado algoritmo. Por exemplo, o algoritmo Deutsch-Jozsa depende do Oracle implementado da primeira forma, enquanto o algoritmo de Grover depende do Oracle implementado da segunda maneira.
Para obter mais informações, consulte a discussão em Gilyén 1711.00465.