Кубит и амплитуды: состояние, которое нельзя прочитать целиком

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

Как думаешь, что хранит кубит

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

Ответь себе до чтения: если это так, почему квантовые компьютеры не решают NP-полные задачи мгновенно - проверить все 2ⁿ наборов и выбрать подходящий? Потому что это не так. В конце вычисления кубиты измеряют, и результат измерения - одна строка из нулей и единиц, выпавшая случайно. Если ничего специально не сделать, она с подавляющей вероятностью окажется одним из негодных наборов. Квантовое состояние и правда описывается 2ⁿ числами, но доступа к ним у нас нет.

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

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

Амплитуда - это высота волны. Вероятность увидеть исход - квадрат высоты, она всегда неотрицательна. Но складываются при вычислении не вероятности, а высоты, и потому два пути к одному исходу могут не усилить, а уничтожить его.

Механизм: амплитуды, измерение, много кубитов

Состояние кубита - пара чисел (a₀, a₁), называемых амплитудами, с условием a₀² + a₁² = 1.

(1, 0)         кубит в состоянии «ноль»
(0, 1)         кубит в состоянии «единица»
(0,6;  0,8)    между ними:   0,36 + 0,64 = 1
(0,6; −0,8)    тоже допустимое состояние: знак амплитуды может быть любым

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

Измерение кубита даёт 0 с вероятностью a₀² и 1 с вероятностью a₁². После измерения состояние становится (1, 0) или (0, 1) - тем, что выпало; прежние амплитуды потеряны. Повторное измерение даст тот же результат. Что вероятность - именно квадрат амплитуды, ниоткуда не выводится: это правило, взятое из опыта. Условие a₀² + a₁² = 1 значит, что вероятности двух исходов в сумме дают единицу.

Состояние, в котором ненулевых амплитуд больше одной, называют суперпозицией. Состояния (0,6; 0,8) и (0,6; −0,8) при измерении ведут себя одинаково: вероятности 0,36 и 0,64. Различаются они тем, что с ними произойдёт, если до измерения применить операцию, - об этом следующий урок.

Несколько кубитов. Состояние n кубитов - не n пар, а одна амплитуда на каждую строку из n нулей и единиц: всего 2ⁿ амплитуд, сумма квадратов равна единице. Измерение всех кубитов даёт одну строку; каждая выпадает с вероятностью, равной квадрату её амплитуды. Парами амплитуд отдельных кубитов описываются не все такие состояния: у двух кубитов есть состояние «либо оба нули, либо обе единицы» с амплитудами около (0,71; 0; 0; 0,71) - точно по 1/√2, - и никакие две пары его не дают. О нём следующий урок.

2 кубита:   амплитуды для 00, 01, 10, 11              4 числа
3 кубита:   для 000, 001, …, 111                      8 чисел
n кубитов:                                            2ⁿ чисел

Отсюда два следствия, и оба важны.

Моделировать квантовое вычисление на обычном компьютере можно всегда: хранить 2ⁿ чисел и пересчитывать их. Квантовый компьютер не вычисляет ничего невычислимого; тезис Чёрча-Тьюринга он не задевает.

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

Правило

Состояние кубита - две амплитуды с суммой квадратов 1; измерение даёт исход с вероятностью, равной квадрату его амплитуды, и разрушает состояние. Состояние n кубитов - 2ⁿ амплитуд, но измерение выдаёт одну строку из n бит. Амплитуды, в отличие от вероятностей, бывают отрицательными.

Разбор: от амплитуд к статистике

Функция izmerit выбирает исход с вероятностью, равной квадрату амплитуды; её последняя строка - страховка от округления, когда сумма квадратов дробных чисел выходит чуть меньше единицы. Функция statistika готовит одно и то же состояние тысячу раз, каждый раз измеряет и считает исходы: так выглядит работа с настоящим квантовым устройством - одно измерение ничего не говорит, статистика говорит.

import random

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

def statistika(amplitudy, raz):
    schyot = [0] * len(amplitudy)
    for povtor in range(raz):
        ishod = izmerit(amplitudy)
        schyot[ishod] = schyot[ishod] + 1
    return schyot

random.seed(8)
for sostoyanie in [[1, 0], [0.6, 0.8], [0.6, -0.8],
                   [0.5, 0.5, 0.5, -0.5]]:
    veroyatnosti = []
    for a in sostoyanie:
        veroyatnosti.append(round(a * a, 2))
    print(veroyatnosti, statistika(sostoyanie, 1000))

[1, 0] [1000, 0]
[0.36, 0.64] [386, 614]
[0.36, 0.64] [354, 646]
[0.25, 0.25, 0.25, 0.25] [247, 229, 283, 241]

Состояние (1, 0) даёт ноль всегда. Состояние (0,6; 0,8) - ноль в 386 случаях из тысячи при ожидаемых 360. Состояние (0,6; −0,8) - 354: в пределах того же разброса. Для тысячи измерений отклонение в полтора-два десятка обычно, а вдвое большее не редкость - как 283 при ожидаемых 250 в последней строке. По статистике измерений эти два состояния не различить: знак амплитуды в вероятность не входит.

Последняя строка - два кубита, четыре исхода с равными вероятностями. Одна из четырёх амплитуд отрицательна, и на счёте исходов это опять никак не сказалось.

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

Разбор: сколько чисел в состоянии

Построим состояние, в котором все 2ⁿ строк имеют одинаковую амплитуду. Оно получается, если к каждому из n кубитов в состоянии «ноль» применить вентиль Адамара - операцию над кубитом, которая делит поровну вероятность между нулём и единицей: амплитуда 1 превращается в две по 0,7071, их квадраты - по половине; подробно она разобрана в следующем уроке. Функция строит вектор амплитуд явно.

import math

def adamar_na_vse(n):
    sostoyanie = [1.0]
    for kubit in range(n):
        novoe = []
        for a in sostoyanie:
            novoe.append(a / math.sqrt(2))
            novoe.append(a / math.sqrt(2))
        sostoyanie = novoe
    return sostoyanie

for n in [1, 2, 3, 10]:
    s = adamar_na_vse(n)
    summa = 0
    for a in s:
        summa = summa + a * a
    print(n, len(s), round(s[0], 4), round(summa, 6))
for n in [30, 40, 50]:
    print(n, 2 ** n, 2 ** (n - 27))

1 2 0.7071 1.0
2 4 0.5 1.0
3 8 0.3536 1.0
10 1024 0.0312 1.0
30 1073741824 8
40 1099511627776 8192
50 1125899906842624 8388608

Первые четыре строки: число кубитов, число амплитуд, величина каждой и сумма квадратов (1/32 = 0,03125 напечатано как 0.0312: после десяти делений на корень накопилось чуть меньше точного, 0,031249…). Каждый кубит удваивает вектор и уменьшает амплитуды в корень из двух раз; сумма квадратов остаётся единицей.

Последние три строки - число амплитуд и объём памяти в гигабайтах по 2³⁰ байт, если хранить каждую восемью байтами: 2ⁿ амплитуд - это 2ⁿ⁺³ байт, то есть 2ⁿ⁻²⁷ гигабайт. Тридцать кубитов - восемь гигабайт, ноутбук. Сорок - восемь тысяч гигабайт, большой сервер. Пятьдесят - восемь миллионов гигабайт: предел для крупнейших вычислительных центров. Каждый следующий кубит удваивает счёт.

А теперь главное. В этом состоянии десяти кубитов «лежат» все 1024 строки, но измерение выдаст одну из них наугад, с вероятностью 1/1024 каждую. Это ровно то же, что бросить десять монет. Равная суперпозиция сама по себе ничего не вычисляет - она только отправная точка, с которой амплитуды начинают перераспределять.

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

«Кубит - это ноль и единица одновременно». Кубит - это две амплитуды. При измерении получается ноль или единица, одно из двух.

«n кубитов проверяют 2ⁿ вариантов сразу». Состояние описывается 2ⁿ числами, но наружу выходит одна строка. Без интерференцииРазбирается в разделе 21, глава «Квантовая модель - кубит, интерференция, алгоритм Шора»: Вентили и интерференция: как амплитуды гасят друг друга квантовый компьютер - дорогой генератор случайных чисел.

Амплитуды путают с вероятностями. Вероятности складываются и не бывают отрицательными. Амплитуды складываются со знаком, а вероятность - квадрат суммы.

«Квантовый компьютер вычисляет невычислимое». Всё, что он делает, моделируется обычным, только экспоненциально медленнее. Границу разрешимого он не сдвигает.

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

Чтение новостей. «Процессор на тысячу кубитов» и «превосходство над суперкомпьютером» значат меньше, чем кажется, пока не сказано, какие операции и с какой точностью выполняются. Зная, что состояние - вектор амплитуд, а результат - одна измеренная строка, можно задать правильный вопрос: какая задача решена и как проверен ответ.

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

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

Теперь сам

1. Кубит в состоянии (0,8; −0,6). С какой вероятностью измерение даст 1?
2. Сколько амплитуд у состояния двадцати кубитов?
3. Кубит в состоянии (0,6; 0,8) измерили и получили 1. В каком он состоянии теперь?
4. Чем состояние (0,6; 0,8) отличается от монеты, которая выпадает решкой с вероятностью 0,64?
5. Сколько памяти нужно, чтобы хранить состояние 33 кубитов по восемь байт на амплитуду?