A Method for Solving a System of Equations Based on the PRSCIiple of Training Generative-adversarial Neural Networks (GAN) Using a Modified Grover Algorithm

Full Text

ВВЕДЕНИЕ

Рост сложности практических задач приводит к росту сложности вычислений, необходимых для их решения [1]. Современные гиперсистемы характеризуются наличием сложных внутренних и внешних связей, динамическим характером этих связей, использованием больших данных и сложных алгоритмических вычислений. Устойчивое развитие таких систем связано с наличием вычислительных мощностей, обеспечивающих быстрое и качественное решение различных задач. Для увеличения скорости вычислений используются алгоритмические примитивы, одним из которых является задача поиска решения системы уравнений. Данная задача является вычислительно сложной, что привело к попыткам реализовать данную задачу при помощи квантовых вычислений. Известны различные способы поиска решения линейных систем уравнений на квантовом компьютере под общим названием Quantum Linear System Problem (QLSP) [2; 3]. Решение QLSP позволяет получить квантовые примитивы для реализации более сложных вычислений. Однако ограничения, связанные с линейностью сужают круг практических задач, в которых эти вычисления могут быть использованы. В этой связи, в статье предлагается метод решения системы уравнений по принципу обучения генеративно-состязательных нейронных сетей (GAN) с помощью алгоритма Гровера [4].

МЕТОД РЕШЕНИЯ СИСТЕМЫ УРАВНЕНИЙ НА ОСНОВЕ МОДИФИЦИРОВАННОГО КВАНТОВОГО АЛГОРИТМА ПОИСКА ГРОВЕРА

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

Предложенный метод заключается в решении следующих задач.

1. Реализация вычислений в рамках каждого уравнения в отдельной итерации Гровера. Такая модификация не является обычным применением итераций Гровера (обычно итерации Гровера это повтор оракула и оператора диффузии, при которых оракул не изменяется).
2. Получение на выходе алгоритма наибольшей вероятности измерения для тех состояний, которые при разбиении на соответствующие регист-ры, удовлетворяют условиям всех уравнений.
3. Использование при вычислениях принципа обучения генеративно-состязательных нейронных сетей (GAN) с помощью алгоритма Гровера [4], поскольку алгоритм Гровера позволяет анализировать все возможные значения переменных. При сравнении с генеративно-состязательными нейронными сетями – этап формирования равновероятных значений квантового регистра будет сравним с «генератором», а последующие функции-оракулы сравнимы с набором различных последовательных «дискриминаторов».
4. Построение собственной функции-оракула алгоритма Гровера для каждого уравнения системы в рамках реализации общей схемы.
5. Представление решений алгоритма в виде битовой строки, которую необходимо разбить на отдельные регистры размерностью, определенной в процессе построения схемы.
6. Реализация некоторых вычислений прямо в теле алгоритма Гровера в целях оптимизации квантовой схемы.
7. Получение оценки вычислительной сложности данного метода, исходя из количества итераций Гровера равной O(2ⁿ/m), где n – количество кубитов, занимаемых неизвестными переменными в «теле» алгоритма Гровера, а m – ожидаемое число решений.
8. Возможность реализации дальнейшего масштабирования схемы и добавление коэффициентов с помощью методов, предложенных в статьях [5; 6].

ПРИМЕНЕНИЕ МЕТОДА

Рассмотрим применение данного метода на примере решения системы уравнений:

$\left\{\begin{array}{l}{с}_1{x}_1\times {с}_2{x}_2=y_1\\ {с}_1{x}_1+{с}_2{x}_2=y_2\end{array}\right.$, (1)

Будем считать известными значения c_i и y_i.

На рис. 1 представлена реализация решения системы уравнений (1) на основе квантового алгоритма поиска Гровера. Элементы «y₁ =», «y₂ =», «x₁ =», «x₂ =» являются комментариями, и не оказывают влияния на схему. Для примера схемы на рис. 1: c₁ = c₂ = 1, y₁ = 9, y₂ = 6.

 

Рис. 1. Квантовая схема для решения системы уравнений

Fig. 1. A quantum circuit for solving a system of equations

 

Решение для рассматриваемой системы представлено в виде битовой строки 1111₂, которая разбивается на отдельные регистры размерностью 2 со значениями x₁ = x₂ = 11₂ = 3₁₀ (рис. 2).

 

Рис. 2. Результаты работы квантового алгоритма

Fig 2. Results of the quantum algorithm

 

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

$N_G=||\frac{\pi }{4}\sqrt{\frac{2^n}{m}}||$.

Откуда следует, что принцип квантового параллельного поиска значений среди области значений квантового регистра с помощью алгоритма Гровера дает возможность решать перебором неполные системы уравнений с квадратичным ускорением, по сравнению с классическими алгоритмами.

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

Предложенные схемы разработаны под архитектуру универсальных квантовых компьютеров и могут быть симулированы в соответствующих средах для симуляции квантовых вычислений, таких как Quirk, Qiskit и т.п. или запущены на универсальном квантовом компьютере с соответствующими характеристиками.

ЗАКЛЮЧЕНИЕ

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

1) реализован способ организации вычислений, в рамках каждого уравнения, в виде отдельной модифицированной итерации Гровера. Данный способ позволяет использовать минимальное количество кубитов для решения системы из n уравнений;

2) реализовано построение собственной функции-оракула алгоритма Гровера для каждого уравнения системы в рамках реализации общей схемы;

3) реализованы вычисления непосредственно в теле алгоритма Гровера в целях оптимизации схемы. Реализация представлена во второй половине схемы на рис. 1;

4) использован принцип обучения генеративно-состязательных нейронных сетей (GAN) с помощью алгоритма Гровера для решения системы уравнений;

5) обоснована возможность реализации дальнейшего масштабирования схемы и добавления коэффициентов;

6) обоснована возможность решения систем уравнений, в которых число уравнений не равно числу неизвестных. Благодаря использованию алгоритма Гровера решения неполных систем уравнений могут быть найдены в пределах ограничений, накладываемых размером выделенных квантовых регистров. Это проиллюстрировано в первой половине схемы на рис. 1.

About the authors

Cesar B. Pronin

Moscow Automobile and Road State Technical University (MADI)

Author for correspondence.
Email: caesarpr12@gmail.com
ORCID iD: 0000-0002-9994-1032

assistant professor

Russian Federation, Moscow

Alexandra V. Volosova

Bauman Moscow State Technical University

Email: volosova@bmstu.ru
ORCID iD: 0000-0002-3817-2671

Cand. Sci. (Eng.), Associate Professor

Russian Federation, Moscow

References

Supplementary files