Пример алгоритма Гровера
• Задана булева функция от трех аргументов
f (x0 , x1, x2 ) , которая принимает значение1 только при одномнаборе аргументов.
Нужно найтиэто состояние. Решение.
1 этап. Подготавливает начальное состояние
ψ0 = 0,0, .0
, т.е. всеячейкиквантового регистра устанавливаются в состоянии0. Или все кубиты в нулевом состоянии.
|
ψ0 = λ0 x0 +λ1x1 + +λ2n−1 x2n−1 |
=1x0 +0x1 + +0x2n−120 |
|
||
|
• 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