Pitfalls of the sublinear QAOA-based factorization algorithm
arXiv:2303.04656 · doi:10.1109/ACCESS.2023.3336989
Abstract
Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor's quantum factorization algorithm requires significant resources scaling linearly with the number size; taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr's lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.
arXiv comment19 pages, 2 figures, 3 tables; algorithm descriptions are extended
References in corpus (22)
- Quantum Cryptography
- Quantum Computing
- Variational Quantum Algorithms
- A Quantum Approximate Optimization Algorithm
- Noisy intermediate-scale quantum (NISQ) algorithms
- Practical challenges in quantum key distribution
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Realization of a scalable Shor algorithm
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
- Experimental demonstration of Shor's algorithm with quantum entanglement
- Computing prime factors with a Josephson phase qubit quantum processor
- Demonstration of Shor's quantum factoring algorithm using photonic qubits
- Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
- Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
- Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
- Towards security recommendations for public-key infrastructures for production environments in the post-quantum era
- Factoring integers with sublinear resources on a superconducting quantum processor
- Quantum computing at the quantum advantage threshold: a down-to-business review
- Forecasting timelines of quantum computing
- A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"