首页|Algorithm for solving quantum linear systems of equations with coherent superposition and extended applications

Algorithm for solving quantum linear systems of equations with coherent superposition and extended applications

扫码查看
原文链接
  • NETL
  • NSTL
  • Oxford Univ Press
Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, two quantum algorithms are proposed to solve quantum linear systems of equations with coherent superposition, and their specific quantum circuits are constructed. In contrast to previous related studies, our quantum algorithms are universal, computing both the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled from the other registers while keeping the data qubits unchanged. On this basis, the two quantum algorithms are applied as subroutines to parallel Simon's algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm. Subsequently, a quantum classifier within Grover Meets Simon algorithm and a detailed test oracle within Alg-PolyQ2 algorithms are constructed, including their respective quantum circuits. To the best of our knowledge, no such specific analysis has been previously performed. The success probability of these algorithms is rigorously analyzed to ensure that the probability of success on the proposed quantum algorithms will not be lower than that of the original algorithms. Finally, we discuss the lower bound of the number of controlled-NOT gates for solving quantum linear systems of equations with coherent superposition. Our analysis indicates that the proposed algorithms are suitable for conducting attacks against lightweight symmetric ciphers within the effective working time of an ion-trap quantum computer.

Qiqing Xia、Qianru Zhu、Huiqin Xie、Li Yang

展开 >

Institute of Information Engineering, Chinese Academy of Sciences, No. 19, Shucun Road, Haidian District, Beijing, 100085, China||Key Laboratory of Cyberspace Security Defense, No. 19, Shucun Road, Haidian District, Beijing, 100085, China||School of Cyber Security, University of Chinese Academy of Sciences, No. 19 Yuquan Road, Shijingshan District, Beijing, 100049, China

Beijing Electronic Science and Technology Institute, No. 7, Fufeng Road, Fengtai District, Beijing, 100070, China

Institute of Information Engineering, Chinese Academy of Sciences, No. 19, Shucun Road, Haidian District, Beijing, 100085, China||Key Laboratory of Cyberspace Security Defense, No. 19, Shucun Road, Haidian District, Beijing, 100085, China

2025

10.1093/comjnl/bxae129

The computer journal

The computer journal

ISSN：0010-4620
年,卷(期)：2025.68(5)
  • 36