Factoring integers via Schnorr's algorithm assisted with VQE

• URL: http://arxiv.org/abs/2411.16632v1
• Date: Mon, 25 Nov 2024 18:11:10 GMT
• Title: Factoring integers via Schnorr's algorithm assisted with VQE
• Authors: Luis Sánchez Cano, Ginés Carrascal de las Heras, Guillermo Botella Juan, Alberto del Barrio García,
• Abstract summary: Current asymmetric cryptography is based on the principle that while classical computers can efficiently multiply large integers, the inverse operation, factorization, is significantly more complex. For sufficiently large integers, this factorization process can take in classical computers hundreds or even thousands of years to complete. This work analyses this article and replicates the experiments they carried out, but with a different quantum method (VQE) being able to factor the number 1961.
• Score: 0.0937465283958018
• License:
• Abstract: Current asymmetric cryptography is based on the principle that while classical computers can efficiently multiply large integers, the inverse operation, factorization, is significantly more complex. For sufficiently large integers, this factorization process can take in classical computers hundreds or even thousands of years to complete. However, there exist some quantum algorithms that might be able to factor integers theoretically -- the theory works properly, but the hardware requirements are far away from what we can build nowadays -- and, for instance, Yan, B. et al. ([14]) claim to have constructed a hybrid algorithm which could be able even to challenge RSA-2048 in the near future. This work analyses this article and replicates the experiments they carried out, but with a different quantum method (VQE), being able to factor the number 1961.

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)
• 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)
• 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)
• Integer Factorization by Quantum Measurements [0.0]
  Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on classical computers. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a quantum-time algorithm for integer factorization. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement.
  arXiv  Detail & Related papers  (2023-09-19T17:00:01Z)
• 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 Multiplication Algorithm Based on the Convolution Theorem [0.0]
  We propose a quantum algorithm for integer multiplication with time complexity $O(sqrtnlog2 n)$. Unlike the Harvey algorithm, our algorithm does not have the restriction of being applicable solely to extremely large numbers. The paper also reviews the history and development of classical multiplication algorithms and motivates us to explore how quantum resources can provide new perspectives and possibilities for this fundamental problem.
  arXiv  Detail & Related papers  (2023-06-14T12:40:54Z)
• 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)
• 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)
• 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)
• Quantum Computing without Quantum Computers: Database Search and Data Processing Using Classical Wave Superposition [101.18253437732933]
  We present experimental data on magnetic database search using spin wave superposition. We argue that in some cases the classical wave-based approach may provide the same speedup in database search as quantum computers.
  arXiv  Detail & Related papers  (2020-12-15T16:21:53Z)

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.