Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Reducing the Number of Qubits in Quantum Factoring

Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher

Published Jan 1, 2025• 11 citations
Publisher
DOI
10.1007/978-3-032-01878-6_13

Related papers

Reducing the Number of Qubits in Quantum Information Set Decoding

Clémence Chevignard, Pierre-Alain Fouque, André Schrottenloher

Lecture notes in computer science•Dec 11, 2024•7 citations

Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The "deduc-reduc" method and its application to quantum factorization of numbers

Richard Tanburn, Emile Okada, Nike Dattani

Adiabatic quantum computing has recently been used to factor 56153 [Dattani & Bryans, arXiv:1411.6758] at room temperature, which is orders of magnitude larger than any number attempted yet using Shor's algorithm (circuit-based quantum computation). However, this number is still vastly smaller than RSA-768 which is the largest number factored thus far on a classical computer. We address a major issue arising in the scaling of adiabatic quantum factorization to much larger numbers. Namely, the existence of many 4-qubit, 3-qubit and 2-qubit interactions in the Hamiltonians. We showcase our method on various examples, one of which shows that we can remove 94% of the 4-qubit interactions and 83% of the 3-qubit interactions in the factorization of a 25-digit number with almost no effort, without adding any auxiliary qubits. Our method is not limited to quantum factoring. Its importance extends to the wider field of discrete optimization. Any CSP (constraint-satisfiability problem), psuedo-boolean optimization problem, or QUBO (quadratic unconstrained Boolean optimization) problem can in principle benefit from the "deduction-reduction" method which we introduce in this paper. We provide an open source code which takes in a Hamiltonian (or a discrete discrete function which needs to be optimized), and returns a Hamiltonian that has the same unique ground state(s), no new auxiliary variables, and as few multi-qubit (multi-variable) terms as possible with deduc-reduc.

arXiv:1508.04816•Aug 19, 2015•8 citations

Prime factorization using quantum variational imaginary time evolution

Raja Selvarajan, Vivek Dixit, Shawn Xingshan Cui +2 more

The road to computing on quantum devices has been accelerated by the promises that come from using Shor's algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as [Formula: see text], where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method's performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.

arXiv:2107.10196•Scientific Reports•Oct 21, 2021•13 citations

Algorithm for Quantum Factorization

Samuel Čarnoký

•Jan 1, 2008•0 citations

A Novel Hybrid Quantum Circuit for Integer Factorization: End-to-End Evaluation in Simulation and Real Quantum Hardware

Jesse Van Griensven Thé, Victor Oliveira Santos, Bahram Gharabaghi

The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low thousands qubit regime therefore remains an important open research objective. This work proposes a hybrid classical-quantum algorithm using a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit, to increase the speed and reduce the number of quantum components, including gates and qubits, to factor integer numbers, which serve as keys in cryptographic methods, like RSA and ECC, when compared with Shor’s algorithm. Several composite numbers, the result of multiplication of two primes, were validated through both simulation and real quantum hardware by benchmarking the full Shor pipeline on simulation and on a real IBM quantum computer. In simulation, the proposed Jesse–Victor–Gharabaghi (JVG) algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. Because Shor and JVG use different register sizes for the same composite N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets to factor the same N, rather than a per-qubit or transform-only efficiency claim. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. Projection for RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 11 hours for a factorization under identical scaling assumptions. The results from these evaluations support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable path toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.

Journal of Cybersecurity and Privacy•Apr 10, 2026•0 citations

Quantum algorithms for factorization problem

Xinhua Peng

•Sep 3, 2016•0 citations
Adiabatic quantum computing has recently been used to factor 56153 [Dattani & Bryans, arXiv:1411.6758] at room temperature, which is orders of magnitude larger than any number attempted yet using Shor's algorithm (circuit-based quantum computation). However, this number is still vastly smaller than RSA-768 which is the largest number factored thus far on a classical computer. We address a major issue arising in the scaling of adiabatic quantum factorization to much larger numbers. Namely, the existence of many 4-qubit, 3-qubit and 2-qubit interactions in the Hamiltonians. We showcase our method on various examples, one of which shows that we can remove 94% of the 4-qubit interactions and 83% of the 3-qubit interactions in the factorization of a 25-digit number with almost no effort, without adding any auxiliary qubits. Our method is not limited to quantum factoring. Its importance extends to the wider field of discrete optimization. Any CSP (constraint-satisfiability problem), psuedo-boolean optimization problem, or QUBO (quadratic unconstrained Boolean optimization) problem can in principle benefit from the "deduction-reduction" method which we introduce in this paper. We provide an open source code which takes in a Hamiltonian (or a discrete discrete function which needs to be optimized), and returns a Hamiltonian that has the same unique ground state(s), no new auxiliary variables, and as few multi-qubit (multi-variable) terms as possible with deduc-reduc.
The road to computing on quantum devices has been accelerated by the promises that come from using Shor's algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as [Formula: see text], where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method's performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.
The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low thousands qubit regime therefore remains an important open research objective. This work proposes a hybrid classical-quantum algorithm using a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit, to increase the speed and reduce the number of quantum components, including gates and qubits, to factor integer numbers, which serve as keys in cryptographic methods, like RSA and ECC, when compared with Shor’s algorithm. Several composite numbers, the result of multiplication of two primes, were validated through both simulation and real quantum hardware by benchmarking the full Shor pipeline on simulation and on a real IBM quantum computer. In simulation, the proposed Jesse–Victor–Gharabaghi (JVG) algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. Because Shor and JVG use different register sizes for the same composite N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets to factor the same N, rather than a per-qubit or transform-only efficiency claim. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. Projection for RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 11 hours for a factorization under identical scaling assumptions. The results from these evaluations support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable path toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.