Algoritmo Deutsch – Jozsa - Deutsch–Jozsa algorithm

O algoritmo Deutsch-Jozsa é um algoritmo quântico determinístico proposto por David Deutsch e Richard Jozsa em 1992 com melhorias por Richard Cleve , Artur Ekert , Chiara Macchiavello e Michele Mosca em 1998. Embora de pouco uso prático atual, é um dos primeiros exemplos de um algoritmo quântico que é exponencialmente mais rápido do que qualquer algoritmo clássico determinístico possível.

Declaração do problema

No problema Deutsch-Jozsa, recebemos 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 dígitos como entrada e produz 0 ou 1 como saída para cada um desses valores. Temos a promessa de que a função é constante (0 em todas as saídas ou 1 em todas as saídas) ou balanceada (retorna 1 para metade do domínio de entrada e 0 para a outra metade). A tarefa então é determinar se é constante ou equilibrado usando o oráculo. ${\ displaystyle f \ dois pontos \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \}}$${\ displaystyle f}$

Motivação

O problema de Deutsch-Jozsa é projetado especificamente para ser fácil para um algoritmo quântico e difícil para qualquer algoritmo clássico determinístico. A motivação é mostrar um problema de caixa preta que pode ser resolvido de forma eficiente por um computador quântico sem erros, enquanto um computador clássico determinístico precisaria de um grande número de consultas à caixa preta para resolver o problema. Mais formalmente, ele produz um oráculo em relação ao qual EQP , a classe de problemas que pode ser resolvida exatamente em tempo polinomial em um computador quântico, e P são diferentes.

Como o problema é fácil de resolver em um computador probabilístico clássico, ele não produz uma separação de oráculo com BPP , a classe de problemas que pode ser resolvida com erro limitado em tempo polinomial em um computador probabilístico clássico. O problema de Simon é um exemplo de problema que produz uma separação de oráculo entre BQP e BPP .

Solução clássica

Para um algoritmo determinístico convencional onde n é o número de bits, avaliações de serão necessárias no pior caso. Para provar que é constante, um pouco mais da metade do conjunto de entradas deve ser avaliada e suas saídas consideradas idênticas (lembrando que a função tem garantia de ser balanceada ou constante, não em algum lugar no meio). O melhor caso ocorre quando a função é balanceada e os dois primeiros valores de saída selecionados são diferentes. Para um algoritmo randomizado convencional , uma avaliação constante da função é suficiente para produzir a resposta correta com uma alta probabilidade (falha com probabilidade com ). No entanto, as avaliações ainda são necessárias se quisermos uma resposta sempre correta. O algoritmo quântico Deutsch-Jozsa produz uma resposta que é sempre correta com uma única avaliação de . ${\ displaystyle 2 ^ {n-1} +1}$${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle k}$${\ displaystyle \ epsilon \ leq 1/2 ^ {k}}$${\ displaystyle k \ geq 1}$${\ displaystyle k = 2 ^ {n-1} +1}$${\ displaystyle f}$

História

O Algoritmo Deutsch-Jozsa generaliza o trabalho anterior (1985) de David Deutsch, que forneceu uma solução para o caso simples em que . Especificamente, recebemos uma função booleana cuja entrada é de 1 bit e perguntamos se ela é constante. ${\ displaystyle n = 1}$
${\ displaystyle f: \ {0,1 \} \ rightarrow \ {0,1 \}}$

O algoritmo proposto por Deutsch originalmente não era, de fato, determinístico. O algoritmo foi bem-sucedido com uma probabilidade de metade. 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, esse algoritmo exigia duas avaliações de função em vez de apenas uma. ${\ displaystyle n}$

Melhorias adicionais no algoritmo Deutsch-Jozsa foram feitas por Cleve et al., Resultando em um algoritmo que é determinístico e requer apenas uma única consulta de . Esse algoritmo ainda é conhecido como algoritmo de Deutsch-Jozsa em homenagem às técnicas inovadoras que empregaram. ${\ displaystyle f}$

Algoritmo

Para o algoritmo Deutsch-Jozsa ao trabalho, o oráculo de computação de tem que ser um oráculo quântica que não decohere . Ele também não deve deixar nenhuma cópia no final da chamada do oráculo. ${\ displaystyle f (x)}$${\ displaystyle x}$ ${\ displaystyle x}$${\ displaystyle x}$

O algoritmo começa com o estado do bit . Ou seja, os primeiros n bits estão cada um no estado e o bit final está . Uma transformação de Hadamard é aplicada a cada bit para obter o estado ${\ displaystyle n + 1}$${\ displaystyle | 0 \ rangle ^ {\ otimes n} | 1 \ rangle}$${\ displaystyle | 0 \ rangle}$${\ displaystyle | 1 \ rangle}$

${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| 0 \ rangle - | 1 \ rangle)}$.

Temos a função implementada como um oráculo quântico. O oráculo mapeia o estado para , onde está o módulo 2 (veja abaixo os detalhes de implementação). Aplicar o oráculo quântico dá ${\ displaystyle f}$${\ displaystyle | x \ rangle | y \ rangle}$${\ displaystyle | x \ rangle | y \ oplus f (x) \ rangle}$${\ displaystyle \ oplus}$

${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| f (x ) \ rangle - | 1 \ oplus f (x) \ rangle)}$.

Para cada um é 0 ou 1. Testando essas duas possibilidades, vemos que o estado acima é igual a ${\ displaystyle x, f (x)}$

${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x )} | x \ rangle (| 0 \ rangle - | 1 \ rangle)}$.

Neste ponto, o último qubit pode ser ignorado e, portanto, permanece abaixo: ${\ displaystyle {\ frac {| 0 \ rangle - | 1 \ rangle} {\ sqrt {2}}}}$

${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} | x \ rangle}$.

Aplicamos uma transformada Hadamard a cada qubit para obter

${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} \ left [{\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {y = 0} ^ {2 ^ {n} -1} (- 1) ^ {x \ cdot y} | y \ rangle \ right] = {\ frac {1} {2 ^ {n}}} \ sum _ {y = 0} ^ {2 ^ {n} -1} \ left [\ sum _ {x = 0 } ^ {2 ^ {n} -1} (- 1) ^ {f (x)} (- 1) ^ {x \ cdot y} \ right] | y \ rangle}$

onde é a soma do produto bit a bit (onde é módulo de adição 2). ${\ displaystyle x \ cdot y = x_ {0} y_ {0} \ oplus x_ {1} y_ {1} \ oplus \ cdots \ oplus x_ {n-1} y_ {n-1}}$${\ displaystyle \ oplus}$

Finalmente, examinamos a probabilidade de medição , ${\ displaystyle | 0 \ rangle ^ {\ otimes n}}$

${\ displaystyle {\ bigg |} {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x) } {\ bigg |} ^ {2}}$

que avalia 1 se for constante ( interferência construtiva ) e 0 se for balanceado ( interferência destrutiva ). Em outras palavras, a medição final será (ou seja, todos zeros) se for constante e produzirá alguns outros estados se estiver equilibrada. ${\ displaystyle f (x)}$${\ displaystyle f (x)}$${\ displaystyle | 0 \ rangle ^ {\ otimes n}}$${\ displaystyle f (x)}$${\ displaystyle f (x)}$

Algoritmo de Deutsch

O algoritmo de Deutsch é um caso especial do algoritmo geral de Deutsch-Jozsa. Precisamos verificar a condição . É equivalente a verificar (onde está o módulo de adição 2, que também pode ser visto como uma porta XOR quântica implementada como uma porta NOT controlada ), se zero, então é constante, caso contrário, não é constante. ${\ displaystyle f (0) = f (1)}$${\ displaystyle f (0) \ oplus f (1)}$${\ displaystyle \ oplus}$${\ displaystyle f}$${\ displaystyle f}$

Começamos com o estado de dois qubit e aplicamos uma transformada de Hadamard a cada qubit. Isso produz ${\ displaystyle | 0 \ rangle | 1 \ rangle}$

${\ displaystyle {\ frac {1} {2}} (| 0 \ rangle + | 1 \ rangle) (| 0 \ rangle - | 1 \ rangle).}$

É-nos dada uma implementação quantum da função que mapeia para . Aplicando esta função ao nosso estado atual, obtemos ${\ displaystyle f}$${\ displaystyle | x \ rangle | y \ rangle}$${\ displaystyle | x \ rangle | f (x) \ oplus y \ rangle}$

${\ displaystyle {\ 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))}$

${\ displaystyle = {\ frac {1} {2}} ((- 1) ^ {f (0)} | 0 \ rangle (| 0 \ rangle - | 1 \ rangle) + (- 1) ^ {f ( 1)} | 1 \ rangle (| 0 \ rangle - | 1 \ rangle))}$

${\ displaystyle = (- 1) ^ {f (0)} {\ frac {1} {2}} \ left (| 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle \ right) (| 0 \ rangle - | 1 \ rangle).}$

Ignoramos o último bit e a fase global e, portanto, temos o estado

${\ displaystyle {\ frac {1} {\ sqrt {2}}} (| 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle).}$

Aplicando uma transformação Hadamard a este estado, temos

${\ displaystyle {\ frac {1} {2}} (| 0 \ rangle + | 1 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 0 \ rangle - (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle)}$

${\ displaystyle = {\ frac {1} {2}} ((1 + (- 1) ^ {f (0) \ oplus f (1)}) | 0 \ rangle + (1 - (- 1) ^ { f (0) \ oplus f (1)}) | 1 \ rangle).}$

${\ displaystyle f (0) \ oplus f (1) = 0}$se e somente se medirmos e se e somente se medirmos . Portanto, com certeza sabemos se é constante ou equilibrado. ${\ displaystyle | 0 \ rangle}$${\ displaystyle f (0) \ oplus f (1) = 1}$${\ displaystyle | 1 \ rangle}$${\ displaystyle f (x)}$

Veja também

• Algoritmo de Bernstein-Vazirani

Referências

links externos

• Palestra de Deutsch sobre o algoritmo Deutsch-Jozsa