assistant professor
ассистент
Cand. Sci. (Eng.), Associate Professor
кандидат технических наук, доцент
The article proposes a method for solving a system of equations based on a quantum Grover search algorithm. Finding a solution to a system of equations is a computationally complex process and can be considered as an algorithmic primitive for solving various problems. The computational complexity of finding a solution to a system of equations has led to attempts to implement this problem using quantum computing. So, the concept of Quantum Linear System Problem (QLSP) is well known – the solution of systems of linear equations using a quantum computer. The method proposed in the article is considered within the framework of solving a system of algebraic equations. A feature of this method is a modification of the Grover algorithm, which consists in placing the condition of each equation in a separate Grover iteration, which differs from the usual use of Grover iterations – repeats of the oracle and the diffusion operator, in which the oracle does not change. Thus, the construction of its own oracle function of the Grover algorithm for each equation of the system is implemented within the framework of the implementation of the general scheme. A feature of the proposed method is the approximation of the problem of solving a system of equations to a problem resembling the pRSCIiple of training generative-adversarial neural networks (GAN) using Grover’s algorithm, since Grover’s algorithm allows analyzing all possible values of variables. Thanks to the use of the modified Grover algorithm, the proposed method is not limited by the mandatory condition that the number of equations is equal to the number of unknowns, since solutions to incomplete systems of equations can be found within the limits imposed by the size of the allocated quantum registers. A quantum circuit optimization method is also proposed, which consists in implementing some calculations directly in the body of the Grover algorithm. The claimed efficiency of the proposed method is
В статье предлагается метод решения системы уравнений на основе квантового алгоритма поиска Гровера. Поиск решения системы уравнений является вычислительно сложным процессом и его можно рассматривать, как алгоритмический примитив для решения различных задач. Вычислительная сложность поиска решения системы уравнений привела к попыткам реализовать данную задачу при помощи квантовых вычислений. Так, хорошо известно понятие Quantum Linear System Problem (QLSP) – решение систем линейных уравнений с помощью квантового компьютера. Предложенный в статье метод рассматривается в рамках решения системы алгебраических уравнений. Особенностью данного метода является модификация алгоритма Гровера, которая заключается в размещении условия каждого уравнения в отдельной итерации Гровера, что отличается от обычного применения итераций Гровера – повторов оракула и оператора диффузии, при которых оракул не изменяется. Таким образом, реализовано построение собственной функции-оракула алгоритма Гровера для каждого уравнения системы в рамках реализации общей схемы. Особенностью предложенного метода является приближение задачи решения системы уравнений к задаче напоминающей принцип обучения генеративно-состязательных нейронных сетей (GAN) с помощью алгоритма Гровера, так как алгоритм Гровера позволяет анализировать все возможные значения переменных. Благодаря использованию модифицированного алгоритма Гровера, предложенный метод не ограничен обязательным условием равенства количества уравнений числу неизвестных, так как решения неполных систем уравнений могут быть найдены в пределах ограничений, накладываемых размером выделенных квантовых регистров. Предлагается также метод оптимизации квантовой схемы, который заключается в реализации некоторых вычисления непосредственно в теле алгоритма Гровера. Заявленная эффективность предложенного метода составляет