Проблема подготовки кунитов к измерению и её решение

П.А. Правильщиков,
в.н.с, к.т.н, с.н.с, pavelp@ipu.ru
ИПУ РАН, г. Москва

Показано, что при использовании квантовых компьютеров (КК) и квантовых процессоров-ускорителей (КвУ), у которых регистр построен не из кубитов, а из кунитов (англ. эквивалент «qudit»), возникает проблема низкой вероятности получения результата решения заданной задачи после квантового считывания информации из регистра (т.е. в результате измерения регистра). Приводится аналогия с опытами, в которой используется игральная кость с шестью гранями: если на каждой грани игральной кости изобразить число 6, то в результате бросания кости с вероятностью, равной 1, всегда будет получено число 6. Подобную процедуру, как изображение цифры 6 на каждой грани игральной кости, предлагается использовать и в случае подготовки кунитов квантового регистра. В этом случае вероятность получения целевого результата решения задачи после измерения будет близка к 1.

It is shown that when using quantum computers (QC) and quantum accelerators (QA), whose register is based on qudits, there is a problem of low probability of obtaining a result of solving the task by measuring the register. Set out the analogy with an experience that uses dice with six faces. If on each face of the cube portray number six, by throwing the dice, will always be received six with a probability equal to 1. The same procedure as the image number six on each face of the cube, it is recommended that you use and in the case of training qudit quantum register. In this case, the probability of obtaining a result solve the given problem after the measurement would be close to 1.

Введение

В вычислительной технике (ВТ) началась новая революция и эта революция квантовая. С учётом начала квантовой революции и завершением эры кремниевых технологий в 2022-2025 гг. некоторые американские физики утверждают, что «страна, которой первой удастся найти подходящую замену кремнию, будет определять судьбы мира» [1, стр. 292]. Возможно, поэтому Российский научный фонд в 2015 выделил 8 приоритетных направлений исследований в нашей науке, среди которых есть и такое: «Перспективные квантовые коммуникации и квантовые вычисления». В мае 2016 г. появилось сообщение ТАСС о том, что первый российский КК будет создан усилиями госкорпорации «Росатом», Министерства образования и науки РФ, а также  Фонда перспективных исследований. Первый в РФ квантовый компьютер (КК) будет разработан через 3,5 года. Стоимость проекта - 750 млн. рублей. На создание в вузах-исполнителях (МИСиС, МФТИ, НГТУ) инфраструктуры, необходимой для разработки КК, выделят 210 млн. рублей. Руководитель проекта - заведующий лабораторией Института физики твердого тела РАН В.В. Рязанов. Однако, насколько известно, квантовый регистр отечественного КК предполагается реализовать с использованием кубитов [2]. В октябре 2016 стало известно, что Президент В.В. Путин распорядился дополнительно выделить $3,5 млрд. руб. на три приоритетных направления, одно из которых называется «Информационные технологии в части квантовых вычислений» [3].

Огромные деньги на исследования и разработку КК выделены за рубежом. Только две корпорации в США (IBM и HP) на разработку КК планируют выделить с 2014 по 2019 соответственно $3 млрд. и $2,5 млрд. [4]. Так, стало известно, что корпорация IBM получила многолетний грант на проведение работ в области квантового компьютеростроения от исследовательского агентства IARPA (Intelligence Advanced Research Projects Activity), подчиняющегося Управлению директора национальной разведки США [5]. Но уже в мае 2016 исследовательское отделение IBM Research объявило, что впервые в истории оно делает квантовые вычисления облачными (с помощью средств IBM Cloud) и доступными для представителей научной общественности [6]. Таким образом, в IBM создан экспериментальный образец КК, квантовый регистр которого содержит 5 кубитов. В 2015 канадская компания D-wave systems презентовала КК D-wave 2X, у которого регистр содержит более 1000 кубитов (1000+), а в 2017 предполагает выпустить КК с регистром в 2000 кубитов. Таблица всех КК D-wave systems и обсуждение результатов вычислений с помощью этих КК приводятся в [7,8]. Там же приведены описания многих других КК, а также проблемно-ориентированных КК или КвУ (иногда их ещё называют, «симуляторами»). В [7,8] рассмотрены также возможности создания квантовых нейронных сетей.

В ИПУ РАН предполагается создать проблемно-ориентированный КК, т.е. специализированный КвУ для решения уравнений и, прежде всего, логических. Квантовый регистр КвУ будет построен с использованием кунитов. Если для кубита размерность dim Н гильбертова пространства равна 2 (dim Н =n = 2), то для кунита dim Н = n, где n может быть больше любого наперёд заданного числа . Заметим, что неравенство n > является идеализацией. Одно из направлений развития состоит в увеличении числа n для разрядов квантового регистра КК и КвУ. При переходе от такого разряда регистра как кубит (n =2) к кутриту (n =3) и далее к куквадриту (n =4) приращение Dn числа n равно 1. Чтобы не изменять каждый раз алгоритмы и исчисления в зависимости от развития КК и КвУ и, следовательно, в зависимости от числа n или приращения Dn в общем случае n > . Исходя из этого, кубит можно рассматривать в качестве частного случая кунита, содержащего только два состояния, которые могут быть закодированы двумя числами. Это означает, что кубит может хранить одновременно два числа. Здесь уместно привести векторы состояния (векторы и ) для кубита и кунита, а также условия (правила) нормировки для них.

; + = 1. (1)

В (1) коэффициенты и , называются амплитудами и справа приведено условие нормировки для кубита. Для кунита вектор имеет вид:

(2)

Правило нормировки для кунита имеет вид:

= 1. (3)

1. Постановка задачи

В случае решения булевых уравнений с использованием матричного варианта исчисления кубических комплексов и квантовых D-алгоритмов [8-11], чем больше число n, тем меньше вероятность получить решение уравнения в том или ином куните. Если нас интересует только одно решение уравнения, например, вектор X_i = á0111ñ для логического уравнения от 4-х аргументов (n = 4) в виде:

, (4)

или в более конкретной форме:

f(x₁,x₂,x₃,x₄) = (x₁ Ú x₂)¢ Å (x₃ & x₄)¢ = (y₅ Å y₆) = z₇= 0, (6)

то в случае поиска решения SAT-проблемы с использованием квантового D-алгоритма одного вектора X_i будет достаточно [10-11]. Теперь можно рассмотреть упрощённый пример, когда после выполнения третьего шага (q = 3) квантового D-алгоритма и удаления квантового мусора [12, стр. 207-208] будет получен куб , в виде (7):

(7)

В (7) первые 4 координаты содержат вектор X_i , являющийся решением (6). Это легко проверить:

(0 Ú 1)¢ Å (1 & 1)¢ = (1 Å 1) = z₇= 0,

Из приведённого примера куба = ,можно видеть, что (без учёта кодирования) потребуется кунит, который содержит не менее 7 чисел. На самом деле число 7 может быть в k раз больше, так как число k определяет число тех векторов, которые также являются решениями (6).

Таблица 1

Табличное задание функции f(x1,x2,x3,x4) = z7
Xi	<x1 x2 x3 x4>	z7	Xi	<x1 x2 x3 x4>	z7
X1	<0 0 0 0>	0	X9	<1 0 0 0>	1
X2	<0 0 0 1>	0	X10	<1 0 0 1>	1
X3	<0 0 1 0>	0	X11	<1 0 1 0>	1
X4	<0 0 1 1>	1	X12	<1 0 1 1>	0
X5	<0 1 0 0>	1	X13	<1 1 0 0>	1
X6	<0 1 0 1>	1	X14	<1 1 0 1>	1
X7	<0 1 1 0>	1	X15	<1 1 1 0>	1
X8	<0 1 1 1>	0	X16	<1 1 1 1>	0

Из табл. 1 следует, что множество M_реш = { X₁,X₂,X₃, X₈,X₁₂, X₆} содержит 6 векторов X_i (k = 6). Следовательно, число N_QN = k×N = 6×7 = 42, т.е. n ³ 42. Уместно напомнить, что в результате измерения кунита мы можем получить только одно значение из чисел, которые в нём содержаться. Понятно, что вероятность p того, что будет получено необходимое решение будет мала: p £. Однако наша задача состоит в том, чтобы повысить её до 1. Но для решения этой задачи можно упрощённо рассматривать куб D-алгоритма, в виде транспонированного вектора (7)

2. Аналогия с игральной костью и метод решения поставленной задачи

Существует достаточно простой и изящный метод решения поставленной задачи. Чтобы проиллюстрировать идею этого метода приведём аналогию с игральной костью. На каждой грани стандартной кости нанесены цифры:
1, 2, …, 6. Сначала запишем вектор состояния игральной кости до броска в игре и запишем вектор _n=6 в терминах квантовой механики с нотацией Дирака. Тогда получим выражение:

(8)

В случае идеальной кости вероятность выпадения всякого числа от 1 до 6 одинакова и равна . В этом случае условие нормировки имеет вид:

+++++=+++++ = 1. (9)

Как сделать так, чтобы в игре при бросании кости всегда выпадало некоторое любимое вами, читатель, число (например, 6)? Известно, что существует несколько способов решения. Но здесь будет интересен такой способ: на каждую грань кости нанести цифру 6. Тогда вероятность p выпадения цифры 6 при бросании кости будет равна 1.

В этом случае выражение (9) можно записать: +++++= 1. Это означает, что в игре при бросании кости с вероятностью 1 будет выпадать число 6, записанное на разных гранях.

Уместно напомнить, что великий Эйнштейн утверждал: “Бог не играет в кости”. На что один из основателей квантовой механики Н. Бор отвечал «Эйнштейн, не говорите Богу, что ему делать». Поэтому приём с переобозначением граней игральной кости следует применить для некоторого переобозначения квантовой «игральной кости». Для этого перепишем в куниты k_1,1, k_1,2, …, k_1,4 куб C₃ (7). Это позволит для каждого из кунитов k_1,1, k_1,2, …, k_1,4
не зависимо от числа n (n = dim H) измерять координаты, в которых содержатся значения переменных x₁, x₂, x₃, x₄. В результате измерения каждого кунита будет получено только одно значение аргументов x₁, x₂, x₃, x₄. Следовательно, понадобится n вспомогательных кунитов, для получения одного решения логического уравнения вида (6) в виде вектора X_i = á x₁,x₂, …, x_n ñ с вероятностью близкой к 1, а не к 0 и независимо от числа n. В нашем случае n = 4, значит понадобится не менее 4 кунитов. Для этого необходимо использовать специальные унитарные перестановочные матрицы U^†_s®f , где s ¾ координата, содержащая символ e в исходном векторе амплитуд ¾ векторе V_{исх ;} f ¾ координата, содержащая символ e в результирующем векторе амплитуд ¾ векторе V_рез. Здесь для обозначения амплитуды, отличной от 0, используется символ e = .

Приведём пример унитарной перестановочной матрицы U^†_s®f и покажем её действие. Пусть задан исходный вектор-столбец V_исх в транспонированной форме: V_исх = [e 0 0 0 0 0 0 0 0]^T. Примером перестановочной матрицы U^†_s®f = =U^†_4®1 является следующая матрица:

U^†_4®1 ´ V_исх = = − перевод символа e из 1-й координаты в 4-ю.

В результате умножения U^†_4®1 ´ V_исх будет получен результирующий вектор V_рез = [0 0 0 e 0 0 0 0 0]^T. Эта же матрица может быть использована и для перевода e из координаты 4 в координату 1, т.е. U^†_1®4 = U^†_4®1. Примером может служить умножение U^†_4®1 ´ V_исх, где V_исх = V_рез = [0 0 0 e 0 0 0 0 0]^T.

U^†_4®1 ´ V_исх = = − перевод символа e из 4-й координаты в 1-ю.

Использование таких матриц, как U^†_4®1 позволяет осуществить получение в результате измерения значение первого аргумента x₁. Но для этого необходимо использовать блочно-диагональные матрицы, содержащие в качестве блоков (подматриц) матрицы, подобные U^†_4®1. Размер приведённых матриц U^†_s®f при использовании квантовых D-алгоритмов равен размеру элементарной матрицы Рота [8-11] ¾ матрицы U^†_R , т.е. (r ´ r) = (9 ´ 9). Возможный вариант квадратной матрицы U^†_R имеет вид:

U^†_R = (10)

При выполнении квантовых D-алгоритмов матрица Рота реализует в матричной форме известную таблицу правил пересечения при выполнении операции a_g в случае, когда используются классические последовательные D-алгорит-мы [8], либо классические параллельно-последовательные D-алгоритмы [9]. Операция a_g представляет собой элементарную операцию покоординатного пересечения кубов и является основной операцией классического исчисления кубических комплексов (D-исчисления) [8].

Матрицы U^†_s®f , имеющие тот же размер, что и матрица U^†_R, являются подматрицами соответствующей блочно-диагональной матрицы [U_s®f ]_n . Матрицы [U_s®f ]_n используются с кунитами, у которых dim H = n. Общее математическое описание блочно-диагональных матриц (БДМ) приводится, например, в [13,14]. Здесь БДМ имеет вид:

. (11)

По сути, БДМ [U_s®f ]_n выполняют переобозначение граней, которые здесь называются секциями, квантовой «игральной кости» для того, чтобы получить нужное значение переменной x₁ с вероятностью равной 1 — см. выражения (8) и (9). Отметим, что значения переменной в других координатах кунита, например, кунита k_1,1, нас не интересуют. Наша цель получить в результате измерения значение, содержащееся в первой координате кунита k_1,1 (т.е. значение 0 вектора X_i = á0111ñ). При измерении кунита k_1,2 — наша цель: получить значение x₂(т.е. значение 1 во 2-й координате вектора X_i = á0111ñ).Аналогично и для других кунитов вплоть до k_1,n (в нашем случае n = 4).

3. Общее правило преобразования единичной матрицы I₉ в матрицу U^†_s®f.

Сразу же отметим, что s ¹ f и в нашем случае r = 9. Задан исходный вектор V_исх и задана пара (s, f). Напомним, что в исходном векторе V_исх s – координата, содержащая символ e. В векторе V_рез, который является результатом умножения U^†_s®f ´ V_исх и f ¾ это координата, в которой будет записан символ e - см. примеры выше. Таким образом, требуется вывести правило преобразования матрицы I₉ в унитарную матрицу U^†_s®f, того же размера (9´9). Фор^{мально это можно записать I9 U†s®f, где R ¾ правило преобразования матрицы I9 в матрицу U†s®f. В общем виде квадратную матрицу I9 можно записать в виде: I9 = [аi=j = 1]9.} Правило R может быть записано в виде всего лишь двух пунктов (двух шагов).
1. I₉ U^†_s®f: a_fs Þ 1 & a_ff Þ 0. Содержательно, это означает, что в элементе a_fs записывается 1 и в той же строке f в элементе a_ff на главной диагонали матрицы I₉ записывается 0. Например, для заданной матрицы I₉ и заданной пары (s, f)= (4,1) первый шаг

^.

2. Второй шаг: I_n U^†_4®1, т.е. a_s,f Þ1, a_s,s Þ 0. В матрице полученной на первом шаге в первой строке (строке s) в четвёртом столбце (столбце f) элемент a_{s,f =} a_1,4 приравнивается 1: a_s,f = a_1,4=1. Проис-ходит преобразование a_s,f = a_1,4 Þ1, а затем элемент a_s,s = a_{1,1 приравнивается 0, то есть происходит преобразование} a_{s,s =} a_{1,1= 0.} Например, для полученной выше матрицы и заданной пары (s, f)= (4,1) второй шаг R₂ правила R имеет вид:

^{U†s®f = U†4®1.}

Таким образом, мы построили перестановочную матрицу U^†_4®1, которая переставляет символ e в первую строку вектор столбца. В терминах игральной кости матрица U^†_4®1 записывает на некоторой грани нужное нам число. В качестве граней у нас выступают секции транспонированного вектора, которые записаны в одном куните, и таких секций (или граней) может быть достаточно много. Для записей нужных чисел в каждой секции должны быть использованы блочно-диагональные матрицы вида (11). Кроме этого, для построения таких блочно-диагональных матриц необходимо использовать условные операции. Матрицы таких условных операций и квантовые схемы, реализующие их хорошо известны. Их описание приводится, например, в [11, стр. 229-238]. Здесь можно лишь отметить, что матрицы условных операций легко представить в виде блочно-диагональных матриц, которые используются для решения с помощью квантовых D-алгоритмов, что увеличивает степень параллелизма в процессе поиска решения логических уравнений, например, вида (6), а также вида КНФ с любым числом аргументов.

Заключение

Использование приведённого здесь метода и перестановочных матриц позволяет подготовить полученное решение логических уравнений так, что в процессе измерения с вероятностью близкой к 1 будет получено искомое решение. При этом увеличение временной и пространственной сложности решения задачи увеличивается полиномиально. Следовательно, для получения общего решения логических уравнений, в частности, SAT-проблемы требуются полиномиальные ресурсы времени, квантовой памяти и аппаратуры.

Литература

1. Каку М. Физика будущего / Пер. с англ. — 3-е изд. — М.: Альпина нон-фикшн, 2014. — 584 с. ISBN 978-5-91671-338-1

2. В.В. Рязанов Джозефсоновский p-контакт сверхпроводник-ферромагнетик-сверхпроводник как элемент квантового бита. // УФН. 1999. Том 169. № 8. С. 920-922.

3. Перспективные исследования в России дополнительно профинансируют на 3,5 млрд. рублей.
URL: https://rns.online/science/Perspektivnie-issledovaniya-v-Rossii-dopolnitelno-profinansiruyut-na-35-mlrd-rublei-2016-10-17/

4. Шах А. IBM рапортует об успехах в создании квантовых компьютеров. 26.06.2015.
URL: http://www.computerworld.ru/articles/IBM-raportuet-ob-uspehah-v-sozdanii-kvantovyh-kompyuterov

5. Годин Ш. Квантовые компьютеры все ближе к реальности. 18.12.2015.
URL: http://www.dgl.ru/articles/kvantovye-komputery-vse-blije-k-realnosti_8416.html

6. Правильщиков П.А. Использование квантовых компьютеров и квантовых ускорителей в информационных технологиях (Обзор). // «Информационные технологии в проектировании и производстве». 2016. № 2, Стр. 3-12.

7. Правильщиков П.А. Использование квантовых алгоритмов в информационных технологиях и задачах управления. (Обзор)

8. Roth J.P. Diagnosis of automata failures: a calculus and method. // IBM Journal of Research and Development. 1966. № 7 (July). P. 18-32.

9. Правильщиков П.А. Закон сохранения перебора и естественный параллелизм D-алгоритмов для построения тестов и моделирования в технической диагностике. // Автоматика и телемеханика. 2004. № 7, Стр. 156-199.

10. Правильщиков П.А. Центральная проблема современной дискретной математики и квантовый генератор тестов. / Пленарный доклад в Трудах 14-й международной конференции «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта » (CAD/CAM/PDM-2014). Федеральное государственное бюджетное учреждение науки Институт проблем управления РАН им. Трапезников. 2014. Стр. 15-20. ISBN – 978-5-905675-26-3.

11. Правильщиков П.А. Квантовые D-алгоритмы и центральная проблема современной дискретной математики. /Пленарный доклад в Трудах 14-й международной конференции «Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта » (CAD/CAM/PDM-2014). Федеральное государственное бюджетное учреждение науки Институт проблем управления РАН им. Трапезников. 2014. Стр. 88-93.
ISBN – 978-5-905675-26-3.

12. Нильсен М., Чанг И. Квантовые вычисления и квантовая информация: Пер. с англ.— М.: Мир, 2006. — 824с.

13. Бортаковский А.С., Пантелеев А.В. Линейная алгебра в примерах и задачах. М.: Высш. шк., 2010. — 591 с.

14. Ильин В. А., Позняк Э.Г. Линейная алгебра. М.: ФИЗМАТЛИТ. 2007. — 280 с.