ЖЭТФ, 2020, том 157, вып. 5, стр. 771-776
© 2020
ПРИМЕНЕНИЕ АЛГОРИТМА КВАНТОВОГО ПЕРЕЧИСЛЕНИЯ
ДЛЯ ОЦЕНКИ ВЕСА БУЛЕВЫХ ФУНКЦИЙ В КВАНТОВОМ
СИМУЛЯТОРЕ QUIPPER
Д. В. Денисенко*
Московский государственный технический университет им. Н. Э. Баумана
105005, Москва, Россия
Поступила в редакцию 26 октября 2019 г.,
после переработки 3 декабря 2019 г.
Принята к публикации 10 декабря 2019 г.
Квантовое перечисление — одна из известных задач, в которых проявляется ускорение вычислений за
счет использования квантового параллелизма. В различных работах можно найти разные оценки вероят-
ности успеха алгоритма квантового перечисления. Кроме того, в одних источниках в алгоритме кванто-
вого перечисления используют прямое квантовое преобразование Фурье, в других — обратное квантовое
преобразование Фурье. В данной работе представлены результаты математического моделирования при-
менения алгоритма квантового перечисления для оценки веса некоторых булевых функций, зависящих
от шести переменных, в квантовом симуляторе Quipper с целью проверки известных оценок вероятности
успеха алгоритма квантового перечисления.
DOI: 10.31857/S0044451020050016
бота [7], согласно которой с помощью 54-кубитного
процессора «Sycamore» продемонстрировано суще-
1. ВВЕДЕНИЕ
ственное ускорение в решении одной специальной
Квантовые вычисления — одно из направлений
задачи: вычисление 1 млн раз 53-кубитной кванто-
квантовых технологий, стремительно развивающих-
вой схемы на квантовом процессоре «Sycamore» за-
ся с конца XX века. В настоящее время фунда-
нимает около 200 с, в то время как решение ана-
ментальные исследования в области квантовых вы-
логичной задачи на классическом суперкомпьютере,
числений направлены на создание квантовых симу-
по оценкам авторов, займет не менее 10000 лет.
ляторов и квантовых процессоров: в 2017 г. груп-
Одной из задач, в которых проявляется ускоре-
па физиков заявила о создании программируемого
51-кубитного квантового симулятора [1], разработан
ние вычислений за счет использования квантового
параллелизма, является задача квантового перечис-
53-кубитный симулятор, основанный на ионах в оп-
тических ловушках [2]. В компании IBM успешно
ления [8-10]. Задача квантового перечисления мо-
жет быть использована в различных областях на-
испытан прототип 50-кубитного квантового процес-
уки, в том числе и в информационной безопаснос-
сора [3], а в декабре 2017 г. опубликована статья [4],
ти (см. [11]). Проблема в том, что в работе [8] ве-
согласно которой представлен проект масштабируе-
роятность успеха алгоритма квантового перечисле-
мого кремниевого квантового процессора, представ-
ния оценена снизу величиной 8/π2, в работе [9] та
ляющего собой массив из 24 × 20 = 480 кубитов.
же самая вероятность успеха оценивается снизу ве-
В январе 2018 г. компания Intel сообщила о созда-
личиной 2/3, в [12] вероятность успеха квантового
нии 49-кубитного сверхпроводящего квантового чи-
алгоритма определения собственного числа, на ко-
па «Tangle Lake». В марте 2018 г. компания Google
объявила о создании 72-кубитного квантового про-
тором основан алгоритм квантового перечисления,
оценивается снизу величиной 4/π2, причем в [10,12]
цессора «Bristlecone», с помощью которого компа-
указано, что если в регистре управления m = t +
ния надеялась продемонстрировать «квантовое пре-
+ [log2(2 + 1/2ϵ)] кубитов, то вероятность успеха ал-
восходство» [5,6]. Осенью 2019 г. опубликована ра-
горитма определения собственного числа, а значит
* E-mail: DenisenkoDV@bmstu.ru
и квантового перечисления, будет не менее 1 - ϵ.
771
Д. В. Денисенко
ЖЭТФ, том 157, вып. 5, 2020
Таким образом, в источниках информации мож-
Следуя [10], обозначим
но найти различные оценки вероятности успеха ал-
∑
∑
1
1
горитма квантового перечисления, из-за чего ре-
|α〉 ≡
√
|x〉,
|β〉 ≡
√
|x〉,
N -Mx
M
зультаты практического применения квантового пе-
bad
xgood
речисления могут отличаться от ожидаемых теоре-
тогда состояние равновероятной суперпозиции «вхо-
тических результатов. Кроме того, в оригинальной
дов» рассматриваемой булевой функции f можно
работе [8] в алгоритме квантового перечисления ис-
записать в виде
пользуется прямое квантовое преобразование Фу-
√
√
рье, а в [9,10] используется обратное преобразование
N -M
M
Фурье.
|ψ〉 =
|α〉 +
|β〉.
N
N
В настоящей работе представлены результаты
√
математического моделирования применения алго-
Обозначим cos(θ/2) =
(N - M)/N, тогда |ψ〉 =
ритма квантового перечисления для оценки веса
= cos(θ/2)|α〉 + sin(θ/2)|β〉, вероятность получить в
некоторых булевых функций, зависящих от 6 пере-
результате измерения кубитов какое-либо одно из
менных, в квантовом симуляторе Quipper [13-15] с
M возможных решений равна sin2(θ/2). В базисе,
целью проверки оценок вероятности успеха алгорит-
состоящем из |α〉 и |β〉, итерацию Гровера можно
ма квантового перечисления. Результаты представ-
записать следующим образом (см. [10]):
лены на рис. 2-9, их можно рассматривать как ре-
(
)
зультаты экспериментов с идеальным 12-кубитным
cosθ
- sinθ
G=
,
(1)
квантовым компьютером и использовать при тести-
sinθ
cosθ
ровании физических реализаций квантовых вычис-
лительных систем по аналогии с тестами [16]. Кро-
где 0 ≤ θ ≤ π/2 (для случая M ≤ N/2), sin θ =
√
ме того, проведены эксперименты по моделирова-
=2
M (N - M)/N.
нию квантового перечисления с использованием как
После k итераций Гровера получим состояние
прямого, так и обратного квантового преобразова-
(
)
(
)
ния Фурье. Получен вывод о том, что в алгоритме
2k + 1
2k + 1
Gk|ψ〉 = cos
θ
|α〉 + sin
θ
|β〉.
квантового перечисления можно использовать как
2
2
прямое, так и обратное квантовое преобразование
[
]
√
Фурье (результаты выполненных экспериментов по-
После k
= π/4
N/M итераций Гровера
лучились одинаковыми).
и измерения кубитов с высокой вероятностью
sin2 ((2k + 1)/2θ) получим одно из M возможных
решений.
2. КВАНТОВОЕ ПЕРЕЧИСЛЕНИЕ
Квантовое перечисление — это применение про-
цедуры нахождения собственного числа итерации
Задача квантового перечисления рассмотрена в
Гровера G, позволяющее определить количество ре-
работах [8-10]. Пусть имеется проиндексированное
шений M задачи поиска.
множество из N = 2n элементов. В задаче поис-
Пусть |a〉 и |b〉 — два собственных вектора итера-
ка с помощью квантового алгоритма Гровера [17]
ции Гровера в пространстве, натянутом на векторы
требуется найти индекс элемента, удовлетворяюще-
|α〉 и |β〉, а θ — угол поворота, определяемый ите-
го некоторому критерию поиска, задаваемому буле-
рацией Гровера. Квантовый алгоритм, решающий
вой функцией f : Vn → V1, причем предполагается,
рассматриваемую задачу квантового перечисления,
что всего существует M таких элементов. Если с по-
имеет два параметра: булева функция f и количе-
мощью квантового алгоритма Гровера можно найти
ство кубитов m, которое определяет точность, с ко-
какое-то одно решение рассматриваемой задачи, то
торой мы оцениваем величину M, и влияет на время
с помощью квантового алгоритма перечисления —
выполнения всего алгоритма. Квантовый алгоритм
оценку общего количества решений в рассматривае-
перечисления основан на двух унитарных преобра-
мой задаче поиска.
зованиях:
Задача квантового перечисления: дана слу-
Gx : |x〉 ⊗ |Ψ〉 → |x〉 ⊗ Gxf|Ψ〉,
чайная булева функция f : Vn → V1, требуется оце-
(
)
нить количество M = |f-1(1)| аргументов, на кото-
∑
1
2πixj
рых рассматриваемая булева функция принимает
QFT-1m : |x〉 →
√
exp
-
|j〉,
2m
2m
значение 1.
j=0
772
ЖЭТФ, том 157, вып. 5, 2020
Применение алгоритма квантового перечисления...
|0
H
•
|0
H
•
-1
QF T
|0
H
•
|0
H
•
|0
/n
H⊗n
m -1
G20
G21
G22
G2
|1
H
Рис. 1. Квантовая схема для алгоритма определения угла поворота θ итерации Гровера G. Регистр управления содержит
m кубитов
P
P
TargetProbSuccess
TargetProbSuccess
1.0
0.95
0.92
ExperimentProbSuccess
0.93
ExperimentProbSuccess
0.92
0.8
0.90
0.89
0.75
0.6
0.85
0.4
0.80
0.2
0.18
0.75
7.5. 10-2
0.75
0
0.70
t = 2
t = 3
t = 2
t = 3
Рис. 3. f(x1, x2, x√x4, x5, x6) = x1x2x3x4x5, M = 2, N =
Рис. 2. f(x1, x2, x3, x4, √ x6) = x1x2x3x4x5x6, M = 1,
= 26, θ = 2arcsin
M/N = 0.355421. Pt=2(|Δθ| < 0.25) =
N = 26, θ = 2arcsin
M/N = 0.250656. В регистре
= 0.93, Pt=3(|Δθ| < 0.125) = 0.89
управления 5 кубитов, т. е. m = 5. Поскольку m = t +
+[log2(2+1/2ϵ)], рассмотрим два варианта: 1) t = 2, тогда
ϵ = 1/12 и согласно теории |Δθ| < 0.25, |ΔM| < 3, теоре-
тическая вероятность успеха 1 - ϵ = 0.916667; 2) t = 3, то-
Схема определения собственного числа, исполь-
гда ϵ = 1/4 и согласно теории |Δθ| < 0.125, |ΔM| < 1.25,
зуемая для квантового перечисления представлена
теоретическая вероятность успеха 1 - ϵ = 0.75. Экспери-
на рис. 1.
ментальная вероятность успеха определяется как сумма
Согласно [10], для того чтобы полученная оценка
вероятностей тех исходов, на которых |θ -
θ| < 0.25 при
θ с вероятностью не менее 1 - ϵ имела погрешность
t = 2 либо |θ - θ| < 0.125 при t = 3
не более 2-t, t ∈ N, в первом регистре должно быть
m ≡ t+[log2(2 + 1/2ϵ)] кубитов, во втором регистре
должно быть n+1 логических кубитов (считаем, что
итерации Гровера G могут быть эффективно реали-
где i =
√-1 , оператор Gxf — композиция x итера-
ций Гровера относительно булевой функции f, m —
зованы без вспомогательных кубитов).
количество кубитов для оценки величины угла по-
Состояние второго регистра с помощью преобра-
ворота θ итерации Гровера. Собственные числа опе-
зования Адамара H⊗n переводится в суперпозицию
ратора G равны exp(iθ) и exp(i(2π - θ)) (см. [10],
всех возможных входных значений булевой функ-
разд. 6.3).
ции f с равными амплитудами вероятностей, т. е. в
773
Д. В. Денисенко
ЖЭТФ, том 157, вып. 5, 2020
P
P
TargetProbSuccess
1.0
TargetProbSuccess
0.97
ExperimentProbSuccess
0.92
ExperimentProbSuccess
1.0
0.89
0.92
0.8
0.75
0.8
0.75
0.6
0.6
0.45
0.48
0.4
0.4
t = 2
t = 3
t = 2
t = 3
Рис. 4. f(x1, x2, x3, x4, x5, x6) = x1x2x3x4x5⊕x1x2x3x4x6⊕
Рис. 6. f(x1, x2, x3, x4, x5, x6) = x1x2√x4 ⊕ x1x2x3x5x6⊕
⊕x1x2x3x√5x6, M
=
3, N
=
26, θ
=
⊕x1x2x3x4x5x6, M = 5, θ = 2 arcsin
M/N = 0.566564.
= 2arcsin
M/N = 0.436469. Pt=2(|Δθ| < 0.25) = 0.89,
Pt=2(|Δθ| < 0.25) = 0.97, Pt=3(|Δθ| < 0.125) = 0.48
Pt=3(|Δθ| < 0.125) = 0.45
P
P
TargetProbSuccess
TargetProbSuccess
1.0
0.94
ExperimentProbSuccess
1.0
0.92
0.92
ExperimentProbSuccess
0.8
0.75
0.8
0.75
0.62
0.6
0.6
0.4
0.47
0.19
0.2
0.4
0
t = 2
t = 3
t = 2
t = 3
Рис. 5. f(√, x2, x3, x4, x5, x6) = x1x2x3x4, M = 4, θ =
Рис. 7. f(x1, x2, x3, x4, x5, x6) = x1√x3x4 ⊕ x1x2x3x5⊕
= 2arcsin
M/N = 0.505361. Pt=2(|Δθ| < 0.25) = 0.62,
⊕x1x2x3x4x5, M = 6, θ = 2 arcsin
M/N = 0.622368.
Pt=3(|Δθ| < 0.125) = 0.19
Pt=2(|Δθ| < 0.25) = 0.94, Pt=3(|Δθ| < 0.125) = 0.47
состояние суперпозиции собственных состояний |α〉
M+ΔM
M
θ + Δθ
θ
и |β〉 (так как G|α〉 = ei(2π-θ)|α〉, G|β〉 = eiθ|β〉).
-
in2
- sin2
=
s
=
N
N
2
2
Квантовая схема на рис. 1 дает ответ θ или 2π - θ
(
)
с точностью |Δθ| ≤ 2-t при вероятности не менее
θ + Δθ
θ
θ + Δθ
θ
= sin
+ sin
in
- sin
s
.
1-ϵ. Более того, ответ 2π-θ эквивалентен ответу θ с
2
2
2
2
той же точностью, поэтому в действительности про-
К первому множителю применимо тригонометриче-
цедура определения собственного числа определяет
ское неравенство:
значение θ с точностью 2-t и вероятностью успеха
1 - ϵ.
θ + Δθ
θ
|Δθ|
Используя уравнение sin2(θ/2) = M/N и оценку
in
sin
+
,
s
<
2
2
2
для величины θ, можно оценить величину ошибки
ΔM для количества решений M:
ко второму множителю —
774
ЖЭТФ, том 157, вып. 5, 2020
Применение алгоритма квантового перечисления...
√
P
MN
N
|ΔM| <
+
TargetProbSuccess
2t
22(t+1)
1
ExperimentProbSuccess
1
При выборе t = n/2, m = [n/2] + 3 получим
1.0
оценку M, используя 2n/2+3 итераций Гровера, т. е.
всего за 2n/2+3 обращений к функции f, а не за 2n
0.92
при полном переборе аргументов f в классическом
0.9
случае. При этом вероятность того, что будет полу-
чен заданный уровень погрешности Δθ и ΔM (ве-
роятность успеха алгоритма квантового перечисле-
0.8
ния), составляет 1-1/12 = 0.916667. Таким образом,
0.75
получено квадратичное ускорение по сравнению с
классическим алгоритмом полного перебора «вхо-
дов» f для оценки мощности прообраза |f-1(1)|.
0.7
Далее рассмотрим результаты математического
t = 2
t = 3
моделирования применения квантового алгоритма
перечисления.
Рис.
8. f(x1, x2,√3, x4, x5, x6)
= 0, M
= 0, θ
=
= 2arcsin
M/N = 0. P (θ = 0.03125) ≈ 1
3. РЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ
P
АЛГОРИТМА КВАНТОВОГО
ПЕРЕЧИСЛЕНИЯ ДЛЯ ОЦЕНКИ ВЕСА
TargetProbSuccess
1.0
БУЛЕВОЙ ФУНКЦИИ В КВАНТОВОМ
0.92
ExperimentProbSuccess
СИМУЛЯТОРЕ QUIPPER
0.75
Задача квантового перечисления рассмотрена
относительно некоторых булевых функций f : V6 →
0.5
→ V1 веса M = 1,2,...,6. Общий вид квантовой
схемы, использующейся для решения задачи кван-
тового перечисления, представлен на рис. 1:
1) пять кубитов в верхнем регистре управления;
0
0
2) шесть кубитов соответствуют переменным бу-
0
левой функции;
3) еще один кубит требуется для реализации
«итерации Гровера» относительно рассматривае-
t = 2
t = 3
мых булевых функций f.
Получена квантовая схема на 12 кубитах. Ре-
Рис. 9. f(x1, x2, x3, x4, x5, x6) = 1, M = 64, условие M <
< N/2 не выполнено, но мы посмотрели, что получится в
зультат измерения первого регистра, верхние пять
результате применения алгоритма квантового перечисле-
кубитов, обозначим |x〉. После процедуры измерения
ния в таком случае: P (θ = 0) ≈ 1
|x〉 получим оценку 25 θ, т. е. для того, чтобы полу-
чить
θ, необходимо разделить целое число x на 25.
Отметим, что стандартные квантовые схемы, ре-
θ + Δθ
θ
|Δθ|
in
- sin
,
ализующие прямое и обратное квантовые преобра-
s
≤
2
2
2
зования Фурье, инвертируют порядок записи куби-
таким образом получаем оценку
тов, т. е. старшие кубиты и младшие кубиты меня-
(
ются местами. Для того чтобы вернуть исходный
|ΔM|
θ
|Δθ|
) |Δθ|
<
2 sin
+
порядок записи, требуется применять SWAP-гейты,
N
2
2
2
которые обычно не указывают (см. [10], рис. 5.1,
√
Подставив сюда sin(θ/2) =
M/N, полагая, что
с. 219). В квантовом симуляторе Quipper обрат-
|Δθ| ≤ 2-t, получим окончательную оценку для
ное преобразование Фурье выполняется с помо-
ошибки |ΔM|:
щью композиции функций «reverse_generic_endo»
(
√
)
и «qft_big_endian», в результате чего старшие и
M
1
1
младшие кубиты меняются местами.
|ΔM| < N
2
+
,
N
2t+1
2t+1
775
Д. В. Денисенко
ЖЭТФ, том 157, вып. 5, 2020
Результаты применения квантового ал-
5.
C. S. Calude and E. Calude, arXiv:1712.01356v1.
горитма перечисления для оценки веса
6.
J. Kelly, A Preview of Bristlecone, Google’s New
||f(x1, x2, x3, x4, x5, x6)|| представлены на рис. 2-9.
Quantum Processor, Quantum AI Lab, 05.03.2018,
Программную реализацию можно найти в [18].
bristlecone-googles-new.html.
4. ЗАКЛЮЧЕНИЕ
7.
F. Arute, K. Arya, J. M. Martinis et al., Nature
574,
505
В целом, за исключением случаев, проиллюстри-
019-1666-5.
рованных на рис. 2 и 5, при выборе t = n/2, m =
= [n/2] + 3 с вероятностью не менее 4/π2 = 0.405285
8.
полученные оценки M за 2n/2+3 итераций Грове-
org/abs/quant-ph/9805082v1.
ра имеют заданный уровень погрешности ΔM, т. е.
за 2n/2+3 обращений к функции f можно получить
9.
M. Mosca, in Proceedings of Randomized Algorithms,
оценку |f-1(1)|, однако вероятность успеха алго-
Workshop of Mathematical Foundations of Computer
Science (1998), pp. 90-100.
ритма квантового перечисления может существен-
но отличаться от теоретической оценки 1 - ϵ при
10.
M. A. Nielsen and I. L. Chuang, Quantum Compu-
m = t + [log2(2 + 1/2ϵ)] из [10].
tation and Quantum Information, Cambridge Univ.
Таким образом, с помощью алгоритма квантово-
Press, New York (2010), pp. 261-263.
го перечисления, вероятность успеха которого обыч-
но составляет не менее 4/π2 = 0.405285, может быть
11.
получено квадратичное ускорение по сравнению с
org/abs/1811.09931.
классическим алгоритмом полного перебора «вхо-
12.
G. Benenti, G. Casati, and G. Strini, Principles of
дов» f для оценки мощности прообраза |f-1(1)|.
Quantum Computation and Information, World Sci.
ЛИТЕРАТУРА
13.
mathstat.dal.ca/selinger/quipper/.
1. H. Bernien, S. Schwartz, A. Keesling, H. Levine, and
A. Omran, Nature 551, 579 (2017), DOI:10.1038/
14.
A. S. Green, P. L. Lumsdaine, N. J. Ross, P. Selinger,
nature24622; arXiv:1707.04344.
and B. Valiron, arXiv:1304.5485v1.
2. J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis,
15.
S. Siddiqui, M. J. Islam, and O. Shehab, arXiv:1406.
and P. Becker, Nature 551, 601 (2017), DOI:10.1038/
4481v2[quant-ph].
nature24654; arXiv:1708.01044.
16.
P. Murali, M. Martanosi et al., arXiv:1905.11349v2
future-is-quantum.
[quant-ph].
4. M. Veldhorst, H. G. J. Eenink, C. H. Yang, and
17.
L. K. Grover, Phys. Rev. Lett. 79, 325 (1997).
A. S. Dzurak, Nature Comm.
8,
1766
(2017),
18.
10.1038/s41467-017-01905-6.
QuantumCounting.git.
776
