Эффективные алгоритмы в модели квантовых ветвящихся программ

• Автор: Васильев, Александр Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Казань
• Количество страниц: 105 с. : ил.

Основные обозначения и понятия

1 Предварительные сведения

1.1 Детерминированные ветвящиеся программы

1.1.1 Определения

1.1.2 Связь с другими моделями вычислений

1.2 Вероятностные ветвящиеся программы

1.2.1 Определения

1.2.2 Уменьшение вероятности ошибки

1.2.3 Метод Fingerprinting

2 Квантовые ветвящиеся программы

2.1 Основы квантовых вычислений

2.2 Определение квантовых ветвящихся программ
2.3 Эффективные квантовые ветвящиеся программы
2.4 Схемное представление
2.5 Уменьшение вероятности ошибки
2.6 Связь с другими схемными моделями вычислений
3 Квантовый метод отпечатков
3.1 Квантовый метод отпечатков
3.1.1 Существование “хорошего” множества параметров

3.1.2 Конструктивные методы построения “хорошего” множества параметров
3.1.3 Варианты использования техники отпечатков
3.2 Вычисление функции MODm
3.2.1 Вычисление функции MOD'm
3.3 Квантовая OBDD для проверки равенства и сводимых к
ней функций
3.3.1 Понятие сводимости
3.3.2 Проверка равенства
3.3.3 Проверка симметрии
3.3.4 Проверка периодичности
3.3.5 Функция Semi-Simon
3.4 Квантовая OBDD для проверки перестановочности матрицы
3.5 Квантовая OBDD для задачи о скрытой подгруппе
3.5.1 Доказательство верхней оценки сложности
3.6 Вычисление функции голосования на одном кубите
3.7 Проблема равенства в коммуникационной модели SMP
3.8 Упрощенный метод отпечатков
4 Моделирование функций из NC1 квантовыми Zc-OBDD
4.1 Перестановочные ветвящиеся программы
4.2 Результаты Баррингтона
4.3 Моделирование NC1 квантовыми &-OBDD
Заключение
Литература

Основные обозначения и понятия
[а] - наименьшее целое число, не меньшее а.
[_aj - наибольшее целое число, не превосходящее а. log а = log2 а.
К - мощность конечного множества К.
Вп - множество булевых функций от п переменных.
Нормы вектора а — [а ad):
ІНІї = Е*=і аи
ii«ib = vS7w-
UT - транспонированная матрица U.
W = (UT)* - эрмитово сопряжение к U.
|а) - вектор-столбец (кет-вектор) а.
(6| = (|£>)т)* - вектор-строка (бра-вектор) Ь*.
(аЬ) - скалярное произведение |а) и |Ъ).
Iа) ® 1^) ~ тензорное (правое кронекерово) произведение векторов а, Ъ. Для |а) = (аь ..., ad)T и Ь) = (Ь1} ..., 6;)т |а) ® |Ь) = (афі, аф2, • • •, афи афъ • • •, adbi)T.
|а) |Ь) = |аЪ) = |а) ® |Ъ)
|о) (Ь = |о) ® {Ь

Глава 3. Квантовый метод отпечатков
можем записать это состояние в виде
Ш = |0>®]о8'|0)+7|0)®!обг|1) +
+ X} К) (аг 10} + А |1) )
1=2 4
ДЛЯ некоторых амплитуд 7, И А.
Т.е. описанное преобразование “собирает” амплитуды со всеми личными косинусами при нулевом базисном состоянии.
5. Состояние |"г/’з) измеряется в стандартном вычислительном баа и входной набор принимается, если результатом измерения явл ся базисное состояние |0)®1о®г |0). Вероятность такого исхода р
т.е. 1 для тех наборов, которые д отображает в 0 по модулю ограничена сверху константой е для остальных.