Введение
Глава 1. Квантовые вычисления 12
1.1. Квантовые вычисления 12
1.1.1. Краткая история теории квантовых вычислений 12
1.1.2. Общая информация о квантовых вычислениях 13
1.2. Квантовые алгоритмы 18
1.2.1. Общие сведения 18
1.2.2. Алгоритм поиска Гровера 18
1.2.3. Квантовое преобразование Фурье 20
1.2.4. Квантовый алгоритм нахождения периода функции 21
1.2.5. Алгоритм разложения числа на простые множители (Алгоритм Шора) 22
1.2.6. Квантовый алгоритм вычисления дискретного логарифма 23
1.2.7. Другие квантовые алгоритмы 24
1.3. Способы описания квантовых алгоритмов 25
1.3.1. Квантовые схемы 25
1.3.2. Квантовая машина Тьюринга 28
1.3.3. Сложность квантовых вычислений 29
1.3.4. Языки квантового программирования 30
1.4. Организация квантового компьютера 31
1.5. Реализация квантовых компьютеров 31
1.6. Квантовые компьютеры и информационная безопасность 32
1.7. Моделирование квантовых компьютеров 37
1.8. Выводы 38
Глава 2. Алгоритмы для имитации квантового компьютера 40
2.1. Квантовые регистры 40
2.2. Использование линейного массива для хранения вектора состояния квантового регистра 40
2.3. Использование связного списка для хранения вектора состояния квантового регистра 42
2.4. Использование структуры данных, основанной на графах для хранения вектора состояния квантового регистра 42
2.4.1. Алгебраические решающие диаграммы 42
2.4.2. Алгоритм построения алгебраических решающих диаграмм 45
2.4.3. Кодирование матриц и векторов 53
2.4.4. Квантовые преобразования 60
2.5. Алгоритмы для имитации квантового компьютера 74 t
2.5.1. Способ имитации квантового компьютера 74
2.5.2. Имитация квантовых преобразований 74
2.5.3. Имитация измерений квантовых регистров 75
2.6. Выводы 76
Глава 3. Реализация библиотеки функций 77
3.1. Выбор языка программирования 77
3.2. Реализация библиотеки функций для работы с алгебраическими решающими диаграммами 79
3.3. Реализация библиотеки функций для работы с векторами 86
3.4. Примеры эффективного применения алгебраических решающих диаграмм 88
3.5. Реализация библиотеки функций для моделирования квантового компьютера 91
3.6. Выводы 95
Глава 4. Язык для представления квантовых алгоритмов 97
4.1. Постановка задачи 97
4.2. Требования к языку 97
4.3. Описание языка 98
4.3.1. Структура языка 98
4.3.2. Стандартные преобразования 101
4.4. Примеры программ 103
4.4.1. Программа факторизации натурального числа с помощью квантового алгоритма Шора 103
4.5. Программа, реализующая алгоритм гровера 103
4.6. Интерпретатор 104
4.6.1. Общие сведения 104
4.6.2. Использование интерпретатора 105
4.7. Тестирование производительности 106
4.8. Выводы 113
Заключение и общие выводы 115
Литература 116
Приложение... 125
