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.
19 pages, 2 figures, 3 tables; algorithm descriptions are extended
References in corpus (15)
- Quantum Computing
- Variational Quantum Algorithms
- A Quantum Approximate Optimization Algorithm
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Experimental demonstration of Shor's algorithm with quantum entanglement
- Demonstration of Shor's quantum factoring algorithm using photonic qubits
- 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"