Алгоритм Дойча — Йожи

Игрушечная, но показательная задача, где квантовый компьютер обходит классический за один запрос.

Алгоритм Дойча — Йожи за один обращение к функции определяет, является ли она постоянной (всюду 0 или всюду 1) или сбалансированной (ровно половина входов даёт 0, половина — 1).

Задача

Нам дана «чёрный ящик» функция f от n-битового входа, про которую обещано: она либо постоянна, либо сбалансирована. Нужно узнать, какая. Классически в худшем случае придётся проверить чуть больше половины входов: 2^(n-1) + 1 запросов, чтобы быть уверенным. Дойч — Йожи решает это за один квантовый запрос. Практической пользы у задачи нет — но она первой строго доказала разрыв между квантовым и классическим.

Идея на простом случае (n=1)

Для одного входного бита функция f задаётся двумя значениями f(0), f(1). Постоянная: f(0)=f(1). Сбалансированная: f(0) не равно f(1). Алгоритм Дойча: применить Адамар, дать оракулу записать значение f в фазу, снова Адамар, измерить. Если измерили 0 — функция постоянна; если 1 — сбалансирована. Смоделируем оба случая «по фазам» на чистом Python.

import math

r = 1/math.sqrt(2)
H = [[r, r], [r, -r]]

def apply(g, s):
    a, b = s
    return [g[0][0]*a + g[0][1]*b, g[1][0]*a + g[1][1]*b]

def deutsch(f):
    # старт |0> -> H -> фазовый оракул (фаза (-1)^f(x)) -> H -> измерение
    s = apply(H, [1+0j, 0+0j])
    s = [((-1)**f(0)) * s[0], ((-1)**f(1)) * s[1]]
    s = apply(H, s)
    p0 = abs(s[0])**2
    return 'постоянная' if p0 > 0.5 else 'сбалансированная'

print('f=const0 :', deutsch(lambda x: 0))
print('f=const1 :', deutsch(lambda x: 1))
print('f=id     :', deutsch(lambda x: x))       # f(0)=0,f(1)=1 - сбаланс.
print('f=not    :', deutsch(lambda x: 1 - x))   # сбалансированная

Вывод:

f=const0 : постоянная
f=const1 : постоянная
f=id     : сбалансированная
f=not    : сбалансированная

Один «вызов» оракула — и ответ точен. Классически для n=1 нужно два запроса (узнать оба f(0) и f(1)); для больших n разрыв становится экспоненциальным.

Как работает под капотом

Трюк — в фазовом оракуле: значение f(x) превращается в знак амплитуды (-1)^f(x). Если f постоянна, все амплитуды получают один и тот же множитель — относительные фазы не меняются, и финальный Адамар возвращает чистое |0>. Если f сбалансирована, знаки расставлены так, что после Адамара амплитуда |0> гасится деструктивной интерференцией, и измерение даёт не-ноль. Алгоритм не вычисляет ни одного значения f явно — он спрашивает про глобальное свойство (одинаковы ли фазы), и именно поэтому хватает одного запроса.

Частые ошибки

• Считать Дойча — Йожи практически полезным. Это демонстрация принципа, не более.
• Думать, что алгоритм «узнаёт значения f». Он узнаёт лишь свойство постоянна/сбалансирована.
• Забывать про обещание: если f не постоянна и не сбалансирована, алгоритм неприменим.

Итог

• Дойч — Йожи различает постоянную и сбалансированную функцию за один запрос.
• Это первое строгое доказательство квантового преимущества.
• Механизм: фазовый оракул + интерференция отвечают на глобальный вопрос о функции.