Лекция 3. Обратимые вычисления

Принцип Ландауэра говорит о том, что при необратимых вычислениях комьютер обязательно выделяет тепло. В связи с этим принципом интересно изучать обратимые вычисления – их можно проводить без выделения тепла. Мы сформулировали, что такое обратимые вычисления, и показали, что булевы схемы можно сводить к обратимым. При этом, благодаря лемме об очистке мусора, мы способны делать это сведение без существенного увеличения памяти. Мы обсудили примеры обратимых вентилей и написали конкретный алгоритм того, как при помощи вентиля Тоффоли можно реализовать произвольную обратимую операцию, дали верхнюю и нижнюю оценки.