На главную страницу НМУ

Кристоф Питэ/Christophe Pittet

Разложения на простые: алгоритм Шора/MATHEMATICAL ASPECTS OF QUANTUM COMPUTATIONS

The goal of the course is to give a complete mathematical description of Shor's algorithm which factors an N digit integer in O(NNlog(N)log(log(N))) steps on a quantum computer.

  1. Quantum bits, Bloch sphere and Hopf fibration of the three sphere.

  2. Quantum computations and measurements, unitary operators and projectors.

  3. Entangled states and tensor products.

  4. Period finding, Fourier transform and the characters of cyclic groups.

  5. Probability estimates for the Euler function and Euler constant.

FIFTH AND LAST LECTURE ON SHOR'S ALGORITHM

May 4, 17h30-19h, IUM 304

I will describe each~Z step in Shor's algorithm. For those who could not attempt a previous course, the prerequisites to understand this last lecture are explained in the second and third set of notes (attached to this message). Everyone is welcome.

FOURTH LECTURE ON SHOR'S ALGORITHM

April 27, 17h30-19h, IUM 304

I will give the mathematical definition of a quantum-measurement (in terms of orthogonal projectors), recall the Fourier transform on cyclic groups, and explain how they are used in Shor's algorithm.

Attached is a first set of notes.

THIRD LECTURE ON SHOR'S ALGORITHM

March, 23, 17h30-19h, IUM 304
(there will be no course March, 16) I will give the mathematical definitions of a~Z quantum-memory (in terms of tensor products), of a quantum-computation (in terms of unitary transformations), and of a quantum-measurement (in terms of orthogonal projectors), used in Shor's algorithm.

Everyone is welcome.

SECOND LECTURE ON SHOR'S ALGORITHM

February 23, 17h30-19h, IUM 304. 1) I will finish to explain how the problem of factoring an integer N reduces to the problem of finding the period of a function. Namely why the reduction procedure explained in the first lecture works with probability at least 1/2 (assuming N is odd~Z and not a prime power).

2) I will give the mathematical definitions of quantum-bit, quantum-memory, and quantum-computation, used in Shor's algorithm.

Everyone is welcome.

FIRST LECTURE ON SHOR'S ALGORITHMГ

February 16, 17h30-19h, IUM 304

I will explain how the problem of factoring an integer reduces to the problem of finding the period of a function. This is the first step in Shor's algorithm. It relies only on elementary arithmetic.

Everyone is welcome.

Rambler's Top100