- •Понятие о квантовых вычислениях
- •n- кубитовый регистр
- •Вычисление функции в кубитовом регистре
- •Идея квантовых вычислений
- •Решение
- •Алгоритм Дойча-Джоза
- •Алгоритм ускоренного поиска (алгоритм Гровера)
- •Представлене булевой функции таблицей истинности
- •Пример алгоритма Гровера
- •Выводы
- •Криптосистема РША
- •Квантовый компьютер и криптосистема РША
- •Пример длинного числа
- •Идеи квантовых вычислений
- •Алгоритм Шора 1994г.
- •Пример факторизации на основе поиска периода
- •Реализация алгоритма Шора на двух квантовых регистрах
- •Этапы алгоритма Шора
- •Вычисление периода
- •Способы практической реализации квантовых компьютеров
- •Ядерные магнитно-резонансные компьютеры
Лекция5
Квантовые вычисления и оценка стойкости криптоалгоритмов
1
Понятие о квантовых вычислениях
•В классическихЭВМ бит задаетсяячейками с двумя устойчивымисостояниями:триггер, конденсатор,магнитный домен…Одноиз этих состоянийусловнообозначается 0, другое 1.
•Для хранениянескольких бит используются регистры как совокупностьячеекдля хранениябит
1 |
2 |
3 |
|
n-1 |
n |
Для хранения2n чисел |
|
1 |
0 |
1 |
|
0 |
|
1 |
нужно 2n регистров |
|
|
|
|||||
|
|
|
|
|
|
|
|
2
•Вквантовом компьютере битэтоквантоваясистема с двумя возможными физическимисостояниями элементарной частицы: спин электрона в магнитном поле, энергетический уровень атома водорода, две поляризации фотона.
•Математическая модель состояниячастицыописывается вектором в 2-х мерном пространстве:
|
0 , |
|
|
|
ψ = λ0 |
|
0 +λ1 |
|
1 |
|
|
(1) |
|
|
|
|
|
|
|
|
|||||
где |
|
1 |
- состояния системы, |
|
а λ и λ |
- комплексные |
||||||
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
амплитуды |
|
состояния. |
|
|||||||||
|
|
|
|
Соотношение (1) называетcяквантовым битом или q-битом.
Квадратымодулей являются вероятностями обнаружения
частицы при измерении с соответствующих - 0 , 1 |
||
состояниях. |
λ0 |
2 +λ12 =1 |
Состояние частицы выясняется только после измерения, а текущее (скрытое) состояние представляетсобойлинейную смесь(1).
3
n- кубитовый регистр
1 |
2 |
3 |
|
n-1 |
n |
|
|
|
|
|
|
|
|
|
В одном регистре сразу |
▪▫ |
▫▪ |
▪▫ |
|
▫▪ |
|
▪▫ |
|
|
|
может быть 2n возможных чисел |
|||||
|
|
|
|
|
|
|
С увеличением числа ячеек в регистре состояния частиц оказываются взаимосвязанными (сцепленными). Например система из 2-х кубитов может находиться в состоянии
λ00│00>+ λ01│01>+ λ10│10>+ λ11│11>
При обобщении на n-кубитовый регистр по аналогии описывается линейной комбинацией.:
ψ = ∑−1 λx x
x=02n
где [x>=[010…10> - состояние регистра
4
сцепленные состояния:
Смысл в том, что если измеренное состояние 1-й частицы [0>или [1>, то состояние второй частицы можно не выяснять – она в том же состоянии, не была а стала после измерения
.
Пример не сцепленных состояний:
5