Лаборатория кубитов

Прошлая глава кончилась числом, перед которым пасует любая машина из этой книги. Чтобы описать пятьдесят взаимодействующих спинов электронов, нужно $2^{50}$ комплексных чисел — петабайты памяти. Природа же справляется с такими системами в каждой молекуле, ничего не храня. Все наши машины построены на битах. Но физика допускает другой способ вычислять, и в этой главе мы будем им пользоваться — пока в симуляции.

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

Опыт 1. Монетка, которая помнит

Начнём со ставки.

Есть кубит в состоянии «0» и операция H. Если применить H один раз и измерить, выпадет 0 или 1 — пополам, как у честной монетки. А если применить H два раза подряд и только потом измерить?

0 и 1 пополам — две монетки подряд дают ту же монетку 0 чаще: три раза из четырёх всегда 0 всегда 1

Всегда 0. Для монетки было бы пополам: сколько её ни подбрасывай, результат случаен. А кубит после первого H — не «0 или 1 с вероятностью ½», а нечто третье, и второй H возвращает его туда, откуда начали. Ниже — почему.

Монетку описывают вероятности: столбик из двух чисел, «орёл» и «решка», и бросок умножает его на матрицу. Сколько ни бросай, получается пополам. Кубит описывают другие числа — амплитуды, и от вероятностей они отличаются одним: амплитуды бывают отрицательными, а вообще — комплексными. Вероятность исхода — квадрат модуля амплитуды. После первого H у кубита амплитуды $\tfrac{1}{\sqrt2}$ и $\tfrac{1}{\sqrt2}$: вероятности по ½, и тысяча измерений дают около пятисот нулей. После второго H к нулю приходят два вклада, $\tfrac12 + \tfrac12 = 1$, а к единице — $\tfrac12 - \tfrac12 = 0$. Пути, ведущие к единице, погасили друг друга.

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

Кубит, измерение, гейты

Теперь определения. Кубит — система с двумя базисными состояниями, их пишут $|0\rangle$ и $|1\rangle$. Его состояние — вектор $\alpha|0\rangle + \beta|1\rangle$, то есть столбец $(\alpha, \beta)$ из двух комплексных чисел с условием $|\alpha|^2 + |\beta|^2 = 1$. Про кубит, у которого обе амплитуды ненулевые, говорят, что он в суперпозиции. Слово пугающее, но за ним только линейная алгебра: $|0\rangle$ и $|1\rangle$ — базис двумерного пространства, а состояние — любой вектор длины 1 в нём.

Прочитать амплитуды нельзя. Единственный способ узнать что-то о кубите — измерение: оно выдаёт 0 с вероятностью $|\alpha|^2$ и 1 с вероятностью $|\beta|^2$, и после этого кубит становится $|0\rangle$ или $|1\rangle$ — прежние амплитуды пропадают. Повторное измерение покажет то же самое. Поэтому одно измерение даёт ровно один бит, сколько бы информации ни было в амплитудах.

Всё остальное, что можно делать с кубитом, — квантовые гейты: умножение вектора состояния на матрицу. Годится только матрица, которая сохраняет длину вектора, иначе вероятности перестанут складываться в единицу. Такие матрицы называют унитарными, и все они обратимы: квантовое вычисление до измерения можно прокрутить назад. Три гейта нам понадобятся с самого начала:

$$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \qquad H = \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.$$

$X$ — квантовое «не»: меняет местами амплитуды $|0\rangle$ и $|1\rangle$. $Z$ меняет знак у амплитуды $|1\rangle$ и ничего не меняет в вероятностях. $H$, гейт Адамара, превращает $|0\rangle$ в $(|0\rangle + |1\rangle)/\sqrt2$, а $|1\rangle$ — в $(|0\rangle - |1\rangle)/\sqrt2$. Эти два состояния обозначают $|{+}\rangle$ и $|{-}\rangle$. Измерение их не различает: у обоих вероятности по ½. А интерференция различает.

$|{+}\rangle$ и $|{-}\rangle$ одинаковы для измерения, но после ещё одного $H$ первое даёт $|0\rangle$, а второе $|1\rangle$. Разница между ними — знак, или, как говорят физики, фаза. Фаза невидима для прямого измерения и решает всё при интерференции. Последняя строка — маленькое тождество, которое ещё пригодится: если окружить $Z$ двумя $H$, получится $X$.

Состояние одного кубита удобно рисовать. Общий множитель вида $e^{i\gamma}$ у обеих амплитуд ни на что не влияет — ни на вероятности, ни на интерференцию, — и, отбросив его, любое состояние можно записать как $\cos\frac\theta2\,|0\rangle + e^{i\varphi}\sin\frac\theta2\,|1\rangle$. Два угла — точка на сфере, её называют сферой Блоха, по имени физика Феликса Блоха. На северном полюсе $|0\rangle$, на южном $|1\rangle$, на экваторе — равные суперпозиции, различающиеся фазой. А гейты — повороты сферы.

Опыт 2. Два кубита

У двух битов четыре состояния: 00, 01, 10, 11. У двух кубитов — четыре амплитуды, по одной на каждое: вектор $(a_{00}, a_{01}, a_{10}, a_{11})$. Номер амплитуды — двоичная запись исхода, и мы будем считать нулевой кубит старшим битом, левым. Если кубиты независимы — первый в состоянии $(\alpha, \beta)$, второй в $(\gamma, \delta)$, — амплитуды перемножаются: $(\alpha\gamma, \alpha\delta, \beta\gamma, \beta\delta)$. Такую операцию над векторами называют тензорным произведением, в numpy это np.kron. Она же собирает гейт для всей системы из гейтов отдельных кубитов: np.kron(H, I) — это $H$ на нулевой кубит и ничего на первый.

Новое здесь — гейты, которые действуют на два кубита сразу. Главный из них, CNOT, — «управляемое не»: если управляющий кубит равен 1, он переворачивает целевой, иначе ничего не делает. На базисных состояниях это обычная логика, как XOR из главы 29: $|a, c\rangle \mapsto |a, a \oplus c\rangle$. Интересное начинается, когда управляющий кубит в суперпозиции.

Получилось $(|00\rangle + |11\rangle)/\sqrt2$ — одно из четырёх состояний Белла. Измерения выдают 00 и 11 случайно, пополам, но никогда 01 или 10: результаты кубитов всегда совпадают. При этом каждый кубит по отдельности ведёт себя как монетка: ноль и единица выпадают пополам. И описать каждый кубит своим собственным состоянием невозможно.

Состояние двух кубитов, которое не раскладывается в произведение состояний каждого, называют запутанным. Из-за запутанности описание $n$ кубитов требует $2^n$ амплитуд, а не $2n$: состояние нельзя разделить на независимые кусочки. Соберите такие схемы сами.

Связь, по которой нельзя говорить

Совпадающие монетки ещё не чудо. Можно положить в два конверта две одинаковые записки и раздать их Алисе и Бобу — результаты тоже совпадут. Отличить запутанность от заранее разложенных записок помогает игра. Она выросла из теоремы Джона Белла (1964) в той форме, которую ей дали в 1969 году Клаузер, Хорн, Шимони и Холт. Алиса и Боб расходятся по разным комнатам, и каждый получает случайный бит-вопрос: Алиса $x$, Боб $y$. Каждый отвечает битом, $a$ и $b$, не переговариваясь. Они выигрывают, если $a \oplus b = x \land y$: ответы должны различаться, только когда оба вопроса — единицы.

А если у Алисы и Боба по кубиту из пары Белла, они могут выигрывать в $\cos^2\frac\pi8 \approx 85\,\%$ случаев: каждый поворачивает свой кубит на угол, зависящий от вопроса, и измеряет. Проверьте сами.

Восемьдесят пять процентов не достижимы никакими записками в конвертах, и на этом строится экспериментальная проверка запутанности. Такие опыты ставили с 1970-х годов, всё точнее закрывая лазейки, и в 2022 году Джон Клаузер, Ален Аспе и Антон Цайлингер получили за них Нобелевскую премию по физике. Но передать по такой связи сообщение нельзя, ни быстрее света, ни медленнее: ответы Алисы сами по себе — монетка, что бы ни делал Боб. Связь проявляется только тогда, когда результаты сравнивают, а для этого их надо переслать обычным способом.

Опыт 3. Почему это трудно симулировать

Наш симулятор хранит все амплитуды. Каждый новый кубит удваивает их число. Проверим, как быстро это становится неподъёмным: применим $H$ ко всем кубитам сразу. Матрица $2^n \times 2^n$ тут не нужна: $H$ на кубит $k$ — это проход по массиву, который смешивает пары амплитуд, различающиеся только $k$-м битом.

Двадцать кубитов — 16 мебибайт и около десятой доли секунды. Тридцать — 16 гибибайт, это уже серьёзный сервер. Пятьдесят — 16 пебибайт, а 300 кубитов потребовали бы больше байтов, чем атомов в наблюдаемой Вселенной. Хитрые симуляторы умеют обходиться меньшей памятью, когда запутанности немного, но в общем случае выхода не знают. Это и было наблюдение Фейнмана.

Из этого вырос популярный пересказ: «квантовый компьютер перебирает все $2^n$ вариантов одновременно». Он неверен. Амплитуд действительно $2^n$, но измерение выдаёт одну-единственную строку из $n$ битов, случайную. Если «посчитать всё сразу» и измерить, получится случайный ответ, не лучше догадки. Выигрыш бывает только тогда, когда задачу удаётся устроить так, чтобы интерференция погасила неправильные ответы, как в первом опыте. Таких задач известно немного; две из них — в следующих опытах.

Опыт 4. Дойч — Йожа: одно обращение вместо полумиллиона

Вам дают функцию $f$, которая принимает $n$-битное число и возвращает 0 или 1. Про неё обещано одно из двух: либо она постоянная — на всех входах одно и то же, — либо сбалансированная: ровно на половине входов 0, на половине 1. Какая? Устройство функции скрыто, её можно только вызывать — так скрытую функцию называют оракулом, как в главе 56, только этот оракул не блефует и отвечает на любой вход. Обычному детерминированному алгоритму в худшем случае не хватит и половины входов: можно увидеть $2^{n-1}$ нулей подряд и всё ещё не знать ответа. Нужно $2^{n-1} + 1$ вызовов — при $n = 20$ больше полумиллиона.

Квантовому алгоритму, который в 1992 году придумали Дэвид Дойч и Ричард Йожа, хватает одного. Оракул в квантовом мире работает так: он умножает амплитуду каждого $|x\rangle$ на $(-1)^{f(x)}$. Схема — $H$ на все кубиты, оракул, снова $H$ на все кубиты, измерение.

Постоянная функция даёт $00\ldots0$ всегда, сбалансированная — никогда. Почему, видно из одной строчки: после второго $H$ амплитуда $|00\ldots0\rangle$ равна среднему всех знаков, $\frac1N \sum_x (-1)^{f(x)}$. У постоянной функции все знаки одинаковы, и среднее равно $\pm 1$. У сбалансированной плюсов столько же, сколько минусов, и они гасят друг друга до нуля. Опять интерференция: функцию вызвали один раз, но в одном вызове участвовали все $N$ амплитуд, и ответ — свойство всей функции, а не её отдельного значения.

Запишем в журнал и оговорку. Если разрешить случайность, обычному компьютеру тоже хватит немногого: вызовите $f$ на десяти случайных входах — если ответы разные, функция сбалансирована, а если одинаковые, она постоянная с ошибкой не больше $2^{-9}$, как у теста простоты Миллера — Рабина из главы 26. Так что практической пользы у Дойча — Йожи нет. Это один из первых строгих примеров, где квантовый алгоритм обгоняет любой классический детерминированный экспоненциально, и в его приёме — $H$, оракул, $H$ — уже видна схема будущих алгоритмов, включая алгоритм Шора.

Опыт 5. Гровер: иголка за √N

Задача из жизни: среди $N$ вариантов ровно один подходит, и проверить вариант легко, а никакой структуры, кроме проверки, нет. Подобрать ключ, найти вход, на котором функция вернёт «да». Обычный компьютер перебирает варианты по одному, в среднем $N/2$ проверок. В 1996 году Лов Гровер из Bell Labs придумал квантовый алгоритм, которому хватает около $\frac{\pi}{4}\sqrt N$ обращений к проверке.

Сколько обращений к проверке нужно алгоритму Гровера, чтобы почти наверняка найти один нужный вариант среди миллиона?

около 20, как двоичному поиску около 800 около полумиллиона, как перебору одно, как у Дойча — Йожи

$\frac\pi4\sqrt{10^6} \approx 785$. Это гораздо меньше полумиллиона, но гораздо больше двадцати: двоичному поиску помогает порядок, а у Гровера никакой структуры нет. И одним обращением тут не обойтись — это доказано.

Шаг алгоритма — два действия. Оракул переворачивает знак амплитуды у нужного варианта. Потом каждую амплитуду отражают относительно среднего всех амплитуд: $a \mapsto 2\bar a - a$ (это тоже унитарная операция, её собирают из гейтов $H$, $X$ и управляемого $Z$). Пусть вначале все $N$ амплитуд равны $1/\sqrt N$. После переворота нужная стала $-1/\sqrt N$, среднее чуть уменьшилось, а отражение подбрасывает нужную амплитуду почти до $3/\sqrt N$ — остальные же почти не меняются. Поначалу каждый шаг добавляет нужной амплитуде примерно по $2/\sqrt N$, потом прибавки тают, и до единицы она дорастает примерно за $\frac\pi4\sqrt N$ шагов.

Двадцать пять шагов вместо пятисот в среднем у перебора — и вероятность 0,999. Но дальше она падает: через пятьдесят шагов нужный вариант почти не выпадает. Геометрически каждый шаг — поворот вектора состояния на один и тот же угол $2\theta$, где $\sin\theta = 1/\sqrt N$, в плоскости, натянутой на нужный вариант и равную смесь всех остальных. После $k$ шагов вероятность успеха — $\sin^2\bigl((2k+1)\theta\bigr)$: поворот, не остановленный вовремя, проскакивает цель.

Лучше Гровера нельзя. Ещё в 1997 году Беннет, Бернштейн, Брассар и Вазирани доказали, что любому квантовому алгоритму, который ничего не знает о задаче, кроме ответов оракула, нужно порядка $\sqrt N$ обращений. Поэтому от трудных задач Гровер не спасает. Задачи из NP можно решать перебором подсказок, а Гровер ускоряет перебор только квадратично: $2^n$ превращается в $2^{n/2}$ — всё ещё экспонента. Для симметричных шифров из главы 59 это значит вот что: перебор 128-битного ключа AES квантовый компьютер сократил бы до порядка $2^{64}$ шагов, и защита — ключ длиннее, 256 бит.

Шор и RSA

Самый знаменитый квантовый алгоритм мы уже встречали — в главе 60. В 1994 году Питер Шор показал, как раскладывать числа на множители и вычислять дискретные логарифмы за полиномиальное время, а значит, ломать RSA и Диффи — Хеллмана. В основе у него тот же приём, что в опытах 4 и 5. Квантовая часть ищет период последовательности $a, a^2, a^3, \ldots \bmod n$: в суперпозиции считаются все степени сразу, а квантовое преобразование Фурье устраивает интерференцию так, что усиливаются исходы, связанные с периодом, и гасятся остальные. Дальше работает обычная арифметика остатков, её разбирает «Царица наук».

Для трезвой оценки — два числа. Самые большие числа, разложенные на реальных квантовых компьютерах по схеме Шора, — 15 (IBM, 2001 год, семь кубитов) и 21 (2012 год), и даже эти опыты упрощали схему, заранее зная ответ. А по оценке, которую мы приводили в главе 60, для 2048-битного RSA нужно меньше миллиона шумных физических кубитов и меньше недели работы. В самых крупных нынешних машинах кубитов от сотни до тысячи с небольшим — на три-четыре порядка меньше. Угроза реальна, хотя и не сегодняшняя. Ответ на неё — постквантовые стандарты — уже принят.

Чего квантовый компьютер не умеет

Задачи, которые квантовый компьютер решает за полиномиальное время, ошибаясь не чаще чем в трети случаев, образуют класс BQP. Ошибку в треть можно сделать сколь угодно малой, повторив вычисление несколько раз и проголосовав. Вот что о нём известно на карте классов из главы 57. BQP содержит P: обычное вычисление можно сделать обратимым и выполнить на кубитах. BQP лежит внутри PSPACE: амплитуды можно сложить по одной, пусть и за экспоненциальное время, но в полиномиальной памяти. Разложение на множители лежит в BQP, а быстрого классического алгоритма для него не знают.

А дальше — сплошное «не знаем». Неизвестно, решает ли квантовый компьютер NP-полные задачи за полиномиальное время; большинство исследователей считает, что нет, и предел Гровера намекает почему: «перебор всего сразу» не работает. Неизвестно даже, шире ли BQP, чем P: доказательство потребовало бы разделить P и PSPACE, а это открытая задача. Одно известно наверняка. Квантовый компьютер вычисляет те же функции, что машина Тьюринга, — обычный компьютер может его симулировать, пусть и экспоненциально медленно. Значит, неразрешимые задачи из главы 56 остаются неразрешимыми, и тезис Чёрча — Тьюринга о том, что вычислимо, квантовая механика не отменяет. Под вопросом только то, как быстро.

Опыт 6. Шум и коррекция ошибок

До сих пор наши кубиты были идеальными. Реальные кубиты — сверхпроводящие контуры при температуре в сотые доли градуса над абсолютным нулём, ионы в ловушках, атомы в лучах лазеров — всё время взаимодействуют с окружением. Каждое такое взаимодействие — маленькое неконтролируемое измерение: амплитуды понемногу портятся, и суперпозиция превращается в обычную случайную монетку — у сверхпроводящих кубитов за доли миллисекунды, у ионов и атомов за секунды. Это называют декогеренцией. Гейты тоже неточны: у лучших машин двухкубитный гейт ошибается примерно в одном случае из тысячи. Алгоритму Шора для RSA нужны миллиарды гейтов. Без исправления ошибок он не дойдёт до конца.

Обычные биты защищают повторением: храним три копии и голосуем. С кубитами это, кажется, невозможно дважды. Неизвестное квантовое состояние нельзя скопировать — это теорема, — а измерить кубит, чтобы проверить, значит разрушить его. Выход всё же есть; код из трёх кубитов, о котором речь ниже, описал ещё в 1985 году физик Ашер Перес. Копировать не нужно: состояние $\alpha|0\rangle + \beta|1\rangle$ можно закодировать в три кубита как $\alpha|000\rangle + \beta|111\rangle$ — CNOT-ами, не зная $\alpha$ и $\beta$. А измерять нужно попарные чётности кубитов: совпадают ли кубиты 0 и 1, совпадают ли 1 и 2. У $|000\rangle$ и $|111\rangle$ чётности одинаковы, поэтому измерение чётностей ничего не говорит об $\alpha$ и $\beta$ и не разрушает их. Зато если один кубит перевернулся, чётности покажут, какой.

Код из трёх кубитов спасает от любого одного переворота, а проигрывает, только если перевернулись два или три: это случается с вероятностью $3p^2 - 2p^3$. При $p = 0{,}01$ — три на десять тысяч вместо одного на сто. Амплитуды $0{,}6$ и $0{,}8i$ пережили исправление нетронутыми: мы ни разу не узнали их, но вернули на место. Но кубит может испортиться и иначе: сменить знак, как от гейта $Z$. В 1995 году тот же Питер Шор собрал код из девяти кубитов, который защищает и от того, и от другого, — первый код, исправляющий любую ошибку одного кубита: трижды повторённые тройки, переложенные гейтами $H$. Сегодня в ходу коды на плоской решётке кубитов, поверхностные.

Кубит, закодированный во многих физических, называют логическим. Главный результат теории — пороговая теорема середины 1990-х: если ошибки физических кубитов реже некоторого порога, то, увеличивая код, ошибки логического кубита можно сделать сколь угодно малыми, и каждый шаг увеличения уменьшает их в разы. Если чаще порога — увеличение кода только вредит. В нашей ячейке это видно в миниатюре: при $p = 0{,}3$ код выигрывает немного, а при $p > \tfrac12$ он стал бы проигрывать. Поэтому в оценке для RSA меньше миллиона физических кубитов, но логических среди них — около 1400, а всё остальное — их защита.

Как читать новости

В этой истории никто не обманывал: опыт 2019 года был крупным научным достижением. Но заголовок «квантовый компьютер за 200 секунд сделал то, на что суперкомпьютеру нужно 10 000 лет» читатель понимал иначе, чем авторы опыта. Вот что стоит спросить у любой новости о квантовых компьютерах.

1. Какая задача? Полезная — химия, материалы, разложение чисел — или придуманная, чтобы квантовой машине было удобно? «Превосходство» почти всегда показывали на вторых.
2. С чем сравнивали? С лучшим известным классическим алгоритмом или с удобным? Классические методы тоже совершенствуются, и рекорды «10 000 лет» несколько раз сокращались до дней и секунд.
3. Какие кубиты? Физические или логические, и как часто они ошибаются. Сто шумных кубитов и сто логических — машины разных эпох.
4. Можно ли проверить ответ? Результат случайной схемы трудно проверить даже её авторам. Поэтому так ценны опыты, где ответ проверяем, — в октябре 2025 года Google заявила о первом проверяемом преимуществе на физической задаче, примерно в 13 000 раз быстрее суперкомпьютера.
5. Что сказано о сроках? Обещания скорых сроков звучат в этой области давно, а вехи — коррекция ниже порога, первый логический гейт, первая полезная задача — надёжнее дат.

И трезвая картина на осень 2026 года. Лучшие машины на сверхпроводниках и ионах насчитывают около сотни–полутора сотен физических кубитов, и у самых точных двухкубитный гейт ошибается примерно раз на тысячу (в лабораторном рекорде 2025 года — раз на десять тысяч); бывают машины и на тысячу с лишним кубитов, но кубиты в них заметно шумнее. Числа в несколько тысяч из новостей относятся к другому: к квантовым отжигателям D-Wave, на которых не запустить ни Шора, ни Гровера, или к массиву из 6100 атомов в лазерных ловушках (Калтех, 2025), где кубиты держали в суперпозиции, но вычислений на всём массиве не вели. Коррекция ошибок впервые работает так, как обещает теория: больше кода — меньше ошибок. Но логические кубиты пока ошибаются примерно раз на тысячу циклов, а для больших алгоритмов нужно в тысячи раз реже. До Шора на RSA-2048 — примерно на три порядка больше кубитов, чем в самых крупных машинах. Ни «никогда», ни «скоро» из этих чисел не следует: сроков не знает никто. Поэтому шифры и меняют на постквантовые уже сейчас.

Заголовок: «Новый квантовый процессор решил за пять минут задачу, на которую самому быстрому суперкомпьютеру понадобилось бы $10^{25}$ лет». Что из этого следует наверняка?

RSA скоро перестанет быть безопасным квантовые компьютеры теперь быстрее обычных почти во всём на одной специально подобранной задаче известные сегодня классические методы сильно отстают доказано, что квантовые компьютеры сильнее классических

Так в декабре 2024 года сообщили о процессоре Willow. Утверждение верное, если читать его буквально: задача — выборка из случайной схемы, оценка — для лучших известных сегодня классических алгоритмов.

Задачи

Три задачи — три прибора для лаборатории: симулятор, генератор состояний Белла с опознавателем и поиск Гровера, которому не страшны шестьдесят пять тысяч вариантов. Везде действует соглашение главы: в двухкубитном состоянии номер амплитуды — $2 q_0 + q_1$, кубит 0 — старший бит.

Напишите две функции для двухкубитного состояния — массива numpy из четырёх комплексных амплитуд $(a_{00}, a_{01}, a_{10}, a_{11})$. apply(state, gate, qubit) применяет гейт — матрицу 2 × 2 — к кубиту 0 или 1. cnot(state, control, target) применяет CNOT с управляющим кубитом control и целевым target (это 0 и 1 в любом порядке). Обе функции возвращают новый вектор и не меняют переданный. Тесты проверяют базисные состояния, комплексные фазы и сотню случайных гейтов.

Проверьте заготовку на простом: apply(|00⟩, X, 0) должна дать $|10\rangle$, то есть единицу в амплитуде номер 2. В np.kron(A, B) матрица A действует на старший бит номера, B — на младший. Какой из них кубит 0?

CNOT — перестановка амплитуд. Пройдите по номерам $i$ от 0 до 3, достаньте биты: кубит 0 — (i >> 1) & 1, кубит 1 — i & 1. Если управляющий бит равен 1, амплитуда переезжает в номер с перевёрнутым целевым битом. Не забудьте сделать копию: out = state.copy(), и сразу приведите тип к complex.

Весь симулятор — две операции: тензорное произведение для однокубитных гейтов и перестановка для CNOT. Этого достаточно для любых схем: $H$, фазовые гейты и CNOT вместе универсальны — из них приближённо собирается любая унитарная операция, как из NAND в главе 29 собиралась любая логика. Порядок в np.kron — главный источник ошибок во всех самодельных симуляторах: в библиотеке Qiskit, например, принят обратный порядок, кубит 0 — младший бит.

Напишите bell_circuit(k): схему, которая из $|00\rangle$ готовит $k$-е состояние Белла: 0 — $(|00\rangle + |11\rangle)/\sqrt2$, 1 — $(|00\rangle - |11\rangle)/\sqrt2$, 2 — $(|01\rangle + |10\rangle)/\sqrt2$, 3 — $(|01\rangle - |10\rangle)/\sqrt2$. Схема — список строк вроде "H 0", "X 1", "Z 0", "CNOT 0 1", не длиннее шести гейтов. Общий множитель у всего вектора (например, −1) физически ничего не меняет, и тесты его прощают. Вторая функция, identify(state), получает одно из четырёх состояний — возможно, с таким общим множителем — и возвращает его номер $k$.

Схема «H на кубит 0, потом CNOT» превращает $|00\rangle$ в первое состояние. Что она сделает с $|01\rangle$, $|10\rangle$, $|11\rangle$? Приготовьте нужный базисный вход гейтами $X$ — и все четыре состояния получатся одной схемой.

Для identify прогоните схему задом наперёд: CNOT, затем $H$ на кубит 0. Каждое состояние Белла превратится в базисное, и номер можно прочитать по самой большой по модулю амплитуде — общий множитель модули не меняет.

Схема «H, CNOT» переводит базис $|ab\rangle$ в базис Белла, а обратная схема — назад; так и устроено измерение в базисе Белла. На нём держатся квантовая телепортация и сверхплотное кодирование: Алиса, действуя гейтами $X$ и $Z$ только на свою половину пары Белла, выбирает одно из четырёх состояний — два бита, — и Боб, получив её кубит, читает оба бита одним измерением в этом базисе. Кубит для этого всё равно приходится переслать: запутанность и здесь сама по себе сообщений не передаёт.

Напишите grover(n, marked, steps): начав с равной суперпозиции $N = 2^n$ вариантов, сделайте steps шагов Гровера (оракул переворачивает знак у варианта marked, затем отражение относительно среднего) и верните массив вероятностей всех $N$ исходов. И best_steps(n) — число шагов, при котором вероятность найти отмеченный вариант наибольшая. Тесты начинают с $N = 4$, где один шаг даёт ответ наверняка, и кончают $N = 65\,536$, которые нужно обработать быстрее двух секунд.

Матрица отражения для $N = 65\,536$ — это четыре миллиарда чисел, 32 гибибайта. Но умножать на неё не нужно: $\bigl(\tfrac2N J - I\bigr)\,a = 2\bar a - a$, где $\bar a$ — среднее амплитуд. Одна строка numpy.

Формула $\frac\pi4\sqrt N$ — приближение. Точнее: после $k$ шагов вероятность $\sin^2\bigl((2k+1)\theta\bigr)$, где $\sin\theta = 1/\sqrt N$. Для $N = 4$ угол $\theta = 30^\circ$, и уже один шаг даёт $\sin^2 90^\circ = 1$, а два — только $\tfrac14$. Найдите $k$, ближайшее к $\frac{\pi}{4\theta} - \frac12$, и проверьте соседей.

Отражение от среднего стоит $O(N)$, а не $O(N^2)$: на 65 536 вариантах это 201 шаг по доле миллисекунды. На квантовом компьютере этот шаг собирают из $O(n)$ гейтов — $H$ на все кубиты, $X$ на все, многоуправляемый $Z$ и снова $X$ и $H$, — и каждый шаг Гровера стоит одно обращение к оракулу. Ошибка заготовки в best_steps — слепое доверие к асимптотике: $\frac\pi4\sqrt N$ хороша при больших $N$, а при малых промахивается на целый шаг, и для $N = 4$ этот шаг стоит трёх четвертей вероятности.

Куда дальше

Закроем журнал. Кубит — вектор из двух комплексных амплитуд, гейт — унитарная матрица, измерение — один случайный бит, и всё остальное в главе выросло из этих трёх строк: интерференция, запутанность, из-за которой $n$ кубитов требуют $2^n$ чисел, Дойч — Йожа, Гровер, коды, которые исправляют ошибки, не глядя на данные. Видны и границы: Гровер не быстрее $\sqrt N$, NP-полные задачи квантовому компьютеру, по всей видимости, тоже не по зубам, а неразрешимые остаются неразрешимыми.

А слова «неизвестно» и «по всей видимости» встречались в этой главе на каждом шагу. Мы не знаем, шире ли BQP, чем P, — умеет ли квантовый компьютер хоть что-нибудь, чего принципиально не умеет быстро обычный. Не знаем, лёгкое ли разложение на множители и без кубитов. Не знаем, как соотносятся BQP и NP. Ответов не знает никто, и таких пробелов в науке больше, чем кажется. Последняя глава — карта того, что осталось неизвестным: белые пятна, к которым ведут дороги из всех частей этой книги.