Введение
1 Предварительные сведения. 17
1.1 Основы квантовых вычислений 17
1.2 Классические бинарные программы 22
1.2.1 Один раз читающие бинарные программы 26
1.2.2 Забывающие бинарные программы 27
2 Квантовые бинарные программы. Квантовое и классическое моделирование . 33
2.1 Определения и основные вычислительные свойства 33
2.2 Сложность моделирования 39
2.2.1 Классическое моделирование квантовых бинарных программ 39
2.2.2 Квантовое моделирование классических бинарных программ 47
3 Один раз читающие квантовые бинарные программы. Нижняя оценка сложности . 54
3.1 Нижняя оценка сложности вычисления булевой функции в квантовых бинарных программах 55
3.1.1 Доказательство нижней оценки сложности 56
3.2 Сложность реализации функции MODp в классических и квантовых бинарных программах 63
3.2.1 Сложность реализации функции MODp в детерминированных и вероятностных OBDD 64
3.2.2 Реализации функции MODp в квантовых OBDD. 68
4 Классические и квантовые конечные автоматы 73
4.1 Конечные автоматы 73
4.1.1 Детерминированный конечный автомат 73
4.1.2 Вероятностный конечный автомат 74
4.2 Квантовый конечный автомат 77
4.3 Сравнительная сложность квантовых и вероятностных конечных автоматов 80
4.3.1 Классическое моделирование квантовых автоматов. 80
4.3.2 Квантовое моделирование вероятностного автомата. 83
4.4 Нижняя оценка сложности распознавания языков квантовым конечным автоматом . 87
4.4.1 Доказательство нижней оценки сложности
Литература 94
