View source for BSc: B1.V.DV.03.04 MFAI 2024 Mathematical foundations of quantum computing

<span id="теория-вероятностей"></span>
= '''Теория вероятностей''' =

<blockquote>'''Квалификация выпускника''': бакалавр

'''Направление подготовки''': 09.03.01 Информатика и вычислительная техника

'''Направленность (профиль) образовательной программы''': Математические основы искусственного интеллекта

'''Программу разработал(а)''': Фролов А. Н., Райгородский А. М., Ильинский Д. Г.
</blockquote>

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

== 2. Перечень планируемых результатов обучения ==
: '''Целью освоения дисциплины''' является  подготовка специалистов в области квантовых вычислений, которые бы были готовы применять квантовые вычисления для практических прикладных задачах.

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

=== Общая характеристика результата обучения по дисциплине ===
: '''Знания:''' в процессе обучения будут получены знания математических оснований квантовых вычислений. Изучены теоретические основы квантовых компьютеров и особенностях алгоритмов, основанных на моделях квантовых компьютеров.

: '''Умения:''' сформированы умения анализа областей применения алгоритмов для квантовых вычислений и теоретические ограничения, присущие квантовым вычислениям основанные на математических  моделях  квантовых алгоритмов.

: '''Навыки (владения):''' при освоении дисциплины будет сформировано владение навыками выбора квантовых или алгоритмов для решения специальных прикладных задач. Слушатели получат навыки определения вероятностных параметров достоверности и точности полученных результатов при использовании квантовых алгоритмов. 

== 3. Структура и содержание дисциплины ==
{| class="wikitable" style="width:70%; vertical-align:middle; text-align:center; background-color:#F8F9FA; color:#202122;"
|- style="background-color:#EAECF0; color:#202122; font-weight:bold;"
| style="width:10%" | №<br>п/п
| style="width:30%" | Наименование раздела <br> дисциплины
| style="width:60%" | Содержание дисциплины по темам
|-
| 1. || Введение в квантовые вычисления
| style="text-align:left;" |
Обзор классических вычислений и их ограничений
Введение в квантовую механику и кубиты
Квантовые вентили и квантовые схемы
Линейная алгебра для квантовых вычислений
|-
| 2. || Комплексные числа и комплексные векторные пространства
| style="text-align:left;" |
Обозначения Дирака и бра-кет
Квантовые состояния и суперпозиция
Унитарные преобразования и квантовые вентили
|-
| 3. || Квантовые алгоритмы
| style="text-align:left;" |
Квантовое преобразование Фурье
Алгоритмы поиска, алгоритм Гровера
Алгоритм оценки фазы
|-
| 4. || Квантовая запутанность и квантовая телепортация
| style="text-align:left;" |
Запутанные состояния и состояния Белла
Протокол квантовой телепортации
Применение запутанности в квантовой коммуникации
|-
| 5. || Квантовая коррекция ошибок
| style="text-align:left;" |
Основы квантовой коррекции ошибок
Модели квантовых ошибок и коды обнаружения ошибок
Квантовые коды коррекции ошибок
|-
| 6. || Квантовое моделирование
| style="text-align:left;" |
Введение в квантовые симуляторы
Моделирование гамильтоновых процессов
Применение квантового моделирования в химии и физике
|-
| 7. || Теория квантовой сложности
| style="text-align:left;" |
Квантовый оракул и квантовые алгоритмы как задачи принятия решений
Квантовая вычислительная сложность и мощь квантовых вычислений
|}

== 4. Методические и оценочные материалы ==
'''Задания для практических занятий:</b>'''
{| class="wikitable" style="width:70%; vertical-align:middle; text-align:center; background-color:#F8F9FA; color:#202122;"
|- style="background-color:#EAECF0; color:#202122; font-weight:bold;"
| style="width:10%" | №<br>п/п
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
| style="width:60%" | Перечень рассматриваемых тем (вопросов)
|-
| 1. || Введение в квантовые вычисления
| style="text-align:left;" |
Объясните, почему классические компьютеры ограничены в своих возможностях моделирования квантовых систем.
Выведите зависящее от времени уравнение Шредингера.
|-
| 2. || Комплексные числа и комплексные векторные пространства
| style="text-align:left;" |
Покажите, что состояние кубита может быть представлено в виде вектора в двумерном комплексном векторном пространстве.
Докажите, что два кубита могут быть запутаны, и объясните, что это значит.
Докажите, что любая унитарная операция над n кубитами может быть представлена в виде матрицы 2 ^ n x 2 ^ n.
Докажите, что любая эрмитова матрица может быть диагонализирована унитарной матрицей.
Покажите, что любая унитарная матрица может быть выражена как экспонента эрмитовой матрицы.
|-
| 3. || Квантовые алгоритмы
| style="text-align:left;" |
Реализуйте базовые квантовые элементы (такие как NOT, CNOT, Адамара и фазовые элементы), используя матричные представления.
Разработайте простую квантовую схему, реализующую алгоритм Дойча.
Покажите, что алгоритм Гровера может найти отмеченный элемент в несортированной базе данных за O (√N) шагов.
Докажите, что алгоритм Шора может умножать большие целые числа экспоненциально быстрее, чем классические алгоритмы.
|-
| 4. || Квантовая запутанность и квантовая телепортация
| style="text-align:left;" |
Объясните концепцию суперпозиции и то, чем она отличается от классических распределений вероятностей.
Докажите, что любые два чистых состояния ортогональны тогда и только тогда, когда их нельзя с уверенностью отличить никаким измерением.
|-
| 5. || Квантовая коррекция ошибок
| style="text-align:left;" |
Реализуйте код повторения с тремя кубитами, который кодирует один логический кубит в три физических кубита. Продемонстрируйте, как этот код может обнаруживать и исправлять ошибки с одним кубитом.
Реализуйте алгоритм Шора, который кодирует один логический кубит в девять физических кубитов. Продемонстрируйте, как этот код может обнаруживать и исправлять любую ошибку, связанную с одним кубитом.
Распространение ошибок в объединенных кодах: Проанализируйте, как ошибки могут распространяться по нескольким уровням объединенных кодов.
Рассчитайте вероятность того, что ошибка останется необнаруженной после нескольких циклов исправления ошибок.
|-
| 6. || Квантовое моделирование
| style="text-align:left;" |
Реализуйте моделирование системы со спином 1/2 с использованием квантового компьютера. Продемонстрируйте, как подготавливать начальные состояния, эволюционировать в соответствии с гамильтонианом и измерять наблюдаемые величины.

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

Моделируйте многочастичные системы, такие как модель Изинга или модель Гейзенберга, с помощью квантового компьютера. Сравните результаты с классическим моделированием и проанализируйте поведение масштабирования.
|}

'''Текущий контроль успеваемости обучающихся по дисциплине:'''
{| class="wikitable" style="width:70%; vertical-align:middle; text-align:center; background-color:#F8F9FA; color:#202122;"
|- style="background-color:#EAECF0; color:#202122; font-weight:bold;"
| style="width:5%" | №<br>п/п
| style="width:20%" | Наименование раздела<br>дисциплины
| style="width:25%" | Форма текущего контроля
| style="width:50%" | Материалы текущего контроля
|-
| 1. || Квантовая механика и кубиты || ''Письменное тестирование''
| style="text-align:left;" |
Объясните разницу между классическими и квантовыми битами.
Запишите представления вектора состояния и матрицы плотности для одного кубита.
Вычислите ожидаемое значение наблюдаемой величины относительно данного состояния.
Объясните, что такое суперпозиция и запутанность, и приведите примеры.
|-
| 2. || Квантовые вентили и схемы || ''Письменный тест''
| style="text-align:left;" |
Запишите матричное представление общих однокубитных вентилей, таких как Адамар, Паули-X, Паули-Y и Паули-Z.
Запишите матричное представление общих двухкубитных вентилей, таких как CNOT.
Проектируйте и реализуйте простые квантовые схемы с использованием вентилей и измерений.
Объясните, что такое управляемый вентиль, и приведите пример
|-
| 3. || Линейная алгебра и векторные пространства || ''Письменный тест''
| style="text-align:left;" |
Докажите, что два неортогональных вектора в гильбертовом пространстве можно сделать ортогональными с помощью соответствующего преобразования.
Объясните, что такое внутреннее произведение, и приведите пример.
Вычислите собственные значения и собственные векторы простых матриц.
Докажите, что любая унитарная матрица может быть выражена как экспонента антиэрмитовой матрицы.
|-
| 4. || Квантовая коррекция ошибок и квантовые коды || ''Устный опрос''
| style="text-align:left;" |
Объясните, что такое код квантовой коррекции ошибок, и приведите пример.
Опишите, как 9-кубитный код Шора может исправлять ошибки в один кубит.
Объясните, что такое код стабилизации, и приведите пример.
Докажите, что код стабилизатора может обнаруживать и исправлять ошибки с точностью до своего расстояния.
|-
| 5. || Квантовые алгоритмы и симуляция || ''Домашнее задание и устный опрос''
| style="text-align:left;" |
Напишите программу и объясните, как работает алгоритм Шора, и приведите пример.
Напишите программу и объясните, что такое алгоритм Гровера, и приведите пример.
Опишите, как работает квантовый симулятор, и приведите пример
|}

'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
{| class="wikitable" style="width:70%; vertical-align:middle; text-align:center; background-color:#F8F9FA; color:#202122;"
|- style="background-color:#EAECF0; color:#202122; font-weight:bold;"
| style="width:10%" | №<br>п/п
| style="width:25%" | Наименование <br> раздела дисциплины
| style="width:65%" | Вопросы
|-
| 1. || Квантовая механика и кубиты:
| style="text-align:left;" |
Что такое кубит? Чем он отличается от классического бита?
Что такое суперпозиция? Как это представлено математически?
Что такое запутанность? Как это представлено математически?
В чем разница между чистым состоянием и смешанным состоянием? Как они представлены математически?
|-
| 2. || Квантовые элементы и схемы:
| style="text-align:left;" |
Что такое унитарная операция? Как это представлено математически?
Каково матричное представление обычных однокубитных вентилей, таких как Адамар, Паули-X, Паули-Y и Паули-Z?
Каково матричное представление обычных двухкубитных вентилей, таких как CNOT и SWAP?
Что такое управляемый вентиль? Как это представлено математически?
|-
| 3. || Линейная алгебра и векторные пространства:
| style="text-align:left;" |
Что такое внутреннее произведение? Как это представлено математически?
Что такое ортонормированный базис? Как он связан с матричными представлениями?
Что такое собственное значение и собственный вектор? Как они связаны с матричными представлениями?
Что такое унитарная матрица? Как это связано с квантовыми элементами?
|-
| 4. || Квантовая коррекция ошибок и квантовые коды:
| style="text-align:left;" |
Что такое квантовый код коррекции ошибок? Как он работает?
Что такое 9-кубитный код Шора? Как он исправляет однокубитные ошибки?
Что такое код-стабилизатор? Как он работает?
Каково расстояние между кодами? Как это связано с возможностью исправления ошибок?
|-
| 5. || Квантовые алгоритмы и моделирование:
| style="text-align:left;" |
Что такое алгоритм Шора? Как он работает? Каковы его приложения?
Что такое алгоритм Гровера? Как он работает? Каковы его приложения?
Что такое квантовый симулятор? Как он работает? Каковы его приложения?
Что такое универсальный набор вентилей? Как это связано с реализацией квантовых алгоритмов?
|}

'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''

Квантовая механика и кубиты (20 баллов):
* Опишите разницу между классическими и квантовыми битами. (5 баллов)
* Запишите представления вектора состояния и матрицы плотности одного кубита. (5 баллов)
* Вычислите ожидаемое значение наблюдаемой величины относительно данного состояния. (5 баллов)
* Объясните, что такое суперпозиция и запутанность, и приведите примеры. (5 баллов)
Квантовые элементы и схемы (20 баллов):
* Запишите матричное представление обычных однокубитных вентилей, таких как Адамар, Паули-X, Паули-Y и Паули-Z. (5 баллов)
* Запишите матричное представление обычных двухкубитных вентилей, таких как CNOT и SWAP. (5 баллов)
* Спроектируйте и реализуйте простую квантовую схему, которая генерирует запутанное состояние. (5 баллов)
* Объясните, что такое управляемый вентиль, и приведите пример. (5 баллов)
Линейная алгебра и векторные пространства (20 баллов):
* Докажите, что два неортогональных вектора в гильбертовом пространстве можно сделать ортогональными с помощью соответствующего преобразования. (5 баллов)
* Объясните, что такое внутреннее произведение, и приведите пример. (5 баллов)
* Вычислите собственные значения и векторы матрицы. (5 баллов)
* Докажите, что любая унитарная матрица может быть выражена как экспонента антиэрмитовой матрицы. (5 баллов)
Квантовая коррекция ошибок и квантовые коды (20 баллов):
* Объясните, что такое квантовый код коррекции ошибок, и приведите пример. (5 баллов)
* Опишите, как 9-кубитный код Шора может исправлять ошибки в один кубит. (5 баллов)
* Объясните, что такое код стабилизации, и приведите пример. (5 баллов)
* Докажите, что код стабилизатора может обнаруживать и исправлять ошибки на расстоянии. (5 баллов)
Квантовые алгоритмы и симуляция (20 баллов):
* Опишите, как работает алгоритм Шора, и приведите пример. (5 баллов)
* Объясните, что такое алгоритм Гровера, и приведите пример. (5 баллов)
* Опишите, как работает квантовый симулятор, и приведите пример. (5 баллов)
* Объясните, что такое универсальный набор шлюзов, и приведите пример. (5 баллов)
Квантовые протоколы и криптография (20 баллов):
* Объясните, что такое BB84, и опишите, как это работает. (5 баллов)
* Опишите, как протокол квантового распределения ключей может быть использован для обеспечения безопасности связи. (5 баллов)
* Объясните, что такое квантовая телепортация, и опишите, как это работает. (5 баллов)
* Объясните, что такое квантовые деньги, и опишите, как это работает. (5 баллов)

=== Перечень учебно-методического обеспечения дисциплины ===
Список основной литературы:
# Перри Райли.  Элементарное введение в квантовые вычисления. Изд. Интеллект  2018 
# Химено-Сеговиа, Хэрриган, Джонстон. Программирование квантовых компьютеров. Базовые алгоритмы и примеры кода. Издю Питер, 2021
# С. Сысоев, Введение в квантовые вычисления. Квантовые алгоритмы. Изд. СПБ университет, 2019. 

Список дополнительной литературы:
# А. Ю. Китаев, Квантовые вычисления: алгоритмы и исправление ошибок, УМН, 1997, том 52, выпуск 6, 53–112

=== Методические указания для обучающихся по освоению дисциплины ===
{| class="wikitable" style="width:80%; vertical-align:middle; background-color:#F8F9FA; color:#202122;"
|- style="text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
| style="width:20%" | Вид учебных<br>занятий/деятельности
| style="width:80%" | Деятельность обучающегося
|- 
| style="text-align:center;" | Лекция
| style="text-align:left;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
|-
| style="text-align:center;" | Практическое (семинарское) занятие
| style="text-align:left;" | При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.<br>Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
|-
| style="text-align:center;" | Устный/письменный опрос
| style="text-align:left;" | Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части. 
|-
| style="text-align:center;" | Реферат
| style="text-align:left;" | Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты.<br>Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата.
|-
| style="text-align:center;" | Эссе
| style="text-align:left;" | Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др. 
|-
| style="text-align:center;" | Подготовка к промежуточной аттестации
| style="text-align:left;" | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.<br>Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
|-
| style="text-align:center;" | Практические (лабораторные) занятия
| style="text-align:left;" | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов. 
|-
| style="text-align:center;" | Самостоятельная работа
| style="text-align:left;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис. 
|-
| style="text-align:center;" | Видеопрезентация
| style="text-align:left;" | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
|-
| style="text-align:center;" | Доклад
| style="text-align:left;" | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
|-
| style="text-align:center;" | Дискуссия
| style="text-align:left;" | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
|-
| style="text-align:center;" | Контрольная работа
| style="text-align:left;" | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
|-
| style="text-align:center;" | Тестирование (устное/письменное)
| style="text-align:left;" | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
|-
| style="text-align:center;" | Индивидуальная работа
| style="text-align:left;" | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
|-
| style="text-align:center;" | Разработка отдельных частей кода
| style="text-align:left;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
|-
| style="text-align:center;" | Выполнение домашних заданий и групповых проектов
| style="text-align:left;" | Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
|}

=== Методы и технологии обучения, способствующие формированию компетенции ===
{| class="wikitable" style="width:80%; vertical-align:middle; background-color:#F8F9FA; color:#202122;"
|- style="text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
| Методы и технологии обучения, способствующие формированию компетенции
|-
| В курсе  планируется использовать несколько технологий обучения. Таких как, интерактивные лекции, поощряющие участие студентов посредством сессий вопросов и ответов, живых демонстраций концепций квантовых вычислений или групповых дискуссий.

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

Будут применяться программные средства квантовых вычислений: Q#, Qiskit, Cirq или Quil, что позволит им разрабатывать квантовые алгоритмы, симуляции и приложения. Этот практический опыт может способствовать развитию практических навыков и любопытства к квантовым вычислениям.

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

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