Курс «Квантовые вычисления». Глава 4. Квантовые схемы и универсальность

Курс «Квантовые вычисления»

Цели главы. Достроить модель вычислений: научиться читать и составлять квантовые схемы, освоить многокубитные вентили, понять, как обратимо вычислить любую классическую функцию (это понадобится каждому алгоритму курса), и выяснить, какой набор вентилей достаточен для любых квантовых вычислений.

4.1. Схемная модель

Квантовая схема читается слева направо: горизонтальные линии («провода») обозначают кубиты, прямоугольники — вентили, точки и соединяющие их линии — управление, значок измерительного прибора — измерение с классическим результатом. В базовой модели алгоритм представляют конечной последовательностью унитарных операций и завершающих измерений. Произвольное неизвестное состояние нельзя разветвить на две одинаковые копии. При этом современные динамические схемы допускают измерение в середине вычисления, сброс кубита и классическое условное выполнение последующих вентилей; с таким управлением мы уже встретились в лабораторной работе главы 3. Циклический алгоритм перед выполнением можно развернуть в конечную схему для заданного числа итераций.

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

4.2. Многокубитные вентили

Из любого однокубитного вентиля U строится управляемый вентиль CU: применить U к целевому кубиту, если управляющий равен |1⟩. На базисных состояниях: CU|0⟩|ψ⟩ = |0⟩|ψ⟩, CU|1⟩|ψ⟩ = |1⟩(U|ψ⟩). Частные случаи:

• CNOT = CX — уже знакомый из главы 3;
• CZ — управляемый Z. Его матрица симметрична относительно перестановки кубитов: вентиль лишь меняет знак амплитуды состояния |11⟩, поэтому обозначение управляющего и целевого кубитов можно поменять местами. Связь CZ и CNOT: CNOT = (I⊗H)·CZ·(I⊗H) — следствие тождества HZH = X из главы 2;
• SWAP — обмен состояний двух кубитов; собирается из трёх CNOT (упражнение 1) — квантовый аналог классического трюка обмена переменных тремя XOR;
• Вентиль Тоффоли (CCX) — NOT с двумя управляющими: инвертирует третий кубит, если первые два равны единице. При наличии анцилл, инициализированных известными битами, из вентилей Тоффоли можно строить произвольные классические обратимые вычисления.

4.3. Обратимые вычисления классических функций

Все вентили унитарны, а значит, обратимы — но классические операции AND и OR необратимы: по выходу AND нельзя восстановить входы. Как же квантовый компьютер будет вычислять обычные функции — а это нужно каждому алгоритму, от Дойча до Шора?

Стандартное решение: функцию f: {0,1}ⁿ → {0,1}^m реализуют оператором

U_f: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩,

где ⊕ — побитовый XOR. Вход x сохраняется, а f(x) складывается с выходным регистром; U_f переставляет базисные состояния, поэтому унитарен, причём U_f⁻¹ = U_f. Классическую схему размера G можно обратимо воспроизвести с полиномиальными, а для стандартных схем — линейными по G накладными расходами, используя NOT, CNOT, Тоффоли и вспомогательные кубиты (анциллы) в состоянии |0⟩.

Промежуточные анциллы после вычисления содержат значения подвыражений. Если их оставить, они в общем случае будут коррелированы или запутаны с основными регистрами и сохранят информацию о пути вычисления, мешая требуемой интерференции. Приём Беннета compute–copy–uncompute устраняет этот мусор: вычислить результат вместе с промежуточными значениями, перенести значение классической функции в чистый выходной регистр операциями XOR, затем выполнить вычисление в обратном порядке и вернуть анциллы в |0⟩. Это не клонирование неизвестного квантового состояния: CNOT когерентно копирует значения выбранного вычислительного базиса и обычно создаёт запутанность на суперпозиции входов. Вычисление и его обращение дают примерно двукратную цену основной подпрограммы плюс операции переноса результата.

4.4. Универсальные наборы вентилей

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

{H, T, CNOT}

Контур доказательства таков: общую унитарную матрицу раскладывают в произведение операций, нетривиальных лишь на двумерных подпространствах; их реализуют с помощью CNOT и однокубитных вентилей; наконец, композиции H и T образуют плотное подмножество однокубитных унитарных операций. Хотя собственные углы H и T соизмеримы с π, некоторые их произведения задают повороты с углом, несоизмеримым с π, что и обеспечивает плотность.

Насколько дорого приближение? Теорема Соловея–Китаева для конечного универсального набора, замкнутого относительно обращения, даёт длину O(log^c(1/ε)) для ошибки не более ε, где c — постоянная. Поэтому цена точности растёт полилогарифмически, а не как 1/ε. Для набора Клиффорд + T существуют специализированные алгоритмы синтеза с ещё лучшей асимптотикой порядка O(log(1/ε)) по числу T-вентилей.

Почему в наборе нужен T, а не только S? По теореме Готтесмана–Нилла стабилизаторные схемы — подготовка вычислительных базисных состояний, вентили Клиффорда H, S и CNOT, измерения Паули и допустимое классическое управление — эффективно моделируются классическим компьютером, хотя могут создавать запутанность. В представлении схем через набор Клиффорд + T именно T является не-клиффордовским ресурсом, поэтому отдельно считают T-count и T-depth; в распространённых отказоустойчивых схемах его реализация особенно дорога (глава 11). Другие модели могут получать не-клиффордовский ресурс из иных вентилей, состояний или измерений.

4.5. Сколько стоит схема

Квантовые алгоритмы оценивают по нескольким ресурсам: числу логических кубитов (ширине), общему числу вентилей (размеру), глубине, числу и глубине двухкубитных вентилей, а для отказоустойчивых машин — также T-count, T-depth и расходу вспомогательных состояний. Физическая оценка дополнительно учитывает связность, длительности и ошибки операций, код коррекции ошибок и декодирование. Поэтому одно число кубитов или вентилей само по себе не характеризует выполнимость алгоритма.

Итоги главы

• Базовая схема состоит из кубитов, унитарных вентилей и измерений; динамическая схема добавляет измерения в середине и классическое управление. Ключевые метрики — ширина, размер и глубина.
• Управляемый вариант можно определить для любого однокубитного вентиля; важные двух- и трёхкубитные операции — CNOT, CZ, SWAP и Тоффоли.
• Любая классическая функция вычислима обратимо в форме U_f|x⟩|y⟩ = |x⟩|y⊕f(x)⟩; приём compute–copy–uncompute очищает анциллы, когда сохранённый мусор мешает последующей интерференции.
• {H, T, CNOT} — универсальный набор; теорема Соловея–Китаева ограничивает цену аппроксимации полилогарифмом точности.
• Стабилизаторные схемы эффективно моделируются классически; в наборе Клиффорд + T необходимый не-клиффордовский ресурс вносит T-вентиль.

Упражнения

1. Проверьте, что последовательность CNOT_1→2, CNOT_2→1, CNOT_1→2 реализует SWAP, проследив эволюцию всех четырёх базисных состояний.
2. Выпишите матрицу 4×4 вентиля CZ и убедитесь, что она не меняется при перестановке ролей управляющего и целевого кубитов.
3. Используя HZH = X, докажите тождество CNOT = (I⊗H)·CZ·(I⊗H).
4. Постройте U_f для функции AND: f(x₁, x₂) = x₁∧x₂. Какой стандартный вентиль это даёт?
5. Функция f(x₁, x₂, x₃) = (x₁∧x₂)∨x₃ вычисляется через промежуточное значение t = x₁∧x₂. Составьте схему compute–copy–uncompute с одной анциллой и убедитесь, что анцилла возвращается в |0⟩ на всех восьми входах. Указание: a∨b = a⊕b⊕(a∧b).
6. Примените CNOT к состоянию |+⟩⊗|+⟩ и к состоянию |+⟩⊗|−⟩. Во втором случае вы обнаружите, что изменился... управляющий кубит. Этот эффект — «фазовый откат» — станет главным героем главы 5; убедитесь в нём выкладкой уже сейчас.

Ответы и указания. 1: для входа (a,b) три шага дают (a,b⊕a) → (b,b⊕a) → (b,a). 2: CZ = diag(1,1,1,−1). 3: два H на целевом кубите сопрягают условный Z в условный X, а ветвь с управляющим нулём оставляют единичной. 4: вентиль Тоффоли с целевым кубитом y. 5: вычислите t = x₁∧x₂; затем выполните над выходом y операции CNOT(t,y), CNOT(x₃,y) и Toffoli(t,x₃;y), реализующие y ↦ y⊕t⊕x₃⊕t x₃; повторный Toffoli(x₁,x₂;t) очищает анциллу. 6: CNOT(|+⟩|+⟩) = |+⟩|+⟩, но CNOT(|+⟩|−⟩) = |−⟩|−⟩: поскольку X|−⟩ = −|−⟩, фаза откатывается на управляющий кубит.

Литература к главе

1. M. Nielsen, I. Chuang, "Quantum Computation and Quantum Information," гл. 4. Cambridge University Press, 2010.
2. C. Bennett, "Logical Reversibility of Computation," IBM J. Res. Dev. 17, 1973.
3. D. Gottesman, "The Heisenberg Representation of Quantum Computers," 1998. arxiv.org/abs/quant-ph/9807006
4. C. Dawson, M. Nielsen, "The Solovay-Kitaev Algorithm," Quantum Information & Computation 6, 2006. arxiv.org/abs/quant-ph/0505030

Предыдущая глава || Содержание курса || Следующая глава