Программа дисциплины «Квантовые вычисления»

Правительство Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет прикладной математики и кибернетики

Программа дисциплины «Квантовые вычисления»

для специальности 230401.65 «Прикладная математика» подготовки специалиста

Автор программы:

, д. ф.-м. н., профессор, *****@, *****@***ru.

Одобрена на заседании кафедры «Прикладная математика» 29 июня 2012 г.

Зав. кафедрой

Рекомендована секцией УМС [Введите название секции УМС] «___»____________ 20 г

Председатель [Введите ]

Утверждена УС факультета [Введите название факультета] «___»_____________20 г.

Ученый секретарь [Введите ] ________________________ [подпись]

Москва, 2012

2  Область применения и нормативные ссылки

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

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов специальности 230401.65 «Прикладная математика», обучающихся по специализации «Применение математические методы" href="/text/category/instrumentalmznie_i_matematicheskie_metodi/" rel="bookmark">математических методов к решению инженерных и экономических задач», изучающих дисциплину «Квантовые вычисления».

Программа разработана в соответствии с:

·  ГОС 657100 Прикладная математика.

·  Образовательной программой 230401.65 «Прикладная математика».

·  Рабочим учебным планом университета по специальности230401.65 «Прикладная математика», специализации «Применение математических методов к решению инженерных и экономических задач», утвержденным в 2012 г.

3  Цели освоения дисциплины

Целью освоения дисциплины Квантовые вычисления являются

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

4  Компетенции обучающегося, формируемые в результате освоения дисциплины

В результате освоения дисциплины студент должен:

· Знать основные понятия, постановки задач и методы теории квантовых вычислений.

· Иметь навыки чтения научной литературы по этой дисциплине.

5  Место дисциплины в структуре образовательной программы

Настоящая дисциплина относится к циклу «Дисциплины специализации».

Для специализации «Применение математических методов к решению инженерных и экономических задач» настоящая дисциплина является базовой.

Изучение данной дисциплины базируется на следующих дисциплинах:

·  алгебра,

·  математический анализ и функциональный анализ

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

·  основные понятия и факты линейной алгебры, общей алгебры, математического анализа и функционального анализа

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

·  математическое программирование, конструирование вычислительных машин

6  Тематический план учебной дисциплины

[Тематический план отражает содержание дисциплины (перечень разделов), структурированное по видам учебных занятий с указанием их объемов в соответствии с РУП]

[ Таблица для дисциплин, закрепленных за одной кафедрой]

№	Название раздела	Всего часов	Аудиторные часы	Самостоя­тельная работа
Лекции	Семинары	Практические занятия
1	Вычислимость. Классы P и NP, сводимость и полнота. Вероятностные алгоритмы и класс BPP. Проверка простоты числа. Иерархия сложностных классов	4	4
2	Соотношение между классическим и квантовым вычислением. Элементарные квантовые понятия. Математическая формализация. Биты и кубиты	2	2
3	Базисы квантовых схем	2	2
4 7	Определение квантового вычисления. Примеры. Алгоритм Гровера. Квантовые алгоритмы. Структура тензорного произведения на кубитовом пространстве	2	2
5	Квантовые вероятности. Измеряющие операторы	2	2
6	Быстрые квантовые алгоритмы. Алгоритм Шора. Квантовое преобразование Фурье. Класс BQNP	2	2
7	Исправление ошибок. Классические и квантовые коды.	2	2
8	Скрещение и его мера. Случаи двух и трех кубитов.	2	2
1 2	Итого	18	18

7  Формы контроля знаний студентов

Тип контроля	Форма контроля	4 год	Параметры
1	2	3	4
текущий (17 неделя)	курсовая (самостоятельная) работа			*	*	домашняя
итоговый	зачет

7.1  Критерии оценки знаний, навыков

Порядок формирования оценок по дисциплине

Текущий контроль – курсовая работа во втором модуле

Итоговый контроль – зачет в конце второго модуля.

Результирующая оценка за текущий контроль рассчитывается следующим образом:

Отекущий = Окурсовая работа

Итоговая оценка по курсу выставляется по следующей формуле:

Оитоговая = 0,5· Озачет + 0,5·Отекущий

где Озачет – оценка за работу непосредственно на зачете.

7.1.1  Таблица соответствия оценок по десятибалльной и системе зачет/незачет

Оценка по 10-балльной шкале	Оценка по 5-балльной шкале
1	незачет
2
3
4	зачет
5
6
7
8
9
10

8  Содержание дисциплины

Тема 1. Классические вычисления

1.1. Вычислимость, классы P и NP, сводимость и полнота.

1.2. Вероятностные алгоритмы и класс BPP. Проверка простоты числа.

1.3. Иерархия сложностных классов.

Основная литература

А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления, МЦНМО, М., 1999

Дополнительная литература

Н. Катленд, Вычислимость. Введение в теорию рекурсивных функций, Мир, М., 1983

Э. Стин, Квантовые вычисления, Ижевск, 2000.

Тема 2. Квантовые вычисления

2.1. Соотношение между классическим и квантовым вычислением. Элементарные квантовые понятия. Математическая формализация. Биты и кубиты.

2.2. Базисы квантовых схем. 2.3. Определение квантового вычисления. Примеры. Алгоритм Гровера. Квантовые алгоритмы. Структура тензорного произведения на кубитовом пространстве.

2.4. Квантовые вероятности

2.5. Измеряющие операторы

2.6. Быстрые квантовые алгоритмы. Алгоритм Шора. Квантовое преобразование Фурье

2.6. Класс BQNP

2.7. Исправление ошибок. Классические и квантовые коды.

2.8. Скрещение и его мера. Случаи двух и трех кубитов.

Основная литература

А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления, МЦНМО, М., 1999

Дополнительная литература

Квантовый компьютер & квантовые вычисления, НИЦ “Регулярная и хаотическая динамика”, Ижевск, 1999.

Квантовые вычисления: за и против, НИЦ “Регулярная и хаотическая динамика”, Ижевск, 1999.

Э. Стин, Квантовые вычисления, Ижевск, 2000.

, Квантовые вычисления: алгоритмы и исправление ошибок, Успехи математических наук 52 (1997), вып. 6, 53-112.

N. R. Wallach, Quantum computing and entanglement for mathematicians, Lectures on quantum computing, Venice CIME, June 2004 (updated 2012), http://www. math. ucsd. edu/~nwallach/Venice4.pdf

9  Образовательные технологии

Разбор примеров и практических задач.

9.1  Методические рекомендации преподавателю

Нет.

9.2  Методические указания студентам

Нет.

10  Оценочные средства для текущего контроля и аттестации студента

10.1  Тематика заданий текущего контроля

Нет

Вопросы для оценки качества освоения дисциплины

1. Что такое МНР? Что такое машина Тьюринга?

2. Что такое вычислимая функция и схема?

3. Что такое классы P и NP? Что такое сводимости и NP-полнота? Приведите пример сведения.

4. Что такое вероятностный алгоритм и класс BPP?

5. В чем состоит алгоритм проверки простоты целого числа?

6. Что такое иерархия сложностных классов?

7. Что такое пространство состояний системы из n кубитов? Что такое квантовая схема и оператор, ею реализуемый? В чем состоит определение квантового вычисления? Приведите пример.

8. В чем состоит алгоритм Гровера?

9. Что такое класс BQP?

10. Что такое квантовая вероятность? Детерминированное измерение? Квантовая телепортация?

11. Что такое измеряющие операторы? Приведите пример.

12. В чем состоит задача о скрытой подгруппе? Можно ли быстро ее найти на классической вероятностной машине?

13. В чем состоит алгоритм Шора?

14. В чем состоит квантовый алгоритм нахождения периода?

15. В чем состоит квантовый алгоритм решения задачи о скрытой подгруппе?

16. Что такое класс BQNP? Каково его место среди других сложностных классов?

17. Что такое классический код, квантовый код? Приведите примеры.

18. Что такое код Шора?

19. Что такое скрещение и его мера?

10.2  Примеры заданий промежуточного /итогового контроля

Нет.

11  Учебно-методическое и информационное обеспечение дисциплины

11.1  Базовый учебник

А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления, МЦНМО, М., 1999

11.2  Основная литература

А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления, МЦНМО, М., 1999

Э. Стин, Квантовые вычисления, Ижевск, 2000.

11.3  Дополнительная литература

Н. Катленд, Вычислимость. Введение в теорию рекурсивных функций, Мир, М., 1983

Квантовый компьютер & квантовые вычисления, НИЦ “Регулярная и хаотическая динамика”, Ижевск, 1999.

Квантовые вычисления: за и против, НИЦ “Регулярная и хаотическая динамика”, Ижевск, 1999.

Э. Стин, Квантовые вычисления, Ижевск, 2000.

, Квантовые вычисления: алгоритмы и исправление ошибок, Успехи математических наук 52 (1997), вып. 6, 53-112.

N. R. Wallach, Quantum computing and entanglement for mathematicians, Lectures on quantum computing, Venice CIME, June 2004 (updated 2012), http://www. math. ucsd. edu/~nwallach/Venice4.pdf

11.4  Справочники, словари, энциклопедии

Не используются

11.5  Программные средства

Не используются

11.6  Дистанционная поддержка дисциплины

Не предусмотрена

12  Материально-техническое обеспечение дисциплины

Не используется