Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Quantum Order Finding and Rational Reconstruction

1 · Prerequisites

2 · Summary

This page defines denominator-bounded rational reconstruction using normalized finite continued fractions and an exact integer window. It proves the finite-rational Legendre bridge needed for a rational phase sample, candidate uniqueness, and the reconstruction bit bound. The order-finding construction starts from the valid residue $∣ 1 ⟩$ , whose modular-multiplication orbit has Fourier eigenphases $k / r$ ; phase estimation therefore yields a uniform mixture over indices, not a promise that $∣ 1 ⟩$ is an eigenvector. A candidate denominator is retained only after the exact modular power test, and the algorithm returns the minimum retained value. The page gives an explicit clean reversible modular multiplier, its correctness and schoolbook resource bounds, then separates controlled-multiplier calls, black-box controlled- $U_{x}$ queries, gates, and classical bit work. The gate estimate uses ideal exact arbitrary-angle QFT gates; it claims no finite-alphabet compilation or uniform circuit family.

3 · Logical flowchart

4 · Definitions, theorems and proofs

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Finite-rational Legendre criterion before the terminal convergent

Statement

Let $A, p \in Z$ and $D, q \in Z_{> 0}$ , with $A / D$ and $p / q$ reduced and $D > 2 q$ . If $∣ A / D - p / q ∣ < 1 / (2 q^{2})$ , then $p / q$ is a convergent of the normalized finite regular continued fraction of $A / D$ . This is a finite-rational statement; it does not invoke the irrational-input Legendre theorem.

Facts & Assumptions

Given: Reduced $A / D$ with $D > 2 q$ , and reduced $p / q$ with $q > 0$ and $∣ A / D - p / q ∣ < 1 / (2 q^{2})$ .

[F1]

A rational continued fraction terminates at its Euclidean quotient list, and normalized finite expansion chooses the representation whose last digit is at least $2$ unless the expansion is an integer (The continued-fraction algorithm terminates exactly on rational numbers, Normalized finite regular continued fractions are unique).

[F2]

For convergents, $p_{n} = a_{n} p_{n - 1} + p_{n - 2}$ and $q_{n} = a_{n} q_{n - 1} + q_{n - 2}$ , and the finite-prefix formula is $(T p_{j} + p_{j - 1}) / (T q_{j} + q_{j - 1})$ for the positive remaining tail $T$ (Convergents of a regular continued fraction, Convergents are given by the standard recurrences and tail formula, Complete-quotient tail formula).

[F3]

Adjacent convergents satisfy $p_{j} q_{j - 1} - p_{j - 1} q_{j} = (- 1)^{j - 1}$ (Determinant identity for consecutive convergents).

[F4]

The complete quotient is $T = a_{j + 1}$ at the last digit and otherwise $T > a_{j + 1}$ ; the denominator recurrence is increasing after the possible initial equality $q_{0} = q_{1} = 1$ (Complete quotients in the continued-fraction algorithm, Convergents of a regular continued fraction).

[F5]

Reduced means coprime numerator and positive denominator, with gcd $1$ . If $d$ is coprime to $u$ and $d ∣ u v$ , then $d ∣ v$ (Coprime integers: $\gcd (a, b) = 1$ , If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ ). Rational absolute value is multiplicative and satisfies the triangle inequality (Absolute value and the triangle inequality).

Proof

1.1givenF1F2F3F5algebra

By [F1], write $A / D = [a_{0}; \dots, a_{s}]$ in normalized finite form. Since $D > 2 q \geq 2$ , $A / D$ is not an integer, so $s \geq 1$ . Its terminal convergent equals $A / D$ by [F1] and [F2]. By [F3], any common divisor of $p_{s}, q_{s}$ divides $1$ , so this pair is coprime. Cross multiplication gives $A q_{s} = p_{s} D$ . Since $\gcd (A, D) = 1$ , [F5] gives $D ∣ q_{s}$ ; since $\gcd (p_{s}, q_{s}) = 1$ , it also gives $q_{s} ∣ D$ . Both denominators are positive, so they are equal: $q_{s} = D$ .

2.1givenF2step 1.1algebra

If $q = 1$ , then $p$ is an integer and $∣ A / D - p ∣ < 1 / 2$ . Put $a_{0} = ⌊ A / D ⌋$ and $e : = A / D - a_{0} \in (0, 1)$ . The only possible such integers are $a_{0}$ and $a_{0} + 1$ . The first is the zeroth convergent. If $p = a_{0} + 1$ , then $e > 1 / 2$ , hence $a_{1} = ⌊ 1 / e ⌋ = 1$ ; the recurrence in [F2] gives $p_{1} / q_{1} = (a_{0} + 1) / 1$ . Thus $p / q$ is a convergent.

2.2givenF2F4step 1.1choose

Suppose $q \geq 2$ . Since $q < D = q_{s}$ , choose the largest $j$ with $q_{j} \leq q$ . Then $0 \leq j < s$ ; the only repeated initial denominator can be $q_{0} = q_{1} = 1$ , so $q_{j} > 0$ and $s_{0} : = q_{j - 1} / q_{j}$ lies in $[0, 1]$ (with $q_{- 1} = 0$ when $j = 0$ ). Put $T = a_{j + 1}$ if $j + 1 = s$ , and otherwise let $T$ be the complete quotient after the prefix. By [F4], $T \geq a_{j + 1}$ , and $x : = q / q_{j}$ satisfies $1 \leq x < a_{j + 1} + s_{0} \leq T + s_{0} = : L$ .

3.1F2F3F5step 2.2algebra

Put $ε = p_{j} q_{j - 1} - p_{j - 1} q_{j} = \pm 1$ by [F3]. The integers $u = ε (q_{j - 1} p - p_{j - 1} q)$ and $v = ε (p_{j} q - q_{j} p)$ satisfy $(p, q) = u (p_{j}, q_{j}) + v (p_{j - 1}, q_{j - 1})$ by expansion and $ε^{2} = 1$ ; hence $x = u + v s_{0}$ . Cross multiplication using the tail formula [F2] gives $\frac{p}{q} - \frac{A}{D} = \frac{(u p_{j} + v p_{j - 1}) (T q_{j} + q_{j - 1}) - (T p_{j} + p_{j - 1}) (u q_{j} + v q_{j - 1})}{q (T q_{j} + q_{j - 1})} = \frac{ε (u - v T)}{q_{j}^{2} x L}$ . Since $q = x q_{j}$ , it follows that $q^{2} ∣ A / D - p / q ∣ = x ∣ u - v T ∣ / L$ . Finally $L = T + s_{0}$ and $x = u + v s_{0}$ , so $u - v T = x - v L$ and $q^{2} ∣ A / D - p / q ∣ = x ∣ x - v L ∣ / L$ .

4.1givenstep 3.1algebra

The hypothesis makes the expression in step 3.1 less than $1 / 2$ . If $v \leq - 1$ , then $∣ x - v L ∣ \geq x + L$ , so $x ∣ x - v L ∣ / L > x \geq 1$ . If $v \geq 2$ , then $∣ x - v L ∣ \geq 2 L - x > L$ because $x < L$ , so again $x ∣ x - v L ∣ / L > x \geq 1$ . Both alternatives are impossible.

4.2givenF4step 2.2step 3.1algebra

If $v = 1$ , then $u = x - s_{0}$ is an integer. If $s_{0} < 1$ , $x \geq 1$ implies $u > 0$ ; if $s_{0} = 1$ , then $j \geq 1$ and $q_{j} = q_{j - 1} = 1$ , while $q \geq 2$ forces $x \geq 2$ . Thus $u \geq 1$ . Also $q < q_{j + 1}$ implies $u < a_{j + 1}$ , so $L - x = T - u \geq 1$ . Hence $x (L - x) / L \geq x / (x + 1) \geq 1 / 2$ , contradicting the strict hypothesis. Thus $v \neq 1$ .

5.1F1step 4.1step 4.2algebra∎

The alternatives $v \leq - 1$ , $v \geq 2$ , and $v = 1$ were excluded in steps 4.1–4.2, so $v = 0$ . Then $(p, q) = u (p_{j}, q_{j})$ , hence $p / q = p_{j} / q_{j}$ and $p / q$ is the $j$ th convergent. The proof includes the terminal case $j + 1 = s$ because only $T \geq a_{j + 1}$ was used, allowing equality at the terminal tail.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Uniqueness of denominator-bounded phase candidates

Statement

Let $N \geq 1$ , $Q > 4 N^{2}$ be integers and $0 \leq y < Q$ . There is at most one reduced fraction $p / q$ with $1 \leq q \leq N$ satisfying $2 ∣ y q - p Q ∣ \leq q$ .

Facts & Assumptions

Given: Integers $N \geq 1$ , $Q > 4 N^{2}$ , an integer $y$ with $0 \leq y < Q$ , and reduced fractions with positive denominators.

[F1]

A fraction is reduced when its integer numerator and positive denominator are coprime; coprime means gcd equal to $1$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Coprime integers: $\gcd (a, b) = 1$ ).

[F2]

Rational subtraction is computed by cross multiplication: $p_{1} / q_{1} - p_{2} / q_{2} = (p_{1} q_{2} - p_{2} q_{1}) / (q_{1} q_{2})$ when $q_{1}, q_{2} > 0$ (Arithmetic on the rationals).

[F3]

Rational absolute value is multiplicative and satisfies $∣ u + v ∣ \leq ∣ u ∣ + ∣ v ∣$ (Absolute value and the triangle inequality).

Proof

1.1givenF2F3algebra

For any fraction $p / q$ passing the test, division by the positive integer $2 Q q$ gives $∣ y / Q - p / q ∣ \leq 1 / (2 Q)$ . Thus two passing fractions have distance at most $1 / Q$ by the triangle inequality.

2.1givenF1F2step 1.1algebra∎

If $p_{1} / q_{1}$ and $p_{2} / q_{2}$ are distinct reduced fractions, [F2] makes their difference a nonzero integer divided by $q_{1} q_{2}$ , so its absolute value is at least $1 / (q_{1} q_{2}) \geq 1 / N^{2}$ . Since $Q > 4 N^{2}$ , $1 / Q < 1 / (4 N^{2}) < 1 / N^{2}$ , contradicting the bound from step 1.1. Therefore the two fractions coincide.

LemmaStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Elementary lower bound for the totient ratio

Statement

For every integer $r \geq 1$ , $φ (r) / r \geq 1 / (1 + \log_{2} r)$ , with $φ (1) = 1$ .

Facts & Assumptions

Given: An integer $r \geq 1$ and its distinct prime divisors.

[F1]

If the distinct prime divisors of $r$ are $p_{1} < \dots < p_{ω}$ , then $φ (r) / r = \prod_{i = 1}^{ω} (1 - 1 / p_{i})$ ; the empty product is $1$ when $r = 1$ (Euler's product formula $φ (n) = n \prod_{p ∣ n} (1 - 1 / p) = \prod_{p^{k} ∥ n} (p^{k} - p^{k - 1})$ for $n \geq 1$ , stated through a finite injective list of its prime divisors).

[F2]

A prime is an integer greater than $1$ with no positive divisors other than $1$ and itself, and every integer $r \geq 2$ is a finite product of primes (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ , The fundamental theorem of arithmetic: every integer $n \geq 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i < r} p_{i} = \prod_{j < s} q_{j}$ with every $p_{i}$ and $q_{j}$ prime, then $r = s$ and $q_{i} = p_{π (i)}$ for some $π \in Sym (r)$ ).

[F3]

Integer multiplication is associative and commutative, and $d ∣ r$ means $r = d c$ for some integer $c$ (The integers form a commutative ring, Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Proof

1.1givenF1

If $r = 1$ , then $ω = 0$ and [F1] gives $φ (1) / 1 = 1$ , which is the claimed bound. Suppose $r > 1$ .

2.1F1F2step 1.1algebra

For every $i$ , the increasing distinct primes satisfy $p_{i} \geq i + 1$ : there are only $i - 1$ integers strictly between $1$ and $i + 1$ , so fewer than $i$ distinct primes can lie there. Therefore each factor in [F1] obeys $1 - 1 / p_{i} \geq 1 - 1 / (i + 1) = i / (i + 1)$ . Multiplying positive factors gives $φ (r) / r \geq \prod_{i = 1}^{ω} i / (i + 1) = 1 / (ω + 1)$ .

3.1F2F3step 2.1algebra∎

Take a prime factor list for $r$ from [F2] and sort its distinct entries as $p_{1} < \dots < p_{ω}$ , choosing for each value its first occurrence in that finite list. By associativity and commutativity in [F3], regrouping the list gives $r = (p_{1} \dots p_{ω}) c$ for a positive integer $c$ . Thus the distinct-prime product divides $r$ , and since every $p_{i} \geq 2$ , $r \geq 2^{ω}$ . Therefore $ω \leq \log_{2} r$ , so $1 / (ω + 1) \geq 1 / (1 + \log_{2} r)$ . This proves the assertion.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Denominator-bounded rational phase reconstruction

Definition

Let $N, Q$ be integers with $N \geq 1$ and $Q > 4 N^{2}$ . A measured phase label is represented by the unique integer $y$ with $0 \leq y < Q$ as in For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ . Write the normalized finite regular continued fraction of $y / Q$ as $[a_{0}; \dots, a_{s}]$ and denote its convergents by $p_{j} / q_{j}$ . Every convergent is reduced by Determinant identity for consecutive convergents. A candidate is a convergent whose numerator and denominator are reduced, whose denominator satisfies $1 \leq q_{j} \leq N$ , and which passes the exact integer test $2 ∣ y q_{j} - p_{j} Q ∣ \leq q_{j} .$

The reconstruction result is the unique candidate if the candidate set is nonempty, and is FAIL otherwise. The candidate set includes the terminal convergent whenever it meets the same conditions. Uniqueness, and hence well-definedness of this value, follows from Uniqueness of denominator-bounded phase candidates under $Q > 4 N^{2}$ .

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Rational reconstruction from a phase sample

Definition

Input. Integers $N \geq 1$ , $Q > 4 N^{2}$ , and $y \in {0, \dots, Q - 1}$ , with $Q = 2^{m}$ and $y$ the label from Quantum phase estimation when this routine is called from QPE.

Output. A reduced fraction $p / q$ with $1 \leq q \leq N$ , or FAIL.

Instructions. Set $u : = y$ , $v : = Q$ , and $j : = 0$ . Repeatedly divide $u$ by the positive integer $v$ , obtaining the unique quotient $a_{j}$ and remainder $r_{j}$ with $u = a_{j} v + r_{j}$ and $0 \leq r_{j} < v$ . Append $a_{j}$ ; if $r_{j} = 0$ , stop, and otherwise set $(u, v) : = (v, r_{j})$ , increment $j$ , and repeat. For $y = 0$ this immediately gives the one-digit expansion $[0]$ ; for every other input, The continued-fraction algorithm terminates exactly on rational numbers gives termination and the resulting normalized finite expansion is the one in Denominator-bounded rational phase reconstruction. Starting from $p_{- 2} = 0, p_{- 1} = 1, q_{- 2} = 1, q_{- 1} = 0$ , process the digits in order using $p_{j} = a_{j} p_{j - 1} + p_{j - 2}$ and $q_{j} = a_{j} q_{j - 1} + q_{j - 2}$ ; this lists all convergents including the terminal one by Convergents of a regular continued fraction. For each convergent, reject it if $q > N$ ; otherwise compute $2 ∣ y q - p Q ∣$ exactly and accept it precisely when this integer is at most $q$ . Return the first accepted candidate, or FAIL if none exists. The uniqueness result lem-qa-rational-reconstruction-candidate-uniqueness shows there cannot be two. The algorithm makes no floating-point comparison. Its deterministic bit bound is proved separately in thm-qa-rational-reconstruction-bit-cost, which also establishes that these instructions terminate.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Correctness of phase-sample rational reconstruction

Statement

Let integers $N \geq 1$ , $m \geq 0$ , $Q = 2^{m}$ , and $1 \leq r \leq N$ satisfy $Q > 4 N^{2}$ , and let $k \in Z$ with $0 \leq k < r$ and $\gcd (k, r) = 1$ . Let $y \in {0, \dots, Q - 1}$ be any nearest grid label to phase $k / r$ in circular distance, meaning $\min_{z \in Z} ∣ k / r - y / Q - z ∣ \leq 1 / (2 Q)$ . Then Rational reconstruction from a phase sample returns $k / r$ . For every phase label $y$ , there is at most one passing candidate with denominator at most $N$ .

Facts & Assumptions

Given: Reduced $k / r \in [0, 1)$ with $r \leq N$ , $Q = 2^{m} > 4 N^{2}$ for an integer $m \geq 0$ , and a nearest circular grid label $y$ .

[F1]

Circular distance is $d_{T} (θ, y / Q) = \min_{z \in Z} ∣ θ - y / Q - z ∣$ ; for $θ \in [0, 1)$ , a nearest label has distance at most $1 / (2 Q)$ (Circular phase distance modulo one).

[F2]

The reconstruction routine tests the exact condition $2 ∣ y q - p Q ∣ \leq q$ on normalized finite-CF convergents with $q \leq N$ (Rational reconstruction from a phase sample, Denominator-bounded rational phase reconstruction).

[F3]

For reduced $A / D$ with $D > 2 q$ , a reduced $p / q$ satisfying $∣ A / D - p / q ∣ < 1 / (2 q^{2})$ is a convergent of the normalized finite expansion (Finite-rational Legendre criterion before the terminal convergent).

[F4]

At most one reduced fraction of denominator at most $N$ passes the exact reconstruction window when $Q > 4 N^{2}$ (Uniqueness of denominator-bounded phase candidates).

Proof

1.1givenF2F4algebra

If $k = 0$ , reducedness forces $r = 1$ . The only nearest circular grid label is $y = 0$ , so $y / Q = 0$ and its normalized finite expansion is $[0]$ with terminal convergent $0 / 1$ . This convergent has denominator $1 \leq N$ and passes the exact test, so [F2] and [F4] return $0 / 1 = k / r$ .

1.2givenF1algebra

Suppose $k > 0$ . The distance from $k / r$ to either endpoint $0, 1$ is at least $1 / r \geq 1 / N > 1 / (2 Q)$ , by $Q > 4 N^{2}$ . Therefore a nearest circular label cannot cross an endpoint: if $y / Q$ were on the other side of $0$ or $1$ , the circular distance would be at least the distance of $k / r$ from that endpoint, contradicting [F1]. Thus $∣ y / Q - k / r ∣ \leq 1 / (2 Q)$ .

2.1givenF2F4step 1.2algebra

Reduce $y / Q$ to $A / D$ with $D > 0$ . If $A / D = k / r$ , its normalized finite expansion terminates at that fraction; its terminal convergent is $k / r$ , whose denominator is at most $N$ , and step 1.2 gives $2 ∣ y r - k Q ∣ \leq r$ . Thus it passes [F2], and uniqueness [F4] makes the algorithm return it.

2.2givenF3step 1.2algebra

If $A / D \neq k / r$ , then $∣ A r - k D ∣$ is a positive integer, so $∣ A / D - k / r ∣ \geq 1 / (D r)$ . Combining with step 1.2 gives $D \geq 2 Q / r > 8 N^{2} / r \geq 8 r > 2 r$ , because $r \leq N$ . Also $Q > 4 N^{2} \geq 4 r^{2}$ gives $∣ A / D - k / r ∣ \leq 1 / (2 Q) < 1 / (8 r^{2}) < 1 / (2 r^{2})$ . Applying [F3] with $p / q = k / r$ shows it is a convergent of $A / D$ .

3.1F2F4step 1.2step 2.1step 2.2algebra∎

The same linear error bound in step 1.2 gives $2 ∣ y r - k Q ∣ \leq r$ . Therefore this convergent passes the exact test and denominator bound in [F2]. By [F4] it is the unique accepted candidate, so the algorithm returns $k / r$ . The two cases establish correctness and candidate uniqueness.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Reversible modular multiplication by a unit

Definition

Input. An integer $N \geq 2$ , $n = ⌈ \log_{2} N ⌉$ , a one-bit control $c$ , an $n$ -bit data register $z$ , and integers $a, a^{- 1}$ with $0 \leq a, a^{- 1} < N$ and $a a^{- 1} \equiv 1 (m o d N)$ . The data encoding is valid when its unsigned value is less than $N$ .

Residue addition and multiplication are in $Z / N$ with the class operations of The congruence class $[a]_{n}$ and the quotient set $Z / n$ , Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ , and For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold. The inverse condition says $[a]_{N}$ is a unit, equivalently $\gcd (a, N) = 1$ by The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ and For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ . Kets use Dirac Notation Conversion; $c, z$ are ordered computational-basis registers with the unsigned encoding of Finite registers and their ordered computational bases and Big-endian encoding of ordered bit strings, tensor order as in Ordered tensor registers, their inner product, and wire permutations, and circuit denotation as in Denotational semantics of a finite layered circuit. “Clean work” means initialized and returned to zero under Clean and dirty ancillas.

Output. A reversible circuit on $c, z$ and clean work registers which implements the controlled map $z \mapsto a z m o d N$ for $c = 1$ and valid $z$ , and is the identity on invalid encodings and when $c = 0$ .

Instructions. Define the total Boolean function on $(c, z)$ by $f_{a} (c, z) = {\begin{cases} a z m o d N, & c = 1 and z < N, \\ z, & otherwise. \end{cases}$ Generate the following explicit NOT/AND/OR DAG for this function. Bit arrays in the instructions below are indexed from least significant bit $0$ ; the input and output port lists retain the repository's most-significant-first register order. Begin with the distinct input identifiers $c, z_{n - 1}, \dots, z_{0}$ and two constant nodes $0, 1$ . Every gate emission appends a fresh identifier in consecutive order, referencing only existing identifiers. A named bit below is an alias of its node identifier, never an additional gate. Expand every macro call immediately in the stated loop order.

Define $XOR (u, v)$ by emitting, in order, $o = OR (u, v)$ , $h = AND (u, v)$ , $d = NOT (h)$ , and $e = AND (o, d)$ , returning $e$ . Define ${ADD}_{w} (U, V, d_{0})$ by looping $i = 0, \dots, w - 1$ : emit $e_{i} = XOR (U_{i}, V_{i})$ , $s_{i} = XOR (e_{i}, d_{i})$ , $h_{i} = AND (U_{i}, V_{i})$ , $j_{i} = AND (e_{i}, d_{i})$ , and $d_{i + 1} = OR (h_{i}, j_{i})$ . Return $(s_{0}, \dots, s_{w - 1})$ and $d_{w}$ . Define ${SUB}_{w} (U, V)$ by first emitting $NOT (V_{i})$ in increasing $i$ and then calling ${ADD}_{w} (U, NOT (V), 1)$ ; return its difference bits and carry bit $h$ (the no-borrow bit).
Define ${SELECT}_{w} (h, U, V)$ by emitting $d = NOT (h)$ and, for $i = 0, \dots, w - 1$ , $u_{i} = AND (h, U_{i})$ , $v_{i} = AND (d, V_{i})$ , $s_{i} = OR (u_{i}, v_{i})$ . It returns the selected bit array $S$ . Public constant arrays below refer to the shared $0, 1$ nodes and are zero-padded to the displayed width.
Initialize a $2 n$ -bit accumulator $P$ with zero aliases. For $i = 0, \dots, n - 1$ , form a $2 n$ -bit row $H$ : for $j = 0, \dots, n - 1$ , emit $H_{i + j} = AND (a_{i}, z_{j})$ , where $a_{i}$ is the constant bit of $a$ ; all other row bits alias $0$ . Replace $P$ by the sum output of ${ADD}_{2 n} (P, H, 0)$ , ignoring the carry output.
Initialize $R$ to $n$ zero aliases. For $ℓ = 2 n - 1, \dots, 0$ , form the $(n + 1)$ -bit array $V$ by $V_{0} = P_{ℓ}$ and $V_{i} = R_{i - 1}$ for $1 \leq i \leq n$ . Call ${SUB}_{n + 1} (V, N)$ , obtaining difference $D$ and carry $h$ . Set $R$ to the low $n$ bits of ${SELECT}_{n + 1} (h, D, V)$ .
Pad $z$ by a zero high bit, call ${SUB}_{n + 1} (z, N)$ , and let $h$ be its carry. Emit $v = NOT (h)$ and $g = AND (c, v)$ . Set $F = {SELECT}_{n} (g, R, z)$ . The ordered output ports are $F_{n - 1}, \dots, F_{0}$ . This completes the finite DAG and its topological order. Construct a second DAG by the identical recipe with constant $a^{- 1}$ in place of $a$ .

Compile each DAG to the clean-target XOR oracle of Coherent XOR function oracle using Reversible embedding of a Boolean circuit, whose exact gate-emission rules apply also to repeated-source ports. Allocate an $n$ -bit clean target, compute $f_{a} (c, z)$ into it, swap the data and target registers with three CNOT gates per bit, then apply the compiled XOR computation for $f_{a^{- 1}}$ to the old-data target, using the new data as input. Each compiled XOR oracle is an involution by A total Boolean XOR oracle is unitary and involutive. Return the concatenated gate list with every compute-copy-uncompute stage included. Separate items thm-qa-modular-multiplication-circuit-correctness and thm-qa-modular-arithmetic-cost establish its basis action and gate/work bounds. No depth bound is part of this algorithm.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Correctness of the reversible modular multiplier

Statement

For $N \geq 2$ , $n = ⌈ \log_{2} N ⌉$ , and a unit $a (m o d N)$ with supplied inverse $a^{- 1}$ , the circuit of Reversible modular multiplication by a unit is unitary. On a computational-basis state it fixes the control bit, sends $∣ z ⟩$ to $∣ a z m o d N ⟩$ if $c = 1$ and $z < N$ , and fixes $z$ if $c = 0$ or $z \geq N$ . All Boolean value, target, and scratch registers return to zero. Its action therefore extends coherently to superpositions.

Facts & Assumptions

Given: $N \geq 2$ , a unit $a (m o d N)$ and inverse $a^{- 1}$ , a one-bit control and an $n$ -bit data register, and the construction in Reversible modular multiplication by a unit.

[F1]

The circuit computes the total function $f_{a} (c, z)$ into a clean target by an XOR oracle, swaps that target with $z$ , then computes $f_{a^{- 1}}$ on the new data to clear the old-data target (Reversible modular multiplication by a unit). Its gate list acts in the declared chronological order on the stated wires (Denotational semantics of a finite layered circuit).

[F2]

Reversible embedding maps $∣ x, y, 0^{w} ⟩$ to $∣ x, y \oplus f (x), 0^{w} ⟩$ for every basis input and target, restores clean work, and extends to superpositions; a clean register begins in its all-zero basis vector (Gate, workspace, and serial-depth costs of reversible embedding, Clean and dirty ancillas).

[F3]

A coherent XOR oracle acts as $∣ x, y ⟩ \mapsto ∣ x, y \oplus f (x) ⟩$ and is a unitary involution for every total Boolean $f$ on the ordered computational-basis register (Coherent XOR function oracle, A total Boolean XOR oracle is unitary and involutive, Finite registers and their ordered computational bases).

[F4]

A residue class is a unit exactly when its representative is coprime to $N$ ; multiplication by a unit has its stated inverse in $Z / N$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

Proof

1.1givenF1algebra

The DAG's XOR formula is $(u \lor v) \land \neg (u \land v)$ , which is $u + v$ modulo $2$ for each of the four input pairs. In its adder, $U_{i} + V_{i} + d_{i} = s_{i} + 2 d_{i + 1}$ : if both input bits are $1$ the carry is $1$ , if exactly one is $1$ the carry is $d_{i}$ , and if both are $0$ the carry is $0$ ; the displayed sum bit has the corresponding parity. Multiplying by $2^{i}$ and summing proves $U + V + d_{0} = S + 2^{w} d_{w}$ . Subtraction therefore represents $U + (2^{w} - 1 - V) + 1 = U - V + 2^{w}$ ; its carry is $1$ exactly when $U \geq V$ , and its low bits are $U - V$ modulo $2^{w}$ . The selector's disjoint branches give $U$ for $h = 1$ and $V$ for $h = 0$ .

2.1F1step 1.1inductionalgebra

After the first $i$ product rows, the accumulator is $z \sum_{j < i} a_{j} 2^{j}$ . This holds initially and is preserved by step 1.1; no overflow occurs because every partial sum is at most $a z < 2^{2 n}$ . Thus the final product bits represent $a z$ even for invalid input encodings. In the remainder loop, the invariant is that $R$ is the remainder modulo $N$ of the already scanned product prefix and $0 \leq R < N$ . Appending bit $P_{ℓ}$ gives $V = 2 R + P_{ℓ} < 2 N$ . Subtraction and selection from step 1.1 give $V - N$ if $V \geq N$ and $V$ otherwise, so the next value lies in $[0, N)$ and is the new prefix remainder. It fits $n$ bits, making the discarded high bit zero, even when $N = 2^{n}$ . Induction proves the final $R = a z m o d N$ . The final no-borrow comparison gives $v = 1$ exactly when $z < N$ , and selection by $c \land v$ therefore computes precisely $f_{a} (c, z)$ . The same argument applies to $a^{- 1}$ .

3.1givenF1F4step 2.1algebra

Fix $c, z$ . If $c = 0$ or $z \geq N$ , the defining function and its inverse-function counterpart both return $z$ . If $c = 1$ and $z < N$ , the first function returns $z^{'} = a z m o d N < N$ and the inverse function returns $a^{- 1} z^{'} m o d N = z$ , by [F4]. Thus in every case $f_{a^{- 1}} (c, f_{a} (c, z)) = z$ .

4.1F1F2F3step 3.1algebra

By [F2] and [F3], the first computation adds $f_{a} (c, z)$ into a clean target and restores all value-computation work. A bitwise swap made from CNOTs acts as $(u, v) \mapsto (u, u \oplus v) \mapsto (v, u \oplus v) \mapsto (v, u)$ , so after the three CNOTs per bit the data register contains $f_{a} (c, z)$ and the target contains the old $z$ .

5.1F1F2step 3.1step 4.1algebra

Apply the clean XOR computation for $f_{a^{- 1}}$ to the new data and the target holding old $z$ . Step 3.1 says its output is exactly that old $z$ , so XOR changes the target to $z \oplus z = 0$ and restores its computation work by [F2]. Hence all temporary registers are clean and the data/control action is the claimed one.

6.1F2F4step 5.1algebra∎

On valid residue encodings, multiplication by $a$ is a bijection of the residue register because $a^{- 1}$ is its inverse; on invalid encodings and at control $0$ the map is the identity. It is therefore a permutation of the full finite computational basis. A basis permutation is unitary, and [F2] supplies the same action on arbitrary superpositions with clean work. This proves the statement.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Modular order finding with rational reconstruction

Definition

Input. An integer $N \geq 3$ , the standard representative $x \in {1, \dots, N - 1}$ of a unit class modulo $N$ , and an integer $b \geq 1$ specifying target failure probability $δ = 2^{- b}$ .

The representative is the unique one in $0 \leq x < N$ by For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ; unit membership is equivalent to $\gcd (x, N) = 1$ by The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ and For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ . The register ket $∣ 1 ⟩$ uses Dirac Notation Conversion. The superposition output law for applying the QPE gate list to this non-eigenvector input is supplied by Phase estimation on a superposition of eigenspaces.

Output. An accepted candidate, or FAIL.

Instructions. Set $n = ⌈ \log_{2} N ⌉$ , $m = 2 n + 3$ , $Q = 2^{m}$ , and $t = 4 (n + 1) b$ . The inequality $Q > 4 N^{2}$ follows from $N \leq 2^{n}$ . Compute the inverse constant by the following binary-integer loop. Initialize $(R, S, U, V) : = (N, x, 0, 1)$ . While $S > 0$ , use division with remainder to compute $q, r$ with $R = q S + r$ and $0 \leq r < S$ , compute the least residue $h = (U - q V) m o d N$ , and simultaneously replace $(R, S, U, V)$ by $(S, r, V, h)$ . Division and least residues use Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ and For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ; use schoolbook binary arithmetic for every update. When the loop stops, return FAIL if $R \neq 1$ ; otherwise set $b_{0} : = U$ and $a_{0} : = x$ . The inverse identity, termination, and preprocessing bit cost are established in Gate and bit cost of modular multiplication and powering. For $j = 0, \dots, m - 2$ , compute $a_{j + 1} = a_{j}^{2} m o d N$ and $b_{j + 1} = b_{j}^{2} m o d N$ . Then $a_{j} = x^{2^{j}} m o d N$ and $b_{j} = a_{j}^{- 1} m o d N$ for all $j < m$ .

Repeat independently for samples $s = 1, \dots, t$ . Initialize the system register to the valid residue $∣ 1 ⟩$ and apply the QPE phase-estimation circuit with phase-register length $m$ . Its controlled $U_{x}^{2^{j}}$ gate is implemented by the explicit controlled modular-multiplication circuit for $a_{j}$ from Reversible modular multiplication by a unit. This procedure uses the QPE gate list on $∣ 1 ⟩$ ; it does not assert that $∣ 1 ⟩$ is an eigenvector. Measure the phase register to obtain $y$ . Run Rational reconstruction from a phase sample with $(N, Q, y)$ . If it returns FAIL, retain no denominator from this sample. If it returns $p / q$ , compute $x^{q} m o d N$ as follows: set $v : = 1$ , $a : = x$ , $e : = q$ ; while $e > 0$ , if $e$ is odd set $v : = v a m o d N$ , then set $a : = a^{2} m o d N$ and $e : = ⌊ e / 2 ⌋$ . Retain $q$ exactly when the final $v = 1$ .

After all samples, return the smallest retained positive denominator; return FAIL if none was retained. A passing candidate is not called the order unless it is minimal. The exact criterion $x^{q} = 1$ iff the order divides $q$ is If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ . The separate item thm-qa-modular-order-finding-success proves the probability guarantee and the fact that every retained candidate is an order multiple.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Gate and bit cost of modular multiplication and powering

Statement

Let $N \geq 2$ , $n = ⌈ \log_{2} N ⌉$ , and let $1 \leq x < N$ be the standard representative of a known unit modulo $N$ . In the explicit schoolbook Boolean construction of Reversible modular multiplication by a unit, each controlled multiplication by a known unit has a Boolean DAG with $S, E = O (n^{2})$ . Under the compiler of Gate, workspace, and serial-depth costs of reversible embedding, the complete clean circuit, including both XOR computations, $n$ swaps, and inverse cleanup, uses $O (n^{2})$ elementary gates and $O (n^{2})$ clean work bits. Repeated-squaring constants $x^{2^{j}} m o d N$ and their inverses for $O (n)$ powers can be computed in $O (n^{3})$ deterministic multitape bit transitions. No depth bound is asserted.

Facts & Assumptions

Given: $N \geq 2$ , $1 \leq x < N$ a standard unit representative, the stated schoolbook arithmetic, the reversible circuit in Reversible modular multiplication by a unit, and the resource models in Circuit-family and computation cost model and Classical bit-operation cost.

[F1]

The reversible compiler uses at most $6 S + 4 E + m$ elementary gates and at most $S + E$ clean work bits for an $m$ -bit output Boolean DAG (Gate, workspace, and serial-depth costs of reversible embedding).

[F2]

The multiplier computes a controlled constant product, a remainder, a validity condition, the inverse cleanup, and $n$ swaps; its correctness is established by Correctness of the reversible modular multiplier and its circuit stages are specified in Reversible modular multiplication by a unit.

[F3]

Bit cost counts multitape Turing-machine transitions and charges classical arithmetic, address/input work, and output writing; it is separate from gate and query costs (Classical bit-operation cost, Circuit-family and computation cost model).

[F4]

Division by a positive integer gives a unique quotient and smaller nonnegative remainder; the Euclidean descent from $(N, x)$ with $x > 0$ terminates at $(\gcd (N, x), 0)$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ , The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ ).

[F5]

The operations in $Z / N Z$ are well-defined ring operations, so congruences are preserved by subtraction and multiplication (For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[F6]

A residue class modulo $N$ is a unit exactly when its representative is coprime to $N$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[F7]

Every residue class modulo positive $N$ has a unique standard representative $x$ with $0 \leq x < N$ (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

Proof

1.1givenF2algebra

In the explicit DAG of [F2], XOR emits four nodes, each adder bit emits two XORs and three carry nodes, hence $11$ nodes, and subtraction emits one additional NOT per bit, hence $12 w$ nodes at width $w$ . Selection emits $1 + 3 w$ nodes. The product uses $n^{2}$ partial-product AND nodes and $n$ adders of width $2 n$ , totaling $23 n^{2}$ nodes. Its $2 n$ remainder stages use $2 n (12 (n + 1) + 1 + 3 (n + 1))$ nodes. The final comparison uses $12 (n + 1)$ nodes, validity/control uses two more, final selection uses $1 + 3 n$ , and the two shared constant nodes complete the count. Thus $S \leq 100 (n + 1)^{2}$ suffices for all $n \geq 1$ ; every gate has at most two input ports, so $E \leq 2 S$ . The correctness supplier in [F2] proves that the row sums never overflow and that each remainder stage needs only one conditional subtraction; these are exactly the loops just counted.

1.2givenF3F4F5F6F7inductionalgebra

For the inverse computation, initialize $(R, S, U, V) = (N, x, 0, 1)$ and, while $S > 0$ , divide $R = q S + r$ with $0 \leq r < S$ , set $h = (U - q V) m o d N$ to its least residue, and simultaneously update $(R, S, U, V)$ to $(S, r, V, h)$ . Initially $R \equiv U x$ and $S \equiv V x (m o d N)$ ; these two congruences are preserved because $r = R - q S \equiv (U - q V) x \equiv h x (m o d N)$ by [F5]. The remainder pair is exactly the Euclidean descent in [F4], so it terminates at $(R, S) = (\gcd (N, x), 0) = (1, 0)$ by [F6]. The invariant then gives $U x \equiv 1 (m o d N)$ , and [F7] gives the returned inverse constant $b_{0} = U \in [0, N)$ . For its cost, at every division $0 < S < R \leq N$ ; the new remainder is $r < R / 2$ : if $S \leq R / 2$ , then $r < S \leq R / 2$ , while if $S > R / 2$ , then $q = 1$ and $r = R - S < R / 2$ . Thus every two successive positive remainder values shrink by at least a factor of two, giving $O (n)$ iterations. The quotients and remainders have $O (n)$ bits, and $U, V$ always lie in $[0, N)$ , so the signed intermediate $U - q V$ has $O (n)$ bits as well (its magnitude is at most $N^{2} + N$ ). Schoolbook division, multiplication, subtraction and reduction each take $O (n^{2})$ multitape transitions, including signed reduction by dividing the absolute value and, when needed, replacing a nonzero remainder $d$ by $N - d$ . Hence this explicit loop costs $O (n^{3})$ transitions. Set $a_{0} = x$ , and for the remaining $O (n)$ powers compute $a_{j + 1} = a_{j}^{2} m o d N$ and $b_{j + 1} = b_{j}^{2} m o d N$ . Induction gives $a_{j} \equiv x^{2^{j}}$ and $a_{j} b_{j} \equiv 1 (m o d N)$ ; each stage uses two $O (n^{2})$ schoolbook modular products, so all powers and inverses still cost $O (n^{3})$ transitions.

2.1F1F2step 1.1algebra

Step 1.1 counts the complete Boolean function DAG, including the validity comparison, control, and conditional output, and gives $S, E = O (n^{2})$ . Apply [F1] separately to the forward and inverse functions; the two compiled XOR maps and their clean work each cost $O (n^{2})$ . The swap uses $3 n$ CNOT gates. Adding these counts proves the claimed $O (n^{2})$ gate and clean-work bounds; [F2] ensures they implement the required map.

3.1F1F3step 2.1step 1.2∎

The resource definition [F3] keeps gate count, classical bit transitions, and oracle queries separate. The preceding counts establish only gate/work and stated classical arithmetic bounds; no circuit layering or depth estimate follows from them.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Bit cost of phase-sample rational reconstruction

Statement

Let $N \geq 1$ , $m \geq 0$ , $Q = 2^{m} > 4 N^{2}$ , and $y \in {0, \dots, Q - 1}$ be integers, and set $L = ⌈ \log_{2} (Q + 1) ⌉$ . Under the multitape bit-transition model of Classical bit-operation cost, Rational reconstruction from a phase sample uses $O (L)$ Euclidean divisions and $O (L^{3})$ deterministic bit transitions. No real-number arithmetic is used.

Facts & Assumptions

Given: Integers $N \geq 1$ , $m \geq 0$ , $Q = 2^{m} > 4 N^{2}$ , $0 \leq y < Q$ , the reconstruction routine, and the bit-cost convention.

[F1]

Rational continued fractions are computed by the Euclidean quotient algorithm; integer division has quotient and remainder $u = a v + r$ with $0 \leq r < v$ , and convergent denominators obey $q_{j} = a_{j} q_{j - 1} + q_{j - 2}$ (Rational reconstruction from a phase sample, Finite and infinite regular continued fractions, Convergents of a regular continued fraction, Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[F2]

Bit cost counts transitions of a fixed finite-alphabet multitape machine and charges comparison, arithmetic, reading, and output work (Classical bit-operation cost).

Proof

1.1F1givenalgebra

Let $q_{j}$ be the convergent denominators, with $q_{0} = 1$ and $q_{1} \geq 1$ . The recurrence in [F1] gives $q_{j + 2} \geq q_{j + 1} + q_{j} \geq 2 q_{j}$ whenever both indices exist. Since the terminal denominator is at most $Q$ , every two quotient steps at least double a positive denominator, so the number of Euclidean divisions is at most $2 L + O (1) = O (L)$ .

2.1F1F2step 1.1algebra

The reduced denominator of $y / Q$ is at most $Q$ , so the recurrence in [F1] makes each convergent denominator at most its terminal denominator. Since $0 \leq y / Q < 1$ , the normalized expansion starts with $a_{0} = 0$ ; its initial convergents satisfy $0 \leq p_{0} \leq q_{0}$ and $0 \leq p_{1} \leq q_{1}$ , and the recurrence with positive later digits preserves $0 \leq p_{j} \leq q_{j}$ . Thus all convergent numerators and denominators have $O (L)$ bits. By the division algorithm in [F1], binary long division of two such integers can be performed by at most $O (L)$ compare/subtract scans of at most $O (L)$ bits, hence $O (L^{2})$ multitape transitions under [F2].

3.1F1F2step 1.1step 2.1algebra

Updating a convergent numerator and denominator by [F1] uses a constant number of products and sums on $O (L)$ -bit integers, hence $O (L^{2})$ transitions per update. Each convergent candidate also requires a constant number of products $y q_{j}$ and $p_{j} Q$ , an absolute difference, a doubling, and a comparison with $q_{j}$ . Schoolbook multiplication and these scans each cost $O (L^{2})$ transitions. There are $O (L)$ candidates by step 1.1, so total comparison work is $O (L^{3})$ ; writing the selected numerator and denominator costs only $O (L)$ .

4.1F1F2step 3.1∎

The routine normalizes the rational by exact Euclidean divisions and applies only the integer test from [F1]; all work is covered by the above bounds. Hence its deterministic multitape bit cost is $O (L^{3})$ and it performs no floating-point comparison.

TheoremStatement: Literature-sourcedProof: AI-adaptedjudge pass (gpt-6-luna)Open item page →

Success probability and repetition for modular order finding

Statement

Let integer $N \geq 3$ , and let $x$ be a unit modulo $N$ of order $r$ . Use Modular order finding with rational reconstruction with $b \in Z_{\geq 1}$ and $δ = 2^{- b}$ . One independent phase sample yields denominator $r$ with probability at least $\frac{4}{π^{2}} \frac{φ (r)}{r} \geq \frac{4}{π^{2} (1 + \log_{2} N)} .$ After $t = 4 (n + 1) b$ independent samples, where $n = ⌈ \log_{2} N ⌉$ , the algorithm returns the exact order with probability at least $1 - 2^{- b}$ . For any requested $0 < δ < 1$ , taking $b = ⌈ \log_{2} (1 / δ) ⌉$ gives success probability at least $1 - δ$ .

Facts & Assumptions

Given: $N \geq 3$ , a unit class $x$ modulo $N$ , its order $r$ , and the circuit/sampling instructions in Modular order finding with rational reconstruction.

[F1]

The unit classes form a finite group of size $φ (N)$ ; an element of a finite group has finite order dividing the group size. Standard representatives identify this group with a subset of ${0, \dots, N - 1}$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , The order of every element of a finite group divides the order of the group, For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ ).

[F2]

On valid residues, $U_{x} ∣ z ⟩ = ∣ x z m o d N ⟩$ and invalid $n$ -bit encodings are fixed by the multiplier circuit (Reversible modular multiplication by a unit, Correctness of the reversible modular multiplier).

[F3]

The finite cyclic characters are orthogonal: $\sum_{s = 0}^{r - 1} e^{2 π i (k - ℓ) s / r} = r$ if $k = ℓ (m o d r)$ and $0$ otherwise (Orthogonality of the characters $x \mapsto e^{2 π i k x / N}$ on $Z / N Z$ ).

[F4]

For each eigenphase, phase estimation on a superposition has the eigenspace-weighted outcome mixture; every nearest $Q$ -grid label has probability at least $4 / π^{2}$ (Phase estimation on a superposition of eigenspaces, Phase-estimation nearest-grid and tail bounds).

[F5]

A coprime class modulo $r$ is counted among the $φ (r)$ units, and $φ (r) / r \geq 1 / (1 + \log_{2} r)$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , Elementary lower bound for the totient ratio).

[F6]

If $x$ has order $r$ , then $x^{q} = 1$ exactly when $r ∣ q$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[F7]

For every integer $s \geq 3$ , the circumscribed regular $s$ -gon has perimeter $O_{s} = 2 s \tan (π / s)$ and satisfies $2 π < O_{s}$ (Inscribed regular-polygon perimeters increase to 2 pi, while circumscribed perimeters decrease to 2 pi).

[F8]

The cofunction identity gives $\sin (π / 2 - x) = \cos x$ , and the Pythagorean identity gives $\sin^{2} x + \cos^{2} x = 1$ (Cofunction, supplementary, quarter-turn, and reflection identities for the six trigonometric functions, Pythagorean and parity identities for all six trigonometric functions on their natural domains).

[F9]

Sine is strictly increasing on $[- π / 2, π / 2]$ , cosine is strictly decreasing on $[0, π]$ , $\sin 0 = 0$ , $\cos (π / 2) = 0$ , and $π > 0$ (Signs, monotonicity intervals, and ranges of sine and cosine, Quarter-turn values and shifts by pi/2 and pi, Pi as twice the smallest positive zero of cosine).

[F10]

On its natural domain, $\tan x = \sin x / \cos x$ (Tangent, cotangent, secant, and cosecant on their exact natural domains).

[F11]

Distinct computational-basis vectors of a register are orthonormal (The computational basis is orthonormal).

Proof

1.1givenF1F2algebra

By [F1], $r$ is a positive integer and $r \leq φ (N) \leq N$ : write $φ (N) = d r$ with integer $d$ by divisibility in [F1]. The group contains its identity, so $φ (N) > 0$ ; since $r > 0$ , $d > 0$ and thus $d \geq 1$ . Consequently $r \leq φ (N)$ , while the group counts only standard residue representatives and so $φ (N) \leq N$ . The orbit $∣ x^{s} m o d N ⟩$ , $0 \leq s < r$ , consists of distinct valid computational-basis vectors, since equality of two residues would imply a smaller positive power of $x$ is $1$ .

1.2givenF2inductionalgebra

The algorithm starts with $a_{0} = x$ and $b_{0} = x^{- 1}$ in standard representatives. Suppose $a_{j} \equiv x^{2^{j}}$ and $a_{j} b_{j} \equiv 1 (m o d N)$ . Squaring the first identity gives $a_{j + 1} \equiv x^{2^{j + 1}}$ , and the two loop updates give $a_{j + 1} b_{j + 1} \equiv (a_{j} b_{j})^{2} \equiv 1$ . Induction proves both identities for all $j < m$ ; every constant remains in $[0, N)$ and is a unit with the supplied inverse. On valid residues, repeated application of [F2] therefore gives $U_{x}^{2^{j}} ∣ z ⟩ = ∣ a_{j} z m o d N ⟩$ ; on invalid encodings both this power and the multiplier are identity. Thus each controlled multiplier in the QPE gate list is the required controlled power on the full data register, with its work returned clean.

2.1F2F3F11step 1.1algebra

Define $∣ ψ_{k} ⟩ = r^{- 1 / 2} \sum_{s = 0}^{r - 1} e^{- 2 π i k s / r} ∣ x^{s} m o d N ⟩$ for $0 \leq k < r$ . The shift action in [F2] gives $U_{x} ∣ ψ_{k} ⟩ = e^{2 π i k / r} ∣ ψ_{k} ⟩$ , including the wrap from $s = r - 1$ to $s = 0$ . By [F11] and [F3] these are orthonormal unit vectors; the same character sum gives $∣ 1 ⟩ = r^{- 1 / 2} \sum_{k = 0}^{r - 1} ∣ ψ_{k} ⟩$ .

3.1F3F4F5step 1.2step 2.1

Apply the QPE circuit from [F4] to this decomposition. Its outcome law is the uniform mixture over $k = 0, \dots, r - 1$ , each phase being $k / r$ ; this uses the superposition law in [F4], rather than an eigenvector promise for $∣ 1 ⟩$ . There are exactly $φ (r)$ indices with $\gcd (k, r) = 1$ , counted by [F5].

4.1F4F5F6step 1.1step 3.1algebra

For each coprime $k$ , [F4] gives probability at least $4 / π^{2}$ to a nearest grid label. Here $m = 2 n + 3$ , $Q = 2^{m} > 4 N^{2}$ , and $r \leq N$ by step 1.1, so the reconstruction correctness theorem applies and returns reduced denominator $r$ on that event. By [F6], $x^{r} = 1$ ; hence the algorithm's exact verification retains this denominator. Summing the disjoint eigenspace-mixture probabilities gives one-sample success at least $(4 / π^{2}) φ (r) / r$ . By [F5] and $r \leq N$ , this is at least $4 / [π^{2} (1 + \log_{2} N)]$ .

5.1F6step 4.1algebra

Every retained $q$ passes $x^{q} = 1$ , so [F6] implies $r ∣ q$ . If the exact denominator $r$ is ever retained, no retained candidate is smaller than $r$ and $r$ itself is present; the algorithm's minimum rule therefore returns $r$ .

6.1givenF7F8F9F10step 4.1step 5.1algebra

First put $θ = π / 4$ . Since $π > 0$ by [F9], $0 < θ < π / 2$ . The cofunction law [F8] gives $\sin θ = \cos θ$ ; strict monotonicity and the endpoint values in [F9] show both are positive. Thus [F10] gives $\tan (π / 4) = 1$ , and [F7] at $s = 4$ gives $2 π < O_{4} = 8 \tan (π / 4) = 8$ , so $π < 4$ . Now put $n = ⌈ \log_{2} N ⌉$ and $u = 1 / [4 (n + 1)]$ . The one-sample lower bound in step 4.1 and $π < 4$ , together with $1 + \log_{2} N \leq n + 1$ , give $p \geq u$ . Independent resets make the $t = 4 (n + 1) b$ samples independent, hence the probability that no successful sample occurs is at most $(1 - u)^{t}$ . Since $1 - u \leq (1 + u)^{- 1}$ , and with integer $K = 4 (n + 1)$ the binomial expansion gives $(1 + 1 / K)^{K} \geq 1 + K (1 / K) = 2$ , we obtain $(1 - u)^{K b} \leq 2^{- b}$ . By step 5.1, the output is the exact order except on this event.

7.1givenstep 6.1algebra∎

For arbitrary $0 < δ < 1$ , choosing $b = ⌈ \log_{2} (1 / δ) ⌉$ gives $2^{- b} \leq δ$ . Thus the stated guarantee follows without using an inexact floating-point threshold.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Separate order-finding query, gate, and bit costs

Statement

Let integer $N \geq 3$ , $n = ⌈ \log_{2} N ⌉$ , $b \in Z_{\geq 1}$ , and $δ = 2^{- b}$ . With the explicit multiplier of Gate and bit cost of modular multiplication and powering and the ideal continuous exact-arbitrary-angle QFT cost model, the algorithm uses $O (n^{2} b)$ controlled modular-multiplier circuits, $O (n^{4} b)$ elementary gates, and $O (n^{4} b)$ schoolbook classical bit transitions. Equivalently these are $O (n^{2} (1 + \ln (1 / δ)))$ , $O (n^{4} (1 + \ln (1 / δ)))$ , and $O (n^{4} (1 + \ln (1 / δ)))$ . With only controlled $U_{x}$ access, the query count is exactly $t (Q - 1)$ for $t = 4 (n + 1) b$ and $Q = 2^{2 n + 3}$ ; this is not a polynomial query bound. No finite gate alphabet, uniform circuit family, or generator-time bound is asserted.

Facts & Assumptions

Given: The modular order-finding circuit and sample count, the QPE cost model, and the distinct gate/bit/query coordinates in Circuit-family and computation cost model and Classical bit-operation cost.

[F1]

The algorithm uses $m = 2 n + 3$ phase bits, $Q = 2^{m}$ , $t = 4 (n + 1) b$ independent samples, and one controlled modular multiplication for each of the $m$ QPE powers per sample (Modular order finding with rational reconstruction).

[F2]

One phase-estimation run uses $Q - 1$ controlled- $U_{x}$ calls if only controlled- $U_{x}$ is supplied; exact ideal QFT gate count is $O (m^{2})$ (Phase-estimation query and gate costs).

[F3]

Each controlled modular multiplier uses $O (n^{2})$ gates, while repeated-squaring constants and inverses cost $O (n^{3})$ classical bit transitions (Gate and bit cost of modular multiplication and powering).

[F4]

Continued-fraction reconstruction costs $O (n^{3})$ bit transitions when $Q = 2^{2 n + 3}$ , and the declared model charges classical arithmetic separately from oracle and gate operations (Bit cost of phase-sample rational reconstruction, Classical bit-operation cost, Circuit-family and computation cost model).

Proof

1.1F1givenalgebra

Since $Q = 2^{2 n + 3}$ , its bit length is $O (n)$ ; [F1] has $m = O (n)$ and $t = O (n b)$ . There are exactly $t m = O (n^{2} b)$ controlled modular-multiplier circuits.

2.1F1F2F3step 1.1algebra

By [F3], those arithmetic circuits contribute $O (n^{2}) \cdot O (n^{2} b) = O (n^{4} b)$ gates. Each QPE phase preparation and ideal inverse QFT contributes $O (m^{2}) = O (n^{2})$ more gates per sample by [F2], for total $O (n^{3} b)$ , which is bounded by $O (n^{4} b)$ since $n \geq 2$ . Thus the stated gate bound follows.

2.2F1F3F4step 1.1algebra

Precomputing all modular powers and inverses costs $O (n^{3})$ bits by [F3]. In each sample, reconstruction costs $O (n^{3})$ by [F4]. Testing a candidate $q \leq N$ by binary modular exponentiation uses $O (n)$ modular products on $O (n)$ -bit values, each with $O (n^{2})$ schoolbook transitions as in [F3], hence $O (n^{3})$ bits. Across $t = O (n b)$ samples this is $O (n^{4} b)$ , including preprocessing because $n \geq 2$ and $b \geq 1$ .

3.1F1F2F3F4step 2.1step 2.2

Under only controlled- $U_{x}$ access, [F2] charges exactly $Q - 1$ calls for each run, so $t (Q - 1)$ is the total query count. Under compiled known modular arithmetic, the multiplier circuits have the separate cost in step 2.1. The cost coordinates in [F4] are independent, so this gate bound does not turn a black-box controlled- $U_{x}$ query into a polynomial-cost circuit.

4.1F1F2F3F4step 3.1∎

For $b \geq 1$ , $1 + b = O (1 + \ln (1 / δ))$ when $δ = 2^{- b}$ , since $\ln (1 / δ) = b \ln 2$ . This gives the equivalent logarithmic forms. The ideal QFT model uses exact continuous rotations, and none of [F1]–[F4] provides a finite-alphabet compilation or a uniform-family generator, so those claims are outside this theorem.

5 · Examples, counterexamples and false statements

None yet.

Quantum Order Finding and Rational Reconstruction

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Finite-rational Legendre criterion before the terminal convergent

Statement

Facts & Assumptions

Proof

Uniqueness of denominator-bounded phase candidates

Statement

Facts & Assumptions

Proof

Elementary lower bound for the totient ratio

Statement

Facts & Assumptions

Proof

Denominator-bounded rational phase reconstruction

Definition

Rational reconstruction from a phase sample

Definition

Correctness of phase-sample rational reconstruction

Statement

Facts & Assumptions

Proof

Reversible modular multiplication by a unit

Definition

Correctness of the reversible modular multiplier

Statement

Facts & Assumptions

Proof

Modular order finding with rational reconstruction

Definition

Gate and bit cost of modular multiplication and powering

Statement

Facts & Assumptions

Proof

Bit cost of phase-sample rational reconstruction

Statement

Facts & Assumptions

Proof

Success probability and repetition for modular order finding

Statement

Facts & Assumptions

Proof

Separate order-finding query, gate, and bit costs

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources