Инспектор
Вы можете этот курс.
Классические и квантовые вычисления
: Информация
Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Этот курс предназначен для первоначального знакомства с новой быстро развивающейся и популярной областью исследований - теорией квантовых вычислений.
Вначале приводится краткое введение в классическую теорию сложности вычислений.
Затем подробно излагаются основы теории квантовых вычислений, включая описание основных известных к настоящему времени эффективных квантовых алгоритмов.
Необходимые знания: Для студентов физико-математических специальностей (начиная со второго года обучения), аспирантов, научных работников: математиков и физиков.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Введение1 час 5 минут | ПредисловиеОглавление | - |
Лекция 11 час 17 минут | Что такое алгоритм?
В лекции рассматриваются понятие алгоритма и машины Тьюринга, даются определения вычислимых функций, разрешимых предикатов и сложностных классов, приводятся описание булевых функций и таблицы их значений.
Оглавление | - |
Тест 124 минуты | - | |
Лекция 252 минуты | Класс NP: сводимость и полнота
В лекции дается определение класса NP, описаны условия принадлежности предиката к указанному классу, рассматривается понятие и доказательство полиномиальной сводимости предикатов (сводимости по Карпу), приводятся примеры NP-полных задач.
Оглавление | - |
Тест 224 минуты | - | |
Лекция 342 минуты | Вероятностные алгоритмы и класс BPP. Проверка простоты числа
В лекции описаны основные особенности вероятностных машин Тьюринга, рассмотрены условия принадлежности предикатов к классу BPP, приведены Малая теорема Ферма и Китайская теорема об остатках, рассмотрен алгоритм проверки простоты числа и его анализ.
Оглавление | - |
Тест 324 минуты | - | |
Лекция 443 минуты | Иерархия сложностных классов
В лекции рассматривается понятие класса дополнений, приводится теорема Лаутемана и ее доказательство, дается описание класса PSPACE и машины Тьюринга с оракулом, рассматривается задача TQBF.
Оглавление | - |
Тест 424 минуты | - | |
Лекция 539 минут | Квантовые вычисления
В лекции дается понятие квантовых вычислений, рассматриваются отличия пространства состояний обычного и квантового компьютеров, приводятся определения элементарных преобразований в классическом и квантовом случаях, вводится понятие бра- и кет-векторов, дается понятие квантовых схем и реализуемых ими операторов.
Оглавление | - |
Тест 524 минуты | - | |
Лекция 622 минуты | Соотношение между классическим и квантовым вычислением
Основное внимание в лекции уделено понятию обратимой классической схемы и реализуемых ею перестановок, вводится понятие элемента Тоффоли, рассматривается содержательный смысл операции обратимого копирования.
Оглавление | - |
Тест 624 минуты | - | |
Лекция 744 минуты | Базисы для квантовых схем
В лекции описывается проблема выбора базиса в квантовых схемах, подробно рассматриваются условия точной и приближенной реализуемости операторов, вводятся понятия оператора с квантовым управлением и специальной ортогональной группы, действующей на трехмерном евклидовом пространстве.
Оглавление | - |
Тест 724 минуты | - | |
Лекция 841 минута | Определение квантового вычисления. Примеры
В лекции дается подробное описание квантовых вычислений, приводится определение функции голосования, дается определение универсальной переборной задачи в классической и квантовой постановке, вводится понятие универсальной квантовой схемы, рассматриваются квантовые алгоритмы и класс BQP.
Оглавление | - |
Тест 824 минуты | - | |
Лекция 938 минут | Квантовые вероятности
В лекции рассматриваются "физические" аспекты квантовых вычислений, приведено сравнение свойств классической и квантовой вероятностей, дается определение матрицы плотности, чистого и смешанного состояний, а также частичного следа от оператора по пространству.
Оглавление | - |
Тест 924 минуты | - | |
Лекция 1029 минут | Физически реализуемые преобразования матриц плотности
В лекции рассматриваются основные преобразования матриц плотности, описан механизм измерения квантовых регистров, вводится понятие детерминированного измерения, приводится задача "о квантовой телепортации".
Оглавление | - |
Тест 1024 минуты | - | |
Лекция 1119 минут | Измеряющие операторы
В этой рассматривается особый класс операторов - измеряющий оператор, а также подробно описываются его свойства. Кроме того в лекции подробно рассмотрен пример прикладного использования измеряющего оператора для исследования физических явлений, а также его математическое обоснование.
Оглавление | - |
Тест 1124 минуты | - | |
Лекция 121 час 40 минут | Быстрые квантовые алгоритмы
В лекции приводится "задача о скрытой подгруппе", дается ее решение, рассмотрен квантовый алгоритм для решения задачи о нахождении периода числа, описан процесс построения измеряющего оператора.
Оглавление | - |
Тест 1224 минуты | - | |
Лекция 131 час 21 минута | Квантовый аналог NP: класс BQNP
В лекции вводится понятие частично определенных функций, рассматривается доказательство леммы "об усилении вероятностей", дается описание класса BQNP и входящих в него полных задач, приводится определение локального гамильтониана, и кроме того, рассматривается вопрос о том, какое место класс BQNP занимает среди других сложностных классов.
Оглавление | - |
Тест 1324 минуты | - | |
Лекция 142 часа 22 минуты | Классические и квантовые коды
Изучив эту лекцию, Вы познакомитесь с понятием классических и квантовых кодов, научитесь использовать и применять код Шора, симплектические (стабилизирующие) коды, а также торические коды. Узнаете, каким образом коды могут исправлять ошибки, и как правильно выбрать способ кодирования в каждом конкретном случае.
Оглавление | - |
Тест 1424 минуты | - | |
Дополнительный материал5 часов 14 минут | Решения задач
Приводятся решения задач или неформальные указания, пользуясь которыми заинтересованный читатель может восстановить строгое решение самостоятельно.
Оглавление | - |
5 часов | - |