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.

Operator-norm error of QFT truncation

Statement

Let $n \geq 1$ , $N = 2^{n}$ , and let $m \geq 1$ be an integer. For $1 \leq m < n$ ,

$∥ {QFT}_{2^{n}} - {QFT}_{2^{n}}^{(m)} ∥ \leq \sum_{s = m + 1}^{n} (n - s + 1) \frac{2 π}{2^{s}} \leq 2 π n 2^{- m} .$

For $m \geq n$ , the truncated circuit is exact and the error is zero. In particular, for $0 < ε < 1$ , the cutoff $m = \min {n, ⌈ \log_{2} (2 π n / ε) ⌉}$ gives operator-norm error at most $ε$ .

Facts & Assumptions

Given: The exact and truncated circuits on a nonzero $2^{n}$ -dimensional register, with $n \geq 1$ , and an integer cutoff $m \geq 1$ .

[F1]

The exact and truncated gate lists agree except that each controlled phase with denominator index $s > m$ is replaced by the identity (Exact binary QFT circuit, Truncated binary QFT).

[F2]

The ideal controlled phase is $diag (1, 1, 1, e^{2 π i / 2^{s}})$ (QFT ideal and finite-set gate-cost models).

[F3]

For a nonzero finite-dimensional domain, the operator norm is the maximum over unit vectors (The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||).

[F4]

Compatible products satisfy $∥ S T ∥ \leq ∥ S ∥ ∥ T ∥$ (The operator norm is submultiplicative and satisfies ||T^*T|| = ||T||^2).

[F5]

In finite dimension, a unitary is an isometry and its adjoint is its inverse (For an endomorphism in finite dimension, preserving lengths, preserving inner products, carrying orthonormal bases to orthonormal bases, and $T^{*} T = I$ are equivalent).

[F6]

The vector norm induced by an inner product satisfies $∥ u + v ∥ \leq ∥ u ∥ + ∥ v ∥$ (The inner-product norm is definite, homogeneous, and satisfies the triangle inequality).

[F7]

For real $t$ , $e^{i t} = \cos t + i \sin t$ and $∣ e^{i t} ∣ = 1$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ ).

[F8]

$∣ \sin u - \sin v ∣ \leq ∣ u - v ∣$ for real $u, v$ (Sine and cosine are $1$ -Lipschitz on $R$ ).

[F9]

$\sin 0 = 0$ (The derivatives of sine and cosine are cosine and minus sine).

[F10]

$\cos (2 u) = 1 - 2 \sin^{2} u$ (Double-angle and quadratic power-reduction identities).

[F11]

The exact circuit denotes ${QFT}_{2^{n}}$ (Exact binary QFT circuit correctness).

[F12]

A wire permutation of an ordered tensor register is unitary (Finite wire permutations are unitary basis permutations).

[F13]

Adding spectator factors or moving the selected wires preserves the operator norm of a local gate (Operator Norm Is Unchanged by Spectator Registers).

[F14]

A tensor map acts on elementary product vectors by applying its factor maps (Tensor products of finitely many linear maps).

[F15]

The two-qubit computational basis is orthonormal (The product basis is orthonormal and tensor dimensions multiply).

[F16]

Coordinates in a finite orthonormal basis satisfy Parseval and Bessel bounds (Bessel's inequality for a finite orthonormal list and Parseval's identity for an orthonormal basis).

[F17]

A unitary gate on distinct ordered wires has a unique unitary global embedding acting by the local gate on those wires and by the identity on the others (A local gate has a unique global wire embedding).

[A1]

Denotational semantics of a finite layered circuit identifies the chronological gate list with the right-to-left product of its embedded gate operators.

Proof

technique · direct

Given: The circuits and hypotheses above.

1.1F7F8F9F10algebra

For real $t$ , [F7] and [F10] give $∣ 1 - e^{i t} ∣^{2} = (1 - \cos t)^{2} + \sin^{2} t = 2 (1 - \cos t) = 4 \sin^{2} (t / 2)$ . By [F8]–[F9], $∣ \sin (t / 2) ∣ = ∣ \sin (t / 2) - \sin 0 ∣ \leq ∣ t ∣ / 2$ , hence $∣ 1 - e^{i t} ∣ \leq ∣ t ∣$ .

2.1F2F3F13F15F16step 1.1algebra

For an omitted gate at level $s$ , set $t_{s} = 2 π / 2^{s}$ and $D_{s} = {C P}_{s} - I$ on its two-qubit target. By [F2], $D_{s}$ has only one nonzero diagonal entry, $e^{i t_{s}} - 1$ , in the orthonormal basis [F15]. For any unit vector, Bessel's inequality [F16] bounds its $∣ 11 ⟩$ coordinate in modulus by $1$ , so $∥ D_{s} v ∥ \leq ∣ e^{i t_{s}} - 1 ∣$ ; equality is attained at $v = ∣ 11 ⟩$ . Thus $∥ D_{s} ∥ = ∣ e^{i t_{s}} - 1 ∣ \leq 2 π / 2^{s}$ by step 1.1, and embedding it on the full register preserves this norm by [F13].

3.1A1F2F3F4F5F6F7F11F12F14F17step 2.1algebra

By [A1], let $G_{1}, \dots, G_{K}$ be the embedded operators in chronological order, so the exact circuit product is $G_{K} \dots G_{1}$ and the truncated product replaces omitted $G_{r}$ by ${\tilde{G}}_{r} = I$ . The local embedding action is [F17]. By [F11], the exact product is ${QFT}_{2^{n}}$ . Their difference telescopes as $\sum_{r = 1}^{K} G_{K} \dots G_{r + 1} (G_{r} - {\tilde{G}}_{r}) {\tilde{G}}_{r - 1} \dots {\tilde{G}}_{1}$ . Each $H$ is unitary by direct multiplication of its matrix in [F2]; each ${C P}_{s}$ is unitary because it is diagonal with unit-modulus entries by [F2,F7]; each SWAP is unitary by [F12], and each omitted gate is replaced by $I$ . A local unitary $U$ tensored with $I$ has inverse $U^{- 1} \otimes I$ by [F14], and conjugating by the unitary wire permutation preserves unitarity. Thus every outside product is unitary and has norm $1$ by [F3,F5]. For any operators $X, Y$ , [F6] and the definition [F3] give $∥ X + Y ∥ \leq ∥ X ∥ + ∥ Y ∥$ ; submultiplicativity [F4] therefore bounds the telescoping sum by the sum of the omitted-gate norms from step 2.1.

4.1F1step 2.1step 3.1algebra

At level $s$ , the pairs $0 \leq i < j < n$ satisfying $j - i + 1 = s$ have $i = 0, \dots, n - s$ , so there are $n - s + 1$ such gates. Summing step 2.1 over the omitted levels gives the first bound. Since $n - s + 1 \leq n$ and $\sum_{s = m + 1}^{n} 2^{- s} \leq 2^{- m}$ , this is at most $2 π n 2^{- m}$ .

5.1F1step 4.1algebra∎

If $m \geq n$ , no gate is omitted by [F1], so the error is zero. Otherwise the displayed sum bound applies. For $m = ⌈ \log_{2} (2 π n / ε) ⌉ < n$ , $2^{m} \geq 2 π n / ε$ , hence $2 π n 2^{- m} \leq ε$ ; taking $m = \min {n, ⌈ \log_{2} (2 π n / ε) ⌉}$ selects either this case or $m = n$ .

Remarks

No axiom of choice is used. The key local proof obligation is the telescoping operator-norm estimate: the cited QFT treatments motivate the cutoff but do not supply this complete operator-norm argument. The sine/cosine suppliers are published and read; the QFT circuit suppliers remain in the assigned cross-pair dependency set.

Depends on

Used by

QFT circuit order and truncation examples Example
Finite universal-gate compilation cost for the truncated QFT Theorem
Truncated QFT ideal gate count Theorem

Dependency tree · two levels

72 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)