Спецкурс "Квантовые вычисления"

Лектор: профессор О.Н.Граничин

Слушатели: 5 курс (10-й семестр), отделение информатики

 

Аннотация:

Ежегодное уменьшение на 10-30% элементарных вычислительных модулей приведет в ближайшие годы к практическому использованию устройств с элементарными модулями размером примерно в 100-200 ангстрем (10-20нм). Для описания работы таких устройств не применимы классические объекты и методы «Информатики». В частности, в силу квантового принципа неопределенности Гейзенберга, в таких микроскопических системах нет аналога   понятию «bit». Вместо двоичных цифр новые устройства будут оперировать с «волновыми функциями» («квантовыми битами»). С одной стороны, это обуславливает переосмысление и замену основных классических (не квантовых) алгоритмов, а, с другой стороны, дает возможность вплотную подступиться к решению проблем «искусственного интеллекта».   

 

Темы курса:

 

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

2.       Концепция обобщенной машины Тьюринга (2 ч. лекц.).

3.       Математическая модель квантовых вычислений (2 ч. лекц.).

4.       Квантовый параллелизм. Задачи Дойча, Бернштейна-Вазирани, алгоритм Саймона (6 ч. лекц.).

5.       Алгоритм Гровера  (квантовой поиск в базе данных) (4 ч. лекц.).

6.       Алгоритм факторизации П.Шора. Квантовое преобразование Фурье (6 ч. лекц.).

7.       Адиабатические вычисления (4 ч. лекц.).

8.       Рандомизрованные алгоритмы стохастической аппроксимации для решения многомерных задач оптимизации (4 ч. лекц.).

 

Литература:

Основная

1.         Граничин О.Н., Молодцов С.Л. "Создание гибридных сверхбыстрых компьютеров и системное программирование" СПб. 2006. 108 с.

2.     Preskill J. “Quantum Information and Computation”, http://www.theory.caltech.edu/~preskill/ph229.

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

1.       Deutsch D. Quantum theory, the Church-Turing Principle and the Universal Quantum Computer // Proceedings of the Royal Society of London. Ser.A. 400 (1985) P.97-117.

2.       Feynman R. Modeling of physics on computers} // Int. Journal of Theoretical Physics.  21 (1982). No 6/7.

3.       Copeland J.B. The Church-Turing Thesis // NeuroQuantology. (2004) No 2. P.101-115.

4.       Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM J. Comput. 26 (1997) P.1484-1509.

5.       Bennet C.H., Shor P.W. ” Quantum information theory” IEEE Transactions on Information Theory. 44 (1988). P.2724-2742.

6.       Shor P.W. “Quantum computing”.  In: Proceedings of the 9-th Int. Math. Congress. Berlin, 1998, www.math.nine.edu/documenta/xvol-icm/Fields/Fields.html. 

7.       Kieu Tien D. Computing the non-computable // Contemporary Physics. 44 (2003) .

8.       Граничин О.Н., Жувикина И.А. Новая модель процесса вычислений: обобщение концепции машины Тьюринга // Нейрокомпьютеры: разработка, применение, 2006, № 7 , с. 24-31. 

9.       Граничин О.Н., Поляк  Б.Т.} Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Hаука. 2003. 291с.

10.   Нариньяни А.С. Модель или алгоритм: новая парадигма информационных технологий. Российский НИИ ИИ. 2004.

11.   Садовничий В.А. Квантовый компьютер и квантовые вычисления. Т.2. Ижевск. 1999.

12.   Фаддеев Л.Д., Якубовский О.А. Лекции по квантовой механике для студентов-математиков. Ижевск. Изд-во РХД. 2001.

 

Перечень примерных контрольных вопросов и заданий для самостоятельной работы:

·                Какие физические явления будут, вероятно, использоваться при создании элементной базы вычислительных устройств нового поколения?

·                Какие определения вычислимости вы знаете?

·                Какова область применимости тезиса Черча-Тьюринга?

·                Какие постулаты квантовой механики лежат в основе математической модели квантовых вычислений?

·                В чем заключается квантовый параллелизм?

·                Как выполняется алгоритм быстрого преобразования Фурье?

·                На каких математических принципах основывается RSA-шифрование?

·                Кто и когда решил 10-ю проблему Гильберта?

·                Какие методы поиска минимума дифференцируемой функции вы знаете?

 

Примерный перечень вопросов к экзамену по всему курсу:

·              Гибридные вычислительные устройства.

·              Обобщенная машина Тьюринга.

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

·              Задача Дойча.

·              Задача Бернштейна-Вазирани.

·              Алгоритм Саймона.

·              Алгоритм Гровера.

·              Квантовое преобразование Фурье.

·              Алгоритм факторизации П.Шора.

·              Решение задачи о корнях диофантового уравнения.

·              Алгоритм вычисления псевдоградиента многомерной функции за один такт.