Deutsch-Jozsa Mal-entendido

Question

Não consigo entender o algoritmo Deutsch-Jozsa. Como sugere a wikipedia:${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$. A função recebe valores binários de n dígitos como entrada e produz 0 ou 1 como saída para cada valor. 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 {\ displaystyle f} f é constante ou balanceado usando o oráculo.

Pergunta 1: Se eu usar um algoritmo probabilístico em um computador normal, não posso simplesmente inserir uma vez um único 0 no oráculo e, em seguida, inserir uma vez um único 1. E pronto.

Eu também li aqui: http://www.diva-portal.org/smash/get/diva2:840938/FULLTEXT01.pdf: Considere que Bob gera uma lista de comprimento arbitrário a partir de uma função balanceada. Então, a lista conterá igualmente muitos zeros e uns, portanto, se Alice desenhar um elemento aleatório na lista, será um zero ou um com uma probabilidade de 1/2. Se ela desenha dois elementos. então ela pode obter os resultados ”00”, ”01”, ”10” e ”11”, cada um com uma probabilidade igual de 1/4. Se Alice agora tiver que adivinhar se a função era constante ou equilibrada, ela adivinhará corretamente na metade das vezes. Se ela desenhar um terceiro elemento, o resultado será uma distribuição de probabilidade uniforme sobre os seguintes resultados possíveis "000", "001", "010", "011", "100", "101", "110" e "111 ”. Alice agora vai adivinhar corretamente seis de oito vezes.

Qurstion 2: Então, se ela tem ”001” (ou véspera "01" / "10"), isso já não é uma função equilibrada?

Answer 1

Em relação à sua primeira pergunta, existem $n$ entradas para $f$ e a tarefa é determinar se $f$é constante ou equilibrada (sob a promessa de que é uma ou outra); você pode fazer isso em um computador quântico com uma única consulta para$f$. E se$n=1$, então, classicamente, você pode fazer o que sugere, inserir $0$ para uma consulta e entrada $1$ para outra consulta, para um total de duas consultas, mas o computador quântico ainda ganha com apenas uma consulta.

Em relação à sua segunda pergunta, sim, você está correto; se você obtiver classicamente duas saídas que diferem, então (sob a promessa) você pode ter certeza de que a função está balanceada. No entanto, Deutsch-Josza observa que você pode garantir que ele seja balanceado com apenas uma única consulta.

Classicamente, você precisa de pelo menos dois e até $2^{n-1}+1$, consultas, mas da mecânica quântica uma única consulta é suficiente.

Answer 2

Se ainda não o fez, comece dando uma olhada no algoritmo de Deutsch, que é a versão de qubit único do algoritmo de Deutsch-Jozsa que você está vendo.

Aqui você tem alguns recursos rápidos:

• http://www.cs.xu.edu/~kinne/quantum/deutche.html
• https://www.youtube.com/watch?v=5xsyx-aNClM

É mais simples do que Deutsch-Jozsa e um bom ponto de partida.