Обратимые вычисления и бильярдный компьютер Фредкина
Классический компьютер строится на логических вентилях: НЕ, И, ИЛИ и универсальном вентиле И-НЕ (NAND). Но у обычных вентилей есть проблема: они необратимы. Если на выходе вентиля И получился , вы не знаете, что было на входе: , или . Часть информации стирается.
Рольф Ландауэр доказал, что стирание 1 бита информации физически обязано рассеивать минимальное количество тепла (предел Ландауэра). А законы физики на микроуровне обратимы! Это навело Эдварда Фредкина и Томаса Тоффоли на идею обратимых вентилей, в которых число входов равно числу выходов, и по выходу всегда однозначно восстанавливается вход:
- CNOT (Управляемое НЕ): . Если управляющий бит , второй бит инвертируется.
- Вентиль Тоффоли (CCNOT): два управляющих бита инвертируют третий, только если оба равны . С помощью вспомогательных (ancilla) и мусорных битов он универсален!
- Вентиль Фредкина (CSWAP): если первый бит равен , второй и третий меняются местами. При этом количество единиц на входе всегда равно количеству единиц на выходе.
Фредкин показал, что его вентиль можно собрать на идеальном бильярдном столе из сталкивающихся шаров и стенок-зеркал, где — это наличие шара, а — его отсутствие. Эта красивая модель подтолкнула Ричарда Фейнмана к замене бильярдных шаров квантовыми частицами.