The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
arXiv:2111.06102 · doi:10.1109/TQE.2022.3183385
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 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.
References in corpus (19)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- Error mitigation for short-depth quantum circuits
- Validating quantum computers using randomized model circuits
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Practical Quantum Error Mitigation for Near-Future Applications
- Realization of a scalable Shor algorithm
- An approximate Fourier transform useful in quantum factoring
- Computing prime factors with a Josephson phase qubit quantum processor
- Pretending to factor large numbers on a quantum computer
- Approximate Quantum Fourier Transform with T gates
- An Experimental Study of Shor's Factoring Algorithm on IBM Q
- Factoring in a Dissipative Quantum Computer
- Demonstration of Shor's factoring algorithm for N=21 on IBM quantum processors
- Quantum algorithms for computing short discrete logarithms and factoring RSA integers
- Forecasting timelines of quantum computing
- Subdivided Phase Oracle for NISQ Search Algorithms
- Revisiting Shor's quantum algorithm for computing general discrete logarithms