Сравнительная сложность квантовых и классических моделей вычислений

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

Основные обозначения, используемые в работе

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

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

1.2 Классические бинарные программы

1.2.1 Один раз читающие бинарные программы

1.2.2 Забывающие бинарные программы

2 Квантовые бинарные программы. Квантовое и классическое моделирование

2.1 Определения и основные вычислительные свойства

2.2 Сложность моделирования

2.2.1 Классическое моделирование квантовых бинарных программ

2.2.2 Квантовое моделирование классических бинарных программ

3 Один раз читающие квантовые бинарные программы.
. Нижняя оценка сложности
3.1 Нижняя оценка сложности вычисления булевой функции
в квантовых бинарных программах
3.1.1 Доказательство нижней оценки сложности

3.2 Сложность реализации функции МОПр в классических
и квантовых бинарных программах
3.2.1 Сложность реализации функции МООр в детерминированных и вероятностных ОЕЮО
3.2.2 Реализации функции МОВр в квантовых ОВОО
4 Классические и квантовые конечные автоматы
4.1 Конечные автоматы
4.1.1 Детерминированный конечный автомат
4.1.2 Вероятностный конечный автомат
4.2 Квантовый конечный автомат
4.3 Сравнительная сложность квантовых и вероятностных конечных автоматов
4.3.1 Классическое моделирование квантовых автоматов
4.3.2 Квантовое моделирование вероятностного автомата
4.4 Нижняя оценка сложности распознавания языков квантовым конечным автоматом
4.4.1 Доказательство нижней оценки сложности
Литература

Основные обозначения и понятия, используемые в работе.
|aj - наибольшее целое, не большее а. log а = log2 а.
|Л| - мощность конечного множества А.
Вп - множество двоичных слов (наборов) длины п.
Е - непустое конечное множество символов, которое будем называть алфавитом.
■ Е* - множество всех слов над алфавитом Е, включающее пустое слово
Произвольное подмножество LCS* называется языком над алфави-ш том Е.
I - единичная матрица.
Вектор р = (pi pn) - стохастический, если 0 < р,- < 1(г
1 п), и £"=1рг
Матрица М = [m,j]-j=1 - стохастическая, если 0 < m,-j < 1 (i,j
■ ■ 1,••■,**) и Ej=imio = 1(г=1 гг)
Матрица М = [тг-^]";-=1 - стохастическая по столбцам, если 0 < miyj < 1 (г, j = 1 п) и 1 mij = 1 С? = 1, • • •, п).
а®Ь, А® В - тензорное (правое кронекерово) произведение векторов а, b и матриц А, В, соответственно, определенные следующим образом.
Для а= (at ad) и 6 = (6Ь...,bt) a®b = (aibhaib2 аф/, a2bi adbi).

Бинарные программы. Квантовое и классическое моделирование

Замечание 2.3 Отметим, что на каждом шаге после промежуточного измерения состояние квантовой бинарной программы - это смешанное состояние (mixture) {pk, где pk - вероятность нахождения
квантовой системы в чистом состоянии 11рк)- Традиционно в теории квантовых вычислений смешанное состояние описывается при помощи матрицы плотности р (см., например [10]). В работе из технических соображений конструктивного описания квантовой бинарной программы мы фактически не используем представление смешаного состояния при помощи матрицы плотности.
Теорема 2.3 (Квантовое моделирование) Пусть функция / вычислима вероятностной забывающей бинарной программой (d,l)-PBP Р. Тогда она вычислима много раз измеряемой квантовой бинарной программой (d,l)-MM-QBP Q такой, что
Ргасс(ё) = РгаЛ°') для всех а € {0,1}"
Доказательство: Пусть (d, l)-PBP Р - забывающая вероятностная
бинарная программа, вычисляющая функцию / (напомним, что, согласно Свойствам 2 и 3, любая вероятностная бинарная программа может быть преобразована в забывающую не более чем с полиномиальным увеличением сложности). При этом каждый уровень j (j = 0,— 1) программы Р
• либо детерминированный уровень, где в каждой вершине тестируется булева переменная X{j+1, и, в зависимости от значения считанной переменной, осуществляется детерминированный переход из этой вершины уровня j в некоторую вершину уровня j + 1.
• либо вероятностный уровень, где из каждой вершины с вероятностью 1/2 осуществляется переход в одну из двух вершин уровня 3 + 1.