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+ε) for any
ε>0; with practical choices of parameters, we expect scalings as low as
O(n1.3). Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with
O(n2+ε) gates and only
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+ε). 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
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≥2 factors, a quadratic-character test (odd
q) or absolute-trace test (characteristic
2) is nonconstant with an exactly known probability
pq,s≥1/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(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(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
A.