Материал: Лекция 5 Квантовые вычисления и оценка стойкости криптоалгоритмов
• 2 этап. Приготавливаем смесь равновероятных состояний ψ1 
= H 3 ψ0 
=
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
1 |
|
|
|
0,354 |
|
|
|
|
|
−1 |
1 |
−1 |
1 |
−1 |
1 |
|
|
|
|
0 |
|
|
|
0,354 |
|
|
|
|
1 |
−1 |
|
|
|
|
|
|
|||||||||
|
|
|
|
1 |
−1 |
−1 |
1 |
1 |
−1 |
|
|
|
|
0 |
|
|
|
0,354 |
|
1 |
|
|
1 |
−1 |
|
|
|
|
|
|
|||||||||
|
|
1 |
−1 |
−1 |
1 |
1 |
−1 |
−1 |
1 |
|
|
|
0 |
|
= |
|
0,354 |
|
|
|
|
|
|
1 |
1 |
1 |
−1 |
−1 |
−1 |
|
|
|
0 |
|
|
0,354 |
|
||
2 2 |
|
|
|||||||||||||||||
|
|
|
|
||||||||||||||||
|
1 |
−1 |
|
|
|
|
|
|
|||||||||||
|
|
|
1 |
−1 |
1 |
−1 |
−1 |
1 |
−1 |
1 |
|
|
|
0 |
|
|
|
0,354 |
|
|
|
|
|
1 |
−1 |
−1 |
−1 |
−1 |
1 |
1 |
|
|
|
0 |
|
|
|
0,354 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
−1 |
−1 |
1 |
−1 |
1 |
1 |
|
|
|
|
0 |
|
|
|
0,354 |
|
|
|
|
1 |
−1 |
|
|
|
|
|
|
|||||||||
Состояние [ψ> является суперпозицией 2^n возможных
состояний системы из n кубитов.
21
•3 этап.
•Несколько раз применяемоператор G
• ψ2 
= G G ψ1 
, где G = ROf , а
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
−3 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
1 |
2 |
n−1 −1 |
|
1 |
2 |
n−1 |
|
|
1 |
2 |
n−1 |
|
|
1 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
1 |
|
|
1 |
|
n−1 −1 |
|
1 |
|
|
|
|
1 |
|
||
2 |
n−1 |
2 |
|
2 |
n−1 |
|
4 |
|||||||||
R = |
|
|
|
|
|
|
|
|
|
|
= |
1 |
||||
|
|
|
|
|
|
|
|
|
4 |
|||||||
|
|
|
|
|
||||||||||||
|
1 |
|
|
|
1 |
|
|
|
1 |
|
n−1 −1 |
|
1 |
|
||
2 |
n−1 |
|
2 |
n−1 |
2 |
|
4 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
14 |
14 |
14 |
14 |
14 |
−3
4
−3
4
−3
4
−3
4
−3
4
−3
4 14 14 14 14 14 14
1 |
4 |
|
|
|
|
||
14 |
|
||
|
|||
1 |
4 |
|
|
|
|
||
1 |
4 |
|
|
|
|
||
1 |
4 |
|
|
|
|
||
1 |
|
|
|
4 |
|
||
1 |
|
||
|
|||
4 |
|
||
|
|
||
−3 4 |
|
||
|
|
|
|
Так называемыйоператор диффузии
22
(−1)f (000)
Of = 00
0
(−1)f (001)
0
0
0
(−1)f (111)
|
|
|
1 |
|
|
|
0 |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
0 |
|
= |
|
||
|
|
0 |
|
|
|
||
|
|
|
|
|
|
0 |
|
|
|
||
|
|
|
0 |
|
|
|
|
|
|
|
0 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0
0
0
0
0
0
−01
Так называемаяматрица – фазовыйзапрос
(пустыеместавматрице нули)
23
Результатыпреобразования
|
|
|
|
|
|
0,177 |
|
|
|
|
|
|
|
−0,088 |
|
|
|
|
|
|
|
−0.305 |
|
|
|
|
|
|
|
0,177 |
|
|
|
|
|
|
|
−0,088 |
|
|
|
|
|
|
|
−0.305 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
0,177 |
|
|
|
|
|
|
|
−0,088 |
|
|
|
|
|
|
|
−0.305 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
G |
|
ψ |
|
= |
|
0,177 |
|
GG |
|
ψ |
|
= |
|
−0,088 |
|
GGG |
|
ψ |
|
= |
|
−0.305 |
|
|
|
|
|
|
|
||||||||||||||||||
|
1 |
|
0,177 |
|
|
1 |
|
−0,088 |
|
|
1 |
|
−0.305 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
0,177 |
|
|
|
|
|
|
|
−0,088 |
|
|
|
|
|
|
|
−0.305 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
0,177 |
|
|
|
|
|
|
|
−0,088 |
|
|
|
|
|
|
|
−0.305 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
0,884 |
|
|
|
|
|
|
|
0,972 |
|
|
|
|
|
|
|
0,575 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Оптимальное число применений оператора G π |
|
|
раз. |
2n |
|||
4 |
|
|
|
Состояние соответствующее решению уравнения
f(x)=1, будет иметь максимальную амплитуду и может появиться в процессе измерения с максимальной вероятностью. Вероятность получить неправильный результат в алгоритме Гровера оценивается как
O(1/2^n). |
O(2n/2 ) операций. |
Решение задачи алгоритмом Гровера требует |
|
Классический переборный алгоритм требует |
O(2n−1) операций. |
24
Выводы
•Квантовый компьютер сможет найти запись в случайной базе данных гораздо быстрее чем классический компьютер.
•В случайной(неотсортированной) базе данных с N записями обычный компьютер будет в среднем делать N / 2 поисковых попыток прежде чем он обнаружит искомую запись.
•Для поиска на квантовом компьютере в той же
базе данных размера N потребуется всего 
N попыток (алгоритм Гровера)
25