Введение
1 Предварительные сведения 15
1.1 Детерминированные ветвящиеся программы 15
1.1.1 Определения 15
1.1.2 Связь с другими моделями вычислений 17
1.2 Вероятностные ветвящиеся программы 19
1.2.1 Определения 19
1.2.2 Уменьшение вероятности ошибки 20
1.2.3 Метод Fingerprinting 21
2 Квантовые ветвящиеся программы 23
2.1 Основы квантовых вычислений 23
2.2 Определение квантовых ветвящихся программ 32
2.3 Эффективные квантовые ветвящиеся программы 35
2.4 Схемное представление 36
2.5 Уменьшение вероятности ошибки 37
2.6 Связь с другими схемными моделями вычислений . 40
3 Квантовый метод отпечатков 42
3.1 Квантовый метод отпечатков 42
3.1.1 Существование "хорошего" множества параметров 44
3.1.2 Конструктивные методы построения "хорошего" множества параметров 46
3.1.3 Варианты использования техники отпечатков . 48
3.2 Вычисление функции MODm 52
3.2.1 Вычисление функции MODm 55
3.3 Квантовая OBDD для проверки равенства и сводимых к ней функций 57
3.3.1 Понятие сводимости 57
3.3.2 Проверка равенства 58
3.3.3 Проверка, симметрии 61
3.3.4 Проверка периодичности 62
3.3.5 Функция Semi-Simon 64
3.4 Квантовая OBDD для проверки перестановочности матрицы 65
3.5 Квантовая OBDD для задачи о скрытой подгруппе . 69
3.5.1 Доказательство верхней оценки сложности . 71
3.6 Вычисление функции голосования на одном кубите . 74
3.7 Проблема равенства в коммуникационной модели SMP 76
3.8 Упрощенный метод отпечатков 80
4 Моделирование функций из NC1 квантовыми fc-OBDD 84
4.1 Перестановочные ветвящиеся программы 85
4.2 Результаты Баррингтона 87
4.3 Моделирование NC1 квантовыми &-OBDD 92
Заключение 96
Литература 99
