Survey on Quantum Algorithms for Solving Hard Problems in Lattice
Author:
Affiliation:

Clc Number:

TP309

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    With the rapid development of Lattice-based post-quantum cryptography, algorithms for hard problems in Lattices have become an essential tool for evaluating the security of post-quantum cryptographic schemes. Algorithms such as enumeration, sieve, and Lattice basis reduction have been developed under the classical computing model, while quantum algorithms for solving hard problems in Lattices, such as quantum sieve and quantum enumeration, are gradually attracting attention. Although Lattice problems possess post-quantum properties, techniques such as quantum search can accelerate a range of Lattice algorithms. Given the challenges involved in solving hard problems in Lattices, this study first summarizes and analyzes the research status of quantum algorithms for such problems and organizes their design principles. Then, the quantum computing techniques applied in these algorithms are introduced, followed by an analysis and comparison of their computational complexities. Finally, potential future developments and research directions for quantum algorithms addressing Lattice-based hard problems are discussed.

    Reference
    Related
    Cited by
Get Citation

曹金政,罗向阳,陈晓峰,程庆丰.格上困难问题量子求解算法综述.软件学报,2026,37(1):398-424

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:January 18,2024
  • Revised:April 07,2024
  • Adopted:
  • Online: July 30,2025
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063