TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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 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.

Depends on

Used by

Separate Shor factoring bit, gate, and query costs Theorem

Cited to discharge well-definedness by Modular order finding with rational reconstruction.

Dependency tree · two levels

45 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

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