==== TABLE OF CONTENTS ====
Exact-quantum-factoring-over-a-fixed-finite-gate-set//01-introduction.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//02-model.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//03-order-transform.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//04-dyadic-order.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//05-factor-process.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//06-exactness.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//appendix-primality.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//bibliography.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//main.tex
Exact-quantum-factoring-over-a-fixed-finite-gate-set//same-history-events.tex
===========================

==== BEGIN Exact-quantum-factoring-over-a-fixed-finite-gate-set//01-introduction.tex ====
\section{Introduction}\label{sec:introduction}

The integer factorization problem asks, on input a binary integer $N\ge2$,
for the nondecreasing list of primes whose product is $N$, including
multiplicities. We consider quantum circuits on qubits with classical
basis inputs. A circuit family is polynomial-time uniform if a
deterministic classical algorithm generates the circuit for inputs of each
bit length in time polynomial in that length.

\begin{theorem}\label{thm:main}
There is a polynomial-time uniform family of polynomial-size quantum circuits that outputs the complete prime factorization of every input integer $N\ge2$ with probability one. The number of gates and qubits is bounded by a fixed polynomial in the bit length of $N$. One fixed finite gate set suffices: NOT, CNOT, Toffoli, Hadamard, $\operatorname{diag}(1,i)$, their inverses, and their singly controlled versions.
\end{theorem}

\subsection{Factoring and exact quantum computation}

Shor's quantum algorithms established polynomial-time factorization and
discrete logarithms with bounded error~\cite{Shor}. Their order-based
factoring reduction builds on Miller's work~\cite{Miller,Shor}: suitable
multiplicative orders produce nontrivial square roots of unity and hence
gcd splits. The splitting argument used here is proved directly in
Section~\ref{sec:process}. Verifying a proposed factorization makes
repetition reliable, but a procedure that retries until success need not
have a polynomial worst-case running time. Approximating an arbitrary-angle
rotation to increasingly high precision likewise does not by itself yield
probability-one correctness over a fixed finite gate set.

Exact transforms and algorithms have been developed in several quantum
models. Mosca and Zalka~\cite{MZ} construct exact Fourier transforms using
computed rotations and obtain exact discrete-logarithm algorithms for
known group orders. Their discussion also reports Mosca's exact factoring
algorithm in a generalized model permitting gate parameters obtained
during the computation~\cite[Section~5.2]{MZ}; see also
\cite[Section~1]{Imran}. Imran's exact order-finding algorithm takes a
supplied multiple of the unknown order~\cite[Section~3]{Imran}. A suitable
multiple of polynomial bit length is additional information, which the
factoring problem does not provide initially. These are material model
and input distinctions. Nishimura and Ozawa~\cite{NO} study exact
computation by finitely generated uniform circuit families; their results
also explain why approximate universality cannot replace an explicit gate
analysis in an exact algorithm. Theorem~\ref{thm:main} uses the single
finite gate set stated there and receives only the integer to be factored.

Recent quantum factoring algorithms also address resource costs. Regev's
multidimensional construction~\cite{Regev} initially used a
number-theoretic hypothesis; Pilatte~\cite{Pilatte} proves unconditional
correctness for modified algorithms. Their success guarantees retain a
nonzero failure probability. The present construction addresses certainty
and worst-case polynomial bounds in a specified exact gate model. Its
large polynomial parameters are not intended as practical resource
improvements. It makes no claim of a classical deterministic or randomized
polynomial-time factoring algorithm.

The final step belongs to the amplitude-amplification method originating
in quantum search~\cite{Grover,BHMT}. Exact probability engineering already
appears in Brassard and H\o yer's exact algorithm for Simon's
problem~\cite{BH}, and Mosca and Zalka explicitly use success probability
$1/4$ followed by one ordinary amplification step~\cite[Section~2.1]{MZ}.
General exact amplification may employ phases depending on the success
probability~\cite{Hoyer,BHMT}. Here the preceding construction makes that
probability exactly $1/4$ using dyadic arithmetic and the fixed gates, so
the established pair of sign reflections suffices.

\subsection{Proof strategy and the ancestry of its ingredients}

The proof has two main ingredients beyond the order-based reduction to
factoring. First, it constructs an order trial whose mass on the true
order is a prescribed dyadic rational, meaning a rational with a
power-of-two denominator. For a unit $a$ modulo $m$, its order is the least
positive integer $r$ with $a^r\equiv1\pmod m$. Our trial returns no candidate
or a positive multiple of $r$, and its probability of returning $r$ is an
explicit arithmetic function of $r$. A phase register realizes a
piecewise-linear interpolant of the complex exponential. Its use of
controlled modular shifts is related to the phase-kickback construction
of Cleve, Ekert, Macchiavello, and Mosca~\cite[Section~7]{CEMM}, but the
register here is a four-phase step state rather than a Fourier eigenstate.
Testing its return produces the stated interpolated matrix with its
actual, unnormalized probability.

Lev's four-phase approximation to the order-sampling
transform~\cite[Sections~3--4]{Lev} provides a related approach to avoiding
fine phase rotations. The interpolation and exact
corrections below supply a different selected-branch transform and a
specific success law. The residue-class probabilities admit dyadic
majorants whose sums can be evaluated by a bounded number of polynomial
pieces and exact power sums. Mosca and Zalka use power sums to approximate
a transform's success probability to arbitrary precision, then use a
rotation with a computed angle to obtain an exact
transform~\cite[Sections~4.1--4.2]{MZ}. Here the finite polynomial pieces give
exact dyadic sums. Two small correction branches then make
the required true-order mass exact; neither the true order nor its
factorization is needed to run the trial.

Second, a factoring run also generates the prime factorizations of $p-1$
for its prime factors $p>2$, recursively. This auxiliary occurrence tree
has polynomial size. Its recursive shape is related to Pratt's succinct
primality certificates~\cite{Pratt}, although its role here is different:
prime labels are checked by the deterministic primality test proved in
Appendix~\ref{app:primality}, and the auxiliary factorizations determine
orders and transition probabilities. The appendix adapts the
polynomial-congruence method of Agrawal, Kayal, and Saxena~\cite{AKS}, with
its constants and auxiliary-prime choice established directly.

Once the run has completed and its data have been verified, those data
determine the exact probabilities needed to test earlier outputs. Ordinary
transitions are mixed with uniform guesses of their outputs, and filters
are computed from the completed data. Each transition has the same exact
retained mass. The crucial argument identifies these deferred tests with
a hypothetical sequence of tests using the true data: passing that
sequence itself forces the run to generate the data. Both descriptions
mark the same recorded runs. Thus the analysis introduces neither advice
nor conditioning on eventual completion.

This separates an arithmetic task---making a useful event have a
computable exact mass---from a verification task---recovering the
information needed to evaluate that mass on completed runs. Quantum
rejection sampling~\cite{ORR} is a related use of selective retention and
amplification, with different state-conversion inputs and parameterized
rotations. Our one-transition completion argument is stated independently
in Lemma~\ref{lem:completion}; efficient application also requires
verification of the auxiliary data and the all-good generation property.
A second dyadic correction makes the full preparation's success
probability exactly $1/4$.

Section~\ref{sec:model} specifies exact sampling and coherent classical
control. Section~\ref{sec:order} constructs the prescribed-probability
order trial. Section~\ref{sec:process} builds the factoring process and its
auxiliary data. Section~\ref{sec:exactness} equalizes the transition masses,
identifies the deferred and analytical events, and proves
Theorem~\ref{thm:main} by exact amplification.
==== END Exact-quantum-factoring-over-a-fixed-finite-gate-set//01-introduction.tex ====

==== BEGIN Exact-quantum-factoring-over-a-fixed-finite-gate-set//02-model.tex ====
\section{Exact circuits and classical records}\label{sec:model}

We first fix the computational conventions needed for exact probabilities.
All logarithms in bit bounds are to base two. For an input integer $N\ge2$, put
\begin{equation}\label{eq:parameters-n}
 n=\max\{128,\lfloor\log_2N\rfloor+1\},\qquad B=2^n.
\end{equation}
Thus $N\frac1{vB}+\frac1{2Q}.
\]
For the strict inequality, note that
$2Q>vB(B-1)$ because $v\frac1{8d}.
\]
For completeness, \(\pi<2\sqrt3\), obtained from
\(\tan(\pi/6)>\pi/6\), bounds the parenthesis below by
\(1/\sqrt3-3/8>1/8\).  The upper bound follows from \(|g|\le1\).

It remains to construct a dyadic majorant whose sum is accessible.
Let \(G\) be the continuous primitive of \(g\) satisfying \(G(0)=0\).
Its real and imaginary parts are quadratic polynomials with rational
coefficients on each quarter interval.  When \(\eta\ne0\),
\begin{equation}\label{majorant-primitive}
 I(u)=\frac{G(u/d+\eta)-G(u/d)}{d\eta}.
\end{equation}
The two arguments range in \([-1/2,3/2]\), so only a bounded number of
pieces occur.  Their boundaries in \(u\) arise when either argument is a
quarter-integer.  On each piece, \(I\) is a complex polynomial in \(u\) of
degree at most two; hence \(J\) is a rational polynomial of degree at most
four.  If \(\eta=0\), the identity \(I(u)=g(u/d)/d\) gives the same conclusion.
All boundaries and coefficients have \(O(n)\) bits and can be computed with
a bounded number of rational operations.  In particular,
\(\eta=(kd-jQ)/d\), so every nonzero \(\eta\) has
\(|\eta|\ge1/d\); the division in \eqref{majorant-primitive} has no hidden
precision cost.

On each piece write \(J(u)=\sum_{q=0}^4a_qu^q\), allowing zero coefficients,
and set \(D=QB^8\).  Replace \(a_q\) by
\(\widetilde a_q=\lceil Da_q\rceil/D\).  Denote the resulting piecewise
polynomial by \(\widetilde J\), assigning boundary points consistently to
one adjacent piece, and define
\begin{equation}\label{majorant-construction}
 U(d,j,u)=\widetilde J(u)+\frac{64}{Q}
 \qquad (u=0,\ldots,d-1).
\end{equation}
Because \(u\ge0\), rounding each coefficient upward increases the value
even when that coefficient is negative.  Moreover,
\[
 0\le \widetilde J(u)-J(u)
 \le \frac{1+u+u^2+u^3+u^4}{QB^8}\le\frac1Q.
\]
Together with \eqref{majorant-integral-bounds}, this yields
\(32/Q\le U(d,j,jt\bmod d)-P(d,j,t)\le97/Q\), proving
\eqref{majorant-error}.  It also gives
\[
 \frac1{128d}
 \le\frac12\sum_{u=0}^{d-1}U(d,j,u)
 \le\frac1{2d}+\frac{65d}{2Q}\le2,
\]
where the last inequality uses \(d2}}\log_2(p-1)
 \le\sum_{p\mid M}\log_2p\le\log_2M.
\]
Thus the total logarithmic size at any depth is at most $\log_2N2$ divides it, so $q-1<(p-1)/20$ for the present range. The same bound holds in dummy slots. Exact dyadic sampling is provided by Lemma~\ref{lem:dyadic}.

\begin{proposition}[Known probability from deferred filters]\label{prop:known-probability}
The implemented preparation just described has success probability exactly
\begin{equation}\label{eq:p-star}
 p_*=(1-2^{-n})^{n^{10}}.
\end{equation}
Every successful branch outputs the correct prime factorization of $N$. The preparation has polynomial worst-case time and workspace, and $p_*>1/2$ is an initially known dyadic with polynomial bit length.
\end{proposition}
\begin{proof}
Fix the true mathematical data $\D(N)$ for the purpose of analysis only. Allocate fresh filter coins in advance, with a common polynomial bound on their lengths. Consider the event obtained by testing each slot immediately against these true data, using the same coins that the actual algorithm will use after completion. Declare this analytical event false on a run that aborts before all $L$ slots are recorded. These hypothetical tests only mark an event on the same recorded runs; their outcomes do not alter the controller's evolution.

Condition on a recorded controller prefix of fewer than $L$ slots together with the coins used by its previous filters, all of which have passed. No later filter coins are exposed. Every output in this prefix is good; choosing canonical good outputs whenever another transition is requested gives an all-good evolution. Proposition~\ref{prop:process} therefore ensures that the controller reaches the next real or dummy slot.

Its transition inputs are fixed. Its new ordinary transition uses fresh registers, so its good-output probability is $s$, even if unobserved old quantum work is entangled; this is the consequence of Lemma~\ref{lem:records} explained in Section~\ref{sec:model}. The branch choice, uniform guess, and next filter coins are also fresh. Lemma~\ref{lem:completion} therefore gives conditional passing probability exactly $z$ for this prefix. This statement holds separately for every passing prefix and for every dummy slot. Induction over the $L$ slots gives probability $z^L$ for the analytical event.

We must identify this event with the one the algorithm implements. Every analytical passing transition has a good output. Proposition~\ref{prop:process} then guarantees completion of the full true data, without abort or truncation by a cap. Such a run passes the actual data verification, and its deferred thresholds and canonical outputs agree with those in the analytical event. Conversely, if an implemented run passes, its verified complete prime factorizations are precisely the true data, by unique factorization. Every deferred test is consequently the corresponding true-data test on the same output and the same coins. The two events coincide on each recorded run. In particular, the conditional calculation above never conditions on eventual completion, and the implementation never uses data it has not generated.

The retained records also justify the probability calculation in a unitary implementation. Every result used for later classical control has an immutable orthogonal history copy. Distinct histories cannot interfere during the preparation; internal interference within a quantum trial is preserved because its pre-interference labels are not copied. All filtering computations are classical controls and fresh-coin comparisons. Thus Lemma~\ref{lem:records} preserves the event probability just established.

The underlying process has polynomial caps on every branch. The $s$ values have $O(nK)$ denominator bits, and the rounded filters have polynomial bit length. There are $L$ of them, so evaluating all deferred tests and retaining their histories still has polynomial cost. The dyadic $p_*$ has at most $nL$ denominator bits and can be computed exactly by integer powering. Finally, Bernoulli's inequality yields
\[
 p_*\ge1-n^{10}2^{-n}>\tfrac12.
\]
At $n=128$ the subtracted term is $2^{-58}$, and $x^{10}2^{-x}$ decreases for real $x\ge128$, since its logarithmic derivative is $10/x-\log_e2<0$.
\end{proof}

Figure~\ref{fig:same-history-events} isolates the two implications that identify the implemented event with the event used in the probability calculation. Both are predicates on one recorded run and the same fresh coins.

\begin{figure}[tb]
\centering
\input{figures/same-history-events}
\caption{Two descriptions of one acceptance event. The probability calculation conditions on passing prefixes. The implementation evaluates its filters after generating and verifying the required data; the analytical tests leave the controller evolution unchanged.}
\label{fig:same-history-events}
\end{figure}

There is no exception for early completion. A run that finishes after $t$ real transitions still undergoes the same construction for its $L-t$ dummy slots, each with $s=1$ and one fixed canonical string. For example, $N=2$ can have only dummy slots. A prime root greater than $2$ must first generate its required $p-1$ descendants.

\subsection{A known quarter of success and one amplification step}

The target probability $1/4$ is the one-step exact-amplification case
of the standard reflection formula~\cite[Section~2]{BHMT}, used explicitly
for exact transforms by Mosca and Zalka~\cite[Section~2.1]{MZ}. The task here
is to reach that probability with the fixed gates. The remaining rounding
is independent of the factoring process. Encode the root factorization by $n$ entries of $n$ bits each: positive primes in nondecreasing order with multiplicity, followed by zeros. Put $J=n^2$. Because $N<2^n$, there are fewer than $n$ prime factors with multiplicity, and each prime is below $2^n$. Exactly one $J$-bit string is valid. Lemma~\ref{lem:primality}, the ordering check, and the product check recognize it in polynomial time. The product of an arbitrary guessed list has at most $n^2$ bits, so this verification is also polynomial on invalid guesses.

\begin{lemma}[Quarter-success preparation]\label{lem:quarter}
There is a polynomial-size uniform unitary preparation $V_N$ whose flag is $1$ with probability exactly $1/4$ and whose flagged output is always the fixed encoding of the prime factorization of $N$.
\end{lemma}
\begin{proof}
With probability $1/2$, run Proposition~\ref{prop:known-probability} and retain its success with the further probability
\[
 c_*=2^{-(J+2)}
       \left\lfloor\frac{2^{J+2}}{2p_*}\right\rfloor.
\]
With probability $1/2$, guess a uniform $J$-bit string, require it to be the valid root factor list, and retain with probability
\[
 2^{J+1}e,\qquad e=\frac14-\frac{p_*c_*}{2}.
\]
Since $1/2n^2.
\end{equation}
\item If $m\le8s$, decide primality by trial division and stop.
Otherwise reject if any integer from $2$ through $8s$ divides $m$.
\item Accept if and only if all the congruences
\begin{equation}\label{eq:primality-congruences}
 (X+a)^m\equiv X^m+a\pmod{m,\,X^s-1},
 \qquad 1\le a\le8s,
\end{equation}
hold.
\end{enumerate}
We prove that the search in the second step succeeds, that the algorithm
is correct, and that its running time is polynomial.

\paragraph{Existence of $s$.}
Let $R=2\lfloor n^8/2\rfloor$ and let $P_R$ be the product of the primes
at most $R$.  The central binomial coefficient $C=\binom{R}{R/2}$ satisfies
$C\ge2^R/(R+1)$.  For every prime $\ell$, the factorial valuation formula gives
\[
 v_\ell(C)=\sum_{j\ge1}
 \left(\left\lfloor\frac{R}{\ell^j}\right\rfloor
       -2\left\lfloor\frac{R/2}{\ell^j}\right\rfloor\right)
 \le\lfloor\log_\ell R\rfloor.
\]
Each summand is zero or one, and it vanishes when $\ell^j>R$.
Consequently, if $\pi(R)$ denotes the number of primes at most $R$, then
\[
 \log_2 C\le\pi(R)\log_2 R
 \le(\log_2 P_R)\log_2 R.
\]
Thus
\begin{equation}\label{eq:primality-prime-product}
 \log_2 P_R
 \ge\frac{R-\log_2(R+1)}{\log_2 R}>n^6.
\end{equation}
For the last inequality, $8\log_2 n+18s$.  Choose one such
$p$.  In an algebraic extension of $\mathbb F_p$, choose a root $w$ of
$1+X+\cdots+X^{s-1}$.  Its value at $1$ is $s\ne0$ in $\mathbb F_p$,
so $w\ne1$.  Since $s$ is prime, $w$ has multiplicative order exactly $s$.

For any product $f$ of the tested linear factors $X+a$, reduction of
\eqref{eq:primality-congruences} modulo $p$ gives
$f(X)^m\equiv f(X^m)\pmod{X^s-1}$.  Frobenius gives the same identity with
exponent $p$.  These identities compose: substitution $X\mapsto X^b$
preserves the ideal $(X^s-1)$, so identities for exponents $b,c$ imply the
identity for $bc$.  Hence, for all nonnegative integers $u,v$,
\begin{equation}\label{eq:primality-propagation}
 f(w)^k=f(w^k),\qquad k=m^u p^v.
\end{equation}

Let $H$ be the subgroup of $(\Z/s\Z)^\times$ generated by the residues
of $m$ and $p$, and put $h=|H|$.  By \eqref{eq:primality-order},
\[
 n^28s$, so different subsets give different monic polynomials.
If two such polynomials $f_1,f_2$ had the same value at $w$, then
\eqref{eq:primality-propagation} would give
$f_1(w^k)=f_2(w^k)$ for every $k\bmod s\in H$.  This would give $h$
distinct roots of the nonzero polynomial $f_1-f_2$, whose degree is at
most $h-1$.  Thus all these values are distinct, and their number is at least
\begin{equation}\label{eq:primality-lower}
 \binom{8s}{h-1}
 \ge\left(\frac{8s}{h-1}\right)^{h-1}
 \ge8^{h-1}.
\end{equation}
Here $\binom{M}{t}\ge(M/t)^t$ follows by comparing each factor
$(M-i)/(t-i)$ with $M/t$.  No division by $f(w)$ has been used.  Indeed
$f(w)=0$ is itself impossible, since \eqref{eq:primality-propagation}
would give $h$ roots of the nonzero polynomial $f$, of degree $h-1$.

For the upper bound, put $q=\lfloor\sqrt h\rfloor$.  The $(q+1)^2>h$
pairs $0\le u,v\le q$ give two distinct pairs for which the corresponding
integers $k_1=m^u p^v$ and $k_2=m^{u'}p^{v'}$ agree modulo $s$.
They are different as integers: since $m$ is composite and not a perfect
power, it has a prime divisor $p'\ne p$.  Equality of $k_1$ and $k_2$
would force $u=u'$ by taking $p'$-adic valuations, and then $v=v'$.
Now $w^{k_1}=w^{k_2}$, so \eqref{eq:primality-propagation} makes every
value counted in \eqref{eq:primality-lower} a root of the nonzero polynomial
$T^{k_1}-T^{k_2}$.  Its degree is at most
\[
 \max(k_1,k_2)\le m^{2q}
 <2^{2nq}\le2^{2n\sqrt h}<2^{2h}.
\]
But \eqref{eq:primality-lower} is at least
$8^{h-1}=2^{3h-3}>2^{2h}$, since $h>n^2\ge128^2$.
This contradiction proves correctness.

\paragraph{Running time.}
Every exponent in a representation $m=b^e$ with $b\ge2$ satisfies $e