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 ...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.展开更多
基金supported by the National Key R&D Program of China(2021YFB3100100)the National Natural Science Foundation of China(61972413,61901525)
文摘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.
