Algorytm Deutscha–Jozsy był pierwszym konkretnym przykładem algorytmu kwantowego, który udowodniono jako przewyższający dowolny algorytm klasyczny w zadaniu typu „czarna skrzynka”. Mając ukrytą funkcję f, która z gwarancją jest albo stała (ten sam wynik dla każdego wejścia), albo zrównoważona (0 dla dokładnie połowy wejść, 1 dla drugiej połowy), komputer klasyczny może w najgorszym przypadku potrzebować sprawdzenia ponad połowy wejść, podczas gdy komputer kwantowy rozwiązuje to za pomocą jednego jedynego zapytania. To koncepcyjne ziarno, z którego później wyrosły algorytmy Grovera i Shora.
|ψ⟩ = H^⊗n|0⟩ — równa superpozycja wszystkich N = 2ⁿ
wejść. U_f|x⟩ = (−1)^f(x)|x⟩ — fazowe „odbicie
zwrotne” wyroczni. P(y) = |⟨y|H^⊗n U_f H^⊗n|0⟩|² —
prawdopodobieństwo zmierzenia wyjścia y. Jeśli f jest stała,
P(0…0) = 1 dokładnie; jeśli f jest zrównoważona, P(0…0) = 0
dokładnie.
David Deutsch zaproponował jednokubitową wersję w 1985 roku; David Deutsch i Richard Jozsa uogólnili ją na n kubitów w 1992 roku — niemal dekadę przed tym, jak algorytm faktoryzacji Petera Shora z 1994 roku rozsławił obliczenia kwantowe. W tamtym czasie był to jeden z niewielu ścisłych dowodów na to, że komputery kwantowe w ogóle mogą przewyższyć klasyczne w czymkolwiek.
Algorytm Deutscha–Jozsy odpowiada na proste zadanie z obietnicą: mając funkcję czarnej skrzynki f, która przekształca n bitów na jeden bit i z gwarancją jest albo stała (ten sam wynik dla każdego wejścia), albo zrównoważona (0 dla dokładnie połowy wejść i 1 dla drugiej połowy), trzeba określić, która to funkcja. Komputer klasyczny, który może jedynie odpytywać f jako czarną skrzynkę, w najgorszym przypadku musi sprawdzić ponad połowę z 2ⁿ wejść, zanim uzyska pewność — aż do 2⁽ⁿ⁻¹⁾ + 1 zapytań w najgorszym przypadku. Komputer kwantowy rozwiązuje to samo pytanie za pomocą jednego jedynego odwołania do wyroczni, kodując f w fazie i pozwalając interferencji skupić całe prawdopodobieństwo na wyniku zerowym właśnie wtedy, gdy f jest stała.
Ten symulator samodzielnie buduje dokładny stan kwantowy: stosuje bramki Hadamarda, aby osiągnąć równą superpozycję, koduje wybraną wyrocznię jako zmianę znaku dla każdego stanu bazowego, a następnie wykonuje prawdziwą transformację Walsha–Hadamarda, aby uzyskać końcowe prawdopodobieństwa pomiaru. Baner wniosku w czasie rzeczywistym odczytuje prawdopodobieństwo zmierzenia ciągu zerowego — wartość bliska 1 oznacza funkcję stałą, bliska 0 oznacza zrównoważoną — dokładnie tak, jak działa prawdziwy algorytm. Pozostaje on fundamentalnym przykładem w kursach obliczeń kwantowych, ponieważ to właśnie on jako pierwszy ściśle udowodnił, że interferencja kwantowa może dać bezwarunkową przewagę szybkości nad dowolną strategią klasyczną, na lata przed tym, jak algorytm Shora rozsławił tę ideę.
Z pewnością określa, czy boolowska funkcja czarnej skrzynki f jest stała, czy zrównoważona, wykorzystując możliwie najmniejszą liczbę odwołań do f. Funkcja jest z góry zagwarantowana jako jedna z tych dwóch, więc algorytm nigdy nie musi radzić sobie z funkcją, która nie jest ani stała, ani zrównoważona.
Klasycznie trzeba odpytywać f po jednym wejściu na raz. Nawet jeśli 2⁽ⁿ⁻¹⁾ razy z rzędu uzyska się ten sam wynik, wciąż nie daje to pewności, że funkcja jest stała — kolejne zapytanie może ujawnić inną wartość. Dopiero po sprawdzeniu nieco ponad połowy wejść, czyli 2⁽ⁿ⁻¹⁾ + 1 zapytań w najgorszym przypadku, można uzyskać ostateczną pewność.
Superpozycja pozwala zastosować wyrocznię do wszystkich 2ⁿ wejść jednocześnie, kodując f(x) w fazie, a nie w odwróceniu bitu. Druga warstwa bramek Hadamarda sprawia następnie, że te fazy interferują ze sobą. Jeśli f jest stała, wszystkie ścieżki konstruktywnie sumują się na wyniku zerowym, nadając mu prawdopodobieństwo 1. Jeśli f jest zrównoważona, ścieżki tam całkowicie się znoszą, dając prawdopodobieństwo 0.
Histogram pokazuje prawdopodobieństwo zmierzenia każdego możliwego ciągu wyjściowego. Słupek przy y = 0 (ciąg zerowy) jest wyróżniony, ponieważ to on niesie wniosek: ten symulator odczytuje to jedno prawdopodobieństwo w czasie rzeczywistym i zgłasza „STAŁA”, gdy jest ono bliskie 1, lub „ZRÓWNOWAŻONA”, gdy jest bliskie 0.