Global Roots and Poles Finding Algorithm on Quantum Computer

Abstract

In this paper, the implementation of the global roots and poles finding algorithm for a complex-valued function of a complex variable on a quantum computer, which allows for solving general nonlinear algebraic equations, is presented. The considered function is sampled with the use of Delaunay’s triangulation on the complex plane and a phase quadrant, in which the value of the function is located, is computed on a classical computer for all of the sampling nodes. Then, if the real and imaginary parts of the function simultaneously change signs for both ends of the same edge in the mesh, then a zero of the function is located in the region around this edge. In order to detect such edges, the mesh is transformed into a one-dimensional array and the required edges, where the sign simultaneously changes for real and imaginary parts of the function, are found with the use of quantum Grover’s algorithm. If the mesh consists of P edges, the computational overhead of this operation, in terms of oracle queries, is equal to $O(\sqrt {P})$ on a quantum computer, instead of $O(P)$ on a classical one. Finally, the existence of function zeros and poles is proved with the use of Cauchy’s argument principle on a classical computer, and the output results are computed, based on the mesh refinement, with the assumed numerical precision of computations. Our method is implemented in Python with the use of the Qiskit software development kit and its applicability is proved by quantum emulations.

Keywords

• Quantum computing
• quantum algorithm
• quantum simulation
• complex roots finding algorithm