Гейт Тоффоли

Гейт Тоффоли (также известный как контролируемый-контролируемый-NOT или CCNOT) — это универсальный трёхкубитный логический вентиль в квантовых вычислениях, являющийся квантовым аналогом классического логического элемента «И-НЕ» (NAND) и обладающий свойством обратимости. Предложен в 1980 году американским учёным Эдвардом Тоффоли.

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

История

Концепция обратимых вычислений и соответствующих логических элементов была разработана в 1970-х годах, когда учёные начали исследовать фундаментальные термодинамические пределы вычислительных процессов. В 1973 году Чарльз Беннетт показал, что любые классические вычисления могут быть выполнены обратимым образом, если использовать специальные логические вентили. Однако предложенные им схемы требовали большого количества дополнительных битов (так называемых «мусорных» битов), что снижало практическую эффективность.

В 1980 году Эдвард Тоффоли, работавший в Массачусетском технологическом институте, представил трёхбитный обратимый вентиль, который получил его имя. В отличие от более ранних обратимых вентилей (например, вентиля Фредкина), гейт Тоффоли требовал только один дополнительный бит для реализации универсальных вычислений. В 1985 году Дэвид Дойч обобщил эту идею на квантовый случай, показав, что квантовый гейт Тоффоли может быть реализован с помощью последовательности однокубитных и двухкубитных квантовых операций (например, гейтов Адамара и CNOT).

Определение и математическое описание

Гейт Тоффоли действует на трёх кубитах: два управляющих (A и B) и один целевой (C). Его таблица истинности в классическом (битовом) случае выглядит следующим образом:

В квантовом случае гейт Тоффоли описывается унитарной матрицей размером 8×8, которая является перестановочной (то есть переставляет базисные состояния). Матрица имеет вид:

\[ \text{CCNOT} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} \]

Матрица является унитарной (UU† = I) и эрмитовой (U = U†), что означает, что гейт Тоффоли является собственным обратным: применение его дважды возвращает систему в исходное состояние.

Свойства

Универсальность

Гейт Тоффоли является универсальным для классических обратимых вычислений. Это означает, что любой обратимый логический элемент может быть построен из комбинации гейтов Тоффоли. В частности, с помощью одного гейта Тоффоли можно реализовать классический вентиль NAND (И-НЕ), который, в свою очередь, является универсальным для всех классических вычислений. Для этого достаточно подать на входы A и B сигналы, а на вход C — константу |1⟩. Тогда на выходе C получится NOT(A AND B), то есть NAND.

Обратимость

Гейт Тоффоли является обратимым: зная выходные состояния всех трёх кубитов, можно однозначно восстановить входные. Это свойство принципиально отличает его от необратимых классических вентилей (например, AND или OR), которые теряют информацию при вычислении. Обратимость позволяет избежать диссипации энергии, связанной с «забыванием» битов, что теоретически позволяет создавать вычислительные устройства с нулевым энергопотреблением (в рамках обратимых вычислений).

Квантовая реализация

Хотя гейт Тоффоли является трёхкубитным, он может быть реализован с помощью последовательности однокубитных и двухкубитных гейтов. Стандартная схема разложения включает 6 гейтов CNOT и 7 однокубитных гейтов (в частности, гейтов Адамара и T). Эта схема была предложена в 1995 году Адрианом Баренко и другими исследователями. В современных квантовых компьютерах гейт Тоффоли реализуется либо напрямую (если архитектура поддерживает трёхкубитные операции), либо через разложение на более простые элементы.

Применение

Квантовые алгоритмы

Гейт Тоффоли является ключевым элементом многих квантовых алгоритмов, включая:

• Алгоритм Гровера (поиск в неструктурированной базе данных) — используется для построения оракула, который инвертирует фазу целевого состояния.
• Алгоритм Шора (факторизация чисел) — применяется в модульном возведении в степень, где требуется реализация обратимых арифметических операций.
• Квантовое сложение — гейт Тоффоли используется для построения квантовых сумматоров (например, сумматора Кюнера), которые выполняют сложение двух чисел без потери информации.

Исправление квантовых ошибок

В квантовых кодах, исправляющих ошибки, гейт Тоффоли применяется для реализации операций, которые позволяют обнаруживать и корректировать ошибки, не нарушая квантовой суперпозиции. Например, в коде Шора (9-кубитном коде) гейт Тоффоли используется для выполнения операции «контролируемый-NOT» на трёх кубитах.

Квантовое моделирование

Гейт Тоффоли используется для симуляции квантовых систем, где требуется реализация трёхчастичных взаимодействий. Например, в модели Гейзенберга (модель спиновой цепочки) гейт Тоффоли может быть использован для аппроксимации трёхспинового обменного взаимодействия.

Реализация в квантовых компьютерах

В современных квантовых компьютерах гейт Тоффоли реализуется с помощью различных физических платформ:

• Сверхпроводящие кубиты (IBM, Google) — гейт Тоффоли реализуется через последовательность импульсов микроволнового излучения, управляющих состояниями кубитов. В 2020 году группа исследователей из Google Quantum AI продемонстрировала реализацию гейта Тоффоли с точностью 99,8% на 53-кубитном процессоре Sycamore.
• Ионные ловушки (IonQ, Honeywell) — гейт Тоффоли реализуется с помощью лазерных импульсов, воздействующих на ионы, удерживаемые в электромагнитных ловушках. В 2021 году на платформе IonQ был продемонстрирован гейт Тоффоли с точностью 99,5%.
• Фотонные системы — гейт Тоффоли может быть реализован с помощью линейных оптических элементов (светоделителей, фазовращателей) и нелинейных эффектов. Однако из-за сложности реализации трёхфотонных взаимодействий такие схемы пока остаются экспериментальными.

Критика и ограничения

Несмотря на свою универсальность, гейт Тоффоли имеет ряд ограничений:

• Высокая стоимость реализации — в квантовых компьютерах трёхкубитные операции требуют значительно большего количества элементарных операций (однокубитных и двухкубитных гейтов), чем двухкубитные. Это увеличивает время выполнения алгоритма и повышает вероятность ошибок из-за декогеренции.
• Чувствительность к шумам — гейт Тоффоли, как и любой трёхкубитный вентиль, более чувствителен к ошибкам, чем двухкубитные операции. В современных квантовых процессорах точность реализации гейта Тоффоли обычно ниже, чем точность реализации гейта CNOT.
• Альтернативные подходы — в некоторых квантовых алгоритмах трёхкубитные операции могут быть заменены последовательностью двухкубитных гейтов с использованием дополнительных (анциллярных) кубитов. Это может упростить реализацию, но увеличивает требуемое количество кубитов.

Интересные факты

• Гейт Тоффоли является частным случаем более общего семейства контролируемых вентилей, где число управляющих кубитов может быть произвольным. Вентиль с n управляющими кубитами называется C^nNOT.
• В классических обратимых вычислениях гейт Тоффоли может быть реализован механически — например, с помощью системы рычагов и шестерёнок. Такие механические обратимые компьютеры были построены в 1990-х годах в Массачусетском технологическом институте.
• Гейт Тоффоли является одним из немногих трёхкубитных вентилей, которые являются универсальными для обратимых вычислений. Другим известным примером является вентиль Фредкина (контролируемый SWAP), который также является трёхкубитным и обратимым.

Источники

• Toffoli, T. (1980). Reversible computing. Automata, Languages and Programming, 632–644.
• Barenco, A., et al. (1995). Elementary gates for quantum computation. Physical Review A, 52(5), 3457–3467.
• Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
• Bennett, C. H. (1973). Logical reversibility of computation. IBM Journal of Research and Development, 17(6), 525–532.
• Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A, 400(1818), 97–117.