Algoritmo de Deutsch-Jozsa

No problema de Deutsch–Jozsa, temos um computador quântico de caixa preta conhecido como oráculo que implementa alguma função: f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}} A função recebe valores binários de n bits como entrada e produz 0 ou 1 como saída para cada valor. É-nos prometido que a função é ou constante (0 em todas as entradas ou 1 em todas as entradas) ou balanceada (1 para exatamente metade do domínio de entrada e 0 para a outra metade). A tarefa então é determinar se f {\displaystyle f} é constante ou balanceada usando o oráculo.

Para um algoritmo determinístico convencional onde n {\displaystyle n} é o número de bits, 2 n − 1 + 1 {\displaystyle 2^{n-1}+1} avaliações de f {\displaystyle f} serão necessárias no pior caso. Para provar que f {\displaystyle f} é constante, pouco mais da metade do conjunto de entradas deve ser avaliado e suas saídas descobertas como idênticas (porque a função é garantida como balanceada ou constante, não algo intermediário). O melhor caso ocorre quando a função é balanceada e os dois primeiros valores de saída são diferentes. Para um algoritmo randomizado convencional, k {\displaystyle k} avaliações constantes da função são suficientes para produzir a resposta correta com alta probabilidade (falhando com probabilidade ϵ ≤ 1 / 2 k {\displaystyle \epsilon \leq 1/2^{k}} com k ≥ 1 {\displaystyle k\geq 1} ). No entanto, k = 2 n − 1 + 1 {\displaystyle k=2^{n-1}+1} avaliações ainda são necessárias se quisermos uma resposta que não tenha possibilidade de erro. O algoritmo quântico Deutsch-Jozsa produz uma resposta sempre correta com uma única avaliação de f {\displaystyle f} .

O algoritmo de Deutsch–Jozsa generaliza o trabalho anterior (1985) de David Deutsch, que forneceu uma solução para o caso simples onde n = 1 {\displaystyle n=1} . Especificamente, descobrir se uma dada função booleana cuja entrada é um bit, f : { 0 , 1 } → { 0 , 1 } {\displaystyle f:\{0,1\}\to \{0,1\}} , é constante. O algoritmo, como Deutsch o propôs originalmente, não era determinístico. O algoritmo tinha sucesso com probabilidade de um meio. Em 1992, Deutsch e Jozsa produziram um algoritmo determinístico que foi generalizado para uma função que recebe n {\displaystyle n} bits como entrada. Ao contrário do algoritmo de Deutsch, este algoritmo exigia duas avaliações da função em vez de apenas uma. Melhorias adicionais ao algoritmo de Deutsch–Jozsa foram feitas por Cleve et al., resultando em um algoritmo que é tanto determinístico quanto requer apenas uma única consulta de f {\displaystyle f} . Este algoritmo ainda é referido como algoritmo de Deutsch–Jozsa em homenagem às técnicas inovadoras que empregaram.

Para que o algoritmo de Deutsch–Jozsa funcione, o oráculo que computa f ( x ) {\displaystyle f(x)} a partir de x {\displaystyle x} deve ser um oráculo quântico que não cause decoerência em x {\displaystyle x} . Em sua computação, ele não pode fazer uma cópia de x {\displaystyle x} , pois isso violaria o teorema da não clonagem. O ponto de vista do algoritmo de Deutsch-Jozsa de f {\displaystyle f} como um oráculo significa que não importa o que o oráculo faz, pois ele apenas precisa realizar sua transformação prometida. O algoritmo começa com o estado de n + 1 {\displaystyle n+1} bits | 0 ⟩ ⊗ n | 1 ⟩ {\displaystyle |0\rangle ^{\otimes n}|1\rangle } . Isto é, os primeiros n bits estão cada um no estado | 0 ⟩ {\displaystyle |0\rangle } e o bit final é | 1 ⟩ {\displaystyle |1\rangle } . Uma porta de Hadamard é aplicada a cada bit para obter o estado 1 2 n + 1 ∑ x = 0 2 n − 1 | x ⟩ ( | 0 ⟩ − | 1 ⟩ ) , {\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle ),}

O algoritmo de Deutsch é um caso especial do algoritmo geral de Deutsch–Jozsa onde n = 1 em f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}} . Precisamos verificar a condição f ( 0 ) = f ( 1 ) {\displaystyle f(0)=f(1)} . É equivalente a verificar f ( 0 ) ⊕ f ( 1 ) {\displaystyle f(0)\oplus f(1)} (onde ⊕ {\displaystyle \oplus } é adição módulo 2, que também pode ser vista como uma porta XOR quântica implementada como uma porta NOT controlada), se zero, então f {\displaystyle f} é constante, caso contrário f {\displaystyle f} não é constante. Começamos com o estado de dois qubits | 0 ⟩ | 1 ⟩ {\displaystyle |0\rangle |1\rangle } e aplicamos uma porta de Hadamard a cada qubit. Isto produz 1 2 ( | 0 ⟩ + | 1 ⟩ ) ( | 0 ⟩ − | 1 ⟩ ) . {\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).} Recebemos uma implementação quântica da função f {\displaystyle f} que mapeia | x ⟩ | y ⟩ {\displaystyle |x\rangle |y\rangle } para | x ⟩ | f ( x ) ⊕ y ⟩ {\displaystyle |x\rangle |f(x)\oplus y\rangle } . Aplicando esta função ao nosso estado atual obtemos 1 2 ( | 0 ⟩ ( | f ( 0 ) ⊕ 0 ⟩ − | f ( 0 ) ⊕ 1 ⟩ ) + | 1 ⟩ ( | f ( 1 ) ⊕ 0 ⟩ − | f ( 1 ) ⊕ 1 ⟩ ) ) = 1 2 ( ( − 1 ) f ( 0 ) | 0 ⟩ ( | 0 ⟩ − | 1 ⟩ ) + ( − 1 ) f ( 1 ) | 1 ⟩ ( | 0 ⟩ − | 1 ⟩ ) ) = ( − 1 ) f ( 0 ) 1 2 ( | 0 ⟩ + ( − 1 ) f ( 0 ) ⊕ f ( 1 ) | 1 ⟩ ) ( | 0 ⟩ − | 1 ⟩ ) . {\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))\\&={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))\\&=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).\end{aligned}}}

O circuito quântico mostrado aqui é de um exemplo simples de como o algoritmo de Deutsch–Jozsa pode ser implementado em Python usando Qiskit, uma estrutura de desenvolvimento de software de computação quântica de código aberto da IBM.