Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Васильев, Александр Валерьевич
01.01.09
Кандидатская
2009
Казань
105 с. : ил.
Стоимость:
499 руб.
Основные обозначения и понятия
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-
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 по модулю ограничена сверху константой е для остальных.
Название работы | Автор | Дата защиты |
---|---|---|
Дескриптивная сложность некоторых преобразований регулярных языков | Поваров, Григорий Андреевич | 2010 |
Теоретико-игровые модели формирования коалиционных структур | Степанов, Денис Сергеевич | 2011 |
Минимизация тени в слое булева куба | Башов, Максим Александрович | 2013 |