Алгоритм Дойча–Йожі став першим конкретним прикладом квантового алгоритму, який доведено перевершує будь-який класичний алгоритм на задачі з чорною скринькою. Маючи приховану функцію f, яка гарантовано є або сталою (однаковий вихід для кожного входу), або збалансованою (0 рівно для половини входів, 1 для іншої половини), класичний комп'ютер у гіршому випадку може перевірити понад половину входів, тоді як квантовий комп'ютер розв'язує це за один єдиний запит. Це концептуальне зерно, з якого пізніше виросли алгоритми Гровера та Шора.
|ψ⟩ = H^⊗n|0⟩ — рівна суперпозиція всіх N = 2ⁿ
входів. U_f|x⟩ = (−1)^f(x)|x⟩ — фазовий "відкат"
оракула. P(y) = |⟨y|H^⊗n U_f H^⊗n|0⟩|² — ймовірність
виміряти вихід y. Якщо f стала, P(0…0) = 1 точно; якщо f
збалансована, P(0…0) = 0 точно.
Девід Дойч запропонував однокубітну версію в 1985 році; Девід Дойч і Річард Йожа узагальнили її на n кубітів у 1992 році — майже за десятиліття до того, як алгоритм факторизації Пітера Шора 1994 року прославив квантові обчислення. На той час це був один із небагатьох строгих доказів того, що квантові комп'ютери взагалі можуть у чомусь перевершити класичні.
Алгоритм Дойча–Йожі відповідає на просту задачу-обіцянку: маючи функцію-чорну скриньку f, яка перетворює n бітів на один біт і гарантовано є або сталою (той самий вихід для кожного входу), або збалансованою (0 рівно для половини входів і 1 для іншої половини), потрібно визначити, яка саме. Класичний комп'ютер, що може лише опитувати f як чорну скриньку, у гіршому випадку може перевірити понад половину з 2ⁿ входів, перш ніж отримає впевненість — до 2⁽ⁿ⁻¹⁾ + 1 запитів у найгіршому випадку. Квантовий комп'ютер розв'язує те саме питання одним-єдиним зверненням до оракула, кодуючи f у фазу й дозволяючи інтерференції зосередити всю ймовірність на нульовому результаті саме тоді, коли f стала.
Цей симулятор будує точний квантовий стан власноруч: застосовує вентилі Адамара, щоб досягти рівної суперпозиції, кодує обраний оракул як зміну знака для кожного базисного стану, а потім виконує справжнє перетворення Волша–Адамара, щоб отримати кінцеві ймовірності вимірювання. Банер висновку в реальному часі зчитує ймовірність виміряти нульовий рядок — близько 1 означає сталу функцію, близько 0 означає збалансовану — саме так, як працює справжній алгоритм. Він залишається основоположним прикладом у курсах квантових обчислень, адже саме він першим строго довів, що квантова інтерференція здатна дати безумовний виграш у швидкості над будь-якою класичною стратегією, за роки до того, як алгоритм Шора прославив цю ідею.
Він з упевненістю визначає, чи є булева функція-чорна скринька f сталою, чи збалансованою, використовуючи щонайменшу можливу кількість звернень до f. Функція заздалегідь гарантована бути однією з цих двох, тож алгоритму ніколи не доводиться опрацьовувати функцію, яка не є ані сталою, ані збалансованою.
Класично доводиться опитувати f по одному входу за раз. Навіть якщо поспіль 2⁽ⁿ⁻¹⁾ разів отримати однаковий результат, це все одно не дає впевненості, що функція стала — наступний же запит може виявити інше значення. Лише перевіривши трохи більше половини входів, 2⁽ⁿ⁻¹⁾ + 1 запитів у гіршому випадку, можна отримати остаточну впевненість.
Суперпозиція дозволяє застосувати оракул до всіх 2ⁿ входів одночасно, кодуючи f(x) у фазу, а не в перевертання біта. Другий шар вентилів Адамара потім змушує ці фази інтерферувати між собою. Якщо f стала, усі шляхи конструктивно складаються на нульовому результаті, надаючи йому ймовірність 1. Якщо f збалансована, шляхи там повністю скасовують одне одного, даючи ймовірність 0.
Гістограма показує ймовірність виміряти кожен можливий вихідний рядок. Стовпчик при y = 0 (нульовий рядок) виділено, оскільки саме він несе висновок: цей симулятор зчитує ту єдину ймовірність у реальному часі й повідомляє "СТАЛА", коли вона близька до 1, або "ЗБАЛАНСОВАНА", коли вона близька до 0.