О реализации булевых функций в квантовых ветвящихся программах методом отпечатков

В работе представлен разработанный нами метод отпечатков вычисления булевых функций в квантовых моделях вычислений. Этот метод является развитием техники fingerprinting.
Применение метода отпечатков демонстрируется на примере вычисления функции $\mathrm{MOD}_m$ в классе квантовых OBDD (забывающих один раз читающих ветвящихся программ). Далее возможности метода отпечатков демонстрируются на примере реализации функции “равенство” в квантовой модели коммуникационных вычислений с рефери (SMP communication model) и на примере распознавания языков в квантовых автоматах.
Все приведенные реализации булевых функций в различных квантовых моделях вычислений (OBDD, коммуникационная модель SMP и конечный автомат) являются асимптотически оптимальными.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 08–07–00449, а также Университета Турку.
Авторы благодарят Юхани Кархумяки за приглашение в Университет Турку и плодотворные обсуждения предмета статьи.