RUS  ENG
Полная версия
СЕМИНАРЫ

Квантовые вычисления
14 февраля 2024 г. 13:10, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom


Лекция 2. Схемная модель вычислений

В. И. Яшин


https://youtu.be/UW2urZWTIIo

Аннотация: На Лекции мы продолжили обсуждение различных свойств классических булевых схем. Любая булева операция содержит некоторое число бит на входе и на выходе. Зачастую естественно считать, что все вентили из словаря имеют конечный вход, поскольку физически реализуемые операции над битами как правило локальны. С другой стороны, поскольку классическую информацию дёшево копировать, зачастую удобно считать, что на число линий на выходе вентиля не ограниченно по $n$. Если принять такое соглашение, и если словарь универсален, то любую функцию можно реализовать за линейную глубину. Также, мы показали при помощи подсчёта, что большинство булевых функций требует экспоненциального числа операций. На протяжении курса нас часто будет интересовать не-универсальный класс афинных булевых функций. Такие функции связаны с линейной алгеброй над $\mathbb{Z}_2$ и их просто реализовывать схемами из словаря $\{\mathrm{NOT},\mathrm{XOR}\}$. Над пространством булевых функций можно ввести преобразование Уолша-Адамара-Фурье. Фурье-преобразованиями линейных булевых функций являются в точности $\delta$-функциями. При помощи семейств булевых схем возможно разрешать языки, и сложность языка определяется сложностью построения таких семейств.


© МИАН, 2024