The Journal of China Universities of Posts and Telecommunications ›› 2022, Vol. 29 ›› Issue (4): 9-20.doi: 10.19682/j.cnki.1005-8885.2022.2015

• Special Topic: Quantum Science and Technology • Previous Articles     Next Articles

Methods for solving equations with errors based on the HHL algorithm

Lv Lihui, Wang Hong, Ma Zhi, Duan Qianheng, Fei Yangyang, Meng Xiangdong   

  1. 1. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China
    2. Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China
  • Received:2022-05-27 Revised:2022-06-05 Accepted:2022-06-11 Online:2022-08-31 Published:2022-08-31
  • Contact: Wang Hong, E-mail:
  • Supported by:
    This work was supported by the National Key R&D Program of China (2021YFB3100100) and the National Natural Science
    Foundation of China (61972413, 61901525).

Abstract: 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.

Key words: Harrow, Hassidim, and Lloyd, polynomial system solving, max-polynomial system solving, learning parity with noise, learning with errors

CLC Number: