The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers

Abstract

The discrete logarithm problem (DLP) is the basis for several cryptographic primitives. Since Shor’s work, it has been known that the DLP can be solved by combining a polynomial-size quantum circuit and a polynomial-time classical postprocessing algorithm. The theoretical result corresponds the situation where a quantum device working with a medium number of qubits of very small errors can solve the DLP. However, all the quantum devices that we can use have a limited number of noisy qubits, as of the noisy intermediate-scale quantum (NISQ) era. Thus, evaluating the instance size that the latest quantum device can solve and giving a future prediction of the size along the progress of quantum devices are emerging research topics. This article contains two proposals to discuss the performance of quantum devices against the DLP in the NISQ era: 1) a quantitative measure based on the success probability of the postprocessing algorithm to determine whether an experiment on a quantum device (or a classical simulator) succeeded; and 2) a procedure to modify bit strings observed from a Shor’s circuit to increase the success probability of a lattice-based postprocessing algorithm. In this article, we conducted our experiments with the ibm_kawasaki device and discovered that the simplest circuit (7 qubits) from a 2-bit DLP instance achieves a sufficiently high success probability to proclaim the experiment successful. Experiments on another circuit from a slightly harder 2-bit DLP instance, on the other hand, did not succeed, and we determined that reducing the noise level by half is required to achieve a successful experiment. Finally, we give a near-term prediction based on required noise levels to solve some selected small DLPs and integer factoring instances.

Keywords

• Discrete logarithm problem (DLP)
• IBM quantum
• lattice
• postprocessing method
• Shor’s algorithm