Интерференция: как усилить нужный ответ

Сердце квантовых алгоритмов: складывать амплитуды так, чтобы нужное усиливалось, а лишнее гасло.

Интерференция — сложение амплитуд разных путей: при совпадении фаз они усиливают друг друга (конструктивно), при противоположных — гасят (деструктивно).

Почему амплитуды, а не вероятности

Классическая вероятность только растёт, когда есть несколько путей к исходу: суммируешь — становится больше. Амплитуды ведут себя иначе: они комплексные и могут быть отрицательными, поэтому два пути к одному исходу могут взаимно уничтожиться. Это и есть ресурс, которого нет у классических вероятностных алгоритмов. Покажем гашение на самом наглядном примере — двойном Адамаре.

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]

# H|0> = (|0>+|1>)/sqrt2. Теперь ещё раз H.
mid = apply(H, [1+0j, 0+0j])
print('после первого H:', [round(x.real, 4) for x in mid])
out = apply(H, mid)
print('после второго H:', [round(x.real, 4) for x in out])
print('p0 =', round(abs(out[0])**2, 4), 'p1 =', round(abs(out[1])**2, 4))

Вывод:

после первого H: [0.7071, 0.7071]
после второго H: [1.0, 0.0]
p0 = 1.0 p1 = 0.0

Вероятность исхода 1 стала ровно нулём. К |1> вели два пути с противоположными знаками амплитуд (+r·r и -r·r), они сократились — деструктивная интерференция. А к |0> оба пути пришли с одинаковым знаком и сложились — конструктивная.

Фаза управляет интерференцией

Вставим между двумя Адамарами гейт Z (он меняет знак амплитуды при |1>). Картина перевернётся: теперь сократится исход 0, а исход 1 станет достоверным. Так относительная фаза, сама по себе невидимая, превращается в наблюдаемый результат.

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

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

s = apply(H, apply(Z, apply(H, [1+0j, 0+0j])))   # H Z H |0>
print('состояние:', [round(x.real, 4) for x in s])
print('p0 =', round(abs(s[0])**2, 4), 'p1 =', round(abs(s[1])**2, 4))

Вывод:

состояние: [0.0, 1.0]
p0 = 0.0 p1 = 1.0

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

Общая схема любого квантового алгоритма теперь видна целиком: (1) Адамары создают суперпозицию всех вариантов; (2) функция/оракул записывает ответ в фазы амплитуд (помечает нужные минусом или поворотом фазы); (3) ещё один слой Адамаров заставляет фазы проинтерферировать так, что амплитуда правильного ответа вырастает; (4) измерение с большой вероятностью даёт его. Дойч — Йожи, Гровер и Шор — это всё разные способы реализовать шаг (2) и подобрать интерференцию на шаге (3).

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

• Думать, что амплитуды складываются как вероятности. Они могут гасить друг друга.
• Игнорировать фазу: именно она решает, будет интерференция конструктивной или деструктивной.
• Ожидать гарантированного ответа. Чаще интерференция делает нужный исход лишь вероятным, и алгоритм повторяют.

Итог

• Амплитуды интерферируют: совпадающие фазы усиливают, противоположные гасят.
• Деструктивная интерференция способна обнулить нежелательный исход.
• Алгоритм = суперпозиция, запись ответа в фазу, интерференция, измерение.