ЖЭТФ, 2019, том 155, вып. 1, стр. 32-53

ПРИМЕНЕНИЕ КВАНТОВОГО АЛГОРИТМА ГРОВЕРА

В ЗАДАЧЕ ПОИСКА КЛЮЧА БЛОЧНОГО ШИФРА SDES

Д. В. Денисенко^*, М. В. Никитенкова

Московский государственный технический университет им. Н. Э. Баумана

105005, Москва, Россия

Поступила в редакцию 6 июля 2018 г.,

после переработки 6 июля 2018 г.

Принята к публикации 10 июля 2018 г.

Рассмотрена задача поиска ключа Simplified-DES — модели блочного шифра DES, с помощью квантового

алгоритма Гровера. Рассмотрены примеры применения алгоритма Гровера. Построена минимальная по

количеству кубитов квантовая схема, реализующая поиск ключа Simplified-DES по одной паре открытого

и шифрованного текстов, для которой требуется 19 кубитов. Проведена симуляция работы построенной

квантовой схемы с использованием квантового симулятора Quipper.

DOI: 10.1134/S0044451019010036

Bristlecone позволит продемонстрировать «кванто-

вое превосходство» [5,6].

Квантовые вычисления оказывают непосред-

1. ВВЕДЕНИЕ

ственное влияние на защиту информации с помо-

В настоящее время большое количество исследо-

щью современных криптографических алгоритмов

ваний направлено на создание квантовых симулято-

и протоколов. Например, возможность применения

ров и квантовых процессоров: в 2017 г., на конферен-

квантового алгоритма Шора [7] делает криптогра-

ции ICQT 2017, группа физиков под руководством

фическую систему RSA небезопасной, квантовый

М. Лукина, сооснователя Российского квантового

алгоритм Саймона [8] делает небезопасным исполь-

центра и профессора Гарвардского университета, со-

зование блочных шифров в режимах CBC-MAC,

общила о создании программируемого 51-кубитного

PMAC, GMAC, GCM и OCB [9]. Квантовый ал-

квантового симулятора [1]. Примерно в это же время

горитм Гровера (см. [10-12]) в модели квантовых

группа ученых из университета Мэриленда разрабо-

вычислений является аналогом метода полного пе-

тала 53-кубитный симулятор, основанный на ионах

ребора ключей алгоритмов шифрования. В работе

в оптических ловушках [2]. В компании IBM успеш-

[13] рассмотрена задача поиска ключа Simplified-

но испытали прототип квантового процессора из 50

DES (SDES)

— уменьшенной модели блочного

кубитов [3], а в декабре 2017 г. опубликована ста-

шифра DES — с помощью квантового алгоритма

тья [4], согласно которой представлен проект мас-

Гровера, представлено описание соответствующей

штабируемого кремниевого квантового процессора,

квантовой схемы, реализующей поиск ключа SDES

представляющий собой массив из 24 × 20 = 480 ку-

по одной известной паре блоков открытого и шиф-

битов. В январе 2018 г. на выставке CES-2018 ком-

рованного текстов, использующей 61 кубит. Авторы

пания Intel сообщила о создании сверхпроводяще-

работы

[13] пользовались квантовым симулято-

го квантового чипа «Tangle Lake», состоящего из 49

ром libquantum (см. [14]), однако исходные коды

кубитов. Intel ведет разработки квантовых компью-

программ не были опубликованы.

теров по двум направлениям: создание устройств

В данной работе представлена квантовая схе-

на сверхпроводниках и кремниевых чипов со «спи-

ма, реализующая поиск ключа SDES по одной па-

новыми кубитами». В марте 2018 года компания

ре открытого и шифрованного текстов на 19 куби-

Google объявила о создании 72-кубитного квантово-

тах, верифицированная с помощью квантового си-

го процессора Bristlecone. В компании надеются, что

мулятора Quipper (см. [15-17]), который, в отли-

чие от libquantum, позволяет автоматически печа-

^* E-mail: DenisenkoDV@bmstu.ru

тать квантовые схемы в PDF-файлы. Показано, что

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

19 кубитов — минимальное количество логических

Шифрование

кубитов, достаточное для реализации поиска клю-

ча SDES по одной паре открытого и шифрованного

текстов.

Главные цели настоящей работы — демонстра-

ция применения квантового алгоритма Гровера в

задаче поиска ключа учебного алгоритма блочного

шифрования SDES и оценка минимального количе-

ства логических кубитов, необходимого для реали-

зации такого поиска.

В Приложении 1 приведен контрольный пример

SDES. Программная реализация применения алго-

ритма Гровера в задачах поиска одного и двух целе-

вых значений в Wolfram Mathematica представлена

в Приложениях 2 и 3. Программная реализация по-

иска ключа SDES квантовым алгоритмом Гровера в

Quipper представлена в Приложении 4.

2. ОПИСАНИЕ АЛГОРИТМА SDES

Блочный шифр SDES — это двухраундовая сеть

Фейстеля E_SDES : V₁₀ × V₈ → V₈, у которой ключ

K ∈ V₁₀, а блоки открытого и шифрованного тек-

ста — восьмибитные двоичные векторы (см. рис. 1).

Процедура зашифрования алгоритмом SDES

представляет собой композицию отображений:

Рис. 1. Схема алгоритма SDES

IP-1◦fk2 ◦SW◦fk1◦IP.

Преобразование f_k определяется следующим об-

Из основного ключа K ∈ V₁₀ формируются два ра-

разом. Пусть P = L||R, L, R ∈ V₄, тогда f_k(L, R) =

ундовых ключа k₁, k₂ ∈ V₈. Сначала к ключу K

= (L ⊕ F (R, k), R).

применяется перестановка битов P10:

Отображение F(R, k): V₄ × V₈ → V₄ состоит из

следующих последовательно применяющихся преоб-

P10 — перестановка

3 5 2 7 4 10 1 9 8 6

разований.

1. Процедура расширения E/P: V₄→V₈, выборка

Затем к каждой половине P10(K) применяется цик-

битов с соответствующими номерами:

лический сдвиг влево на 1 бит (LS-1), после чего из

двух половинок снова формируется десятибитный

E/P

41232341

ключ. Далее применяется P8 — выборка восьми би-

2. XOR результата E/P с аргументом k.

тов с соответствующими номерами — и получается

3. Применение S-боксов. На каждый S-бокс по-

раундовый ключ k₁:

дается 4-битный вектор, первый и четвертый биты

которого образуют номер строки, а второй и третий

P8 — выборка битов с номерами

6 3 7 4 8 5 10 9

образуют номера столбцов таблиц замен:

⎡

⎤

⎡

⎤

Для формирования k₂ после применения LS-1

применяется циклический сдвиг влево на два бита

⎢

⎥

⎢

⎥

⎢

⎥

⎢

⎥

(LS-2), затем применяется P8.

S₀=⎢

⎥,

S₁=⎢

^⎥.

⎢

⎥

⎢

⎥

⎣

⎦

⎣

⎦

Рассмотрим первый раунд зашифрования блока

открытого текста P ∈ V₈ алгоритмом SDES.

К открытому тексту P применяется перестанов-

Нумерация строк и столбцов начинается с нуля.

ка битов IP:

Пример: S₀(1010) = 10, так как в строке с номером

26314857

10 (третья строка) и столбце c номером 01 (второй

ЖЭТФ, вып. 1

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

столбец) в таблице замен S₀ стоит число 2, которое

Для произвольного блочного шифра задача по-

в двоичной системе счисления записывается как 10.

иска ключа с помощью квантового алгоритма Гро-

Координатные функции S₀ имеют вид

вера формулируется следующим образом. Рассмот-

рим блочный шифр с длиной ключа n битов и дли-

y₀(x₀, x₁, x₂, x₃) =x₃⊕x₁x₀⊕x₀x₂⊕x₀x₁x₂x₃,

ной блока m битов E: V_n × V_m → V_m. Известно

некоторое количество пар открытых и шифрован-

y₁(x₀, x₁, x₂, x₃) =x₀x₂⊕x₀x₃⊕x₀x₁⊕x₀x₁x₂x₃.

ных текстов, полученных на одном и том же неиз-

вестном ключе K ∈ V_n, C_i = E(K, P_i), i ∈ 1, t, и ре-

Координатные функции S₁ имеют вид

шается стандартная задача по восстановлению клю-

ча. Для однозначного восстановления ключа, исходя

y₀(x₀, x₁, x₂, x₃) =x₁⊕x₂x₃⊕x₀x₃⊕x₀x₁x₂x₃,

из расстояния единственности шифра [18], количе-

ство пар текстов должно быть не менее t = ⌈n/m⌉.

y₁(x₀, x₁, x₂, x₃) =x₂x₃⊕x₀x₃⊕x₀x₁x₃⊕x₀x₂x₃.

В этом случае с большой вероятностью ключ бу-

4. К 4-битному выходу из S-боксов применяется

дет единственным, а соответствующая булева функ-

перестановка битов P4:

ция f: V_n → V₁ определяется следующим образом:

⋀

2431

f (x) = z (E(x, P_i) ⊕ C_i)) ,

i=1

5. Побитовый XOR с левой половиной IP(P).

где z : V_m → V₁, причем z(x) = 1, если x = 0^m, и

6. Перестановка полубайтов SW: V₈

→ V₈,

z(x) = 0 в противном случае.

SW(L, R) = (R, L).

Отметим, что в работе [13] поиск ключа осу-

Второй раунд выполняется аналогично первому,

ществлен только по одной паре открытого и шиф-

только с ключом k₂. После выполнения второго ра-

рованного текстов (P, C), рассматриваются два слу-

унда применяется IP-1:

чая: в первом — у пары (P, C) нет эквивалентных

ключей (т. е. существует ровно один ключ, на кото-

IP-1

41357286

ром блок открытого текста P переходит в блок шиф-

В результате получим блок зашифрованного

рованного текста C), во втором — у пары (P, C) два

текста C = E_SDES(K, P), C ∈ V₈.

эквивалентных ключа. В данной работе, следуя ра-

боте [13], поиск ключа SDES организован по одной

паре открытого и шифрованного текстов, рассмот-

3. АЛГОРИТМ ГРОВЕРА

рены те же примеры, что и в работе [13].

В Приложениях 2 и 3 представлены программ-

Пусть имеется пронумерованное множество из

ные реализации, демонстрирующие преобразование

N = 2ⁿ элементов и необходимо найти хотя бы

амплитуд квантовых состояний в процессе выпол-

один элемент из этого множества, удовлетворяю-

нения алгоритма Гровера в задачах поиска одного

щий некоторому критерию поиска, при этом множе-

и двух целевых значений соответственно, т. е. рас-

ство элементов, удовлетворяющих выбранному кри-

смотрены случаи, когда M = 1 и M = 2.

терию поиска, не является пустым и состоит из M

Алгоритм 1. Алгоритм Гровера

элементов, M ≤ N/2 (см. [12], с. 318).

Вход. Множество {a₁, a₂, . . . , a_N } из N = 2ⁿ эле-

Можно считать, что задана некоторая булева

ментов, f : V_n → V₁, f(x) = 1 тогда и только тогда,

функция f : V_n → V₁, причем f(x) = 1 тогда и

когда a_x удовлетворяет некоторому критерию поис-

только тогда, когда элемент множества с номером x

ка, где x — номер элемента a_x в двоичной системе

удоветворяет критерию поиска. При этом считается,

счисления, т. е. x ∈ V_n.

что указанная функция f может быть эффективно

Выход. С вероятностью p > 1/2 произвольный

реализована в виде квантовой схемы.

a_x′ : f(x^′) = 1.

При решении задачи поиска на классическом вы-

1. Инициализация n + 1 кубитов в состояние

числителе в общем случае необходимо перебрать все

|ψ₀〉

= |0〉^⊗n |1〉, дополнительные рабочие кубиты

элементы рассматриваемого множества, что в ито-

инициализируются в зависимости от функции f.

ге дает трудоемкость порядка O(N/M), в то время

2. Применение гейтов Адамара H, получим

как квантовый алгоритм Гровера (см. [10-12]) при

∑

решении указанной задачи на квантовом вычисли-

|0〉 - |1〉

√

|ψ₁〉 =

√

|i〉 ⊗

√

теле имеет трудоемкость O(

N/M).

i=0

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

Таблица 1. Распределение вероятностей ключей по-

1) 10 кубитов для записи ключа;

сле 25 итераций Гровера при поиске ровно одного

2) 8 кубитов для записи блока открытого текста;

целевого значения

3) 8 кубитов для записи блока зашифрованного

текста;

Вероятность получить в

4) 34 кубита — рабочее пространство для записи

Ключ SDES результате измерения кубитов

результатов промежуточных вычислений.

соответствующий ключ

На рис. 4-7 представлена более эффективная

квантовая схема итерации Гровера (по сравнению

00000 00000

5.26642 · 10-7

с квантовой схемой, описанной в [13]), реализую-

00000 00001

5.26642 · 10-7

щая поиск ключа SDES по одной паре открытого и

шифрованного текста, финальное измерение куби-

тов. Программная реализация поиска ключа SDES

11000 10011

0.99946124

в квантовом симуляторе Quipper приведена в При-

ложении 4.

Рассмотрим два случая.

11111 11110

5.26642 · 10-7

В первом случае выберем в качестве блока от-

крытого текста P

= 00010000, в качестве блока

11111 11111

5.26642 · 10-7

шифрованного текста C

= 00110011. Для такой

пары (P, C) существует единственный ключ K =

Таблица 2. Распределение вероятностей ключей по-

= 1100010011, на котором E_SDES(K, P) = C.

сле 18 итераций Гровера при поиске одного из двух

Во втором случае выберем P = 10100101 и C =

целевых значений

= 00110110. Для такой пары (P, C) существуют два

ключа

Вероятность получить в

K₁ = 0010010111 и K₂ = 0011011111,

Ключ SDES результате измерения кубитов

соответствующий ключ

на которых E_SDES (K_i, P ) = C, i ∈ {1, 2}.

00000 00000

4.118199 · 10-6

В соответствии с теоретической оценкой количе-

ства итераций Гровера, в первом случае оптималь-

00000 00001

4.118199 · 10-6

ное количество итераций Гровера составляет

√

1024

00100 10111

0.4978955

≈[25.1327] = 25,

R=4

а во втором случае —

√

00110 11111

0.4978955

1024

≈[17.7715] = 18.

11111 11110

4.118199 · 10-6

В табл. 1 представлено распределение вероятно-

стей ключей после 25 итераций Гровера при P =

11111 11111

4.118199 · 10-6

= 00010000 и C = 00110011 (первый случай), полу-

ченное с помощью квантового симулятора Quipper.

В табл. 2 представлено распределение вероятно-

4. Измерение кубитов, с вероятностью p > 1/2

стей ключей после 18 итераций Гровера при P =

получим произвольный a_x′ : f(x^′) = 1.

= 10100101 и C = 00110110 (второй случай), так-

же полученное с помощью квантового симулято-

ра Quipper. Заметим, что ключи 001001011110 =

4. КВАНТОВАЯ СХЕМА SDES И

= 151 и 001101111110 = 223, т. е. соответствуют

АЛГОРИТМА ГРОВЕРА

TargetValues ∈ {151, 223} в задаче, рассмотренной

В работе [13] представлена реализация SDES в

в Приложении 3. Сумма вероятностей

виде квантовой схемы на 60 кубитах и квантовая

схема алгоритма Гровера на 61 кубите (рис. 2, 3):

P (K = 151₂)+P (K = 223₂) = 2·0.4978955 ≡ 0.995791

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

Продолжение таблицы 3

Характеристики квантовых схем,

время их симуляции в Quipper

Количество итераций Гровера

на процессоре Intel Core

i7-4470K 3.50 ГГц

Quantum exhaustive key search (2 keys):

408: "H, arity 1"

14: "Init0"

5: "Init1"

11: "Meas"

1512: "X, arity 1"

1296: "not, arity 1 controls 1"

18 итераций Гровера

648: "not, arity 1 controls 2"

(поиск одного из двух ключей)

144: "not, arity 1 controls 3"

216: "not, arity 1 controls 4"

18: "not, arity 1 controls 4+4"

18: "not, arity 1 controls 9"

144: "swap, arity 2"

Total gates: 4434

Inputs: 0

Outputs: 19

Qubits in circuit: 19

Время работы = 6593.336957 с

Таблица 4. Распределение квантовых вентилей по

Таблица 5. Сравнение количества вентилей в одной

операциям SDES из работы [13]

итерации Гровера

E/P

8 CNOT

Операция

В работе [13] На рис. 4-7

404

XOR полубайтов

4 CNOT

CNOT

936

72+24

XOR с раундовым

8 CNOT

Тоффоли

576

ключом

Обобщенный

SWAP

12 CNOT

CNOT

2 × 32 вентиля Х

Для каждого

2 × 48 Тоффоли

S-бокса

2 × 32 CNOT

В предложенной квантовой схеме используют-

совпадает с вероятностью успеха алгоритма Гровера

ся так называемые обобщенные вентили (гейты)

после 18 итераций в табл. 7, рассчитанной в Wolfram

CNOT(n) — вентили с одним контролируемым куби-

Mathematica (см. Приложение 3).

том и n контролирующими кубитами, для реализа-

Сводные данные по характеристикам построен-

ции которых не требуются дополнительные рабочие

ных квантовых схем представлены в табл. 3.

кубиты (см. [12], с. 236).

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

Нас интересует минимальная оценка количества

В квантовой схеме на рис. 4-7 операции IP, P10,

логических кубитов для реализации алгоритма Гро-

P8, E/P, LS-1, LS-2, P4 реализованы без использова-

вера в задаче поиска ключа SDES. Отображение

ния каких-либо вентилей, что достигается простой

E_SDES: V₁₀ × V₈ → V₈ состоит из 8 булевых коор-

перенумерацией кубитов, которую можно рассчи-

динатных функций f_i(x₁, . . . , x₁₀₊₈), i ∈ 1, 8, зави-

тать заранее.

сящих от 18 переменных. Для того чтобы постро-

В табл. 5 представлено сравнение количества

ить квантовую схему, реализующую изменение зна-

вентилей в одной итерации Гровера.

ка амплитуды искомого состояния (см. алгоритм

Гровера), требуется не менее 18 кубитов для реали-

зации SDES и еще один флаговый кубит. Таким об-

5. ЗАКЛЮЧЕНИЕ

разом, на рис. 4-7 представлена минимальная по ко-

личеству логических кубитов квантовая схема, реа-

В работе представлена минимальная по количе-

лизующая поиск ключа SDES с помощью алгоритма

ству кубитов (19 кубитов) квантовая схема, реализу-

Гровера по одной паре открытого и шифрованного

ющая поиск ключа SDES по одной паре открытого и

текстов.

шифрованного текстов квантовым алгоритмом Гро-

Сравним общее количество квантовых вентилей

вера, в то время как в работе [13] соответствующая

в одной итерации Гровера. В работе [13] подсчету

квантовая схема построена на 61 кубите.

квантовых вентилей посвящен раздел «Complexity

С помощью квантового симулятора Quipper про-

analysis», но их общее количество явно не приведе-

ведена симуляция работы построенных квантовых

но. Согласно [13], процедура выработки раундовых

схем для 18 и 25 итераций Гровера, получены со-

ключей SDES интегрирована в один шаг и требует 8

ответствующие распределения вероятностей успеха

вентилей CNOT, распределение вентилей по осталь-

алгоритма Гровера в задаче поиска ключа SDES для

ным операциям SDES приведено в табл. 4.

случаев, когда для известной пары блоков открыто-

В соответствии с алгоритмом зашифровывания

го и шифрованного текстов (P, C) существует ровно

SDES и табл. 4, пользуясь рис. 2 и 3, можем посчи-

один ключ K ∈ V₁₀, на котором E_SDES (K, P ) =

тать общее количество вентилей в квантовой схеме

= C, и два ключа K₁,K₂

∈ V₁₀, на которых

одной итерации Гровера из работы [13]. При под-

E_SDES(K₁, P) = C и E_SDES(K₂, P) = C.

счете необходимо учитывать процедуру обращения

Контрольный пример учебного алгоритма блоч-

раундовых преобразований (количество вентилей,

ного шифрования SDES приведен в Приложении 1,

участвующих в раундовых преобразованиях, умно-

программная реализация алгоритма Гровера в за-

жается на два), инвертирование флагового кубита

дачах поиска одного и двух целевых значений пред-

(требуется один обобщенный CNOT), рассеивание

ставлена в Приложениях 2 и 3. Программная реали-

Гровера (еще один обобщенный CNOT), а также тот

зация поиска ключа SDES квантовым алгоритмом

факт, что перестановка двух кубитов (SWAP) вы-

Гровера в квантовом симуляторе Quipper представ-

полняется с помощью трех CNOT.

лена в Приложении 4.

ПРИЛОЖЕНИЕ 1

Контрольный пример SDES

Выберем блок открытого текста P = 00101000 и K = 1100011110. Формирование раундового ключа k₁:

Номера битов

P10(K)

LS-1(P10(K))

k₁ = P8(LS-1(P10(K)))

Формирование раундового ключа k₂:

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

Номера битов

P10(K)

LS-3(P10(K))

k₂ = P8(LS-3(P10(K)))

В рассматриваемом примере P = 00101000, IP(P ) = 00100010.

1. Выберем P = 00101000 и K = 1100011110.

2. IP(P) = 00100010.

3. fk1 (L, R) = f_11101001(00100010) = (0010 ⊕ F(0010, 11101001), 0010).

4. F(0010, 11101001) = P4 ◦ Sboxes ◦ (11101001 ⊕ E/P(0010)):

Номера битов

E/P(R)

k₁

E/P(R) ⊕ k₁

Sboxes(E/P(R) ⊕ k₁)

P4(Sboxes(E/P)⊕k₁))

5. Вычислили F(0010, 11101001) = 0001, получили fk1(L, R) = (0011, 0010).

6. SW(0011, 0010) = (0010, 0011).

7. fk2 (L, R) = f_10100111(00100011) = (0010 ⊕ F(0011, 10100111), 0011):

Номера битов

E/P(R)

k₂

E/P(R) ⊕ k₂

Sboxes(E/P(R) ⊕ k₂)

P4(Sboxes(E/P(R) ⊕ k₂))

8. Вычислили F(0011, 10100111) = 0011, получили fk2(L, R) = (0001, 0011).

9. Применили IP-1:

Номера битов

L, R

IP-1(L, R)

Примеры результатов зашифровывания на ключе K = 1100011110:

E_SDES(K, 00101000) = 10001010,

E_SDES(K, 10001101) = 11010000,

E_SDES(K, 11110010) = 11011010,

E_SDES(K, 01010111) = 01100000.

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

ПРИЛОЖЕНИЕ 2

Поиск одного целевого значения с помощью алгоритма Гровера

Пусть N = 2³, M = 1, целевое значение TargetValue=7. Определим вероятности успеха поиска целевого

значения в зависимости от количества итераций алгоритма Гровера.

Листинг 1. Программная реализация в пакете Wolfram Mathematica

TargetValue=7; (*Зададим номер элемента, который хотим получить в результате

измерения кубитов*)

NumberOfQubits=3; (*определили количество кубитов*)

H= HadamardMatrix[2^NumberOfQubits];

(*Инициализировали матрицу Адамара*)

Numb=2^NumberOfQubits; (*ввели дополнительную переменную для более короткой записи*)

matrixD=ConstantArray[ConstantArray[2/Numb,Numb],Numb]-IdentityMatrix[Numb];

(*Инициализировали матрицу D (рассеивание Гровера)*)

Print["Матрица Адамара: \n ",MatrixForm[H]];

⎛

⎞

√

⎜

⎟

⎜

⎟

⎜

⎟

⎜

√

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

√

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

√

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

√

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

√

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

√

⎟

⎜

⎟

⎜

⎟

⎝

⎠

√

Print["Матрица D (рассеивание Гровера): \n ",MatrixForm[matrixD]];

⎛

⎞

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

D=⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎠

⎝ 1

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

FirstState=ConstantArray[0,2^NumberOfQubits];

FirstState[[1]]=1;

(*Инициализировали начальное состояние*)

Print["Инициализировали начальное состояние:",FirstState];

FirstState

= {1, 0, 0, 0, 0, 0, 0, 0}

State=FirstState.H; (*Применили гейты Адамара к каждому кубиту,

т.е. умножили вектор FirstState на матрицу H*)

{

}

State=

√

i=0;

Print["Итерация №", i ," вероятность успеха = ", N[(State[[TargetValue]]*

State[[TargetValue]])]," вероятность неудачи = ",

N[(1-State[[TargetValue]]*State[[TargetValue]])]

];

Итерация №0, вероятность успеха = 0.125, вероятность неудачи = 0.875;

(*Изменение знака амплитуды целевого значения*)

State[[TargetValue]]=(-1)*State[[TargetValue]];

Print["изменили знак у целевого значения: \n",State];

{

}

State=

√

State=State.matrixD; (*Применили рассеивание Гровера, умножили State на матрицу D*)

Print["Применили рассеивание Гровера, умножили State на матрицу D: \n",State];

{

}

State=

√

i=1;

Print["Итерация №", i ," вероятность успеха = ", N[(State[[TargetValue]]*

State[[TargetValue]])]," вероятность неудачи = ", N[(1-State[[TargetValue]]*

State[[TargetValue]])]

];

Итерация №1, вероятность успеха = 0.78125, вероятность неудачи = 0.21875

NumberOfGroverIterations=30;

(*задали количество итераций, например 30*)

For[i=2,i<=NumberOfGroverIterations,i++,

State[[TargetValue]]=(-1)*State[[TargetValue]];

(*изменили знак у целевого значения*)

State=State.matrixD; (*Применили рассеивание Гровера, умножили State на матрицу D*)

p=State[[TargetValue]]*State[[TargetValue]];

Print["Итерация №", i ," вероятность успеха = ", N[p]," вероятность неудачи = ", N[1-p]];

]

Рассчитаем вероятности успешного поиска целевого значения (TargetValue=7) в зависимости от количе-

ства итераций алгоритма Гровера на трех кубитах (см. табл. 6). Оптимальное количество итераций Гровера √ ][

2³

в рассматриваемом примере оценивается величиной^π

= [2.221441469079183] = 2.

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

Таблица 6

Вероятность неудачи

Вероятность успеха алгоритма

алгоритма Гровера,

Номер

Гровера, т. е. вероятность

т. е. вероятность

итерации

получить в результате

Гровера

измерения кубитов

TargetValue=7

0.78125

0.21875

0.945313

0.0546875

0.330078

0.669922

0.012207

0.987793

0.547974

0.452026

0.999786

0.000213623

0.576973

0.423027

0.0194569

0.980543

0.302891

0.697109

0.931266

0.068734

0.804925

0.195075

0.144965

0.855035

0.106316

0.893684

0.756614

0.243386

0.957837

0.0421627

0.357846

0.642154

0.0066241

0.993376

0.51881

0.48119

0.998078

0.00192151

0.605709

0.394291

0.0283488

0.971651

0.276378

0.723622

0.915746

0.0842543

0.827558

0.172442

0.166144

0.833856

0.0889775

0.911022

0.7311

0.2689

0.968798

0.0312024

ПРИЛОЖЕНИЕ 3

Поиск одного из двух целевых значений с помощью алгоритма Гровера

Пусть N

= 2¹⁰, M = 2, целевое значение TargetValue ∈ {151, 223}. Определим вероятности успе-

ха поиска целевого значения в зависимости от количества итераций алгоритма Гровера (см. табл. 7).

[птима]ьное количество итераций Гровера в рассматриваемом примере оценивается величиной

√

2¹⁰

= [17.771531752633464] = 18.

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

Таблица 7

Вероятность неудачи

Вероятность успеха алгоритма

алгоритма Гровера,

Номер

Гровера, т. е. вероятность

т. е. вероятность получить

итерации

получить в результате

в результате измерения

Гровера

измерения кубитов одно из

кубитов значение не из

TargetValues = {151,223}

TargetValues

0.0174867

0.982513

0.0480693

0.951931

0.0927473

0.907253

0.150127

0.849873

0.218419

0.781581

0.295493

0.704507

0.378945

0.621055

0.466173

0.533827

0.554456

0.445544

0.641041

0.358959

0.723227

0.276773

0.79845

0.20155

0.864365

0.135635

0.918916

0.0810837

0.960402

0.0395983

0.987528

0.0124724

0.999448

0.000551974

0.995791

0.0042088

0.976671

0.0233288

0.942684

0.0573158

0.89489

0.10511

0.83478

0.16522

0.764229

0.235771

0.685436

0.314564

0.60086

0.39914

0.513139

0.486861

0.425007

0.574993

0.339214

0.660786

Листинг 2. Программная реализация в пакете Wolfram Mathematica

1 (*Случай когда несколько искомых номеров*)

2 TargetValues={151,223};

(*искомые номера*)

3 NumberOfQubits=10;

(*определили количество кубитов*)

4 H= HadamardMatrix[2^NumberOfQubits]; (*Инициализировали матрицу Адамара*)

5 Numb=2^NumberOfQubits; (*ввели доп. переменную для более короткой записи*)

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

6 matrixD=ConstantArray[ConstantArray[2/Numb,Numb],Numb]-IdentityMatrix[Numb];

7 (*Инициализировали матрицу D (рассеивание Гровера)*)

8 FirstState=ConstantArray[0,2^NumberOfQubits];

9 FirstState[[1]]=1; (*Инициализировали начальное состояние*)

10 State=FirstState.H;

11 (*Применили гейты Адамара к каждому кубиту, т.е. умножили вектор FirstState на матрицу H*)

∑Length[TargetValues]

State [[TargetValues [[k]]]] ∗ State [[TargetValues[[k]]]];

k=1

12 i=0;Print["Итерация №", i ,", вероятность успеха = ", N[p],",

вероятность неудачи = ", N[1-p]];

13 (*Изменение знака у амплитуды целевого значения*)

14 For[i=1,i<=Length[TargetValues],i++,

15 State[[ TargetValues[[i]] ]]=(-1)*State[[ TargetValues[[i]] ]];

];

16 State=State.matrixD;

17 (*Применили рассеивание Гровера, умножили вектор State на матрицу D*)

∑Length[TargetValues]

State [[TargetValues [[k]]]] ∗ State [[TargetValues[[k]]]];

k=1

18 Print["Итерация №", i ,", вероятность успеха = ", N[p],", вероятность неудачи = ", N[1-p]];

19 NumberOfGroverIterations=30;

20 (*задали количество итераций Гровера*)

21 For[i=2,i<=NumberOfGroverIterations,i++,

22 For[j=1,j<=Length[TargetValues],j++,

23 State[[TargetValues[[j]]]]=(-1)*State[[TargetValues[[j]] ]];];

24 State=State.matrixD;

∑_{Length[TargetValues]}

State [[TargetValues [[k]]]] ∗ State [[TargetValues[[k]]]];

k=1

25 Print["Итерация №", i ,", вероятность успеха = ", N[p],", вероятность неудачи = ",

N[1-p]];]

Вероятность успеха после 17 итераций Гровера оказалась чуть больше, чем вероятность успеха после 18 √ ][

итераций Гровера. Это ничему не противоречит, так как^π

— верхняя оценка числа итераций (см.

[12], с. 318).

ПРИЛОЖЕНИЕ 4

Программная реализация алгоритма Гровера для поиска ключа SDES по паре открытого и

шифрованного текстов на квантовом симуляторе Quipper

Программная реализация представляет собой три файла:

1) QSDES.hs — реализация алгоритма SDES,

2) Grover.hs — реализация алгоритма Гровера на базе QSDES,

3) Main.hs — запуск симуляции квантовой схемы.

Приведем содержимое указанных файлов.

QSDES.HS

1 module QSDES where

2 -- Модуль квантовой реализации схемы шифрования SDES

4 import Quipper

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

5 import QuipperLib.Simulation

6 import System.Random

7 import Quipper.Printing

8 import Quipper.QData

10 --Суммирование с ключом

11 sum_qubit :: ([Qubit], [Qubit]) -> Circ [Qubit]

12 sum_qubit ([k0, k1, k2, k3], [x0, x1, x2, x3]) = do

qnot_at x0 ‘controlled‘ [k0]

qnot_at x1 ‘controlled‘ [k1]

qnot_at x2 ‘controlled‘ [k2]

qnot_at x3 ‘controlled‘ [k3]

return [x0, x1, x2, x3]

-- S0

s0_box :: ([Qubit], [Qubit]) -> Circ [Qubit]

s0_box ([x0, x1, x2, x3], [s0, s1])

= do

comment "S0_box"

qnot_at s0 ‘controlled‘ [x3]

qnot_at s0 ‘controlled‘ [x0, x1, x2, x3]

qnot_at s0 ‘controlled‘ [x0, x2]

x0 <- gate_X x0

qnot_at s0 ‘controlled‘ [x0, x1]

x2 <- gate_X x2

qnot_at s1 ‘controlled‘ [x0, x2]

x0 <- gate_X x0

qnot_at s1 ‘controlled‘ [x0, x1, x2, x3]

x1 <- gate_X x1

qnot_at s1 ‘controlled‘ [x0, x1]

x3 <- gate_X x3

qnot_at s1 ‘controlled‘ [x0, x3]

x1 <- gate_X x1

x2 <- gate_X x2

x3 <- gate_X x3

return [s0, s1]

-- S1

s1_box :: ([Qubit], [Qubit]) -> Circ [Qubit]

s1_box ([x0, x1, x2, x3], [s2, s3])

= do

comment "S1_box"

qnot_at s2 ‘controlled‘ [x1]

qnot_at s3 ‘controlled‘ [x0, x2, x3]

x3 <- gate_X x3

qnot_at s3 ‘controlled‘ [x0, x3]

qnot_at s2 ‘controlled‘ [x0, x3]

x1 <- gate_X x1

qnot_at s2 ‘controlled‘ [x0, x1, x2, x3]

qnot_at s3 ‘controlled‘ [x2, x3]

x2 <- gate_X x2

x3 <- gate_X x3

qnot_at s2 ‘controlled‘ [x2, x3]

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

x0 <- gate_X x0

x1 <- gate_X x1

qnot_at s3 ‘controlled‘ [x0, x1, x3]

x0 <- gate_X x0

x2 <- gate_X x2

return [s2, s3]

----------------------1 раунд----------------------

round1 :: ([Qubit], [Qubit]) -> Circ [Qubit]

round1 ([k0, k1, k2, k3, k4, k5, k6, k7, k8, k9], [x0, x1, x2, x3, x4, x5, x6, x7]) = do

comment "ROUND_1"

[x6, x3, x7, x4] <- sum_qubit ([k0, k6, k8, k3], [x6, x3, x7, x4])

[x0, x1] <- s0_box ([x6, x3, x7, x4], [x0, x1])

[x6, x3, x7, x4] <- sum_qubit ([k0, k6, k8, k3], [x6, x3, x7, x4])

[x7, x4, x6, x3] <- sum_qubit ([k7, k2, k9, k5], [x7, x4, x6, x3])

[x2, x5] <- s1_box ([x7, x4, x6, x3], [x2, x5])

[x7, x4, x6, x3] <- sum_qubit ([k7, k2, k9, k5], [x7, x4, x6, x3])

return [x0, x1, x2, x3, x4, x5, x6, x7]

----------------------2 раунд----------------------

round2 :: ([Qubit], [Qubit]) -> Circ [Qubit]

round2 ([k0, k1, k2, k3, k4, k5, k6, k7, k8, k9], [x0, x1, x2, x3, x4, x5, x6, x7]) = do

comment "ROUND_2"

[x0, x1, x5, x2] <- sum_qubit ([k7, k2, k5, k4], [x0, x1, x5, x2])

[x6, x3] <- s0_box ([x0, x1, x5, x2], [x6, x3])

[x0, x1, x5, x2] <- sum_qubit ([k7, k2, k5, k4], [x0, x1, x5, x2])

[x5, x2, x0, x1] <- sum_qubit ([k9, k1, k8, k0], [x5, x2, x0, x1])

[x4, x7] <- s1_box ([x5, x2, x0, x1], [x4, x7])

[x5, x2, x0, x1] <- sum_qubit ([k9, k1, k8, k0], [x5, x2, x0, x1])

return [x0, x1, x2, x3, x4, x5, x6, x7]

-- Схема QSDES ("прямая").

sdes :: ([Qubit], [Qubit]) -> Circ ([Qubit], [Qubit])

sdes (key, plaintext) = do

let [k0, k1, k2, k3, k4, k5, k6, k7, k8, k9] = key

let [x0, x1, x2, x3, x4, x5, x6, x7] = plaintext

100

101

comment_with_label "Key"

102

(k0, k1, k2, k3, k4, k5, k6, k7, k8, k9)

103

("k0", "k1", "k2", "k3", "k4", "k5", "k6", "k7", "k8", "k9")

104

105

comment_with_label "Plaintext"

106

(x0, x1, x2, x3, x4, x5, x6, x7)

107

("x0", "x1", "x2", "x3", "x4", "x5", "x6", "x7")

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

108

109

[x0, x1, x2, x3, x4, x5, x6, x7] <- round1 ([k0, k1, k2, k3, k4, k5, k6, k7, k8, k9],

[x0, x1, x2, x3, x4, x5, x6, x7])

110

[x0, x1, x2, x3, x4, x5, x6, x7] <- round2 ([k0, k1, k2, k3, k4, k5, k6, k7, k8, k9],

[x0, x1, x2, x3, x4, x5, x6, x7])

111

112

swap x6 x0

113

swap x3 x1

114

swap x4 x2

115

swap x5 x7

116

117

return ([k0, k1, k2, k3, k4, k5, k6, k7, k8, k9], [x0, x1, x2, x3, x4, x5, x6, x7])

118

119 -- Схема QSDES ("обращенная").

120 sdes_reverse :: ([Qubit], [Qubit]) -> Circ ([Qubit], [Qubit])

121 sdes_reverse = reverse_generic_endo sdes

122

123 -- Тестовая схема QSDES с ключом, приводимым в суперпозицию.

124 -- Используется для теста № 2.

125 sdes_key_superposition :: [Bool] -> Circ ([Qubit], [Qubit])

126 sdes_key_superposition plaintext = do

127

key_in_superposition <- qinit (replicate 10 False)

128

mapUnary hadamard key_in_superposition

129

plaintext <- qinit plaintext

130

(key, cyphertext) <- sdes (key_in_superposition, plaintext)

131

return (key, cyphertext)

GROVER.HS

1 module Grover where

2 -- Алгоритм Гровера для QSDES

4 import Quipper

5 import Quipper.QData

6 import QSDES

7 -- Оракул для QSDES.

8 sdes_oracle :: ([Qubit], [Qubit], [Bool], Qubit) -> Circ Qubit

9 sdes_oracle (key, plaintext, cyphertext_bool, oracle) = do

(key, cyphertext) <- sdes (key, plaintext)

qnot_at oracle ‘controlled‘ cyphertext .==. cyphertext_bool

(key, plaintext) <- sdes_reverse (key, cyphertext)

return oracle

14 -- Схема inversion about the mean или Conditional Phase Flip (CPF)

15 inversion_about_mean ::

[Qubit] -> Circ [Qubit]

16 inversion_about_mean top_qubits = do

comment "start inversion about mean"

mapUnary hadamard top_qubits

mapUnary gate_X top_qubits

let pos = (length top_qubits) - 1

let target_qubit = top_qubits !! pos

let controlled_qubit = take pos top_qubits

ЖЭТФ, вып. 1

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

hadamard_at target_qubit

qnot_at target_qubit ‘controlled‘ controlled_qubit

hadamard_at target_qubit

mapUnary gate_X top_qubits

mapUnary hadamard top_qubits

comment "end inversion about mean"

return top_qubits

-- Алгоритм Гровера для QSDES

grover_search_circuit_sdes :: (Int, [Bool], [Bool]) -> Circ ([Bit], Bit)

grover_search_circuit_sdes (iterations_num, plaintext, cyphertext) = do

key <- qinit (replicate 10 False)

plaintext <- qinit plaintext

oracle <- qinit True

mapUnary hadamard key

hadamard_at oracle

-- Начало итераций Гровера

let index = iterations_num

for 1 (index) 1 $ \i -> do

comment "start grover iteration"

oracle <- sdes_oracle (key, plaintext, cyphertext, oracle)

key <- inversion_about_mean key

comment "after grover iteration"

endfor

-- Измерение кубитов, возвращение результата.

hadamard_at oracle

(key, oracle) <- measure (key, oracle)

--cdiscard oracle

return (key, oracle)

MAIN.HS

1 module Main where

2 -- Основной модуль. Запуск примеров.

4 import System.Random

5 import Data.Time

6 import Quipper

7 import Quipper.Printing

8 import QuipperLib.Simulation

9 import Quipper.QData

10 import QSDES

11 import Grover

13 -- ЗАПУСК ПРОГРАММЫ

14 main :: IO ()

15 --main = test1_circuit

16 main = test3_exec --25 итераций Гровера,выведет распределение ключей.

18 -- Тест функциональности. Проверка правильности составления схемы.

19 test1_circuit :: IO ()

20 test1_circuit = do

ЖЭТФ, том 155, вып. 1, 2019

Применение квантового алгоритма Гровера. ..

putStrLn "QSDES functionality test:"

print_generic GateCount sdes

((replicate 10 qubit),(replicate 8 qubit))

print_generic PDF sdes ((replicate 10 qubit),(replicate 8 qubit))

test1_exec :: IO ()

test1_exec = do

putStrLn "QSDES functionality test:"

print_generic GateCount sdes

((replicate 10 qubit),(replicate 8 qubit))

g <- newStdGen

print $ run_generic g (0.0 :: Double) sdes ([True,True,False,False,False,True,

True,True,True,False], [False,False,True,False,True,False,False,False])

print $ run_generic g (0.0 :: Double) sdes ([True,True,False,False,False,True,True,

True,True,False],

[True,False,False,False,True,True,False,True])

print $ run_generic g (0.0 :: Double) sdes ([True,True,False,False,False,True,True,

True,True,False],

[True,True,True,True,False,False,True,False])

print $ run_generic g (0.0 :: Double) sdes ([True,True,False,False,False,True,True,

True,True,False],

[False,True,False,True,False,True,True,True])

-- Тест схемы при приведении ключевых кубитов в суперпозицию.

test2_circuit :: IO ()

test2_circuit = do

putStrLn "QSDES results when key is in superposition:"

print_generic PDF (sdes_key_superposition [True,False,False,True,True,False,True,False])

test2_exec :: IO ()

test2_exec = do

putStrLn "QSDES results when key is in superposition:"

-- t1 <- getZonedTime

-- putStrLn $ formatTime defaultTimeLocale "%FT%T%z" t1

g <- newStdGen

print $ sim_generic undefined (sdes_key_superposition

([True,False,False,True,True,False,True,False]))

-- t2 <- getZonedTime

-- putStrLn $ formatTime defaultTimeLocale "%FT%T%z" t2

-- Поиск ключа по паре открытого и закрытого текстов.

-- Пример с одним подходящим ключом.

test3_circuit :: IO()

test3_circuit = do

putStrLn "Quantum exhaustive key search (1 key):"

let parameters = (25,[False,False,False,True,False,False,False,False],

[False,False,True,True,False,False,True,True])

print_generic GateCount (grover_search_circuit_sdes parameters)

-- print_generic PDF (grover_search_circuit_sdes parameters)

test3_exec :: IO()

test3_exec = do

putStrLn "Quantum exhaustive key search (1 key):"

startTime <- getCurrentTime

let parameters = (25,[False,False,False,True,False,False,False,False],

[False,False,True,True,False,False,True,True]) -- O.T.,C.T.

Д. В. Денисенко, М. В. Никитенкова

ЖЭТФ, том 155, вып. 1, 2019

g <- newStdGen

-- print $ run_generic g (0.0 :: Double) (grover_search_circuit_sdes parameters)

print_generic GateCount

(grover_search_circuit_sdes parameters)

print $ sim_generic undefined (grover_search_circuit_sdes parameters)

stopTime <- getCurrentTime

let deltaTime = show $ diffUTCTime stopTime startTime

putStrLn deltaTime

-- Поиск ключа по паре открытого и закрытого текстов.

-- Пример с двумя подходящими ключами.

test4_circuit :: IO()

test4_circuit = do

putStrLn "Quantum exhaustive key search (2 keys):"

let parameters = (18,[True,False,True,False,False,True,False,True],

[False,False,True,True,False,True,True,False])

print_generic GateCount (grover_search_circuit_sdes parameters)

-- print_generic PDF (grover_search_circuit_sdes parameters)

test4_exec :: IO()

test4_exec = do

putStrLn "Quantum exhaustive key search (2 keys):"

startTime <- getCurrentTime

let parameters = (18,[True,False,True,False,False,True,False,True],

[False,False,True,True,False,True,True,False])

print_generic GateCount (grover_search_circuit_sdes parameters)

g <- newStdGen

--print $ run_generic g (0.0 :: Double) (grover_search_circuit_sdes parameters)

print $ sim_generic undefined (grover_search_circuit_sdes parameters)

stopTime <- getCurrentTime

let deltaTime = show $ diffUTCTime stopTime startTime

putStrLn deltaTime

ЛИТЕРАТУРА

https://ai.googleblog.com/2018/03/a-preview-of-bri-

stlecone-googles-new.html.

1. H. Bernien, S. Schwartz, A. Keesling, H. Levine, and

7. P. W. Shor, J. Comput. 26, 1484 (1997).

A. Omran, Nature 551, 579 (2017); DOI:10.1038/

nature24622; arXiv:1707.04344.

8. D. R. Simon, SIAM J. Comput. 26, 1474 (1997).

2. J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis,

9. M. Kaplan, G. Leurent, A. Leverrier et al., Lect.

and P. Becker, Nature 551, 601 (2017); DOI:10.1038/

Notes Comp. Sci., Vol. 9815, Berlin, Springer-Verlag

nature24654; arXiv:1708.01044.

(2016).

3. https://www.ibm.com/blogs/research/2017/11/the-

10. L. K. Grover, Proc. STOC 1996, in ed. by G. L. Mil-

future-is-quantum/.

ler, ACM (1996), p. 212.

4. M. Veldhorst, H. G. J. Eenink, C. H. Yang, and

11. G. Brassard, P. Hoyer, M. Mosca et al., arXiv:

A. S. Dzurak, Nature Comm.

1766

(2017);

quant-ph/0005055.

DOI:10.1038/s41467-017-01905-6; https://doi.org/

10.1038/s41467-017-01905-6.

12. М. Нильсен, И. Чанг, Квантовые вычисления и

квантовая информация, Мир, Москва (2006).

5. C. S. Calude and E. Calude, arXiv:1712.01356v1.

13. M. Almazrooie, A. Samsudin, R. Abdullah, and

6. J. Kelly, A Preview of Bristlecone, Google’s New

K. N. Mutter, SpringerPlus 5, 1494 (2016); DOI:

Quantum Processor. Quantum AI Lab, 05.03.2018,

10.1186/s40064-016-3159-4.