%0 Journal Article
%A Duan Qianheng
%A Fei Yangyang
%A Lv Lihui
%A Ma Zhi
%A Meng Xiangdong
%A Wang Hong
%T Methods for solving equations with errors based on the HHL algorithm
%D 2022
%R 10.19682/j.cnki.1005-8885.2022.2015
%J 中国邮电高校学报（英文）
%P 9-20
%V 29
%N 4
%X To solve polynomial systems, Harrow, Hassidim, and Lloyd (HHL) proposed a quantum algorithm called HHL algorithm. Based on the HHL algorithm, Chen et al. presented an algorithm, the solving the Boolean solutions of polynomial systems (PoSSoB) algorithm. Furthermore, Ding et al. introduced the Boolean Macaulay matrix and analyzed the lower bound on the condition number. Inspired by Ding et al. 's research, several related algorithms are proposed in this paper. First, the improved PoSSoB algorithm using the Boolean Macaulay matrix is proved to have lower complexity. Second, for solving equations with errors, a quantum algorithm for the max-polynomial system solving (Max-PoSSo) problem is proposed based on the improved PoSSoB algorithm. Besides, the Max-PoSSo algorithm is extended to the learning with errors (LWE) problem and its special case, the learning parity with noise (LPN) problem, providing a quantitative criterion, the condition number, for the security of these basic problems.

%U https://jcupt.bupt.edu.cn/CN/10.19682/j.cnki.1005-8885.2022.2015