Entendendo oráculos quânticos

Um oráculo, $O$, é uma operação não exposta que é usada como entrada para outro algoritmo. Muitas vezes, tais operações são definidas usando uma função $clássica f : \{0, 1\}^n \to \{0, 1\}^m$, que usa uma $entrada binária n-bit$ e produz uma $saída binária m-bit$. 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 que 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 $adjoint O^\dagger$, e os oráculos precisam ter um adjoint definido para eles.

Definir um oráculo pelo seu efeito nos estados de base computacional

Você pode lidar com esses dois problemas introduzindo um segundo registro de $m$ qubits para conter 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 ambos os problemas anteriores.

É importante ressaltar que definir um oráculo dessa forma para cada estado $\ket{de base computacional x}\ket{y}$ também define como $O$ age para qualquer outro estado. Este 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$ age 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 (\ket{{0} +{1} \ket{+ -{1}{0} \ket{\ket{) . =\ket{{0} \end{align} $$

Ao definir o oracle $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} $$

Oráculos de fase

Como alternativa, você pode codificar $f$ em um oráculo $O$ aplicando uma fase baseada na entrada para $O$. Por exemplo, você pode definir $O$ tal que $$\begin{\begin{align} O \ket{x}= (-1)^{f(x)}\ket{x}. \end{align} $$

Se um oráculo de fase atua em um registro inicialmente em um estado $\ket{de base computacional x}$, então esta fase é uma fase global e, portanto, não observável. Mas tal oráculo pode ser um recurso poderoso se aplicado a uma superposição ou como uma operação controlada. Por exemplo, considere um oráculo de fase O_f$ para uma função $de qubit $único f$. 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} $$

Mais geralmente, 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.

Escolher a melhor maneira de implementar um oráculo depende muito de como esse oráculo deve ser usado dentro de um determinado algoritmo. Por exemplo, o algoritmo Deutsch-Jozsa depende do oráculo implementado da primeira maneira, enquanto o algoritmo de Grover depende do oráculo implementado da segunda maneira.

Para mais informações, ver a discussão em Gilyén 1711.00465.

Conteúdos relacionados

• Algoritmo de Grover
• Representação Intermediária Quântica
• Vetores e matrizes
• Portões T e fábricas T