Материал: Лекция 5 Квантовые вычисления и оценка стойкости криптоалгоритмов
Для нашего примера f ( x ) = 2x mod 15 состояние регистра после КПФ будет таким, как показано на рисунке, то есть, ненулевые вероятности имеют состояния 
Вероятность какого либо из этих состояний
|
|
|
|
|
|
N |
−1 |
2 |
|
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|||
|
|
|
|
r |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|||||
P |
c |
= |
|
|
∑exp( 2πij( rc mod N ) / N ) |
|
|
|
|
|
|||
N |
2 |
|
|
|
|
|
|||||||
|
|
|
|
j=0 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||
После преобразований можно получить |
P |
|
c ≥ |
4 |
1 |
||||||||
|
|||||||||||||
|
π2 |
r |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
Окончательно мы хотим выделить информацию о периоде r. Для этого проводится измерение состояния регистра x
46
Мы рассмотрели частный случай, когда r делит N нацело. Тогда rc mod N = 0 Если от этого условия отказаться, то
−r / 2 ≤ rc mod N ≤ r / 2 |
(1) |
||||||||||||||
Пусть rc mod N = kN ±r / 2 , тогда условие (1) запишем так |
|||||||||||||||
|
rc −kN |
|
≤ r / 2 |
( 2 ) |
|
||||||||||
|
|
|
|||||||||||||
Разделав обе части (2) |
на Nr, получим |
|
|||||||||||||
|
|
|
c |
|
− k |
|
≤ |
1 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
N |
|
|
2N |
|
|
|
|
|||||
|
|
|
|
r |
|
|
|
|
|
|
|||||
По результатам измерения регистра |
|
x |
мы получили величину c/N, |
||||||||||||
|
|||||||||||||||
тогда используя разложение c/N в цепную дробь, можно рассчитать |
|||||||||||||||
подходящую дробь и найти r. |
|
|
|
|
|||||||||||
Вероятность успеха |
|
P c |
0.4 |
. Для повышения вероятности проводим |
|||||||||||
испытания несколько раз с разными значениями а.
47
Вопросы реализации квантовых вычислений
•Внастоящее время квантовые вычисления находятсяна начальной стадииразвития. Дальнейший прогресс будет зависеть отрешения техническихзадач,связанныхс созданиемэлементной базыквантовых компьютеров.
•Существуюти практические реализации квантового алгоритма Шора. Созданный квантовый компьютер основан на явлении ядерно-магнитного резонанса и состоялизсеми кубитов,чегохватило для разложения числа 15 на простые множители 3 и 5.
•Типы квантовых компьютеров:
-Ядерный магнитный резонанс(NMR) -Ионные ловушки
-Квантовые точки
48
Исследованияквантового компьютера
Компании |
Квантовая среда |
Особенности |
|
|
|
Очень высокая вероятность |
|
|
Исследования квантовой среды |
квантовых ошибок, что не |
|
IBM |
на основе схем из |
позволяет создавать |
|
|
сверхпроводящих металлов |
полноценные квантовые |
|
|
|
компьютеры |
|
|
Исследование теоретически |
Существование квазичастиц, |
|
Microsoft |
более надежной квантовой |
используемых в |
|
среды и создание |
топологическом кубите, пока |
||
|
|||
|
топологического кубита |
не доказано |
|
Alcatel- |
Исследования |
Создание топологического |
|
Lucent |
конденсированного состояния |
кубита на основе дробного |
|
(Bell |
вещества с целью создания |
квантового эффекта Холла |
|
Labs) |
топологического кубита |
пока в стадии исследований |
|
|
Исследования по созданию |
Пока не доказано, что чипы |
|
D-Wave |
квантового компьютера на |
||
построены на основе |
|||
Systems |
основе сверхпроводящего чипа, |
||
квантовых эффектов |
|||
|
содержащего 512 кубитов |
||
|
|
||
|
Разноплановые исследования |
Google адаптирует свои |
|
|
компьютеров D-Wave Systems, |
||
технологии под возможности |
|||
|
построенных на основе |
квантовых компьютеров |
|
|
контактов Джозефсона |
||
|
|
1 Топологический кубит – это теоретический кубит на основе двухмерных квазичастиц
(анионов), являющихся более стабильными, что позволяет уменьшить ошибки декогеренции.
49
Способы практической реализации квантовых компьютеров
•Квантовые вычисления с использованием метода
импульсного ядерного магнитного резонанса в
молекулярных жидкостях.
•Квантовые вычисления на основе использования в качествеэлементной базыквантовых компьютеров: ионов в ловушках в вакууме;спинов одиночных электронов в квантовых точках в двумерном газе в полупроводниковых гетероструктурах;атомы в резонаторах электромагнитного поля.
•Квантовые вычисления, основанные на состояниях сверхпроводников,разделенных переходами Джозефсонаи различающихсячислом зарядов.
50