ЖЭТФ, 2019, том 155, вып. 6, стр. 999-1008
© 2019
О РЕАЛИЗАЦИИ ПОДСТАНОВОК В ВИДЕ КВАНТОВЫХ СХЕМ
БЕЗ ИСПОЛЬЗОВАНИЯ ДОПОЛНИТЕЛЬНЫХ КУБИТОВ
Д. В. Денисенко*
Московский государственный технический университет им. Н. Э. Баумана
105005, Москва, Россия
Поступила в редакцию 23 января 2019 г.,
после переработки 27 января 2019 г.
Принята к публикации 29 января 2019 г.
Представлен способ реализации подстановок (S-боксов) в виде квантовых схем без использования допол-
нительных кубитов. Представлены квантовые схемы, реализующие подстановки блочного шифра ГОСТ
Р 34.12-2015 «Магма» на четырех логических кубитах, а также описания квантовых схем, реализую-
щих S-боксы блочных шифров AES и ГОСТ Р 34.12-2015 «Кузнечик» на восьми логических кубитах —
минимальные по количеству логических кубитов квантовые схемы.
DOI: 10.1134/S004445101906004X
«Bristlecone» позволит продемонстрировать «кван-
товое превосходство» [8,9].
В конце 2018 г. опубликован отчет [10], в кото-
1. ВВЕДЕНИЕ
ром авторы резюмируют текущее состояние уровня
развития квантовых технологий в области кванто-
Теория квантовых вычислений стремительно
вых вычислений. В частности, сделан вывод о том,
развивается с конца прошлого века. Построен
что уровень прогресса в гейтовой модели квантовых
ряд формальных моделей квантовых вычислений,
вычислений можно отслеживать по ключевым па-
согласно которым квантовая природа объектов, с
раметрам, определяющим качество квантового про-
использованием которых проводятся вычисления,
цессора: уровню ошибок при выполнении базовых
теоретически позволяет более эффективно решать
операций с одним и двумя кубитами, глубине взаи-
некоторые вычислительные задачи [1-3].
мосвязи кубитов в одном аппаратном модуле. В от-
В настоящее время фундаментальные исследова-
чете отмечено, что «квантовое превосходство» (ре-
ния направлены на создание квантовых симулято-
шение задачи, которое трудно получить на класси-
ров и квантовых процессоров: в 2017 г. группа физи-
ческом компьютере, независимо от того, имеет ли
ков заявила о создании программируемого 51-кубит-
эта задача практическую полезность) еще не про-
ного квантового симулятора [4], разработан 53-ку-
демонстрировано, при этом опубликованы оценки
битный симулятор, основанный на ионах в оптиче-
необходимого количества ресурсов квантового вы-
ских ловушках [5]. В компании IBM успешно ис-
числителя для решения некоторых задач, в том чис-
пытан прототип 50-кубитного квантового процес-
ле связанных с реализацией криптографических ал-
сора [6], а в декабре 2017 г. опубликована статья
горитмов в виде квантовых схем.
[7], в которой представлен проект масштабируемо-
Данная работа является развитием работ [11,12],
го кремниевого квантового процессора, представля-
в которых рассмотрена задача поиска секретного
ющего собой массив из 24 × 20 = 480 кубитов. В
ключа алгоритмов шифрования с помощью кванто-
январе 2018 г. компания Intel сообщила о созда-
вого алгоритма Гровера. В работе [11] представле-
нии 49-кубитного сверхпроводящего квантового чи-
на минимальная по количеству логических кубитов
па «Tangle Lake». В марте 2018 г. компания Google
квантовая схема, реализующая поиск ключа SDES
объявила о создании 72-кубитного квантового про-
по одной паре открытого и шифрованного текстов:
цессора «Bristlecone». В компании надеются, что
для реализации функции зашифрования SDES тре-
буется 18 кубитов, так как она представляет собой
* E-mail: DenisenkoDV@bmstu.ru
8 булевых функций fi: V10 × V8 → V1, i ∈ 1, 8, зави-
999
Д. В. Денисенко
ЖЭТФ, том 155, вып. 6, 2019
сящих от 18 булевых переменных. Для поиска клю-
Требуется для унитарного оператора U ∈ C2n,2n,
ча SDES алгоритмом Гровера потребуется еще один
соответствующего
выбранной
подстановке
флаговый кубит, в работе [11] представлена соответ-
s ∈ S(Vn), найти представление
ствующая квантовая схема на 19 логических куби-
UN-1UN-2 . . .U1U = I.
тах, т. е. показано, что минимальная оценка коли-
чества кубитов для поиска ключа SDES квантовым
Чтобы построить квантовую схему, реализую-
алгоритмом Гровера (18 + 1 = 19 кубитов) дости-
щую заданную подстановку s ∈ S(Vn) без использо-
жима. Результаты данной работы показывают, что
вания дополнительных кубитов, достаточно выпол-
заявленное в [10,13,14] количество логических куби-
нить следующие действия.
тов, требуемое для реализации криптографических
1. Найти унитарную матрицу U
∈ C2n,2n , со-
алгоритмов в виде квантовых схем, завышено.
ответствующую выбранной подстановке s ∈ S(Vn).
В данной работе представлен алгоритм построе-
Матрица U — подстановочная матрица в простран-
ния квантовых схем, реализующих подстановки
стве V2n , т. е. состоит только из нулей и единиц.
(S-боксы — базовые структурные элементы крипто-
2. Представить матрицу U ∈ C2n,2n в виде про-
графических алгоритмов шифрования и хэш-функ-
изведения двухуровневых матриц
ций) без использования дополнительных логических
кубитов. Представлены квантовые схемы S-боксов
U =V1...Vk,
блочного шифра ГОСТ Р 34.12-2015 «Магма», а так-
же распределение квантовых вентилей в квантовых
где Vi ∈ C2n,2n — двухуровневые унитарные мат-
схемах, реализующих S-боксы ГОСТ Р 34.12-2015
рицы (см. [20], разд. 4.5.1), i ∈ 1, k, k ≤ (2n - 1) +
«Кузнечик» и AES без использования дополнитель-
+(2n -2)+. . .+1 =2n(2n-1)2 (сумма арифметической
ных кубитов. Для реализации S-боксов блочного
прогрессии). Любая унитарная матрица, действую-
шифра ГОСТ Р 34.12-2015 «Магма» достаточно
щая на n кубитов, может быть разложена в произ-
4 логических кубита, а для реализации S-боксов
ведение не более чем 2n-1(2n - 1) двухуровневых
ГОСТ Р 34.12-2015 «Кузнечик» и AES достаточно 8
унитарных матриц.
логических кубитов.
3. В разд. 4.5.2 работы [20] показано, что лю-
Полученные результаты позволяют сделать но-
бую двухуровневую унитарную матрицу можно лег-
вый вывод о минимальных по количеству логи-
ко реализовать с помощью однокубитовых опера-
ческих кубитов квантовых схемах, реализующих
торов и CNOT. Таким образом, построив кванто-
криптографические алгоритмы AES [15], ГОСТ Р
вые схемы, реализующие двухуровневые унитарные
34.12-2015 [16], SHA-2 [17], SHA-3 [18] и ГОСТ Р
матрицы V1 . . . Vk, получим квантовую схему, реали-
34.11-2012 [19] (см. табл. 3, 4 ниже). Представленные
зующую оператор U, соответствующий выбранной
на рис. 1-8 квантовые схемы могут быть полезны
подстановке s ∈ S(Vn).
при экспериментальном тестировании и верифика-
Заметим, что двухуровневые унитарные матри-
ции работы физических реализаций квантовых вы-
цы представляются в виде квантовых схем неодно-
числительных устройств.
значно. При реализации матриц Vi и Vi+1, i ∈ 1, k,
возможно последовательное применение взаимно
обратных квантовых вентилей. Перебрав все воз-
2. ПОСТРОЕНИЕ КВАНТОВОЙ СХЕМЫ,
можные реализации двухуровневых унитарных мат-
РЕАЛИЗУЮЩЕЙ ПРОИЗВОЛЬНУЮ
риц V1 . . . Vk, можно найти минимальную квантовую
ПОДСТАНОВКУ s ∈ S(Vn) БЕЗ
схему, реализующую оператор U = V1 . . . Vk, кото-
ИСПОЛЬЗОВАНИЯ ДОПОЛНИТЕЛЬНЫХ
рый соответствует подстановке s ∈ S(Vn).
КУБИТОВ
Построение квантовой схемы по произвольному
Алгоритм построения квантовой схемы, соот-
унитарному оператору U
∈ C2n,2n реализовано в
ветствующей произвольному унитарному операто-
квантовом симуляторе Quipper (см. [21-23]), причем
ру, описан в работе [20], разд. 4.5.
в реализации не учитывается возможность оптими-
Определение 1. Пусть N = 2n, n ∈ N, и e1,
зации квантовых схем путем удаления последова-
e2, . . . , eN — базис векторного пространства LCN над
тельных взаимно обратных квантовых вентилей.
полем комплексных чисел C. Унитарные матрицы
В разд.
3
представлены оптимизированные
U ∈ C2n,2n, нетривиально действующие не более чем
квантовые схемы, реализующие S-боксы ГОСТ
на два базисных вектора e1, e2, . . . , eN , называются
Р 34.12-2015 «Магма», распределения квантовых
двухуровневыми унитарными матрицами.
вентилей в оптимизированных квантовых схемах,
1000
ЖЭТФ, том 155, вып. 6, 2019
О реализации подстановок в виде квантовых схем...
Таблица 1. Распределение количества квантовых вентилей в квантовых схемах на рис. 1-8
Распределение количества
Распределение количества
Подстановка
Подстановка
квантовых вентилей
квантовых вентилей
1: «X, arity 1» controls 0+3
1: «X, arity 1» controls 0+3
4: «X, arity 1» controls 1+2
2: «X, arity 1» controls 1+2
4: «X, arity 1» controls 2+1
4: «X, arity 1» controls 2+1
π0
π1
4: «X, arity 1» controls 3
2: «X, arity 1» controls 3
20: «not, arity 1» controls 1
20: «not, arity 1» controls 1
Total gates: 33
Total gates: 29
1: «X, arity 1» controls 0+3
1: «X, arity 1» controls 0+3
4: «X, arity 1» controls 1+2
3: «X, arity 1» controls 1+2
5: «X, arity 1» controls 2+1
5: «X, arity 1» controls 2+1
π2
π3
3: «X, arity 1» controls 3
4: «X, arity 1» controls 3
24: «not, arity 1» controls 1
16: «not, arity 1» controls 1
Total gates: 37
Total gates: 29
1: «X, arity 1» controls 0+3
1: «X, arity 1» controls 0+3
4: «X, arity 1» controls 1+2
4: «X, arity 1» controls 1+2
3: «X, arity 1» controls 2+1
6: «X, arity 1» controls 2+1
π4
π5
3: «X, arity 1» controls 3
2: «X, arity 1» controls 3
20: «not, arity 1» controls 1
22: «not, arity 1» controls 1
Total gates: 31
Total gates: 35
1: «X, arity 1» controls 0+3
1: «X, arity 1» controls 0+3
3: «X, arity 1» controls 1+2
4: «X, arity 1» controls 1+2
6: «X, arity 1» controls 2+1
4: «X, arity 1» controls 2+1
π6
π7
3: «X, arity 1» controls 3
4: «X, arity 1» controls 3
18: «not, arity 1» controls 1
18: «not, arity 1» controls 1
Total gates: 31
Total gates: 31
Таблица 2. Распределение количества квантовых вентилей в квантовых схемах, реализующих S-боксы ГОСТ
Р 34.12-2015 «Кузнечик» и AES на 8 логических кубитах
1: «X, arity 1» controls 0+7
1: «X, arity 1» controls 0+7
8: «X, arity 1» controls 1+6
8: «X, arity 1» controls 1+6
28: «X, arity 1» controls 2+5
28: «X, arity 1» controls 2+5
56: «X, arity 1» controls 3+4
56: «X, arity 1» controls 3+4
70: «X, arity 1» controls 4+3
70: «X, arity 1» controls 4+3
πKuznechik
πAES
54: «X, arity 1» controls 5+2
55: «X, arity 1» controls 5+2
27: «X, arity 1» controls 6+1
26: «X, arity 1» controls 6+1
6: «X, arity 1», controls 7
7: «X, arity 1», controls 7
1020: «not, arity 1», controls 1
958: «not, arity 1», controls 1
Total gates: 1270
Total gates: 1209
1001
Д. В. Денисенко
ЖЭТФ, том 155, вып. 6, 2019
Рис. 1. Квантовая схема, реализующая подстановку π0 = (12, 4, 6, 2, 10, 5, 11, 9, 14, 8, 13, 7, 0, 3, 15, 1)
Рис. 2. Квантовая схема, реализующая подстановку π1 = (6, 8, 2, 3, 9, 10, 5, 12, 1, 14, 4, 7, 11, 13, 0, 15)
Рис. 3. Квантовая схема, реализующая подстановку π2 = (11, 3, 5, 8, 2, 15, 10, 13, 14, 1, 7, 4, 12, 9, 6, 0)
Рис. 4. Квантовая схема, реализующая подстановку π3 = (12, 8, 2, 1, 13, 4, 15, 6, 7, 0, 10, 5, 3, 14, 9, 11)
Рис. 5. Квантовая схема, реализующая подстановку π4 = (7, 15, 5, 10, 8, 1, 6, 13, 0, 9, 3, 14, 11, 4, 2, 12)
Рис. 6. Квантовая схема, реализующая подстановку π5 = (5, 13, 15, 6, 9, 2, 12, 10, 11, 7, 8, 1, 4, 3, 14, 0)
Рис. 7. Квантовая схема, реализующая подстановку π6 = (8, 14, 2, 5, 6, 9, 1, 12, 15, 4, 11, 0, 13, 10, 3, 7)
Рис. 8. Квантовая схема, реализующая подстановку π7 = (1, 7, 14, 13, 0, 5, 8, 3, 4, 15, 10, 6, 9, 12, 11, 2)
1002
ЖЭТФ, том 155, вып. 6, 2019
О реализации подстановок в виде квантовых схем...
Таблица 3. Минимальное количество логических
реализующих S-боксы ГОСТ Р 34.12-2015 и AES.
кубитов, требуемое для реализации алгоритмов
В Приложении A представлены соответствующие
ГОСТ Р 34.12-2015 и AES
программные реализации для квантового симуля-
тора Quipper. В Приложении B подробно разобран
пример построения квантовой схемы, реализующей
Минимальное
подстановку s ∈ S(V4).
количество
3. КВАНТОВЫЕ СХЕМЫ S-БОКСОВ ГОСТ Р
Алгоритм
кубитов для
34.12-2015 И AES
реализации в виде
На рис.
1-8 представлены квантовые схемы,
квантовой схемы
реализующие S-боксы ГОСТ Р 34.12-2015 «Маг-
ма». Распределение количества квантовых венти-
ГОСТ Р 34.12-2015 «Магма»
256 + 64 = 320
лей, необходимых для реализации S-боксов ГОСТ
ГОСТ Р 34.12-2015 «Кузнечик»
256 + 128 = 384
Р 34.12-2015 «Магма», представлено в табл. 1. Рас-
пределение количества квантовых вентилей, необхо-
AES-128
128 + 128 = 256
димых для реализации S-боксов ГОСТ Р 34.12-2015
AES-192
192 + 128 = 320
«Кузнечик» и AES, представлено в табл. 2.
Отметим, что в работах [13, 14] для реализации
AES-256
256 + 128 = 384
S-бокса AES требуется 40 логических кубитов, 3584
T-вентилей и 4569 вентилей Клиффорда (множе-
Таблица 4. Минимальное количество логических
ство вентилей {T, H, S, CNOT}, см. [20,24]). В ра-
кубитов, требуемое для реализации алгоритмов
боте [13] описан способ построения квантовой схе-
SHA-2, SHA-3 и ГОСТ Р 34.11-2012
мы, реализующей S-бокс AES на 9 логических ку-
Минимальное
битах, но при этом потребуется 9695 T-вентилей и
12631 вентилей Клиффорда. В табл. 2 показано, что
количество кубитов
Алгоритм
для реализации S-бокса AES на 8 логических куби-
для реализации в
тах требуется 958 вентилей CNOT и 251 обобщен-
виде квантовой схемы
ный вентиль CNOT(C|t) (см. [20, 25], управляемый
кубит с номером t контролируется множеством ку-
SHA-2 (224, 256)
512
битов C). Обобщенные вентили CNOT(C|t) можно
SHA-2 (384, 512)
1024
реализовать без использования дополнительных ку-
битов (см. [20], с. 184), но при этом для их реализа-
SHA-3
1600
ции может потребоваться значительное количество
ГОСТ Р 34.11-2012
1024
T-вентилей и вентилей Клиффорда.
4. ЗАКЛЮЧЕНИЕ
+32 n2 -256 n+8 квантовых вентилей (см. [27]), а для
Полученные результаты позволяют сделать вы-
реализации всего блочного шифра E: Vn ×Vm → Vm
вод о том, что для реализации блочных шифров
потребуется n + m + 1 логических кубитов.
E : Vn × Vm → Vm с ключом K ∈ Vn и блоками
Минимальное количество логических кубитов,
открытого и шифрованного текстов P, C ∈ Vm, в
требуемое для реализации алгоритмов шифрования
структуре которых отсутствует операция сложения
ГОСТ Р 34.12-2015 и AES, представлено в табл. 3,
по модулю 2t, t > 1, достаточно n + m логических
и оно значительно меньше, чем значения, приведен-
кубитов.
ные в работах [10, 13, 14].
При наличии возможности применения кван-
Кроме того, можно сделать вывод о том, что ми-
тового преобразования Фурье операцию модульно-
нимальное количество логических кубитов, необхо-
го сложения можно реализовать без использования
димое для реализации хэш-функций в виде кванто-
вспомогательных кубитов [26].
вых схем, определяется максимальной длиной внут-
Если же в структуре блочного шифра применя-
реннего состояния соответствующей хэш-функции.
ется модульное сложение, а возможность примене-
В табл. 4 представлены оценки минимального ко-
ния квантового преобразования Фурье отсутствует,
личества кубитов, достаточного для реализации
то для реализации операции P ⊞ K mod 2n может
хэш-функций SHA-2, SHA-3 и ГОСТ Р 34.11-2012
потребоваться один дополнительный кубит и23 n3 +
в виде квантовых схем.
1003
Д. В. Денисенко
ЖЭТФ, том 155, вып. 6, 2019
ПРИЛОЖЕНИЕ A
битов. Для того чтобы затем получить оптималь-
ные квантовые схемы, достаточно будет убрать па-
ры квантовых вентилей, реализующие тождествен-
Построение квантовых схем S-боксов c
помощью квантового симулятора Quipper
ные преобразования.
1. MAGMA.hs — строим квантовые схемы S-бок-
Приведем программные реализации, с помо-
сов ГОСТ Р 34.12-2015 «Магма».
щью которых можно построить неоптимальные
2. KUZNECHIK.hs — строим квантовую схему
квантовые схемы, реализующие S-боксы ГОСТ Р
S-бокса ГОСТ Р 34.12-2015 «Кузнечик».
34.12-2015 без использования дополнительных ку-
Приведем содержимое указанных файлов.
MAGMA.HS
1
import Quipper
2
import QuipperLib.Synthesis
3
import Quipper.Printing
4
import QuipperLib.Simulation
5
import Quipper.QData
6
import Quantum.Synthesis.Ring
7
import Quantum.Synthesis.Matrix
8
import Quantum.Synthesis.MultiQubitSynthesis
9
import System.Random
10
------------------------------------------------------------------------
11
--s = [12,4,6,2,10,5,11,9,14,8,13,7,0,3,15,1]
12
--s(x) = y; x.U = y;
13
opertor :: [Qubit] -> Circ [Qubit]
14
opertor (input)
= (exact_synthesis op) (input)
15
where
16
op :: Matrix (Ten_and Six) (Ten_and Six) DRComplex--DOmega
17
op = matrix
[[0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
18
[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],
19
[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0],
20
[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
21
[0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0],
22
[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],
23
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
24
[0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0]]
25
26
sub :: ([Qubit]) -> Circ ([Qubit])
27
sub (input) = do
28
let [q0, q1, q2, q3] = input
29
comment_with_label "input"
30
(q0, q1, q2, q3)
31
("s0", "s1", "s2", "s3")
32
[q0, q1, q2, q3] <- opertor ([q0, q1, q2, q3])
33
return ([q0, q1, q2, q3])
34
35
test1_circuit :: IO ()
36
test1_circuit = do
37
putStrLn "Substitution functionality test:"
38
--print_generic GateCount sub (replicate 4 qubit)
1004
ЖЭТФ, том 155, вып. 6, 2019
О реализации подстановок в виде квантовых схем...
39
--print_generic Preview sub (replicate 4 qubit)
40
--print_generic ASCII sub (replicate 4 qubit)
41
print_generic PDF sub (replicate 4 qubit)
42
43 test1_exec :: IO ()
44 test1_exec = do
45
putStrLn "Substitution functionality test:"
46
print_generic GateCount sub (replicate 4 qubit)
47
g <- newStdGen
48
print $ run_generic g (0.0 :: Double) sub ([False,False,False,False])
49
print $ run_generic g (0.0 :: Double) sub ([False,False,False,True])
50
print $ run_generic g (0.0 :: Double) sub ([False,False,True,False])
51
print $ run_generic g (0.0 :: Double) sub ([False,False,True,True])
52
print $ run_generic g (0.0 :: Double) sub ([False,True,False,False])
53
print $ run_generic g (0.0 :: Double) sub ([False,True,False,True])
54
print $ run_generic g (0.0 :: Double) sub ([False,True,True,False])
55
print $ run_generic g (0.0 :: Double) sub ([False,True,True,True])
56
print $ run_generic g (0.0 :: Double) sub ([True,False,False,False])
57
print $ run_generic g (0.0 :: Double) sub ([True,False,False,True])
58
print $ run_generic g (0.0 :: Double) sub ([True,False,True,False])
59
print $ run_generic g (0.0 :: Double) sub ([True,False,True,True])
60
print $ run_generic g (0.0 :: Double) sub ([True,True,False,False])
61
print $ run_generic g (0.0 :: Double) sub ([True,True,False,True])
62
print $ run_generic g (0.0 :: Double) sub ([True,True,True,False])
63
print $ run_generic g (0.0 :: Double) sub ([True,True,True,True])
64 -- | Run any of the above main functions:
65 main = do
66
test1_circuit
67
test1_exec
KUZNECHIK.HS
1 import Quipper
2 import QuipperLib.Synthesis
3 import Quipper.Printing
4 import QuipperLib.Simulation
5 import Quipper.QData
6 import Quantum.Synthesis.Ring
7 import Quantum.Synthesis.Matrix
8 import Quantum.Synthesis.MultiQubitSynthesis
9 import Data.Time
10 import System.Random
11 -----------------------------------------------------
12 main = do
13
g <- newStdGen
14
startTime <- getCurrentTime
15
let scheme = (exact_synthesis op)
16
--output of the quantum scheme to a text file for further optimization
17
print_generic ASCII scheme [qubit, qubit, qubit, qubit, qubit, qubit, qubit, qubit]
18
stopTime <- getCurrentTime
1005
Д. В. Денисенко
ЖЭТФ, том 155, вып. 6, 2019
19
let deltaTime = show $ diffUTCTime stopTime startTime
20
putStrLn deltaTime
21
print_generic GateCount scheme [qubit, qubit, qubit, qubit, qubit, qubit, qubit, qubit]
22
print $ run_generic g (0.0 :: Double) scheme ([False,False,False,False,False,False,False,
False])
23
print $ run_generic g (0.0 :: Double) scheme ([False,False,False,False,False,False,False,
True])
24
print $ run_generic g (0.0 :: Double) scheme ([True,True,True,True,True,True,True,True])
25
where
26
op :: Matrix (Times (Times Four Four) (Times Four Four)) (Times (Times Four Four)
(Times Four Four)) DRComplex --QRComplex--DOmega
--DRComplex
27
op = matrix [[ here insert the appropriate unitary matrix of size 256x256 ]]
ПРИЛОЖЕНИЕ B
Построение квантовой схемы, реализующей подстановку
π1 = (6, 8, 2, 3, 9, 10, 5, 12, 1, 14, 4, 7, 11, 13, 0, 15)
Построим квантовую схему, реализующую подстановку π1 = (6, 8, 2, 3, 9, 10, 5, 12, 1, 14, 4, 7,11, 13, 0, 15).
Подстановка π1 ∈ S(V4). Обозначим y = π1(x), x, y ∈ V4. Состояния |x〉, |y〉 представляют собой векторы-
столбцы из LC24, действие оператора U|x〉 = |y〉 представляет собой умножение вектора-столбца |x〉 на
матрицу U ∈ C24,24.
1. Подстановке π1 соответствует унитарная матрица
⎛
⎞
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
⎜
⎟
⎜0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0⎟
⎜
⎟
⎜
⎟
⎜0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜
⎟
⎜0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0⎟
⎜
⎟
⎜0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜
⎟
⎜1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0⎟
Uπ1 =
⎜
⎟
⎜
⎟
⎜0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜
⎟
⎜0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0⎟
⎜
⎟
⎜
⎟
⎜0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0⎟
⎜
⎟
⎜
⎟
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
⎜
⎟
⎜
⎟
⎝0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0⎠
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2. Матрицу Uπ1 можно представить в виде произведения двухуровневых унитарных матриц:
Uπ1 = V1 · V2 · V3 · V4 · V5 · V6 · V7 · V8 · V9.
В табл. 5 приведены двухуровневые матрицы
ствуют нетривиально, и квантовые схемы, реализу-
V1, . . . , V9, участвующие в разложении Uπ1 , состоя-
ющие двухуровневые матрицы V1, . . . , V9. Матрицы
ния s и t, на которые двухуровневые матрицы дей-
записаны в виде списка строк, каждая строка пред-
1006
ЖЭТФ, том 155, вып. 6, 2019
О реализации подстановок в виде квантовых схем...
Таблица 5. Представление матрицы Uπ1 в виде произведения двухуровневых матриц
s = |0110
V1 = {200, 4000, 2000, 1000, 800, 400, 8000, 100, 80, 40, 20, 10, 8, 4, 2, 1}
t = |0000
s = |0001
V2 = {8000, 80, 2000, 1000, 800, 400, 200, 100, 4000, 40, 20, 10, 8, 4, 2, 1}
t = |1000
s = |0100
V3 = {8000, 4000, 2000, 1000, 40, 400, 200, 100, 80, 800, 20, 10, 8, 4, 2, 1}
t = |1001
s = |0101
V4 = {8000, 4000, 2000, 1000, 800, 20, 200, 100, 80, 40, 400, 10, 8, 4, 2, 1}
t = |1010
s = |0110
V5 = {8000, 4000, 2000, 1000, 800, 400, 20, 100, 80, 40, 200, 10, 8, 4, 2, 1}
t = |1010
s = |0111
V6 = {8000, 4000, 2000, 1000, 800, 400, 200, 8, 80, 40, 20, 10, 100, 4, 2, 1}
t = |1100
s = |1001
V7 = {8000, 4000, 2000, 1000, 800, 400, 200, 100, 80, 2, 20, 10, 8, 4, 40, 1}
t = |1110
s = |1010
V8 = {8000, 4000, 2000, 1000, 800, 400, 200, 100, 80, 40, 2, 10, 8, 4, 20, 1}
t = |1110
s = |1011
V9 = {8000, 4000, 2000, 1000, 800, 400, 200, 100, 80, 40, 20, 8, 10, 4, 2, 1}
t = |1100
Рис. 9. Квантовая схема, реализующая подстановку π1 = (6, 8, 2, 3, 9, 10, 5, 12, 1, 14, 4, 7, 11, 13, 0, 15)
ставляет собой вектор vi ∈ V16, ||vi|| = 1, i ∈ 1, 16 и
ЛИТЕРАТУРА
записана в шестнадцатеричной системе счисления.
1. P. W. Shor, SIAM J. Comput. 26, 1484 (1997).
Поскольку |y〉 = U|x〉, |y〉 = V1 ·. . .·(V8 ·(V9 ·|x〉)),
квантовая схема, соответствующая Uπ1, имеет вид
2. L. K. Grover, in Proc. of STOC
1996, ed. by
приведенной на рис. 9.
G. L. Miller, ACM (1996), pp. 212-219.
После оптимизации квантовой схемы на рис. 9
получим квантовую схему на рис. 2.
3. D. R. Simon, SIAM J. Comput. 26, 1474 (1997).
1007
Д. В. Денисенко
ЖЭТФ, том 155, вып. 6, 2019
4.
H. Bernien, S. Schwartz, A. Keesling, H. Levine, and
15.
NIST, Specification for the Advanced Encryption
A. Omran, Nature 551, 579 (2017), DOI:10.1038/
Standart (AES), Federal Inf. Process. Stand. Publ.
nature24622; arXiv:1707.04344.
197 (2001).
5.
J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis,
16.
ГОСТ Р 34.12-2015, Информационные техноло-
and P. Becker, Nature 551, 601 (2017), DOI:10.1038/
гии. Защита информации. Блочные шифры.
nature24654; arXiv:1708.01044.
17.
NIST: Secure Hash Standard (SHS), FIPS PUB 180-4
6.
future-is-quantum/.
18.
SHA-3 Standard: Permutation-Based Hash and Ex-
7.
M. Veldhorst, H. G. J. Eenink, C. H. Yang, and
tendable-Output Functions, Federal Inf. Process.
A. S. Dzurak, Nature Comm.
8,
1766
(2017),
Stand. (NIST FIPS)
202
10.6028/NIST.FIPS.202.
10.1038/s41467-017-01905-6.
19.
ГОСТ Р 34.11-2012, Информационная техноло-
8.
C. S. Calude and E. Calude, arXiv:1712.01356v1.
гия. Криптографическая защита информации.
Функция хэширования.
9.
J. Kelly, A Preview of Bristlecone, Google’s New
Quantum Processor, Quantum AI Lab, 05.03.2018,
20.
M. A. Nielsen and I. L. Chuang, Quantum Compu-
tation and Quantum Information, Cambridge Univ.
bristlecone-googles-new.html.
Press, Cambridge (2010).
10.
Quantum Computing: Progress and Prospects, Natio-
21.
nal Academies of Sciences, Engineering, and Medicine
mathstat.dal.ca/˜selinger/quipper/.
(2018), National Acad. Press, Washington, DC,
22.
A. S. Green, P. L. Lumsdaine, N. J. Ross, P. Selinger,
and B. Valiron, arXiv:1304.5485v1.
11.
Д. В. Денисенко, М. В. Никитенкова, ЖЭТФ 155,
32 (2019).
23.
S. Siddiqui, M. J. Islam, and O. Shehab, arXiv:1406.
4481v2 [quant-ph].
12.
Д. В. Денисенко, Г. Б. Маршалко, М. В. Никитен-
кова, В. И. Рудской, В. А. Шишкин, ЖЭТФ 155,
24.
G. H. Low, V. Kliuchnikov, and L. Schaeffer, https://
645 (2019).
arxiv.org/abs/1812.00954v1.
13.
M. Grassl, B. Langenberg, M. Roetteler, and
25.
A. Younes and J. Miller, arXiv:quant-ph/0304099v1.
R. Steinwandt, arXiv:1512.04965v1.
26.
14.
P. Kim, D. Han, and K. C. Jeong, Quant. Inf. Process.
0008033.
2107-3.
27.
P. Kaye, arxiv.org/abs/quant-ph/0408173.
1008
