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

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