Quantum computation of Groebner basis through F4 and F5 algorithms
Ichio Kikuchi, Akihito Kikuchi · 2022
Our main concern in this article is how to apply quantum algorithms to compute Groebner basis through Faugere's F4 and F5 algorithms, which are regarded as the most effective algorithms for this purpose. We give examples and pseudo-codes for these algorithms and investigate where we can apply quantum algorithms. As a result, we have the designs (or the pseudo-codes) of quantum versions of the F4 and F5 algorithms by replacing classical algorithms with quantum ones. The quantum versions of F4 and F5 algorithms are, in nature, the extensions of the quantum Gaussian-Jordan elimination of Diepp, since the computations of Groebner bases are practicable through the matrix representations. In the computation of Groebner bases, quantum algorithms serve to construct the matrices as small as possible (according to the fundamental idea of F4 and F5) and to find the pivotal element as quickly as possible.