Существует ли квантовый алгоритм аля Дойча, который вычисляет AND вместо XOR?

Алгоритм Дойча является хорошо известным квантовым вычислением $f(0) + f(1)\mod{2}$ только с одной оценкой $f$ . Если мы заменим $+$ на $\cdot$ проблема, похоже, станет другой. Мой вопрос: существует ли квантовый алгоритм, вычисляющий значение $f(0)\cdot f(1)$ (или AND, если вы предпочитаете), используя только одну оценку $f$ . В противном случае: известно, что такого алгоритма не существует?

Обновление: теперь я узнал о процедуре, которая дает правильный ответ с вероятностью, большей, чем любая классическая процедура. «Ошибка» является односторонней в том смысле, что она всегда дает правильный ответ, когда $f(0)\wedge f(1)=1$ . Это приводит меня к расширенному вопросу: существует ли алгоритм квентума (возможно, похожий на тот, который упомянут ниже) со свойством, что результат равен $1$ только если $f(0)\wedge f(1)=1$ ? Конечно, «лучший сценарий» будет алгоритм, который дает правильный ответ с вероятностью $1$ .

Это задание 3, вопрос 5 в продолжающемся введении Ричарда Клива в курс квантовых вычислений . (Похоже, это задание было сегодня.)

Хотя мы не должны отвечать на домашние задания по CSTheory, к счастью, задание отвечает на все ваши вопросы. Он также проведет вас через построение квантового алгоритма. Я настоятельно рекомендую прочитать это.

Сначала подготовьте состояние (что можно легко сделать, используя один черный ящик и унитарные запросы). Обратите внимание, что два таких состояния, соответствующие разным , всегда имеют внутреннее произведение . Вы можете легко превратить это наблюдение в алгоритм, выполняющийся с односторонней ошибкой или лучше, если вы допустите двустороннюю ошибку (обратите внимание, что лучшая классическая процедура может достичь вероятности не более ).$\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}$