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

Exact quantum factoring over a fixed finite gate set

OpenAI

Published Oct 6, 2026• 0 citations
Publisher

Abstract

We give a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer N\ge2 with probability one. A fixed finite set of bounded-arity gates suffices, and both the gate count and the number of qubits have polynomial worst-case bounds in the input length.
DOI
10.83295/w2wa-tavg

Related papers

Deterministic Prime Bases for Regev's Algorithm

Steven Tolbert

Regev's quantum factoring algorithm reduces the number of gates per quantum call, but its correctness for the original deterministic prime bases rests on a number-theoretic assumption. We prove that the first ⌈√n⌉ primes work unconditionally for almost all n-bit composite inputs, including almost all composite inputs surviving trial division by those primes. The algorithm retains Regev's original asymptotic gate count per quantum call. A separate theorem covers balanced RSA moduli under three explicit sampling laws. The exceptional input proportion is Θ(2^{-⌈√n⌉}); a population of this order admits no useful relation at any length. On each remaining input, Regev's algorithm finds a nontrivial divisor with constant probability using ⌈√n⌉+4 quantum calls of O(n^{3/2} log n) gates each. The main geometric lemma extracts a useful relation from an earlier successive minimum, determined by the dimension of a quotient of the relation lattice. Prime-divisor counting then gives useful-relation lengths 2^{(3/2+o(1))√n} for general inputs and 2^{(9/2+o(1))√n} for RSA. Both main theorems and finite RSA useful-vector bounds are formally verified in Lean 4; the formalization is archived at https://doi.org/10.5281/zenodo.23407163.

•Oct 16, 2026•0 citations

Quantum circuit for a direct sum of two-dimensional unitary operators

Ville Bergholm, Juha J. Vartiainen, Mikko Möttönen +1 more

In this article we study n-qubit quantum gates which may be represented as direct sums of two-dimensional unitary operators. We call this class of gates uniformly controlled one-qubit gates. We present a quantum circuit which implements any gate of this type using 2^{n-1} - 1 controlled-NOT gates, 2^{n-1} one-qubit gates and a single n-qubit diagonal gate. The construction is based on a modified version of the so-called quantum multiplexor circuit. We illustrate the versatility of the uniformly controlled gates by applying them to the decomposition of a general n-qubit gate and an n-qubit state-preparation procedure. Moreover, we study the implementation of these circuits using only nearest-neighbor gates and give the worst-case one-qubit and CNOT gate counts for all of the aforementioned applications. In all four cases, the proposed method either improves or achieves the previously reported upper bounds for the gate counts.

•Oct 9, 2004•5 citations

Regular trajectories, pruning and quantum parity

OpenAI

We prove that constant-depth quantum circuits with arbitrary one-qubit gates and unbounded-arity Toffoli gates cannot compute parity with any fixed positive worst-case advantage using polynomially many total qubits. Ancillary qubits are initialized to |0\rangle, one output qubit is measured, and all other final registers may be discarded without restriction. This resolves Moore's parity conjecture in the measured-output model.

•Oct 6, 2026•0 citations

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored.

arXiv:quant-ph/0205095•Quantum Information and Computation•Mar 1, 2003•299 citations

Fast quantum integer multiplication with zero ancillas

Gregory D. Kahanamoku–Meyer, Norman Y. Yao

The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of $\mathcal{O}(n^{1+ε})$ for any $ε> 0$; with practical choices of parameters, we expect scalings as low as $\mathcal{O}(n^{1.3})$. Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with $\mathcal{O}(n^{2+ε})$ gates and only $2n + \mathcal{O}(\log n)$ qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is $\mathcal{O}(n^{1.5+ε})$. Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.

arXiv:2403.18006•Mar 26, 2024•31 citations

Exact quantum splitting and the structure of finite algebras

Muhammad Imran

For squarefree $f\in\F_q[x]$, Berlekamp's fixed-point algebra is $B\cong\F_q^r$, where $r$ is the number of irreducible factors. We give an exact quantum splitting procedure in a circuit model permitting efficiently computable, input-dependent single-qubit rotations. For a block with $s\ge2$ factors, a quadratic-character test (odd $q$) or absolute-trace test (characteristic $2$) is nonconstant with an exactly known probability $p_{q,s}\ge1/2$. Its value depends only on $q,s$, not on the hidden factors. An auxiliary-qubit reduction to success probability $1/4$ makes one Grover iteration exact. Thus factorization takes exactly $r-1$ splitting rounds and $O(n^3\log q)$ quantum $\F_q$-operations, with deterministic polynomial classical preprocessing and bookkeeping. The method also extracts primitive idempotents of arbitrary finite-dimensional commutative unital algebras given by structure constants in $O(n^4\log q)$ quantum $\F_q$-operations, staying over $\F_q$ throughout. Computing the radical and passing to the center extends it to the decomposition of $A/\Rad(A)$ into simple two-sided ideals, for an arbitrary finite-dimensional associative $\F_q$-algebra $A$.

quant-pharXiv:2608.30340•Sep 1, 2026•0 citations
Regev's quantum factoring algorithm reduces the number of gates per quantum call, but its correctness for the original deterministic prime bases rests on a number-theoretic assumption. We prove that the first ⌈√n⌉ primes work unconditionally for almost all n-bit composite inputs, including almost all composite inputs surviving trial division by those primes. The algorithm retains Regev's original asymptotic gate count per quantum call. A separate theorem covers balanced RSA moduli under three explicit sampling laws. The exceptional input proportion is Θ(2^{-⌈√n⌉}); a population of this order admits no useful relation at any length. On each remaining input, Regev's algorithm finds a nontrivial divisor with constant probability using ⌈√n⌉+4 quantum calls of O(n^{3/2} log n) gates each. The main geometric lemma extracts a useful relation from an earlier successive minimum, determined by the dimension of a quotient of the relation lattice. Prime-divisor counting then gives useful-relation lengths 2^{(3/2+o(1))√n} for general inputs and 2^{(9/2+o(1))√n} for RSA. Both main theorems and finite RSA useful-vector bounds are formally verified in Lean 4; the formalization is archived at https://doi.org/10.5281/zenodo.23407163.
In this article we study n-qubit quantum gates which may be represented as direct sums of two-dimensional unitary operators. We call this class of gates uniformly controlled one-qubit gates. We present a quantum circuit which implements any gate of this type using 2^{n-1} - 1 controlled-NOT gates, 2^{n-1} one-qubit gates and a single n-qubit diagonal gate. The construction is based on a modified version of the so-called quantum multiplexor circuit. We illustrate the versatility of the uniformly controlled gates by applying them to the decomposition of a general n-qubit gate and an n-qubit state-preparation procedure. Moreover, we study the implementation of these circuits using only nearest-neighbor gates and give the worst-case one-qubit and CNOT gate counts for all of the aforementioned applications. In all four cases, the proposed method either improves or achieves the previously reported upper bounds for the gate counts.
The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of O(n1+ε)\mathcal{O}(n^{1+ε})O(n1+ε) for any ε>0ε> 0ε>0; with practical choices of parameters, we expect scalings as low as O(n1.3)\mathcal{O}(n^{1.3})O(n1.3). Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with O(n2+ε)\mathcal{O}(n^{2+ε})O(n2+ε) gates and only 2n+O(log⁡n)2n + \mathcal{O}(\log n)2n+O(logn) qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is O(n1.5+ε)\mathcal{O}(n^{1.5+ε})O(n1.5+ε). Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.
For squarefree $f\in\F_q[x]$, Berlekamp's fixed-point algebra is $B\cong\F_q^r$, where rrr is the number of irreducible factors. We give an exact quantum splitting procedure in a circuit model permitting efficiently computable, input-dependent single-qubit rotations. For a block with s≥2s\ge2s≥2 factors, a quadratic-character test (odd qqq) or absolute-trace test (characteristic 222) is nonconstant with an exactly known probability pq,s≥1/2p_{q,s}\ge1/2pq,s​≥1/2. Its value depends only on q,sq,sq,s, not on the hidden factors. An auxiliary-qubit reduction to success probability 1/41/41/4 makes one Grover iteration exact. Thus factorization takes exactly r−1r-1r−1 splitting rounds and O(n3log⁡q)O(n^3\log q)O(n3logq) quantum $\F_q$-operations, with deterministic polynomial classical preprocessing and bookkeeping. The method also extracts primitive idempotents of arbitrary finite-dimensional commutative unital algebras given by structure constants in O(n4log⁡q)O(n^4\log q)O(n4logq) quantum $\F_q$-operations, staying over $\F_q$ throughout. Computing the radical and passing to the center extends it to the decomposition of $A/\Rad(A)$ into simple two-sided ideals, for an arbitrary finite-dimensional associative $\F_q$-algebra AAA.