A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"

• URL: http://arxiv.org/abs/2307.09651v2
• Date: Fri, 21 Jul 2023 09:32:10 GMT
• Title: A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"
• Authors: Tanuj Khattar, Noureldin Yosri
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computing has the potential to revolutionize cryptography by breaking classical public-key cryptography schemes, such as RSA and Diffie-Hellman. However, breaking the widely used 2048-bit RSA using Shor's quantum factoring algorithm is expected to require millions of noisy physical qubits and is well beyond the capabilities of present day quantum computers. A recent proposal by Yan et. al. tries to improve the widely debated Schnorr's lattice-based integer factorization algorithm using a quantum optimizer (QAOA), and further claim that one can break RSA 2048 using only 372 qubits. In this work, we present an open-source implementation of the algorithm proposed by Yan et. al. and show that, even if we had a perfect quantum optimizer (instead of a heuristic like QAOA), the proposed claims don't hold true. Specifically, our implementation shows that the claimed sublinear lattice dimension for the Hybrid quantum+classical version of Schnorr's algorithm successfully factors integers only up to 70 bits and fails to find enough factoring relations for random 80 bit integers and beyond. We further hope that our implementation serves as a playground for the community to easily test other hybrid quantum + classical integer factorization algorithm ideas using lattice based reductions.

Related papers

• Quantum inspired factorization up to 100-bit RSA number in polynomial time [0.0]
  We attack the RSA factorization building on Schnorr's mathematical framework. We factorize RSA numbers up to 256 bits encoding the optimization problem in quantum systems. Results do not currently undermine the security of the present communication infrastructure.
  arXiv  Detail & Related papers  (2024-10-21T18:00:00Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Large-scale simulation of Shor's quantum factoring algorithm [0.0]
  We show how large GPU-based supercomputers can be used to assess the performance of Shor's algorithm. We find average success probabilities above 50 %, due to a high frequency of "lucky" cases. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors.
  arXiv  Detail & Related papers  (2023-08-09T16:19:52Z)
• 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 Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• 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)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
  We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices. In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-12-23T15:36:59Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)

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.