Li Yang

Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, we first propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition and construct their specific quantum circuits. Unlike previous related works, our quantum algorithms are universal. Specifically, the two quantum algorithms can both compute 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 with other registers and keep the data qubits unchanged. On this basis, we apply the two quantum algorithms as a subroutine to parallel Simon's algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm, respectively. Afterwards, we construct a quantum classifier within Grover Meets Simon algorithm and the test oracle within Alg-PolyQ2 algorithm in detail, including their respective quantum circuits. To our knowledge, no such specific analysis has been done before. We rigorously analyze the success probability of those algorithms to ensure that the success probability based on the proposed quantum algorithms will not be lower than that of those original algorithms. Finally, we discuss the lower bound of the number of CNOT gates for solving quantum linear systems of equations with coherent superposition, and our quantum algorithms reach the optimum in terms of minimizing the number of CNOT gates. Furthermore, our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers, within the effective working time of an ion trap quantum computer.

Since the elliptic curve discrete logarithms problem (ECDLP) was proposed, it has been widely used in cryptosystem because of its strong security. Although the proposal of the extended Shor's algorithm offers hope for cracking ECDLP, it is debatable whether the algorithm can actually pose a threat in practice. From the perspective of the quantum circuit of the algorithm, we analyze the feasibility of cracking ECDLP with improved quantum circuits using an ion trap quantum computer. We give precise quantum circuits for extended Shor's algorithm to calculate discrete logarithms on elliptic curves over prime fields, including modulus subtraction, three different modulus multiplication, modulus inverse, and windowed arithmetic. Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit, we minimize the number of CNOTs, which greatly affects the time to run the algorithm on an ion trap quantum computer. First, we give the implementation of the basic arithmetic with the lowest known number of CNOTs and the construction of an improved modular inverse, point addition, and the windowing technique. Then, we precisely estimate the number of improved quantum circuits needed to perform the extended Shor's algorithm for factoring an n-bit integer. We analyze the running time and feasibility of the extended Shor's algorithm on an ion trap quantum computer according to the number of CNOTs. Finally, we discussed the lower bound of the number of CNOTs needed to implement the extended Shor's algorithm.

We present improved quantum circuit for modular exponentiation of a constant, which is the most expensive operation in Shor's algorithm for integer factorization. While previous work mostly focuses on minimizing the number of qubits or the depth of circuit, we try to minimize the number of CNOT gate which primarily determines the running time on a ion trap quantum computer. First, we give the implementation of basic arithmetic with known lowest number of CNOT gate and the construction of improved modular exponentiation of a constant by accumulating intermediate date and windowing technique. Then, we precisely estimate the number of improved quantum circuit to perform Shor's algorithm for factoring a $n$-bit integer, which is $217\frac{n^3}{\log_2n}+4n^2+n$. According to the number of CNOT gates, we analyze the running time and feasibility of Shor's algorithm on a ion trap quantum computer. Finally, we discuss the lower bound of CNOT numbers needed to implement Shor's algorithm.

We investigate the exact effect on ion trap quantum computation after field quantization. First an exact expression of failure probability from field quantization after many CNOT operations in Cirac-Zoller scheme is given. It is proportional to operation number and the amplitude of $|1\rangle_x |0\rangle_y$ or $|1\rangle_x |1\rangle_y$ in initial state, and inverse proportional to mean number of photons and amplitude of $|0\rangle_x |0\rangle_y$ or $|0\rangle_x |1\rangle_y$ in initial state. Then we calculate the failure probability when the limitation to mean number of photons in sideband transition is considered. When the initial state is $|1\rangle_x |0\rangle_y$ or $|1\rangle_x |1\rangle_y$, after about $10^2$ times of CNOT operations, failure probability is no less than $10^{-2}$, while $10^{-2}$ is the known maximum threshold in fault-tolerant quantum computation. Then when the initial state is $|1\rangle_x |0\rangle_y$ or $|1\rangle_x |1\rangle_y$, the number of CNOT gates on the same pair of physical qubits should be no more than $10^2$ in one error-correction period, or else the computation cannot be implemented reliably. This conclusion can help to determine the number of CNOT operations between coding and decoding in one error-correction period in fault-tolerant quantum computation.

We investigate the post-quantum security of the encrypted key exchange(EKE) protocols based on some basic physical parameters of ion-trap quantum computer, and show that the EKE protocol with a 40-bit password will be secure against a quantum adversary with several ion-trap quantum computers. We present a password encrypted no-key protocol to resist middle-man attack, and prove that it is also with the post-quantum security. The analysis presented here is probably of general meaning for the security evaluation of various hybrid cryptosystems.

Rabi oscillation of a two-level system driven by a pulse train is a basic process involved in quantum computation. We present a full quantum treatment of this process and show that the population inversion of this process collapses exponentially, has no revival phenomenon, and has a dual-pulse structure in every period. As an application, we investigate the properties of this process in ion-trap quantum computation. We find that in the Cirac--Zoller computation scheme, when the wavelength of the driving field is of the order $10^{-6}$ m, the lower bound of failure probability is of the order $10^{-2}$ after about $10^2$ controlled-NOT gates. This value is approximately equal to the generally-accepted threshold in fault-tolerant quantum computation.