Материал: Лекция 5 Квантовые вычисления и оценка стойкости криптоалгоритмов

Алгоритм Дойча-Джоза

•Обобщает алгоритм Дойча на случай функцииn переменных f (x0 , x1 , , xn−1) : {0,1}n →{0,1}

•Позволяетопределитьза одно измерение являетсяли функцияконстантой или сбалансированной функцией, т.е. если в половине случаев она принимаетзначение 0, а в другой половине1.

•Амплитуда λ0 принимает значение ÷1

если функция константа и 0, если она сбалансирована. 16

Алгоритм ускоренного поиска (алгоритм Гровера)

Рассмотрим решениеуравнения f(x)=1, где функция f(x) принимает значения{0,1},

но только при одномзначенииf(x0)=1.

Состояние системы в общемвиде можнозаписать так

= λ0 x0 +λ1x1 + +λ2n−1 x2n−1

Где λi амплитуда i-го состояния.

17

Представлене булевой функции таблицей истинности

18

•Идеяалгоритма Гровера состоитв том, чтобы увеличить, например, │λx0│ за счет других │λx│.

•Этого можнодобиться k кратным преобразованием диффузии.

[ψ>=DD…D[ψ1>,

где [ψ1> – начальный вектор состояния, D – матрица преобразования.

19

Пример алгоритма Гровера

• Задана булева функция от трех аргументов

f (x0 , x1, x2 ) , которая принимает значение1 только при одномнаборе аргументов.

Нужно найтиэто состояние. Решение.

1 этап. Подготавливает начальное состояние

ψ0 = 0,0, .0 , т.е. всеячейкиквантового регистра устанавливаются в состоянии0. Или все кубиты в нулевом состоянии.