Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 177-186

2.1. Представление классических данных квантовыми данными

Пусть система состоит из $n$ частиц, каждая из которых дает при измерении один из двух результатов – это система из $n$ кубитов. Известно, что квантовые состояния описываются векторами с абсолютным значением, равным 1, и векторы, отличающиеся только фазовым коэффициентом ${{e}^{{i\phi }}}$, описывают одно и то же состояние. То есть, для координат $\left( {{{z}_{0}},...,~{{z}_{{N - 1}}}} \right)$ любого экземпляра квантовых данных, можно положить

где ${{z}_{0}} \in \left[ {0,1} \right]$, ${{z}_{1}}, \ldots ,{{z}_{{N - 1}}} \in \mathbb{C}$. Это уравнение сферы в пространстве ${{\mathbb{R}}^{{2N - 1}}}$, т.е., сферы ${{S}^{{2N - 2}}}$. Каждую ее точку z можно записать в следующих обобщенных сферических координатах: где ${{\delta }_{s}} \in \left[ {0,\frac{\pi }{2}} \right]$, ${{\gamma }_{s}} \in \left[ {0,2\pi } \right)$, $\forall s$.

Пусть имеется классический набор данных x^j, $j = 0, \ldots ,J - 1$, размерности M такой, что значения каждого признака являются целыми числами, лежащими в интервале от 0 до ${{X}_{m}}$ (m = 0, ..., $M - 1,~{{X}_{m}} \in \mathbb{N}$). Иными словами,

Даже если исходный набор данных не таков, можно произвести соответствующее преобразование и получить требуемый набор. Такой датасет можно закодировать в набор квантовых состояний (квантовый датасет), если $M = 2 \cdot {{2}^{n}} - 2$ для какого-то натурального $n$. Если $N = {{2}^{n}}$, то квантовый датасет будет определен формулой (1), в которой для каждого j-го экземпляра данных числа $z_{k}^{j}$ определены формулой (3), в которой

Если в исходном датасете $M \ne 2 \cdot {{2}^{n}} - 2$, то потребуется изменить размерность датасета. Это можно сделать с помощью Python модуля genser, алгоритм работы которого описан далее.

2.2. Алгоритм обобщенной сериализации для изменения размерности датасета

В основе изменения размерности датасета без потери информации лежит хорошо известная сериализация, обобщенная следующей теоремой.

Теорема 1. Пусть $R_{X}^{s}$ = {(x₀, ..., x_{s – 1}), $~{{x}_{j}} \in [0,{{X}_{j}}]$, $~{{x}_{j}} \in \mathbb{Z}$, j = 0, ..., s – 1}. Множества $R_{X}^{s}$ и $R_{Y}^{t}$ изоморфны, если

Доказательство. Предъявим биекцию в явном виде. Заметим, что если выполнено условие теоремы, то оба произведения (равные одному и тому же числу) имеют единственное разложение на простые сомножители (основная теорема арифметики). Имеем следующие альтернативы:

a) все ${{X}_{j}} + 1$ простые и все ${{Y}_{k}} + 1$ тоже простые;

b) все ${{X}_{j}} + 1$ простые, а среди ${{Y}_{k}} + 1$ есть составные;

c) среди ${{X}_{j}} + 1$ есть составные, а все ${{Y}_{k}} + 1$ простые;

d) среди ${{X}_{j}} + 1$ есть составные, и среди ${{Y}_{k}} + 1$ есть составные.

В случае a), очевидно, $s = t$ и можно построить биекцию вида ${{y}_{k}} = {{x}_{j}}$ для ${{X}_{j}} = {{Y}_{k}}$.

Если имеет место случай b), то, очевидно, $t < s$, и среди ${{Y}_{k}} + 1$ найдутся такие, которые являются произведением нескольких сомножителей вида ${{X}_{j}} + 1$:

Для такого случая положим

в качестве прямого отображения и в качестве обратного. Легко проверить, что это взаимно-однозначное отображение. Для оставшихся простыми сомножителей поступаем так же, как в случае a).

При выполнении c), биекция строится аналогично случаю b) с той лишь разницей, что теперь $s < t$ и $X$ нужно поменять местами с Y.

В случае d) нужно заметить, что между $R_{X}^{s}$ и $R_{Y}^{t}$ всегда можно поставить множество $R_{Z}^{p}$ ={(z₀, ..., ${{z}_{{p - 1}}}),~{{z}_{j}} \in [0,{{Z}_{i}}],~i = 0, \ldots ,p - 1\} $, в котором все ${{Z}_{i}} + 1$ являются простыми сомножителями в разложении числа $\prod\limits_{j = 0}^{s - 1} {({{X}_{j}}\, + \,1)} $. По доказанному выше, существует биекция между $R_{X}^{s}$ и $R_{Z}^{q}$, а также биекция между $R_{Z}^{q}$ и $R_{Y}^{t}$, что означает наличие биекции между $R_{X}^{s}$ и $R_{Y}^{t}$. Таким образом, множества $R_{X}^{s}$ и $R_{Y}^{t}$ всегда изоморфны при выполнении условия теоремы.            $\square $

Для алгоритма изменения размерности датасета воспользуемся отображением, построенным при доказательстве Теоремы 1 и будем повышать (понижать) размерность на 1 на каждом шаге. Алгоритм выглядит следующим образом:

Вход: Датасет размерности J со значениями признака $j$ в интервале от 0 до ${{X}_{j}}$.

Выход: Датасет размерности K со значениями признака $k$ в интервале от 0 до ${{Y}_{k}}$, список параметров перехода.

Процедура:

1. Если $K > J$, перейти к шагу 8.

2. Среди величин ${{X}_{j}}$ ($j = 0, \ldots ,J - 1$), характеризующих датасет, выбрать минимальную. Если их несколько – выбрать ту, у которой минимальный индекс (номер признака). Результат обозначим ${{X}_{{{{j}_{1}}}}}$.

3. Повторить шаг 2 для набора величин ${{X}_{j}}$ без ${{X}_{{{{j}_{1}}}}}$, получить ${{X}_{{{{j}_{2}}}}}$.

4. Объединить признаки ${{j}_{1}}$ и ${{j}_{2}}$ по формуле: ${{y}_{{{{j}_{1}}}}} = \left( {{{X}_{{{{j}_{2}}}}} + 1} \right){{x}_{{{{j}_{1}}}}} + {{x}_{{{{j}_{2}}}}}$.

5. Положить ${{y}_{0}} = {{x}_{0}}, \ldots ,{{y}_{{{{j}_{1}} - 1}}} = {{x}_{{{{j}_{1}} - 1}}}$, ${{y}_{{{{j}_{1}} + 1}}}$ = ${{x}_{{{{j}_{1}} + 1}}}$, ..., ${{y}_{{{{j}_{2}} - 1}}} = {{x}_{{{{j}_{2}} - 1}}}$, ${{y}_{{{{j}_{2}}}}} = {{x}_{{{{j}_{2}} + 1}}}, \ldots ,{{y}_{{J - 2}}} = {{x}_{{J - 1}}}$.

6. Записать набор из четырех чисел (j₁, ${{X}_{{{{j}_{1}}}}} + 1,{{j}_{2}},{{X}_{{{{j}_{2}}}}} + 1)$ в список параметров перехода.

7. Если размерность полученного датасета равна K, выдать датасет и список параметров перехода. Иначе – повторить шаги 2–6 для полученного после шага 5 датасета.

8. Среди величин ${{X}_{j}}$ выбрать максимальную. Если их несколько – выбрать ту, у которой максимальный индекс (номер признака). Результат обозначим ${{X}_{k}}$.

9. Если ${{X}_{k}} + 1$ составное число, то факторизовать его фактором, наиболее близким к $\sqrt {{{X}_{k}} + 1} $, получить ${{Y}_{k}} + 1,{{Y}_{J}} + 1$.

10. Если ${{X}_{k}} + 1 > 2$ простое число, то факторизовать X_k + 2 фактором, наиболее близким к $\sqrt {{{X}_{k}} + 2} $, получить ${{Y}_{k}} + 1,{{Y}_{J}} + 1$. Иначе выдать полученный датасет и список параметров с формулировкой “дальнейшее увеличение размерности невозможно”.

11. Разделить признак $k$ на два признака по формулам: ${{y}_{k}} = {{x}_{k}}\bmod \left( {{{Y}_{k}} + 1} \right)$, $~{{y}_{J}} = {{x}_{k}}{{\backslash }}\left( {{{Y}_{k}} + 1} \right)$.

12. Положить ${{y}_{0}} = {{x}_{0}}, \ldots ,{{y}_{{{{k}_{1}} - 1}}} = {{x}_{{{{k}_{1}} - 1}}}$, ${{y}_{{{{k}_{1}} + 1}}} = $ $ = {{x}_{{{{k}_{1}} + 1}}}, \ldots ,{{y}_{{J - 1}}} = {{x}_{{J - 1}}}$.

13. Записать набор из четырех чисел $\left( {k,{{Y}_{k}},J,{{Y}_{J}}} \right)$ в список параметров перехода.

14. Если размерность полученного датасета равна K, выдать датасет и список параметров перехода. Иначе – повторить шаги 8–13 для полученного датасета.

Этот алгоритм реализован в модуле genser: преобразование размерности “туда” осуществляется с помощью функции transform_to, принимающей исходный датасет и число – нужную размерность; преобразование “обратно” осуществляется функциями transform_out_up и transform_out_down, в которые передается трансформированный ранее датасет и список параметров перехода (на выходе – исходный датасет).

Теперь мы можем сравнительно вольно обращаться с размерностью датасета: ее можно трансформировать без потери информации к любой размерности от 1 до $\left\lfloor {\sum\nolimits_{j = 0}^{s - 1} {\log \left( {{{X}_{j}} + 1} \right)} } \right\rfloor $. Например, 3-мерный датасет с ${{X}_{0}} = 1$, ${{X}_{1}} = 12$, ${{X}_{2}} = 50$ можно преобразовать к датасету любой размерности от 1 до 10. В частности, всегда¹¹ можно найти такое $n$, для которого измененная размерность датасета будет удовлетворять условию $M = 2 \cdot {{2}^{n}} - 2$ и, следовательно, данные могут быть представлены как квантовые.

2.3. Запутанный базис

Согласно постулатам квантовой механики, если существуют две системы с ${{n}_{1}}$ и ${{n}_{2}}$ кубитами, соответственно, то состояния объединенной системы имеют вид:

где c^r – амплитуды состояния системы в новом вычислительном базисе, образованном тензорным произведением исходных базисов: $\left| r \right\rangle = \left| {{{k}_{1}}} \right\rangle \left| {{{k}_{2}}} \right\rangle ,$ где ${{k}_{1}} = 0, \ldots ,{{2}^{{{{n}_{1}}}}} - 1$, ${{k}_{2}} = 0, \ldots ,{{2}^{{{{n}_{2}}}}} - 1$.

Получается, что если были системы с пространствами состояний ${{S}^{{{{2}^{{{{n}_{1}} + 1}}} - 2}}}$ и ${{S}^{{{{2}^{{{{n}_{2}} + 1}}} - 2}}}$, то объединенная система будет иметь пространство состояний ${{S}^{{{{2}^{{{{n}_{1}} + {{n}_{2}} + 1}}} - 2}}}$. Но, как легко убедиться,

В случае, когда ${{n}_{1}} = {{n}_{2}} = 1$, получим

Причем в этом простейшем случае причина очевидна – при объединении систем фазовая мультипликативная инвариантность остается только с одним параметром, т.е., добавляется еще один параметр, который раньше был “скрытым” – это был фазовый множитель в одной из исходных систем. Но эта причина не до конца объясняет несовпадение пространств состояний: она добавляет только ${{S}^{1}}$, но снова

ни по размерности, ни топологически. Иными словами, всегда найдется такое состояние объединенной системы, которое не получается произведением состояний исходных систем: налицо системное свойство объединенной системы.

Часть системы ${{n}_{1}} + {{n}_{2}}$-кубитов, которая не может быть выражена как произведение состояний подсистем, образует набор так называемых запутанных состояний. Основное свойство запутанного состояния заключается в том, что для вывода системы из запутанного состояния необходимо выполнить унитарное преобразование, которое существенно влияет на все ее подсистемы. В рассмотренном выше примере системы двух кубитов состояниями, которые не разлагаются в композицию состояний кубитов, являются состояния Белла:

Как известно, они образуют базис Белла. Построение таких состояний легко обобщается на более высокие размерности – состояния в них остаются запутанными и тоже образуют базис в своем пространстве, далее он будет называться запутанным базисом. Его построение осуществляется схемой, обратной схеме на рис. 1.

Если состояние многокубитной системы запутано, то невозможно выйти из него, не затронув каждый кубит. В то же время каждое состояние системы может быть записано в запутанном базисе. Это означает, что каждый компонент состояния в этом базисе существенно влияет на все кубиты. Если мы измерим амплитуды этих компонентов, то сможем увидеть, как подсистемы взаимодействуют в этой квантовой системе. Измерение – многомерный аналог измерения Белла – представлено на рис. 1. Если метки состояний заданы, то необходимо определить, какой базисный вектор соответствует интересующей нас метке, что может быть определено из статистики результатов измерений для данной метки. Далее, если измерять новые состояния этой системы, то с определенной вероятностью можно предсказать их принадлежность к помеченному классу, что соответствует результату измерения, который в наибольшей степени относится к помеченным образцам.

В определенной степени это означает, что классификация может быть выполнена без оптимизации, если зависимости уже есть в данных. Но эти зависимости должны существовать: например, когда данные представляют собой полную суперпозицию чистых состояний, классификация завершится неудачей, так как для каждой метки результаты измерений будут примерно равновероятны.

2.4. Квантовая нейронная сеть на запутанных состояниях

В работе [18] представлены примеры классификации на запутанных состояниях как с оптимизацией, так и без нее. Для настоящего исследования требуется кратко описать построение квантовой нейронной сети на классификаторах без оптимизации, рассматриваемых как квантовые нейроны.

Можно сказать, что на рис. 1 представлен квантовый нейрон (далее q-нейрон), если убрать измерение в первом регистре. В этом случае на входе будет состояние $n$-частичной системы, а на выходе – состояние кубита и $n - 1$-значное измерение. Чтобы построить квантовую нейронную сеть (далее КНС), заметим, что q-нейрон, принимая на вход $n$ кубитов, возвращает $m < n$ кубитов вместе с $k = n - m$ классическими битами информации. КНС может быть обучена на основе этой классической информации и заданной разметки данных. Процедура обучения в случае q-нейронов без оптимизации несколько отличается от обычной: не нужно никаких итераций (эпох обучения), а требуются лишь данные и их метки. Причем, если метка экземпляра данных пришла уже после проведенной классификации, то характеристики КНС, представляющие собой сопоставления базисных векторов меткам, могут измениться прямо в этот момент. То есть такое обучение автоматически становится онлайн-обучением.

Копирование квантовых состояний запрещено. Поэтому КНС не содержат разветвлений. Но q-нейрон может содержать более одного квантового выхода – для этого достаточно просто убрать измерения в нужном числе регистров. Это можно использовать для создания сетей различной архитектуры. Так, КНС прямого распространения получается, если выходы нескольких q-нейронов становятся входами для следующего q-нейрона. А для создания рекуррентной КНС, нужно выход одного или нескольких q-нейронов объединить с новыми квантовыми данными для подачи в следующий слой.

Во всех КНС будет выполняться правило: сумма числа $Q$ кубитов на выходе сети и числа $C$ классических битов, полученных в результате измерений, равна числу $I$ входящих кубитов:

Однако, для сети прямого распространения, все $I$ кубитов должны быть введены в сеть сразу, а для рекуррентной сети квантовые данные могут вводиться постепенно. То есть для рекуррентной КНС можно установить какое-то предельное число $C$ классических бит, используемых в обучении, и работать со стримом квантовых данных, не загружая расчеты избытком статистических данных.

3.1. Онлайн обучение в КНС прямого распространения

Рассмотрим КНС, один блок которой представлен на рис. 2.

На рис. 2, как обычно, квантовые состояния обозначены сплошными одиночными линиями, а классические выходы – двойными линиями. Пунктиром показано повторение регистров и групп регистров. Буквой N обозначен блок, представляющий собой квантовую схему, представленную на рис. 1, в которой измерения установлены не во всех регистрах: часть верхних регистров остается неизмеренной и выходит квантовыми состояниями. В качестве структуры данных для такого блока будем использовать следующую:

Здесь $s$ – номер слоя КНС, $k$ – номер q-нейрона в слое. На входе в блок имеем квантовое состояние $\left| {q_{k}^{s}} \right\rangle $, после прохождения этого q-нейрона получается число ${v}_{k}^{s}$ (результат измерения) и набор квантовых состояний $\left| {q_{{n_{k}^{s}}}^{{s + 1}}} \right\rangle $, каждое из которых идет на вход $n_{k}^{s}$-го q-нейрона следующего слоя. Исходящие из слоя $s$ состояния $\left| {q_{{n_{k}^{s}}}^{s}} \right\rangle $ объединяются в квантовое состояние

где ${{K}_{s}}$ – число q-нейронов в слое $s$, так, что при выполнении условия в нижнем индексе, состояние включается в состояние $\left| {q_{n}^{{s + 1}}} \right\rangle $, а иначе – не включается. Так образуются все блоки $B_{k}^{s}$ для всех слоев КНС. В сети прямого распространения в последнем слое измерим все регистры. Величины ${v}_{k}^{s}$, которые получаются в результате измерений, можно объединить в одно число, двоичная запись которого будет иметь вид где ${{{v}}^{S}}$ – это последовательная запись измерения регистров в последнем слое (номер S), и так далее. Таким образом, в случае КНС прямого распространения, разрядность числа ${v}$ будет равна числу входящих в схему одночастичных регистров. При этом для хорошего качества классификации необходимо, чтобы было $\log \left( {\max {v} + 1} \right) > l$.

Параметры обучения (аналоги весов) в данном случае будут составлять матрицу ${{K}_{{va}}}$, элементы которой равны количеству случаев получения при измерении значения ${v}$ при настоящей метке a. Далее, для осуществления собственно классификации, найдем частоты меток a при полученном значении ${v}$:

и шкалируем их на единичный отрезок:

Для использования при классификации построим словарь $D$, в котором каждому ключу – предполагаемой метке – сопоставим список значений – чисел ${v}$ – таких, при которых нормированная частота ${{\kappa }_{{{v}a}}}$ превышает частоту появления самой распространенной метки в обучающей выборке (возможен вариант “превышает среднюю частоту меток в выборке”).

где ${{t}_{a}}$ – количество значений ${v}$, выбранных по критерию для данного a. Словарь $D$ дает возможность сопоставить метку пробному экземпляру данных после его прохождения через КНС: меткой будет тот ключ в словаре D, в списке которого окажется полученное при измерении число.

Алгоритм обучения будет следующим.

Вход: обучающие данные; нулевая матрица ${{K}_{{va}}}$; правило отбора значений ${v}$ для ключа $a$ в словарь $D$.

Выход: словарь $D,$ матрица ${{K}_{{va}}}$.

Процедура:

1. Пропустить экземпляр данных через КНС и получить результат измерений ${v}$.

2. Получить истинную метку $a$ этого экземпляра данных.

3. Увеличить значение ${{K}_{{{v}a}}}$ на 1.

4. Повторить шаги 1–3 для всех экземпляров обучающих данных.

5. Вычислить все ${{\kappa }_{{{v}a}}}$ по формулам (6) и (7).

6. Для каждого значения метки a перебрать все возможные значения ${v}$ и, при выполнении правила отбора, занести значение ${v}$ в список по ключу $a$ словаря $D$.

Алгоритм работы классификатора на тестовых данных.

Вход: экземпляр данных без метки; словарь $D$, матрица ${{K}_{{va}}}$.

Выход: метка экземпляра данных или $None$.

Процедура:

1. Пропустить экземпляр данных через КНС и получить результат измерений ${v}$.

2. Выбрать ключ $a$, по которому ${v}$ находится в списке в словаре $D$.

3. Если шаг 2 дал результат, то выдать $a$, иначе выдать $None$.

Если через какое-то время истинная метка для тестового экземпляра данных становится известной, то этот экземпляр вместе с меткой подают на вход алгоритма обучения. Тем самым достигается онлайн-обучение: обучающие данные корректируются по мере прихода новых данных с раз-меткой.

Рассмотрим эти алгоритмы на примере датасета о задержках авиарейсов, взятого с ресурса kaggle.com²². Исходный датасет содержит 7 признаков и одну метку. Признаки: авиакомпания, рейс, аэропорт отправления, аэропорт назначения, день недели, время. Метка – наличие задержки. В датасете 539383 экземпляра данных, из которых 240264 имеют метку 1, остальные – 0. Все значения признаков были переведены в целые числа и размерность датасета была обратимым образом увеличена до 30 – это позволило представлять данные в виде состояния 4-частичной квантовой системы. Для таких входящих состояний можно сделать либо однослойную КНС с единственным $q$-нейроном, либо двухслойную с двумя $q$-нейронами в первом слое и одним во втором. Рассмотрим двухслойную КНС.

Очевидно, ${v} = 0, \ldots ,15$, так как на входе 4-частичное состояние. В этом датасете экземпляры данных упорядочены по времени. Поэтому поставим задачу так: будем прогнозировать задержки 1000 рейсов на основе задержек предыдущих 1000 рейсов. Таким образом, обучающая выборка у нас будет включать 1000 экземпляров данных. Реализуем обучающий и тестовый алгоритмы и получим метрику F1 для каждого теста. Очевидно, таких тестов в этом датасете возможно сделать 538, но мы ограничимся 53 – этого будет достаточно, чтобы увидеть тенденцию. Как видно на графике, представленном на рис. 3, значение метрики сильно изменяется от теста к тесту. Однако, во-первых, среднее значение F1 почти в два раза превышает частоту задержек в полной обучающей выборке (из 53 000 экземпляров) и, во-вторых, снижение качества классификации наблюдается с примерной периодичностью, что может говорить о накоплении неучтенных долгосрочных факторов. При использовании рекуррентной КНС это обстоятельство должно быть хотя бы частично преодолено.

3.2. Онлайн обучение в рекуррентной КНС

Обратимся теперь к рекуррентной КНС, онлайн обучаемой без оптимизации. В отличие от предыдущего случая сети прямого распространения, теперь можно запускать экземпляры данных, относящиеся к разным моментам времени, в разные слои сети. Алгоритм обучения при этом будет основан на тех же соображениях, что и раньше, но на вход его будут поданы экземпляры размеченных данных $\left( {\left| {{{q}_{t}}} \right\rangle ,a} \right)$ с имеющимися уникальной временной меткой $t$ и классом $a$. Схема рекуррентной КНС для рассматриваемого датасета авиарейсов представлена на рис. 4. Количество входящих экземпляров данных может быть почти произвольным – ограничено только числом имеющихся кубитов и количеством имеющихся экземпляров данных. Справа от схемы рис. 4 будет стоять такое же завершение, как в случае КНС прямого распространения. И на выходе этой сети будет 4-разрядное двоичное число.

Для эксперимента было выбрано число последовательных векторов, входящих в рекуррентную сеть, равное 5000. Может показаться, что для этого потребуются тысячи кубитов, но это не так: достаточно тех 12 кубитов, что использованы на схеме рис. 4, поскольку обведенная контуром часть схемы может повторяться на тех же кубитах, устанавливаемых каждый раз в требуемое состояние.

Рекуррентная сеть в эксперименте использовалась для предсказания задержки последнего рейса из пакета векторов, т.е., каждого 5000-го рейса. Сеть обучалась накопительным итогом (накапливались значения в матрице $K$).

Эксперимент показал, что рекуррентная КНС показывает более качественную классификацию, чем КНС прямого распространения. В то же время, после определенного числа шагов с накоплением значений, качество начинает ухудшаться. Это явление, аналогичное переобучению.

Результат предсказания задержек рейсов с помощью рекуррентной КНС представлен на рис. 5. На нем видно, что для принятых параметров эксперимента, максимальное значение метрики F1 было достигнуто на примерно 10 проходе и дальше качество начало падать. Таким образом, имеет смысл ограничить накопление значений в матрице $K$ 10 шагами.

Десять шагов с пакетами длиной 5000 – это обучение на истории 50 000 экземпляров. При этом на ближайшие 5–10 шагов сеть дает качество предсказания, близкое к 80%.