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

# Кристоф Питэ/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.

- Quantum bits, Bloch sphere and Hopf fibration of the three sphere.
- Quantum computations and measurements, unitary operators and projectors.
- Entangled states and tensor products.
- Period finding, Fourier transform and the characters of cyclic groups.
- 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.