Czy istnieje algorytm kwantowy ala algorytm Deutscha, który oblicza AND zamiast XOR?

Algorytm Deutscha jest dobrze znanym obliczeniem kwantowym z tylko jedną oceną . Jeśli zastąpimy z problem wydaje się być inna. Moje pytanie brzmi: czy istnieje algorytm kwantowy obliczający wartość (lub AND, jeśli wolisz) przy użyciu tylko jednej oceny . W przeciwnym razie: czy wiadomo, że taki algorytm nie istnieje?$f(0) + f(1)\mod{2}$$f$$+$$\cdot$$f(0)\cdot f(1)$$f$

Aktualizacja: Teraz dowiedziałem się o procedurze, która daje poprawną odpowiedź z prawdopodobieństwem większym niż jest to możliwe w przypadku dowolnej klasycznej procedury. „Błąd” jest jednostronny w tym sensie, że zawsze daje poprawną odpowiedź, gdy . To prowadzi mnie do rozszerzonego pytania: czy istnieje algorytm kwantowy (być może podobny do wymienionego poniżej) z właściwością, że wynik wynosi tylko wtedy, gdy ? Oczywiście „najlepszym scenariuszem” byłby algorytm, który daje prawidłową odpowiedź z prawdopodobieństwem .$f(0)\wedge f(1)=1$$1$$f(0)\wedge f(1)=1$$1$

To jest Zadanie 3, Pytanie 5 w ciągłym wstępie Richarda Cleve'a do kursu obliczeń kwantowych . (Wygląda na to, że to zadanie było dzisiaj należne.)

Chociaż nie powinniśmy odpowiadać na pytania domowe w CSTheory, na szczęście zadanie odpowiada na wszystkie pytania. Prowadzi Cię także przez konstrukcję algorytmu kwantowego. Zdecydowanie polecam przeczytać.

Najpierw przygotuj stan (co można łatwo zrobić za pomocą pojedynczego zapytania do czarnej skrzynki i jednostek unitarnych). Zauważ, że dwa takie stany odpowiadające różnym mają zawsze iloczyn wewnętrzny . Możesz łatwo przekształcić tę obserwację w algorytm, który odniosłby sukces z jednostronnym błędem lub lepiej, jeśli dopuścisz błąd dwustronny (zauważ, że najlepsza klasyczna procedura może osiągnąć prawdopodobieństwo co najwyżej ).$\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}$