The Present and Future of Discrete Logarithm Problems on Noisy Quantum
  Computers
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
post-processing algorithm. Evaluating and predicting the instance size that
quantum devices can solve is an emerging research topic. In this paper, we
propose a quantitative measure based on the success probability of the
post-processing algorithm to determine whether an experiment on a quantum
device (or a classical simulator) succeeded. We also propose a procedure to
modify bit strings observed from a Shor circuit to increase the success
probability of a lattice-based post-processing algorithm. We report preliminary
experiments conducted on IBM-Quantum quantum computers and near-future
predictions based on noisy-device simulations. 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 DLP and integer factoring
instances.
Yoshinori Aono Sitong Liu Tomoki Tanaka Shumpei Uno Rodney Van Meter Naoyuki Shinohara Ryo Nojima