Quantum computation of Groebner basis
Ichio Kikuchi, Akihito Kikuchi · 2021
In this essay, we examine the feasibility of quantum computation of Gr\"obner basis which is a fundamental tool of algebraic geometry. The classical method for computing Gr\"obner basis is based on Buchberger's algorithm, and our question is how to adopt quantum algorithm there. A Quantum algorithm for finding the maximum is usable for detecting head terms of polynomials, which are required for the computation of S-polynomials. The reduction of S-polynomials with respect to a Gr\"obner basis could be done by the quantum version of Gauss-Jordan elimination of matrices which represents polynomials. However, the frequent occurrence of zero-reductions of polynomials is an obstacle to the effective application of quantum algorithms. This is because zero-reductions of polynomials occur in non-full-rank matrices, for which quantum linear systems algorithms (through the inversion of matrices) are inadequate, as ever-known quantum linear solvers (such as Harrow-Hassidim-Lloyd) require the clandestine computations of the inverses of eigenvalues. Such algorithms should be used in limited situations with the guarantee that the matrices could be inverted. For example, the transformation from the non-reduced Gr\"obner basis to the reduced one is of this sort, and the quantum algorithms surely achieve the partial speedup of the computations.