Введение 3
Глава 1 Математическая модель квантовых вычислений 6
1.1 Кубит 6
1.2 Базисы 7
1.3 Измерение кубитов 8
1.4 Система кубитов 9
1.5 Измерение система кубитов 9
1.4 Состояния Белла 10
1.6 Система из n кубитов 10
Глава 2 Эволюция квантовой системы 13
2.1 Операторы 13
2.2 Схемы операторов 13
Глава 3 Квантовые алгоритмы 18
3.1 Задача Дойча 18
3.2 Задача Дойча-Джойза 23
3.3 Вывод 24
Заключение 25
Условные обозначения 26
Список литературы 27
В данной работе поэтапно строится математическая модель квантовых вычислений, рассматриваются квантовые алгоритмы и сравниваются с классическими алгоритмами, решающими те же задачи. Определим два важнейших в данной работе понятия:
• Вычисление - конечный по времени физический процесс с фиксированным набором состояний, меняющий состояние системы.
• Информация - интерпретация состояния физической системы.
Такой материалистический подход позволяет количественно измерять информацию и вычисления.
• Количество вычислений - это количество смен состояний физической системы.
Количество информации найдём, используя формулу Шеннона:
I = “^Pi*log2(Pi),^Pi = 1,
где Pi — вероятность того, что система находится в состоянии i [1].
Количество информации измеряется в битах. Если система с равной вероятностью может находиться в любом из возможных состояний, то количество информации оценивается следующим образом:
1 = —^11О02 (1) = 1О02(П)
i
Вычислительная система характеризуется:
• емкостью (кол-во состояний);
• скоростью смены состояний;
• универсальностью (какие задачи может решать система).
Приведём пример вычислительной физической системы, имеющей один бит информации.
Двигатель Сцилларда представляет сосуд,
подвижными поршнями слева и справа, в центре перегородка, которую можно поднимать и опускать.
одной молекулой идеального газа. Если молекула находится слева от перегородки, то такое состояние кодируется нулём, справа - единицей. Вычисление в данном случае - перемещение молекулы из одной области в другую с помощью подвижных поршней и перегородки [2]. Простейшие физические системы, несущие минимальную квантовую информацию: атом водорода, поляризация фотона.
Атом водорода может находиться в обычном и возбужденном состояниях. Оба этих состояния - решения волновой функции, описывающей состояние электрона. Главное отличие такой системы заключается в том, что состояние электрона также может описываться суперпозицией базисных состояний [3]. По аналогии с классическими системами вводится понятие минимальной квантовой информации - кубит. Кубит описывает простейшее содержательное квантовое состояние.
В данной работе построена модель квантовых чисел. Построен квантовый алгоритм, решающий задачу Дойча. Приведена схема алгоритма Дойча-Джойза. Оценена их сложность. Произведено сравнение сложности квантовых алгоритмов со сложностью классических алгоритмов.
