- •Понятие о квантовых вычислениях
- •n- кубитовый регистр
- •Вычисление функции в кубитовом регистре
- •Идея квантовых вычислений
- •Решение
- •Алгоритм Дойча-Джоза
- •Алгоритм ускоренного поиска (алгоритм Гровера)
- •Представлене булевой функции таблицей истинности
- •Пример алгоритма Гровера
- •Выводы
- •Криптосистема РША
- •Квантовый компьютер и криптосистема РША
- •Пример длинного числа
- •Идеи квантовых вычислений
- •Алгоритм Шора 1994г.
- •Пример факторизации на основе поиска периода
- •Реализация алгоритма Шора на двух квантовых регистрах
- •Этапы алгоритма Шора
- •Вычисление периода
- •Способы практической реализации квантовых компьютеров
- •Ядерные магнитно-резонансные компьютеры
Идеи квантовых вычислений
Текущее состояние частицы представляет собой линейную смесь
λ0 |
|
0 +λ1 |
|
1 |
(1) |
|
|
где λ0, λ1 – комплексные амплитуды. Состояние частицы выясняется
только после измерения. Квадраты модулей которых являются вероятностями обнаружения частицы при измерении с
соответствующих - |
|
0 , |
|
1 состояниях. |
λ0 |
2 +λ12 =1 |
|
||||||
|
|
|||||
|
Соотношение (1) называется квантовым битом или q-битом.
С увеличением числа ячеек в регистре состояния частиц оказываются взаимосвязанными (сцепленными). Например система из 2-х кубитов может находиться в состоянии
λ00│00>+ λ01│01>+ λ10│10>+ λ11│11>
1 |
2 |
3 |
|
n-1 |
n |
|
|
|
|
|
|
|
|
|
В одном n разрядном регистре сразу |
▪▫ |
▫▪ |
▪▫ |
|
▫▪ |
|
▪▫ |
|
|
|
может быть 2n возможных чисел |
|||||
|
|
|
|
|
|
|
31 |
|
|
|
|
|
|
|
•Принципквантовых вычисленийзаключен в увеличениимодулякомплексных амплитуд │λx0│тех состояний│x0,f(x0)>, которые хотелосьбы получить в результате считывания.
•Процессвычисления – последовательность унитарных преобразований ненаблюдаемогосостояниярегистра.
32
Задачи, решаемыес помощьюквантового компьютера
•Проверка является либулева функция константой– алгоритм Дойча-Джоза.
• Задача поиска решенияуравнения f (x) =1 , где функцияпринимает значения(0,1) – алгоритм Гровера.
•КвантовоепреобразованиеФурье.
•Задача факторизациичисла – алгоритм Шора.
33
Алгоритм Шора 1994г.
34