Отбор содержания обучения квантовым вычислениям бакалавров физико-математического образования

Т. С. Стефанова

ОТБОР СОДЕРЖАНИЯ ОБУЧЕНИЯ КВАНТОВЫМ ВЫЧИСЛЕНИЯМ БАКАЛАВРОВ ФИЗИКО-МАТЕМАТИЧЕСКОГО ОБРАЗОВАНИЯ

Работа представлена кафедрой информатики.

Научный руководитель - доктор педагогических наук, профессор М. В. Швецкий

Статья описывает подход к отбору содержания обучения квантовым вычислениям с точки зрения квантово-механических моделей, что, возможно, может привести к формированию у обучаемых нефундаментальной трактовки понятия «вычислимость».

The article describes the approach to selecting the content of quantum computing training in the context of quantum-mechanical models, which may probably result in a nonfundamental interpretation of

the concept «computability».

В данной работе мы будем существенно опираться на эмпирически установленный принцип неисчерпаемости Природы1:

Природа имеет средства для осуществления любой корректно сформулированной человеком задачи.

Другими словами, мы будем «смотреть» на понятие «вычислимость» через призму моделей реальности, что, в конечном счете, должно привести к изменению содержания обучения, заключающееся в появлении понятия «неклассические вычислительные модели».

Квантовые вычисления в настоящее время относятся именно к неклассическим вычислительным моделям. Квантовые вычисления являются большим, чем просто более быстрой и миниатюрной технологией реализации машин Тьюринга: квантовые вычисления являются принципиально другим способом использования природы.

Ясно, что фраза «Природа вычисляет» является эллипсисом: точнее говорить, что мы находим новые вычислительные модели в биолого-химических и квантово-механических моделях.

Важно отметить, что квантовые вычисления требуют глубокого понимания фун-

даментальных законов физики, а также знания вопросов, относящихся к математике (функциональный анализ конечномерных унитарных пространств). В силу этого количество проблем при отборе содержания обучения значительно увеличиваются.

С учетом данных особенностей попытаемся осуществить отбор содержания обучения квантовым вычислениям. Для этого воспользуемся структурой, построенной на основе идей, которые предложили М. Нильсен и И.Чанг2.

Квантовые схемы:

• однокубитовые;

• управляемые многокубитовые.

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

• плотное кодирование, телепортация;

Квантовый параллелизм:

• алгоритм Дойча;

• алгоритм Дойча-Джозса;

• классификация квантовых алгоритмов;

• дискретное преобразование Фурье;

• быстрое преобразование Фурье;

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

• квантовое определение собственного числа;

• квантовое нахождение порядка;

• квантовая факторизация;

• квантовое нахождение периода;

• квантовое нахождение дискретного логарифма.

Теперь рассмотрим содержание обучения квантовым вычислениям.

В зависимости от уровня начальных знаний студентов, целей обучения и продолжительности курса может быть выделена следующая последовательность тем.

1. Элементы линейной алгебры в обозначениях квантовой механики.

Основные понятия: матрицы Паули, матрицы Дирака, блочно-диагональная матрица, прямая сумма матриц, сопряженная матрица, эрмитова матрица, нормальная матрица, унитарная матрица; векторное (линейное) пространство; кет-вектор, бра-вектор; конечномерное линейное пространство; скалярное произведение векторов, неравенство Буняковского-Коши-Шварца, ортогональные векторы, ортонормирован-ный набор векторов; ортогонализация Гра-ма-Шмидта; внешнее произведение векторов; евклидово пространство, унитарное пространство, гильбертово пространство; тензорное произведение пространств, кро-некерово произведение.

2. Линейные операторы в конечномерных векторных пространствах. Постулаты квантовой механики.

Основные понятия: линейные операторы , тождественный оператор, нулевой оператор; матричное представление линейных операторов, представление линейных операторов с помощью внешнего произведения; собственные векторы линейного оператора, собственные значения линейного оператора; сопряженные операторы, эрмитовы операторы, унитарные операторы; проекторы; неотрицательно определенные операторы; функции, определенные на операторах; коммутатор операторов, антикоммутатор операторов; полярное разложение оператора; разложение оператора по сингулярным числам; постулаты квантовой механики.

3. Квантовые вычисления, квантовые схемы, однокубитовые квантовые элементы.

Основные понятия: квантовый компьютер, квантовый клеточный автомат; кубит; состояния вычислительного базиса, суперпозиция состояний; физические модели кубита, геометрическая модель кубита; квантовые вычисления, квантовые схемы; квантовые логические однокубитовые элементы (гейты); Z-Y - разложение однокубито-вого унитарного оператора; представление однокубитовых квантовых вентилей с помощью внешнего произведения.

4. Обратимые классические логические элементы.

Основные понятия: классический логический элемент; классические логические элементы на нескольких битах: NOT, AND, OR, XOR, NAND, NOR; обратимый логический элемент; обратимые классические элементы: CNOT, SWAP, элемент Тоффо-ли, элемент Фредкина, FANOUT; моделирование классических логических элементов с помощью элемента Тоффоли; обратимые классические элементы, реализующие одноразрядное сложение: сумматор без переноса, полусумматор с переносом, сумматор.

5. Многокубитовые квантовые элементы. Управляемые квантовые элементы.

Основные понятия: квантовый регистр; квантовая схема в базисе; квантовый элемент «управляемый U»; управляемые квантовые логические элементы на нескольких кубитах: CNOT, элемент Тоффоли, элемент Фредкина, SWAP; квантовый элемент «управляемый нулем U».

6. Измерение кубитов в квантовых системах.

Основные понятия: измерение кубита; операция «измерение» в базисах, отличных от вычислительного базиса; квантовая операция «измерение»; измерение кубитов в состоянии Белла.

7. Запутанные квантовые состояния.

Основные понятия: теорема неклониру-

емости неизвестных квантовых состояний;

квантовая схема, порождающая состояния Белла (ЭПР-состояния); запутанные квантовые состояния; плотное кодирование; квантовая телепортация.

8. Квантовый параллелизм.

Основные понятия: преобразование Уол-

ша-Адамара; квантовый параллелизм; преобразование Uf; квантовая интерференция; алгоритм Дойча; алгоритм Дойча-Джозса.

9. Дискретное преобразование Фурье. Квантовое преобразование Фурье.

Основные понятия: дискретное преобразование Фурье, обратное дискретное преобразование Фурье; быстрое преобра-зование Фурье; квантовое преобразование Фурье; обратное квантовое преобразование Фурье; квантовая схема для квантового преобразования Фурье; матрица Фурье; квантовое вейвлет-преобразование Хаара.

10. Квантовые алгоритмы, основанные на преобразовании Фурье.

Основные понятия: классификация квантовых алгоритмов; квантовый алгоритм нахождения периода функции.

Квантовые вычисления, рассмотренные нами в рамках содержания обучения, дают идею о возможных вариантах моделирова-ния квантового компьютера на «обычном» компьютере.

Данный отбор содержания обучения предполагает выбор методов, форм и средств обучения.

В качестве основных методов обучения будем использовать метод целесообразно подобранных задач и метод демонстрационных примеров.

Основными формами обучения являются лекции и практические занятия (лабораторные работы, семинары).

Будем считать, что основными средствами обучения для всех тем являются математические пакеты (Maple, MathLAB,

MathCad) и языки программирования LISP и С.

В качестве контроля умений и навыков студентов будем использовать контрольные работы, сочетающие работу за компьютером с выполнением математических вычислений на бумаге.

В заключение отметим, что:

1) идея квантовых вычислений позволяет дать толчок к построению компьютеров с принципиально новой архитектурой, основанной на природном параллелизме;

2) появляется возможность создать новый метаязык квантовых вычислений;

3) несмотря на возможность применения классического компьютера для моделирования квантового компьютера, эффективное осуществление такого моделирования невозможно, т. е. квантовые компьютеры существенно превосходят по скорости классические компьютеры;

4) квантовые вычисления внесли фундаментальный вклад в развитие следующих тем: информатика, теория информации, криптография;

5) происходит формирование новой парадигмы, которую будем называть квантовой парадигмой вычислений;

6) квантовые вычисления учат думать о вычислениях физически, и этот подход открывает много новых возможностей в области обработки информации;

7) квантовая теория вычисления должна быть неотъемлемой частью мировоззрения любого человека, ищущего фундаментального понимания реальности.

Представленное в данной статье содержание обучения квантовым вычислениям использовалось в рамках курса «Представление знаний в информационных системах» для обучения студентов четвертого курса факультета информационных технологий РГПУ им. А. И. Герцена в 2007 г.

ПРИМЕЧАНИЯ

1 Воронов В. К., Подоплелов А. В. Современная физика. М.: КомКнига, 2005. С. 403.

2 Нильсен Н., Чанг И. Квантовые вычисления и квантовая информация/ Пер. с англ. М.: Мир, 2006. С. 8.