Компьютерные науки
Математика и логика

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

Программа о сравнительном анализе традиционной и квантовой информатики. Изучаются пределы классических машин Тьюринга, основы квантовых алгоритмов и физическая реализация кубитов.
Студентов 670 Выпускников 30 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Математика
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Эта учебная программа посвящена комплексному взгляду на теорию вычислимости. Рассматривается переход от классических логических вентилей к квантовым состояниям, изучаются проблемы NP-полных задач и потенциал квантового превосходства. Изучение классической теории сложности вычислений логично перетекает в разбор квантовых алгоритмов, криптографии и телепортации, сопровождаясь строгим математическим аппаратом. Учебная программа предназначена для исследователей, разработчиков алгоритмов и студентов технических вузов, интересующихся фундаментальными границами вычислений.
Цели
  • Дать целостное представление о границах классических и квантовых вычислений.
  • Раскрыть математический аппарат квантовой информатики.
  • Познакомить с алгоритмами, демонстрирующими квантовое превосходство.
Чему я научусь?
  • Сравнивать вычислительную сложность задач в классической и квантовой парадигмах.
  • Анализировать логику работы квантовых вентилей и схем.
  • Понимать принципы квантовой криптографии и защиты информации.

Авторы

Вялый Михаил Николаевич
Вялый Михаил Николаевич
Шень Александр Ханиевич
Шень Александр Ханиевич
Кандидат физико-математических наук, старший научный сотрудник Института проблем передачи информации РАН.
Чему я научусь?
  • Сравнивать вычислительную сложность задач в классической и квантовой парадигмах.
  • Анализировать логику работы квантовых вентилей и схем.
  • Понимать принципы квантовой криптографии и защиты информации.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Предисловие
2 Что такое алгоритм? В лекции рассматриваются понятие алгоритма и машины Тьюринга, даются определения вычислимых функций, разрешимых предикатов и сложностных... В лекции рассматриваются понятие алгоритма и машины Тьюринга, даются определения вычислимых функций, разрешимых предикатов и сложностных классов, приводятся описание булевых функций и таблицы их значений. ещё
Что такое алгоритм? тест для курса Классические и квантовые вычисления 40 мин
3 Класс NP: сводимость и полнота В лекции дается определение класса NP, описаны условия принадлежности предиката к указанному классу, рассматривается понятие и... В лекции дается определение класса NP, описаны условия принадлежности предиката к указанному классу, рассматривается понятие и доказательство полиномиальной сводимости предикатов (сводимости по Карпу), приводятся примеры NP-полных задач. ещё
Класс NP: сводимость и полнота тест для курса Классические и квантовые вычисления 40 мин
4 Вероятностные алгоритмы и класс BPP. Проверка простоты числа В лекции описаны основные особенности вероятностных машин Тьюринга, рассмотрены условия принадлежности предикатов к классу BPP, приведены... В лекции описаны основные особенности вероятностных машин Тьюринга, рассмотрены условия принадлежности предикатов к классу BPP, приведены Малая теорема Ферма и Китайская теорема об остатках, рассмотрен алгоритм проверки простоты числа и его анализ. ещё
Вероятностные алгоритмы и класс BPP. Проверка простоты числа тест для курса Классические и квантовые вычисления 40 мин
5 Иерархия сложностных классов В лекции рассматривается понятие класса дополнений, приводится теорема Лаутемана и ее доказательство, дается описание класса PSPACE... В лекции рассматривается понятие класса дополнений, приводится теорема Лаутемана и ее доказательство, дается описание класса PSPACE и машины Тьюринга с оракулом, рассматривается задача TQBF. ещё
Иерархия сложностных классов тест для курса Классические и квантовые вычисления 40 мин
6 Квантовые вычисления В лекции дается понятие квантовых вычислений, рассматриваются отличия пространства состояний обычного и квантового компьютеров, приводятся определения... В лекции дается понятие квантовых вычислений, рассматриваются отличия пространства состояний обычного и квантового компьютеров, приводятся определения элементарных преобразований в классическом и квантовом случаях, вводится понятие бра- и кет-векторов, дается понятие квантовых схем и реализуемых ими операторов. ещё
Квантовые вычисления тест для курса Классические и квантовые вычисления 40 мин
7 Соотношение между классическим и квантовым вычислением Основное внимание в лекции уделено понятию обратимой классической схемы и реализуемых ею перестановок, вводится понятие элемента... Основное внимание в лекции уделено понятию обратимой классической схемы и реализуемых ею перестановок, вводится понятие элемента Тоффоли, рассматривается содержательный смысл операции обратимого копирования. ещё
Соотношение между классическим и квантовым вычислением тест для курса Классические и квантовые вычисления 40 мин
8 Базисы для квантовых схем В лекции описывается проблема выбора базиса в квантовых схемах, подробно рассматриваются условия точной и приближенной реализуемости... В лекции описывается проблема выбора базиса в квантовых схемах, подробно рассматриваются условия точной и приближенной реализуемости операторов, вводятся понятия оператора с квантовым управлением и специальной ортогональной группы, действующей на трехмерном евклидовом пространстве. ещё
Базисы для квантовых схем тест для курса Классические и квантовые вычисления 40 мин
9 Определение квантового вычисления. Примеры В лекции дается подробное описание квантовых вычислений, приводится определение функции голосования, дается определение универсальной переборной задачи... В лекции дается подробное описание квантовых вычислений, приводится определение функции голосования, дается определение универсальной переборной задачи в классической и квантовой постановке, вводится понятие универсальной квантовой схемы, рассматриваются квантовые алгоритмы и класс BQP. ещё
Определение квантового вычисления. Примеры тест для курса Классические и квантовые вычисления 40 мин
10 Квантовые вероятности "В лекции рассматриваются ""физические"" аспекты квантовых вычислений, приведено сравнение свойств классической и квантовой вероятностей, дается определение... "В лекции рассматриваются ""физические"" аспекты квантовых вычислений, приведено сравнение свойств классической и квантовой вероятностей, дается определение матрицы плотности, чистого и смешанного состояний, а также частичного следа от оператора по пространству." ещё
Квантовые вероятности тест для курса Классические и квантовые вычисления 40 мин
11 Физически реализуемые преобразования матриц плотности "В лекции рассматриваются основные преобразования матриц плотности, описан механизм измерения квантовых регистров, вводится понятие детерминированного измерения,... "В лекции рассматриваются основные преобразования матриц плотности, описан механизм измерения квантовых регистров, вводится понятие детерминированного измерения, приводится задача ""о квантовой телепортации""." ещё
Физически реализуемые преобразования матриц плотности тест для курса Классические и квантовые вычисления 40 мин
12 Измеряющие операторы В этой рассматривается особый класс операторов - измеряющий оператор, а также подробно описываются его свойства. Кроме... В этой рассматривается особый класс операторов - измеряющий оператор, а также подробно описываются его свойства. Кроме того в лекции подробно рассмотрен пример прикладного использования измеряющего оператора для исследования физических явлений, а также его математическое обоснование. ещё
Измеряющие операторы тест для курса Классические и квантовые вычисления 40 мин
13 Быстрые квантовые алгоритмы "В лекции приводится ""задача о скрытой подгруппе"", дается ее решение, рассмотрен квантовый алгоритм для решения задачи... "В лекции приводится ""задача о скрытой подгруппе"", дается ее решение, рассмотрен квантовый алгоритм для решения задачи о нахождении периода числа, описан процесс построения измеряющего оператора." ещё
Быстрые квантовые алгоритмы тест для курса Классические и квантовые вычисления 40 мин
14 Квантовый аналог NP: класс BQNP "В лекции вводится понятие частично определенных функций, рассматривается доказательство леммы ""об усилении вероятностей"", дается описание класса... "В лекции вводится понятие частично определенных функций, рассматривается доказательство леммы ""об усилении вероятностей"", дается описание класса BQNP и входящих в него полных задач, приводится определение локального гамильтониана, и кроме того, рассматривается вопрос о том, какое место класс BQNP занимает среди других сложностных классов." ещё
Квантовый аналог NP: класс BQNP тест для курса Классические и квантовые вычисления 40 мин
15 Классические и квантовые коды Изучив эту лекцию, Вы познакомитесь с понятием классических и квантовых кодов, научитесь использовать и применять код... Изучив эту лекцию, Вы познакомитесь с понятием классических и квантовых кодов, научитесь использовать и применять код Шора, симплектические (стабилизирующие) коды, а также торические коды. Узнаете, каким образом коды могут исправлять ошибки, и как правильно выбрать способ кодирования в каждом конкретном случае. ещё
Классические и квантовые коды тест для курса Классические и квантовые вычисления 40 мин
16 Решения задач Приводятся решения задач или неформальные указания, пользуясь которыми заинтересованный читатель может восстановить строгое решение самостоятельно.
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

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

Удостоверение о повышении квалификации

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

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^