TheoremStatement: AI-adaptedProof: AI-generatedPipeline-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.

Separate Shor factoring bit, gate, and query costs

Statement

Let $N \geq 4$ , $n = ⌈ \log_{2} N ⌉$ , and let $δ = u / v \in (0, 1)$ be a reduced rational encoded in binary, with $B$ the bit length of $v$ . Let $T$ be the attempt cap in Shor factoring with verified output and bounded outer retries, and put $Q = 2^{2 n + 3}$ . For the arithmetic, control, sampler and post-processing work after the declared circuits are supplied, under the explicit reversible-arithmetic branch and ideal exact-angle QFT branch of Shor factoring cost-accounting branches, the procedure uses

$O (n^{4} T) = O (n^{4} (1 + \ln (1 / δ)))$ quantum gates;
$O (n^{2} T)$ controlled modular-multiplier calls and zero external black-box queries;
$O (n^{5} + n^{4} T + B^{3})$ expected classical bit operations, including sampler bits and exact computation of $T$ .

For the same order-finding control flow with only bare controlled access to $U_{x}$ , one phase-estimation sample costs $Q - 1$ controlled- $U_{x}$ queries, so the outer algorithm uses $O (n T (Q - 1))$ such queries. No polynomial-in- $n$ query bound, finite-alphabet compilation, uniform-family gate claim, or circuit-description generation-time bound is asserted.

Facts & Assumptions

Given: The algorithm Shor factoring with verified output and bounded outer retries on binary input $N, δ$ , with its declared outer cap $T$ and phase width $m = 2 n + 3$ .

[F1]

For $m = 2 n + 3$ , $Q = 2^{m}$ , and internal failure target $2^{- b}$ , the order finder uses $t = 4 (n + 1) b$ independent samples. Its cost theorem gives $O (n^{2} b)$ controlled modular-multiplier calls, $O (n^{4} b)$ gates and $O (n^{4} b)$ classical bit transitions in the explicit-arithmetic/ideal-QFT model; with bare controlled- $U_{x}$ access, one sample costs $Q - 1$ queries (Modular order finding with rational reconstruction, Separate order-finding query, gate, and bit costs).

[F2]

A known controlled modular multiplication uses $O (n^{2})$ gates, and the repeated-squaring constants and inverses can be computed in $O (n^{3})$ classical bit transitions (Gate and bit cost of modular multiplication and powering).

[F3]

The ideal exact-angle inverse QFT has $O (m^{2})$ gates, while the named cost convention keeps this ideal count separate from the explicit arithmetic circuits, multiplier calls, bare-unitary queries and classical bit operations; it asserts no finite gate alphabet or uniform family (Shor factoring cost-accounting branches).

[F4]

The even/perfect-power preprocessing takes $O (n^{5})$ schoolbook bit operations (Even and perfect-power preprocessing returns a proper factor).

[F5]

For $h = ⌈ \log_{2} (N - 1) ⌉$ , one rejection-sampler call halts almost surely, returns a uniform element of ${1, \dots, N - 1}$ , and uses at most $2 h$ expected random bits and $O (h)$ expected total bit transitions (Rejection sampling is uniform, almost surely terminating, and has expected linear bit cost).

[F6]

Classical bit cost counts machine transitions, including random-bit generation, arithmetic, comparisons, preprocessing and output writing (Classical bit-operation cost).

[F7]

The resource model records gate occurrences, work wires, oracle queries, description length, generator time, and classical bit costs as distinct coordinates; separate theorems must establish each bound (Circuit-family and computation cost model).

Proof

1.1givenF1algebra

The Shor algorithm fixes $b = 2$ , so [F1] gives $O (n^{2})$ multiplier calls, $O (n^{4})$ gates and $O (n^{4})$ classical bit transitions for each order-finding invocation. There are at most $T$ such invocations, so their totals are $O (n^{2} T)$ calls, $O (n^{4} T)$ gates and $O (n^{4} T)$ bit transitions. The definition of $T$ gives $T = O (1 + \ln (1 / δ))$ because $- \ln (5 / 8)$ is a positive constant.

1.2givenF1algebra

In the bare controlled- $U_{x}$ branch, one phase sample applies controlled powers $U_{x}^{2^{j}}$ for $j = 0, \dots, m - 1$ . Repeating the bare call $2^{j}$ times implements the $j$ th power, so one sample uses $\sum_{j = 0}^{m - 1} 2^{j} = 2^{m} - 1 = Q - 1$ queries. For fixed $b = 2$ , [F1] gives $t = 8 (n + 1) = O (n)$ samples per order call. At most $T$ calls therefore use $O (n T (Q - 1))$ queries.

1.3F1F4F5F6algebra

The perfect-power check costs $O (n^{5})$ by [F4]. Each order call costs $O (n^{4})$ classical bit transitions by [F1]. The outer verification adds at most $O (n^{3})$ transitions per attempt: binary modular exponentiation uses $O (n)$ products of $n$ -bit integers. Schoolbook multiplication takes $O (n^{2})$ transitions, and binary long division has at most $n$ quotient positions, each requiring an $O (n)$ -bit comparison/subtraction, so product remainders also take $O (n^{2})$ transitions. The Euclidean gcd algorithm has $O (n)$ remainder steps because in each pair of successive divisions the positive remainder at least halves; each division takes $O (n^{2})$ transitions by the same long-division count. Divisor comparisons and remainder checks fit this bound. By [F5], each sampler call uses $O (n)$ expected total transitions. Thus all these per-attempt work is $O (n^{4} T)$ in total.

1.4givenF6algebra

The exact cap is computed by increasing $t$ until $5^{t} v \leq 8^{t} u$ . Since $v < 2^{B}$ and $u \geq 1$ , $δ > 2^{- B}$ ; also $(5 / 8)^{2 B} = (25 / 64)^{B} < 2^{- B}$ . Hence $T \leq 2 B$ . Throughout this loop, the exact powers have $O (B)$ bits, and each of at most $2 B$ multiply/compare iterations costs $O (B^{2})$ schoolbook bit transitions. Computing $T$ therefore costs $O (B^{3})$ .

2.1F1F2F3F7step 1.1algebra

In the explicit-arithmetic branch, each multiplier call is charged to the supplied reversible circuit; it is not a black-box query. [F2] supplies its $O (n^{2})$ gate count and [F3] supplies the separate ideal QFT count. The resulting gate count is the $O (n^{4} T)$ bound in step 1.1; the distinct coordinates are those of [F7].

3.1step 1.3step 1.4algebra∎

Combining steps 1.3 and 1.4 gives $O (n^{5} + n^{4} T + B^{3})$ expected classical bit operations.

Remarks

The current cost-model definition and the QA08 arithmetic and order-finding cost theorems provide the stated separate resource coordinates. The supplied-circuit and ideal-QFT conventions above determine which bounds are asserted; they provide no circuit-description generation-time bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

68 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)