Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems

Abstract

Recently Chen and Gao~\cite{ChenGao2017} proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems. The key idea of their approach is to apply a Quantum Linear System (QLS) algorithm to a Macaulay linear system over $\mathbb{C}$, which is derived from the Boolean polynomial system. The efficiency of their algorithm depends on the condition number of the Macaulay matrix. In this paper, we give a strong lower bound on the condition number as a function of the Hamming weight of the Boolean solution, and show that in many (if not all) cases a Grover-based exhaustive search algorithm outperforms their algorithm. Then, we improve upon Chen and Gao's algorithm by introducing the Boolean Macaulay linear system over $\mathbb{C}$ by reducing the original Macaulay linear system. This improved algorithm could potentially significantly outperform the brute-force algorithm, when the Hamming weight of the solution is logarithmic in the number of Boolean variables. Furthermore, we provide a simple and more elementary proof of correctness for our improved algorithm using a reduction employing the Valiant-Vazirani affine hashing method, and also extend the result to polynomial systems over ${\mathbb{F}}_q$ improving on subsequent work by Chen, Gao and Yuan \cite{ChenGao2018}. We also suggest a new approach for extracting the solution of the Boolean polynomial system via a generalization of the quantum coupon collector problem \cite{arunachalam2020QuantumCouponCollector}.

arXiv comment22 pages

References in corpus (14)

• Quantum algorithm for solving linear systems of equations
• Tight bounds on quantum searching
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Preconditioned quantum linear system algorithm
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• On the Complexity of Solving Quadratic Boolean Systems
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Quantum Circulant Preconditioner for Linear System of Equations
• Solving multivariate polynomial systems and an invariant from commutative algebra
• Quantum Coupon Collector

Cited by in corpus (1)

• Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems