HUBO and QUBO models for Prime factorization

• URL: http://arxiv.org/abs/2301.06738v1
• Date: Tue, 17 Jan 2023 07:49:10 GMT
• Title: HUBO and QUBO models for Prime factorization
• Authors: Kyungtaek Jun
• Abstract summary: The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers p and q satisfying N=p*q. This paper presents a prime factoriaation method using D-Wave quantum computer that can threaten the RSA cryptosystem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers p and q satisfying N=p*q . This paper presents a prime factoriaation method using D-Wave quantum computer that can threaten the RSA cryptosystem. The starting point for this method is very simple, representing two prime numbers as qubits. Then, set the difference between the product of two prime numbers expressed in qubits and N as a cost function, and find the solution when the cost function becomes the minimum. D-Wave's quantum annealer can find the minimum value of any quadratic problem. However, the cost function is to be a higher-order unconstrained optimiaation (HUBO) model because it contains the second or higher order terms. We used a hybrid solver and dimod package provided by -Wave Ocean software development kit (SDK) to solve the HUBO problem. We also successfully factoriaed 102,454,763 with 26 logical qubits. In addition, we factoriaed 1,000,070,001,221 using the range dependent Hamiltonian algorithm.

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)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• Quasi-binary encoding based quantum alternating operator ansatz [7.681120805934572]
  This paper proposes a quasi-binary encoding based algorithm for solving a specific quadratic optimization models with discrete variables. In other parts of the QAOA framework, we also incorporate ideas such as CVaR-QAOA and parameter scheduling methods into our QAOA algorithm.
  arXiv  Detail & Related papers  (2023-04-14T03:49:26Z)
• An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
  We show that for $q = pm$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time. On the other hand, classical algorithms can efficiently solve the problem only for much smaller inverse factors.
  arXiv  Detail & Related papers  (2022-10-20T19:35:50Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem.
  arXiv  Detail & Related papers  (2021-06-02T12:50:56Z)
• Sampling electronic structure QUBOs with Ocean and Mukai solvers [44.62475518267084]
  The most advanced D-Wave Advantage quantum annealer has 5000+ qubits, however, every qubit is connected to a small number of neighbors. To compensate for the reduced number of qubits, one has to rely on special software such as qbsolv. We find that the Mukai QUBO solver outperforms the Ocean qbsolv for all calculations done in the present work.
  arXiv  Detail & Related papers  (2021-02-01T23:16:42Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.