O algoritmo de Deutsch–Jozsa é um algoritmo quântico determinístico proposto por David Deutsch e Richard Jozsa em 1992 com melhorias de Richard Cleve, Artur Ekert, Chiara Macchiavello e Michele Mosca em 1998. Embora tenha pouca utilidade prática, é um dos primeiros exemplos de um algoritmo quântico que é exponencialmente mais rápido do que qualquer possível algoritmo clássico determinístico.
O problema de Deutsch–Jozsa é especificamente projetado para ser fácil para um algoritmo quântico e difícil para qualquer algoritmo clássico determinístico. É um problema de caixa preta que pode ser resolvido eficientemente por um computador quântico sem erro, enquanto um computador clássico determinístico precisaria de um número exponencial de consultas à caixa preta para resolver o problema. Mais formalmente, produz um oráculo relativo ao qual EQP, a classe de problemas que podem ser resolvidos exatamente em tempo polinomial em um computador quântico, e P são diferentes.
Como o problema é fácil de resolver em um computador clássico probabilístico, ele não produz uma separação de oráculo com BPP, a classe de problemas que podem ser resolvidos com erro limitado em tempo polinomial em um computador clássico probabilístico. O problema de Simon é um exemplo de problema que produz uma separação de oráculo entre BQP e BPP.
Enunciado do problema No problema de Deutsch–Jozsa, temos um computador quântico de caixa preta conhecido como oráculo que implementa alguma função:
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 é constante ou balanceada usando o oráculo.
Solução clássica Para um algoritmo determinístico convencional onde é o número de bits, avaliações de serão necessárias no pior caso. Para provar que é 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, avaliações constantes da função são suficientes para produzir a resposta correta com alta probabilidade (falhando com probabilidade com ). No entanto, 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 .
História O algoritmo de Deutsch–Jozsa generaliza o trabalho anterior (1985) de David Deutsch, que forneceu uma solução para o caso simples onde . Especificamente, descobrir se uma dada função booleana cuja entrada é um bit, , é 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 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 . Este algoritmo ainda é referido como algoritmo de Deutsch–Jozsa em homenagem às técnicas inovadoras que empregaram.
Algoritmo
Para que o algoritmo de Deutsch–Jozsa funcione, o oráculo que computa a partir de deve ser um oráculo quântico que não cause decoerência em . Em sua computação, ele não pode fazer uma cópia de , pois isso violaria o teorema da não clonagem. O ponto de vista do algoritmo de Deutsch-Jozsa de como um oráculo significa que não importa o que o oráculo faz, pois ele apenas precisa realizar sua transformação prometida.
thumb|400px|right|Circuito quântico do algoritmo de Deutsch-Jozsa
O algoritmo começa com o estado de bits . Isto é, os primeiros n bits estão cada um no estado e o bit final é . Uma porta de Hadamard é aplicada a cada bit para obter o estado
onde percorre todas as strings binárias de bits, que podem ser representadas por números de a . Temos a função implementada como um oráculo quântico. O oráculo mapeia seu estado de entrada para , onde denota adição módulo 2. Aplicando o oráculo quântico obtemos:
Para cada é 0 ou 1. Testando essas duas possibilidades, vemos que o estado acima é igual a
Neste ponto, o último qubit pode ser ignorado e o seguinte permanece:
Em seguida, faremos cada qubit passar por uma porta de Hadamard. A transformação total sobre todos os qubits pode ser expressa com a seguinte identidade:
( é a soma do produto bit a bit). Isto resulta em
A partir disso, podemos ver que a probabilidade de um estado ser medido é
A probabilidade de medir , correspondendo a , é
que vale 1 se é constante (interferência construtiva) e 0 se é balanceada (interferência destrutiva). Em outras palavras, a medição final será (todos os zeros) se e somente se é constante e produzirá algum outro estado se é balanceada.
Algoritmo de Deutsch O algoritmo de Deutsch é um caso especial do algoritmo geral de Deutsch–Jozsa onde n = 1 em . Precisamos verificar a condição . É equivalente a verificar (onde é 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 é constante, caso contrário não é constante.
Começamos com o estado de dois qubits e aplicamos uma porta de Hadamard a cada qubit. Isto produz
Recebemos uma implementação quântica da função que mapeia para . Aplicando esta função ao nosso estado atual obtemos
Ignoramos o segundo qubit e a fase global e, portanto, temos o estado
Aplicando uma porta de Hadamard a este estado temos
se e somente se medirmos e se e somente se medirmos . Então, com certeza sabemos se é constante ou balanceada.
Implementação do algoritmo Deutsch–Jozsa em Qiskit 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.
thumb|Circuito quântico balanceado de Deutsch-Jozsa
Ver também Algoritmo de Bernstein–Vazirani
Referências
Ligações externas Aula de Deutsch sobre o algoritmo de Deutsch-Jozsa
Categoria:Algoritmos quânticos