Вентили и интерференция: как амплитуды гасят друг друга

Если ты применишь вентиль Адамара к состоянию из двух амплитуд, объяснишь, почему два таких вентиля подряд ничего не меняют, а два случайных подбрасывания - меняют, и построишь запутанную пару, - листай до «Теперь сам».

Как думаешь, что будет, если размешать дважды

Есть операция, которая превращает кубит в состоянии «ноль» в состояние с вероятностями 1/2 и 1/2. И кубит в состоянии «единица» - тоже в состояние с вероятностями 1/2 и 1/2. По статистике измерений она неотличима от подбрасывания честной монеты.

Ответь себе до чтения: что получится, если применить эту операцию два раза подряд и только потом измерить? С монетой ответ ясен: случайность, подброшенная ещё раз, остаётся случайностью. С кубитом ответ другой: после двух операций он вернётся в исходное состояние точно, с вероятностью единица. Операция, которая выглядела как потеря информации, ничего не потеряла.

На что это похоже

Наушники с шумоподавлением. Они не заглушают шум и не вычитают громкость из громкости - громкость отрицательной не бывает. Они добавляют к звуковой волне такую же волну с противоположным знаком, и волны в сумме дают тишину.

Если бы звук был устроен как вероятность, добавление второго источника могло бы только усилить его. Погасить можно лишь то, что имеет знак. У амплитуд он есть.

Механизм: вентиль, два пути и запутанность

Вентиль - операция над состоянием, которая каждую новую амплитуду вычисляет как сумму старых, умноженных на постоянные коэффициенты, и сохраняет сумму квадратов равной единице (для комплексных амплитуд, которые встретятся только в последнем уроке главы, - сумму квадратов модулей). Все вентили обратимы: по результату можно восстановить исходное состояние. Оба вентиля ниже обратны сами себе: применённые дважды, возвращают то, что было. Измерение необратимо и вентилем не считается.

вентиль «не»       (a₀, a₁)  →  (a₁, a₀)       меняет амплитуды местами
вентиль Адамара    (a₀, a₁)  →  ( (a₀ + a₁)/√2,  (a₀ − a₁)/√2 )

Деление на √2 сохраняет сумму квадратов: (a₀ + a₁)² + (a₀ − a₁)² = 2a₀² + 2a₁², и после деления каждой амплитуды на √2 остаётся a₀² + a₁². Вентиль Адамара на «нуле» и на «единице»:

(1, 0)  →  ( 1/√2,   1/√2 )     вероятности 1/2 и 1/2
(0, 1)  →  ( 1/√2,  −1/√2 )     вероятности те же,
                                знак второй амплитуды другой

Два вентиля подряд. Применим вентиль Адамара к «нулю» дважды и проследим, откуда берётся каждая амплитуда. В промежуточном состоянии кубит «и ноль, и единица» с амплитудой 1/√2 каждый. Путь - три значения кубита подряд: начальное, промежуточное, конечное. Каждый переход получает от вентиля множитель 1/√2, кроме перехода из единицы в единицу: у него −1/√2, тот самый минус из формулы. Множители вдоль пути перемножаются, а пути с общим концом складываются.

амплитуда нуля в конце:
    путь  0 → 0 → 0:   (1/√2) · (1/√2)   =  +1/2
    путь  0 → 1 → 0:   (1/√2) · (1/√2)   =  +1/2          сумма  1

амплитуда единицы в конце:
    путь  0 → 0 → 1:   (1/√2) · (1/√2)   =  +1/2
    путь  0 → 1 → 1:   (1/√2) · (−1/√2)  =  −1/2          сумма  0

К нулю оба пути приходят с одним знаком и складываются. К единице - с разными и гасят друг друга. Это интерференция. Вероятность единицы равна нулю не потому, что к ней нет путей, а потому, что пути уничтожили друг друга.

С вероятностями так не выходит. Случайный шаг «с вероятностью 1/2 остаться, с вероятностью 1/2 перевернуть» даёт по 1/4 на каждый из четырёх путей, и все вклады положительны: по 1/2 на каждый исход, сколько шагов ни делай.

Вентили на двух кубитах. Управляемое «не» переворачивает второй кубит, если первый равен единице: амплитуды строк 10 и 11 меняются местами, остальные остаются.

Вентиль на первом кубите пары пересчитывает амплитуды строк, которые отличаются только первым битом: 00 с 10 и 01 с 11. Начнём с 00, применим вентиль Адамара к первому кубиту, потом управляемое «не». Запись (00 + 10)/√2 - сокращение: амплитуда 1/√2 у строк 00 и 10, ноль у остальных.

00  →  (00 + 10)/√2  →  (00 + 11)/√2

Получилось состояние с амплитудами 1/√2 у строк 00 и 11 и нулём у остальных. Измерение даёт либо 00, либо 11 - два случайных, но всегда одинаковых бита. Такое состояние называют запутанным: его нельзя записать как «состояние первого кубита и отдельно состояние второго». Для двух кубитов есть простая проверка: состояние раскладывается по кубитам ровно тогда, когда произведение амплитуд у 00 и 11 равно произведению амплитуд у 01 и 10. Откуда она: у двух отдельных кубитов с амплитудами p, q и u, v амплитуды пары перемножаются, как вероятности независимых событий, - pu, pv, qu, qv, - и оба произведения равны pquv. Обратное тоже верно; здесь оно без доказательства. У построенной пары слева 1/2, справа ноль.

Правило

Вентиль пересчитывает амплитуды как суммы с постоянными коэффициентами, сохраняя сумму квадратов. Амплитуда исхода - сумма по всем путям к нему; пути с противоположными знаками гасят друг друга, с одинаковыми - усиливают. Вентиль Адамара, применённый дважды, возвращает исходное состояние. Вентиль Адамара и управляемое «не» создают запутанную пару.

Разбор: два вентиля и две монеты

Функция adamar применяет вентиль к паре амплитуд. Функция monetka применяет к паре вероятностей случайный шаг: с вероятностью 1/2 оставить бит, с вероятностью 1/2 перевернуть. В monetka оба исхода считаются одной формулой, и это не опечатка: остаться и перевернуться равновероятно, поэтому исходы получают поровну.

import math

def adamar(s):
    k = 1 / math.sqrt(2)
    return [k * (s[0] + s[1]), k * (s[0] - s[1])]

def okruglit(s):
    itog = []
    for a in s:
        itog.append(round(a, 4))
    return itog

def monetka(p):
    return [0.5 * (p[0] + p[1]), 0.5 * (p[0] + p[1])]

nol = [1.0, 0.0]
odin = [0.0, 1.0]
print(okruglit(adamar(nol)), okruglit(adamar(odin)))
print(okruglit(adamar(adamar(nol))), okruglit(adamar(adamar(odin))))
print(monetka(nol), monetka(monetka(nol)))

[0.7071, 0.7071] [0.7071, -0.7071]
[1.0, 0.0] [0.0, 1.0]
[0.5, 0.5] [0.5, 0.5]

Первая строка: один вентиль. Из «нуля» получаются амплитуды 0,7071 и 0,7071, из «единицы» - 0,7071 и −0,7071. Вероятности в обоих случаях 0,5 и 0,5: измерив сейчас, не узнаешь, с чего начинали.

Вторая строка: два вентиля. «Ноль» вернулся в «ноль», «единица» - в «единицу». Сведения о начальном состоянии не пропали после первого вентиля; они хранились в знаке, которого измерение не видит.

Третья строка: монета. После одного шага - 0,5 и 0,5, после двух - то же самое. Вероятностям нечем гасить друг друга, и возврата нет.

Разница между первой и третьей строками при измерении незаметна. Она проявляется только на втором шаге - и это значит, что промежуточное состояние кубита нельзя считать «случайным битом, значения которого мы не знаем».

Разбор: пара, которая отвечает одинаково

Состояние двух кубитов - четыре амплитуды в порядке 00, 01, 10, 11. Построим запутанную пару и измерим её тысячу раз. Вызов random.seed(4) закрепляет последовательность случайных чисел, чтобы вывод повторялся от запуска к запуску; с другим зерном счёт будет немного иным.

import math
import random

def adamar_na_pervyj(s):
    k = 1 / math.sqrt(2)
    return [k * (s[0] + s[2]), k * (s[1] + s[3]),
            k * (s[0] - s[2]), k * (s[1] - s[3])]

def upravlyaemoe_ne(s):
    return [s[0], s[1], s[3], s[2]]

def izmerit(amplitudy):
    r = random.random()
    nakopleno = 0
    for i in range(len(amplitudy)):
        nakopleno = nakopleno + amplitudy[i] * amplitudy[i]
        if r < nakopleno:
            return i
    return len(amplitudy) - 1

para = upravlyaemoe_ne(adamar_na_pervyj([1.0, 0.0, 0.0, 0.0]))
okruglyonnye = []
for a in para:
    okruglyonnye.append(round(a, 4))
print(okruglyonnye)
random.seed(4)
schyot = [0, 0, 0, 0]
for povtor in range(1000):
    ishod = izmerit(para)
    schyot[ishod] = schyot[ishod] + 1
print(schyot)

[0.7071, 0.0, 0.0, 0.7071]
[492, 0, 0, 508]

Амплитуды - у строк 00 и 11. Из тысячи измерений 492 раза выпало 00 и 508 раз 11; строки 01 и 10 не выпали ни разу. Каждый бит по отдельности случаен, а вместе они всегда совпадают.

Вентиль Адамара на первом кубите пересчитывает амплитуды парами: 00 с 10 и 01 с 11 - строки, которые отличаются только первым битом. Вентиль на одном кубите из n обходит весь вектор из 2ⁿ амплитуд; для моделирования это 2ⁿ действий, а для квантового устройства - одна операция: физическое воздействие на один кубит меняет состояние всей системы сразу, амплитуды нигде не хранятся по отдельности. В этом несоответствии и находится возможный выигрыш.

Кубиты пары можно разнести и измерять порознь, у двух разных людей. Сообщений запутанная пара при этом не передаёт: каждая сторона видит случайный бит и не может на него повлиять. Совпадение обнаруживается только при сравнении результатов. Но в алгоритмах с большим выигрышем, у Гровера и Шора, она возникает неизбежно: без неё состояние n кубитов распадалось бы на n отдельных пар амплитуд и моделировалось бы легко.

Что ломается без этого

Промежуточное состояние считают случайным битом. Тогда два вентиля Адамара должны были бы дать случайность, а дают исходное состояние. Амплитуды до измерения - не незнание, а состояние.

Знак амплитуды считают несущественным. На вероятности он не влияет, на следующую операцию - полностью.

Измерение посередине. Измерив кубит между двумя вентилями, уничтожаешь суперпозицию - остаётся (1, 0) или (0, 1), - и второй вентиль снова даёт 1/2 и 1/2. Подсматривание меняет результат - это не метафора, а свойство модели.

Запутанность принимают за связь. Пара даёт согласованные случайные биты, но ни один из них нельзя задать. Передать этим сообщение невозможно.

Зачем это в работе

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

Понимать, почему это трудно построить. Амплитуды разрушаются любым взаимодействием с окружением, которое «подсматривает» состояние. Настоящие устройства шумят, и исправление ошибок требует сотен и тысяч физических кубитов - настоящих шумящих элементов - на один надёжный, с которым работает алгоритм.

Квантовое распределение ключей. Свойство «измерение меняет состояние» используют напрямую: попытка перехватить кубиты оставляет следы, которые стороны обнаруживают.

Теперь сам

1. Примени вентиль Адамара к состоянию (0,6; 0,8). Какими будут вероятности исходов?
2. Сколько путей ведёт к каждому исходу после двух вентилей Адамара и с какими знаками?
3. К состоянию 00 применили только вентиль Адамара на первом кубите. Запутано ли оно?
4. Что произойдёт, если между двумя вентилями Адамара измерить кубит?
5. Запутанную пару (00 + 11)/√2 измерили, и первый бит оказался единицей. Каким окажется второй?