TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Exact binary QFT ideal gate count

Statement

For $n \geq 0$ , the exact circuit uses $n$ Hadamards, $n (n - 1) / 2$ controlled phase rotations, $⌊ n / 2 ⌋$ SWAP gates, no ancillas, and

$n + \frac{n (n - 1)}{2} + ⌊ n / 2 ⌋ = O (n^{2})$

ideal gates in the model of QFT ideal and finite-set gate-cost models. If every SWAP is expanded into three exact CNOTs, the circuit instead has $3 ⌊ n / 2 ⌋$ CNOTs in place of the SWAPs.

Facts & Assumptions

Given: An integer $n \geq 0$ , the exact circuit of Exact binary QFT circuit, and the ideal gate model of QFT ideal and finite-set gate-cost models.

[F1]

The exact circuit applies one $H$ on each wire, one controlled phase for each pair $0 \leq i < j < n$ , then $⌊ n / 2 ⌋$ reversal swaps (Exact binary QFT circuit).

[F2]

Each $H$ , controlled phase and named SWAP counts as one ideal gate; an expanded SWAP uses three CNOTs (QFT ideal and finite-set gate-cost models).

[F3]

The two-wire SWAP equals the exact three-CNOT sequence (A SWAP Is Three CNOTs).

Proof

technique · direct

Given: The circuit and gate-count convention above.

1.1F1algebra

The loop has one Hadamard for each of the $n$ wires. Its controlled phases are indexed by pairs $(i, j)$ with $0 \leq i < j < n$ ; summing the $j$ possible lower controls for each target gives $\sum_{j = 0}^{n - 1} j = n (n - 1) / 2$ . The final reversal consists of exactly one swap for each pair $(j, n - 1 - j)$ with $j < ⌊ n / 2 ⌋$ , hence $⌊ n / 2 ⌋$ swaps.

2.1givenF2F3step 1.1algebra∎

By [F2], the ideal count is the displayed sum and there are no other gates or ancillas. For $n \geq 1$ , the sum is at most $n + n (n - 1) / 2 + n / 2 \leq 3 n^{2} / 2$ , so it is $O (n^{2})$ ; at $n = 0$ all counts vanish. Replacing each counted SWAP by the exact identity [F3] gives exactly $3 ⌊ n / 2 ⌋$ CNOTs.

Depends on

Used by

Phase-estimation query and gate costs Theorem

Dependency tree · two levels

14 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)
Andrew M. Childs, Lecture Notes on Quantum Algorithms (standard reference, not scraped)
John Preskill, Quantum Information, Chapter 6: Quantum Algorithms (standard reference, not scraped)