Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Этот курс предназначен для первоначального знакомства с новой быстро развивающейся и популярной областью исследований - теорией квантовых вычислений.
Вначале приводится краткое введение в классическую теорию сложности вычислений. Затем подробно излагаются основы теории квантовых вычислений, включая описание основных известных к настоящему времени эффективных квантовых алгоритмов.
Необходимые знания: Для студентов физико-математических специальностей (начиная со второго года обучения), аспирантов, научных работников: математиков и физиков.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Введение 
1 час 5 минут
Предисловие
Оглавление
    -
    Лекция 1
    1 час 17 минут
    Что такое алгоритм?
    В лекции рассматриваются понятие алгоритма и машины Тьюринга, даются определения вычислимых функций, разрешимых предикатов и сложностных классов, приводятся описание булевых функций и таблицы их значений.
    Оглавление
      -
      Тест 1
      24 минуты
      -
      Лекция 2
      52 минуты
      Класс NP: сводимость и полнота
      В лекции дается определение класса NP, описаны условия принадлежности предиката к указанному классу, рассматривается понятие и доказательство полиномиальной сводимости предикатов (сводимости по Карпу), приводятся примеры NP-полных задач.
      Оглавление
        -
        Тест 2
        24 минуты
        -
        Лекция 3
        42 минуты
        Вероятностные алгоритмы и класс BPP. Проверка простоты числа
        В лекции описаны основные особенности вероятностных машин Тьюринга, рассмотрены условия принадлежности предикатов к классу BPP, приведены Малая теорема Ферма и Китайская теорема об остатках, рассмотрен алгоритм проверки простоты числа и его анализ.
        Оглавление
          -
          Тест 3
          24 минуты
          -
          Лекция 4
          43 минуты
          Иерархия сложностных классов
          В лекции рассматривается понятие класса дополнений, приводится теорема Лаутемана и ее доказательство, дается описание класса PSPACE и машины Тьюринга с оракулом, рассматривается задача TQBF.
          Оглавление
            -
            Тест 4
            24 минуты
            -
            Лекция 5
            39 минут
            Квантовые вычисления
            В лекции дается понятие квантовых вычислений, рассматриваются отличия пространства состояний обычного и квантового компьютеров, приводятся определения элементарных преобразований в классическом и квантовом случаях, вводится понятие бра- и кет-векторов, дается понятие квантовых схем и реализуемых ими операторов.
            Оглавление
              -
              Тест 5
              24 минуты
              -
              Лекция 6
              22 минуты
              Соотношение между классическим и квантовым вычислением
              Основное внимание в лекции уделено понятию обратимой классической схемы и реализуемых ею перестановок, вводится понятие элемента Тоффоли, рассматривается содержательный смысл операции обратимого копирования.
              Оглавление
                -
                Тест 6
                24 минуты
                -
                Лекция 7
                44 минуты
                Базисы для квантовых схем
                В лекции описывается проблема выбора базиса в квантовых схемах, подробно рассматриваются условия точной и приближенной реализуемости операторов, вводятся понятия оператора с квантовым управлением и специальной ортогональной группы, действующей на трехмерном евклидовом пространстве.
                Оглавление
                  -
                  Тест 7
                  24 минуты
                  -
                  Лекция 8
                  41 минута
                  Определение квантового вычисления. Примеры
                  В лекции дается подробное описание квантовых вычислений, приводится определение функции голосования, дается определение универсальной переборной задачи в классической и квантовой постановке, вводится понятие универсальной квантовой схемы, рассматриваются квантовые алгоритмы и класс BQP.
                  Оглавление
                    -
                    Тест 8
                    24 минуты
                    -
                    Лекция 9
                    38 минут
                    Квантовые вероятности
                    В лекции рассматриваются "физические" аспекты квантовых вычислений, приведено сравнение свойств классической и квантовой вероятностей, дается определение матрицы плотности, чистого и смешанного состояний, а также частичного следа от оператора по пространству.
                    Оглавление
                      -
                      Тест 9
                      24 минуты
                      -
                      Лекция 10
                      29 минут
                      Физически реализуемые преобразования матриц плотности
                      В лекции рассматриваются основные преобразования матриц плотности, описан механизм измерения квантовых регистров, вводится понятие детерминированного измерения, приводится задача "о квантовой телепортации".
                      Оглавление
                        -
                        Тест 10
                        24 минуты
                        -
                        Лекция 11
                        19 минут
                        Измеряющие операторы
                        В этой рассматривается особый класс операторов - измеряющий оператор, а также подробно описываются его свойства. Кроме того в лекции подробно рассмотрен пример прикладного использования измеряющего оператора для исследования физических явлений, а также его математическое обоснование.
                        Оглавление
                          -
                          Тест 11
                          24 минуты
                          -
                          Лекция 12
                          1 час 40 минут
                          Быстрые квантовые алгоритмы
                          В лекции приводится "задача о скрытой подгруппе", дается ее решение, рассмотрен квантовый алгоритм для решения задачи о нахождении периода числа, описан процесс построения измеряющего оператора.
                          Оглавление
                            -
                            Тест 12
                            24 минуты
                            -
                            Лекция 13
                            1 час 21 минута
                            Квантовый аналог NP: класс BQNP
                            В лекции вводится понятие частично определенных функций, рассматривается доказательство леммы "об усилении вероятностей", дается описание класса BQNP и входящих в него полных задач, приводится определение локального гамильтониана, и кроме того, рассматривается вопрос о том, какое место класс BQNP занимает среди других сложностных классов.
                            Оглавление
                              -
                              Тест 13
                              24 минуты
                              -
                              Лекция 14
                              2 часа 22 минуты
                              Классические и квантовые коды
                              Изучив эту лекцию, Вы познакомитесь с понятием классических и квантовых кодов, научитесь использовать и применять код Шора, симплектические (стабилизирующие) коды, а также торические коды. Узнаете, каким образом коды могут исправлять ошибки, и как правильно выбрать способ кодирования в каждом конкретном случае.
                              Оглавление
                                -
                                Тест 14
                                24 минуты
                                -
                                Дополнительный материал 
                                5 часов 14 минут
                                Решения задач
                                Приводятся решения задач или неформальные указания, пользуясь которыми заинтересованный читатель может восстановить строгое решение самостоятельно.
                                Оглавление
                                  -
                                  5 часов
                                  -