Материал: Лекция 5 Квантовые вычисления и оценка стойкости криптоалгоритмов
Идеи квантовых вычислений
Текущее состояние частицы представляет собой линейную смесь
λ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
Пример факторизации на основе поиска периода
35