- •Понятие о квантовых вычислениях
- •n- кубитовый регистр
- •Вычисление функции в кубитовом регистре
- •Идея квантовых вычислений
- •Решение
- •Алгоритм Дойча-Джоза
- •Алгоритм ускоренного поиска (алгоритм Гровера)
- •Представлене булевой функции таблицей истинности
- •Пример алгоритма Гровера
- •Выводы
- •Криптосистема РША
- •Квантовый компьютер и криптосистема РША
- •Пример длинного числа
- •Идеи квантовых вычислений
- •Алгоритм Шора 1994г.
- •Пример факторизации на основе поиска периода
- •Реализация алгоритма Шора на двух квантовых регистрах
- •Этапы алгоритма Шора
- •Вычисление периода
- •Способы практической реализации квантовых компьютеров
- •Ядерные магнитно-резонансные компьютеры
Алгоритм Дойча-Джоза
•Обобщает алгоритм Дойча на случай функции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
Представлене булевой функции таблицей истинности
x3 |
x2 |
x1 |
y=f(x1,x2,x3) |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
18
•Идеяалгоритма Гровера состоитв том, чтобы увеличить, например, │λx0│ за счет других │λx│.
•Этого можнодобиться k кратным преобразованием диффузии.
[ψ>=DD…D[ψ1>,
где [ψ1> – начальный вектор состояния, D – матрица преобразования.
19