Пример факторизации на основе поиска периода
35
•В алгоритме Шора задача факторизации M=pq сводитсяк задаче нахождения
периода r функции ax mod M .Наименьшее значениех, при котором ax mod M =1 называетсяпоказателемa по модулю М.
36
Реализация алгоритма Шора на двух квантовых регистрах
Обозначения:
M = p q
M < N < M 2 , N = 2n
37
Этапы алгоритма Шора
0.Подготовительный этап. Установка регистров в нулевое состояние.
1.Перевод регистров в равновесное состояние.
2.Вычисление степеней а^x в регистре Y, измерение состояния регистра.
3.Предвычисление периода с помощью квантового преобразования Фурье7
4.Вычисление периода на основе подходящих дробей
(на обычном компьютере)
38
Рис. 5. Инициализация регистров
ψ2 = (H n 0
) 0
Рис. 6. Применение преобразования Адамара к регистру |x>
39
Рис. 7. Применение квантового возведения в степень |
40 |
Измерение состояния регистра Y 
Например, фиксированному состоянию Последовательность значений x
y
= 8 соответствует
|
|
1 |
( |
|
|
|
|
|
11 +...) |
|
|
|
|
1 |
|
A |
|
|
|
|
|
φ2 = |
|
|
3 + |
|
7 + |
|
|
8 |
= |
|
|
∑j=0 |
|
r j +l |
|
|
8 |
||||
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||
|
А+1 |
|
|
|
|
A+1 |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
где А наибольшее целое меньшее, |
чем ( N −l ) / r, |
A ≈ N / r. |
|||||||||||||||||||
41