A New Hybrid Algorithm for Multivariate Polynomial System Solving

The method of solving a polynomial system of equations plays a crucial role in various domains of cryptography. For instance, multivariate cryptography using public keys relies on the computational difficulty of solving a multivariate polynomial problem over a finite field. Aram Harrow, Avinatan Hassidam, and Seth Loyd proposed a quantum algorithm (HHL) to solve the Equation Ax = b, where A is a Hermitian matrix. Compared to the fastest classical approach, which has an \(O(N \sqrt{\kappa })\) $O(N\sqrt{\kappa })$ run time, the HHL algorithm has a poly \((\text {Log}N, \kappa )\) $(\text{Log}N,\kappa )$ runtime that offers exponential speed-up. To solve a set of multivariate polynomial equations, we turned to the HHL method for assistance. In particular, our proposed algorithm will be a building block for future quantum XL algorithms. Here, we have proposed a new hybrid quantum XL algorithm and used it to solve a standard problem to demonstrate its efficacy.