Алгоритмическое и программное обеспечение для моделирования квантового компьютера

• Автор: Ключарёв, Пётр Георгиевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 155 с. : ил.

Оглавление

ВВЕДЕНИЕ

ГЛАВА 1. КВАНТОВЫЕ ВЫЧИСЛЕНИЯ

1.1. Квантовые вычисления

1.1.1. Краткая история теории квантовых вычислений

1.1.2. Общая информация о квантовых вычислениях

1.2. Квантовые алгоритмы

1.2.1. Общие сведения

1.2.2. Алгоритм поиска Гровера

1.2.3. Квантовое преобразование Фурье

1.2.4. Квантовый алгоритм нахождения периода
функции
1.2.5. Алгоритм разложения числа на простые
множители (Алгоритм Шора)
1.2.6. Квантовый алгоритм вычисления дискретного
логарифма
1.2.7. Другие квантовые алгоритмы
1.3. Способы описания квантовых алгоритмов
1.3.1. Квантовые схемы
1.3.2. Квантовая машина Тьюринга
1.3.3. Сложность квантовых вычислений
1.3.4. Языки квантового программирования
1.4. Организация квантового компьютера
1.5. Реализация квантовых компьютеров
1.6. Квантовые компьютеры и информационная безопасность
1.7. Моделирование квантовых компьютеров

сто.
1.8. Выводы
ГЛАВА 2. АЛГОРИТМЫ ДЛЯ ИМИТАЦИИ КВАНТОВОГО КОМПЬЮТЕРА
2.1. Квантовые регистры
2.2. Использование линейного массива для хранения вектора состояния квантового регистра
2.3. Использование связного списка для хранения вектора состояния квантового регистра
2.4. Использование структуры данных, основанной на графах для хранения вектора состояния квантового регистра
2.4.1. Алгебраические решающие диаграммы
2.4.2. Алгоритм построения алгебраических решающих диаграмм
2.4.3. Кодирование матриц и векторов
2.4.4. Квантовые преобразования
2.5. Алгоритмы для имитации квантового компьютера
2.5.1. Способ имитации квантового компьютера
2.5.2. Имитация квантовых преобразований
2.5.3. Имитация измерений квантовых регистров
2.6. Выводы
ГЛАВА 3. РЕАЛИЗАЦИЯ БИБЛИОТЕКИ ФУНКЦИЙ
3.1. Выбор языка программирования
3.2. Реализация библиотеки функций для работы с алгебраическими решающими диаграммами
3.3. Реализация библиотеки функций для работы с векторами
3.4. Примеры эффективного применения алгебраических решающих диаграмм

сто.
3.5. Реализация библиотеки функций для моделирования
квантового компьютера
3.6. Выводы
ГЛАВА 4. ЯЗЫК ДЛЯ ПРЕДСТАВЛЕНИЯ КВАНТОВЫХ
АЛГОРИТМОВ
4.1. Постановка задачи
4.2. Требования к языку
4.3. Описание языка
4.3.1. Структура языка
4.3.2. Стандартные преобразования
4.4. Примеры программ
4.4.1. Программа факторизации натурального числа с
помощью квантового алгоритма Шора
4.5. Программа, реализующая алгоритм Гровера
4.6. Интерпретатор
4.6.1. Общие сведения
4.6.2. Использование интерпретатора
4.7. Тестирование производительности
4.8. Выводы
ЗАКЛЮЧЕНИЕ И ОБЩИЕ ВЫВОДЫ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ. НАИБОЛЕЕ ВАЖНЫЕ ИСХОДНЫЕ КОДЫ

сможет перехватить информацию. В литературе методы передачи ключей по квантовому каналу, называют квантово-криптографическими.
Квантовой криптографии посвящен ряд работ, в частности, [35, 45, 51, 65, 93] и др. В настоящее время существует сеть квантовой передачи ключей, соединяющая не менее 10 точек на территории США и действующая в интересах американских вооруженных сил [65, 66]. Кроме того, ряд компаний уже продает коммерческие образцы оборудования для квантового распространения ключей. В качестве примера можно привести швейыарскую компанию кКЗиапйцие.
Существуют различные протоколы квантового распространения ключей. Подробное их рассмотрение выходит далеко за рамки настоящей диссертации. Для полноты обзора приведем лишь один протокол квантового распространения ключей, рассмотренный в книге [1].
Итак, пусть у нас есть канал связи, по которому можно передавать квантовые биты. Два пользователя, А и В, хотят договориться об общем ключе для шифрования информации, передаваемой по открытому каналу.
Пользователь А может кодировать информацию в различных базисах. Определим два базиса: в первом 0 кодируется в |о), а 1 кодируется в |1), во
втором базисе: 0 кодируется в —у=(|о) —11)), а 1 -в -|=(|о) + |1)).
л/2 л/2
Протокол квантового распространения ключей заключается в следующем:
1. А случайно выбирает битовую строку.
2. А случайно выбирает последовательность базисов, длиной равной битовой строке.
3. А кодирует битовую строку, используя соответствующие базисы, и передает закодированную битовую строку В.
4. В принимает квантовые биты от А и измеряет их, случайно выбирая базисы для измерения.