Existe um algoritmo quântico como o algoritmo de Deutsch que calcula AND em vez de XOR?

O algoritmo de Deutsch é uma computação quântica bem conhecida $f(0) + f(1)\mod{2}$ com apenas uma avaliação de $f$ . Se substituirmos $+$ por $\cdot$ o problema parecerá bastante diferente. Minha pergunta é: existe um algoritmo quântico calculando o valor de $f(0)\cdot f(1)$ (ou AND, se você preferir) usando apenas uma avaliação de $f$ . Caso contrário: sabe-se que esse algoritmo não existe?

Atualização: agora tomei conhecimento de um procedimento que fornece uma resposta correta com uma probabilidade maior do que qualquer procedimento clássico é capaz. O "erro" é unilateral, no sentido de sempre produzir a resposta correta quando $f(0)\wedge f(1)=1$ . Isso me leva a uma pergunta estendida: existe um algoritmo de quentum (possivelmente semelhante ao mencionado abaixo) com a propriedade de que o resultado é $1$ somente se $f(0)\wedge f(1)=1$ ? Obviamente, o "melhor cenário" seria um algoritmo que fornece a resposta correta com probabilidade $1$ .

Esta é a tarefa 3, questão 5, da introdução contínua de Richard Cleve ao curso de computação quântica . (Parece que essa tarefa estava vencida hoje.)

Embora não devamos responder perguntas de lição de casa no CSTheory, felizmente a tarefa responde a todas as suas perguntas. Ele também leva você através da construção do algoritmo quântico. Eu recomendo a leitura.

Primeiro, prepare um estado (que pode ser feito facilmente usando uma consulta de caixa preta única e unitaristas). Observe que dois desses estados correspondentes a diferentes têm sempre produto interno . Você pode facilmente transformar essa observação em um algoritmo que tenha êxito com erro unilateral ou melhor, se você permitir erro bilateral (observe que o melhor procedimento clássico pode atingir probabilidade no máximo ).$\frac{1}{\sqrt{3}}((-1)^{f(0)}|00\rangle + (-1)^{f(1)}|01\rangle + |11\rangle)$$f$$\frac{1}{3}$$\frac{8}{9}$$\frac{2}{3}$