Pitfalls of the sublinear QAOA-based factorization algorithm

• URL: http://arxiv.org/abs/2303.04656v6
• Date: Thu, 14 Dec 2023 10:23:38 GMT
• Title: Pitfalls of the sublinear QAOA-based factorization algorithm
• Authors: Sergey V. Grebnev, Maxim A. Gavreev, Evgeniy O. Kiktenko, Anton P. Guglya, Albert R. Efimov, Aleksey K. Fedorov
• Abstract summary: The prime factorization problem is at the heart of widely deployed public-key cryptographic tools. The implementation of Shor's quantum factorization algorithm requires significant resources scaling linearly with the number size. Recent proposal by Yan et al. claims a possibility of solving the factorization problem with sublinear quantum resources.
• Score: 0.8987776881291144
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography [0.0]
  This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations.
  arXiv  Detail & Related papers  (2024-10-07T11:55:23Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Generative AI-enabled Quantum Computing Networks and Intelligent Resource Allocation [80.78352800340032]
  Quantum computing networks execute large-scale generative AI computation tasks and advanced quantum algorithms. efficient resource allocation in quantum computing networks is a critical challenge due to qubit variability and network complexity. We introduce state-of-the-art reinforcement learning (RL) algorithms, from generative learning to quantum machine learning for optimal quantum resource allocation.
  arXiv  Detail & Related papers  (2024-01-13T17:16:38Z)
• A comment on "Factoring integers with sublinear resources on a superconducting quantum processor" [0.0]
  We present an open-source implementation of the Schnorr's lattice-based integer factorization algorithm. Our implementation shows that the claimed sublinear lattice dimension for the Hybrid quantum+classical version of Schnorr's successfully factors integers only up to 70 bits. We hope that our implementation serves as a playground for the community to easily test other hybrid quantum + classical integer factorization algorithm ideas.
  arXiv  Detail & Related papers  (2023-07-18T21:46:54Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Factoring integers with sublinear resources on a superconducting quantum processor [11.96383198580683]
  Shor's algorithm has seriously challenged information security based on public key cryptosystems. To break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. We report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm.
  arXiv  Detail & Related papers  (2022-12-23T14:45:02Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP) We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
  arXiv  Detail & Related papers  (2021-09-23T07:46:20Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.