Вентиль Тоффолі

Позначення вентиля Тоффолі на схемі

Вентиль Тоффолі (також вентиль CCNOT) — у логічних схемах вентиль, винайдений Томмазо Тоффолі, є універсальним оборотним логічним вентилем, що означає, що будь-яка оборотна схема може бути побудована з вентилів Тоффолі. Він також відомий як вентиль «контрольоване-контрольоване-НЕ», який описує його дію. Він має 3-бітові входи та виходи; якщо перші два біти встановлені в 1, він інвертує третій біт, інакше всі біти залишаються незмінними.

Основи

Логічний вентиль L є оборотним, якщо для будь-якого виходу y існує унікальний вхід x, такий що виконується L(x) = y. Якщо вентиль L є оборотним, існує зворотний вентиль L′, який відображає y в x, де L′(y) = x. Із загальноприйнятих логічних входів вентиль «НЕ» є оборотним, як це видно з таблиці істинності нижче.

ВХІД	ВИХІД
0	1
1	0

Однак у загальному випадку вентиль «І» не є оборотним. Входи 00, 01 і 10 відображаються на виході в 0.

Оборотні вентилі вивчали з 1960-х років. Початковою мотивацією було те, що оборотні вентилі розсіюють менше тепла (або, в принципі, не розсіюють тепла). Якщо розглянути логічний вентиль як щось, що споживає подане на вхід, інформація втрачається, оскільки на виході наявно менше інформації, ніж на вході. Через цю втрату інформації втрачається енергія до навколишнього середовища у вигляді тепла через термодинамічну ентропію. Іншим способом зрозуміти це є те, що заряди в ланцюзі стікають на землю забираючи з собою невелику кількість енергії, коли вони змінюють стан. Оборотний вентиль лише переміщує стани, і оскільки інформація не втрачається, енергія зберігається.

Більш недавня мотивація походить від квантових обчислень. Квантова механіка вимагає, щоб перетворення були оборотними і дозволяє більш загальні обчислення, ніж класичні комп'ютери (принцип суперпозиції).

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

Будь-який оборотний вентиль, який споживає свої вхідні дані та дозволяє всі вхідні обчислення, повинен мати не більше вхідних бітів, ніж вихідні біти, за принципом Діріхле. Для одного вхідного біта існує два можливих оборотних вентиля. Один з них НЕ. Інший — вентиль ідентичності, який відображає свої вхідні дані у вихідні дані без змін. Для двох вхідних бітів єдиним нетривіальним вентилем є вентиль «контрольоване-НЕ», який виконує операцію «Виключне АБО» першого біта і другого біта і залишає перший біт незмінним.

Таблиця істинності	Форма матриці перестановки
INPUT OUTPUT  0   0   0   0  0 1 0 1 1 0 1 1 1 1 1 0	${\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}$

На жаль, є оборотні функції, які неможливо обчислити, використовуючи лише ці вентилі. Іншими словами, набір, що складається з вентилів NOT і XOR, не є універсальним. Щоб обчислити довільну функцію за допомогою оборотних вентилів, нам потрібен інший вентиль. Одним з можливих є вентиль Тоффолі, запропонований Тоффолі в 1980 році.

Цей шлюз має 3-бітові вхід та вихід. Якщо встановлено перші два біти, він змінює на протилежне значення третій біт. Далі наведена таблиця вхідних і вихідних бітів:

Таблиця істинності	Форма матриці перестановки
INPUT OUTPUT  0   0   0   0   0   0  0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0	${\begin{bmatrix}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{bmatrix}}$

Це також можна описати як відображення бітів {a, b, c} в {a, b, c XOR (a AND b)}.

Вентиль Тоффолі універсальний; це означає, що для будь-якої булевої функції f(x₁, x₂, …, x_m), існує ланцюг, що складається з вентилів Тоффолі, який приймає x₁, x₂, …, x_m та деякі додаткові біти, які мають значення 0 або 1 для виходів x₁, x₂, …, x_m, f(x₁, x₂, …, x_m), а також додаткові біти (що називаються сміттєвими). По суті, це означає, що можна використовувати вентиль Тоффолі для побудови систем, які оборотно виконуватимуть обчислення будь-якої бажаної булевої функції.

Пов'язані логічні вентилі

Вентиль Тоффолі може бути сконструйований з одиничних кубітних вентилів і мінімум шести вентилів CNOT.

• Вентиль Фредкіна — це універсальний оборотний 3-бітовий вентиль, який міняє місцями два останні біти, якщо перший біт дорівнює 1; реалізує операцію керованого обміну.
• n — бітовий вентиль Тоффолі є узагальненням вентиля Тоффолі. Це приймає n біт x₁, x₂, …, x_n у якості входів і віддає n бітів. Перші n−1 вихідних бітів це просто x₁, …, x_n−1. Останній вихідний біт (x₁ AND … AND x_n−1) XOR x_n . Вентиль Тоффолі може бути реалізовано з п'яти двохкубітних квантових вентилів.Насправді для реалізації вентиля Тоффолі потрібно мінімум п'ять двохкубітних квантових вентилів.

• Пов'язаний з ними квантовий вентиль Дойча може бути реалізований за допомогою п'яти оптичних імпульсів з нейтральними атомами. Вентиль Дойча — це універсальний вентиль для квантових обчислень.

Відношення до квантових обчислень

Будь-які оборотні вентилі можуть бути реалізовані на квантовому комп'ютері, отже, вентиль Тоффолі також є квантовим оператором. Однак вентиль Тоффолі не може бути використаний для універсальних квантових обчислень, хоча це означає, що квантовий комп'ютер може реалізувати всі можливі класичні обчислення. Вентиль Тоффолі повинен бути реалізований разом з деякими по суті квантовими вентилями, щоб бути універсальним для квантових обчислень. Насправді достатньо будь-якого одиночного кубіта з реальними коефіцієнтами, який може створити нетривіальний квантовий стан. Вентиль Тоффолі на основі квантової механіки був успішно реалізований в січні 2009 року в Університеті Інсбрука, Австрія. Хоча реалізація n-кубітового Тоффолі вимагає 2n CNOT вентилів, застосування взаємодії багатьох тіл може безпосередньої використовувати для роботи вентиль на атомах Ридберга та реалізації надпровідних ланцюгів.