Vector Spaces

Обратимые вычисления и бильярдный компьютер Фредкина

Вентили и схемы, статья 13 из 20

Классический компьютер строится на логических вентилях: НЕ, И, ИЛИ и универсальном вентиле И-НЕ (NAND). Но у обычных вентилей есть проблема: они необратимы. Если на выходе вентиля И получился 00, вы не знаете, что было на входе: (0,0)(0,0), (0,1)(0,1) или (1,0)(1,0). Часть информации стирается.

Рольф Ландауэр доказал, что стирание 1 бита информации физически обязано рассеивать минимальное количество тепла (предел Ландауэра). А законы физики на микроуровне обратимы! Это навело Эдварда Фредкина и Томаса Тоффоли на идею обратимых вентилей, в которых число входов равно числу выходов, и по выходу всегда однозначно восстанавливается вход:

  • CNOT (Управляемое НЕ): (x,y)↦(x,x⊕y)(x, y) \mapsto (x, x \oplus y). Если управляющий бит x=1x = 1, второй бит инвертируется.
  • Вентиль Тоффоли (CCNOT): два управляющих бита инвертируют третий, только если оба равны 11. С помощью вспомогательных (ancilla) и мусорных битов он универсален!
  • Вентиль Фредкина (CSWAP): если первый бит равен 11, второй и третий меняются местами. При этом количество единиц на входе всегда равно количеству единиц на выходе.
CNOT(x, y) → (x, x⊕y)Тоффоли(x, y, z) → (x, y, z⊕xy)Фредкинесли x = 1, то y и zменяются местами
Обратимые вентили: по выходу всегда можно восстановить вход. CNOT и Тоффоли инвертируют целевой бит, вентиль Фредкина меняет два бита местами.

Фредкин показал, что его вентиль можно собрать на идеальном бильярдном столе из сталкивающихся шаров и стенок-зеркал, где 11 — это наличие шара, а 00 — его отсутствие. Эта красивая модель подтолкнула Ричарда Фейнмана к замене бильярдных шаров квантовыми частицами.