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.

QC24 Discrete Alphabet Approximate Preparation Lower Bound

Statement

Fix real numbers $0 < δ < 1 / 4$ and $0 \leq ε < \sqrt{δ}$ . Let integers $n \geq 2$ , $A \geq 1$ , $k \geq 1$ , and $W \geq n$ be fixed, with $D = 2^{n}$ , gate-alphabet size $A$ , and maximum arity $k$ . For an integer gate budget $g \geq 0$ , every circuit starts on $∣ 0^{n} ⟩ ∣ 0^{W - n} ⟩$ and must return the workspace exactly to zero, with its data output within projective chord distance $ε$ of the target ray. If a circuit family prepares every $D$ -dimensional pure-state ray and each circuit in the family has at most $g$ gates in this model, then $g = Ω (D / \log W)$ as $n \to \infty$ , with constants depending on $A, k, δ, ε$ . In particular, if $W = poly (n)$ , then $g = Ω (2^{n} / \log n)$ .

Facts & Assumptions

Given: The fixed finite-alphabet width model with exact clean-workspace output, fixed integers $A \geq 1$ , $k \geq 1$ , and fixed $δ, ε$ in the Statement, and the ray-packing and circuit-count bounds below.

[F1]

The page contains at least $\exp (c_{δ} D)$ rays pairwise separated by at least $2 \sqrt{δ}$ in $d_{c h}$ (QC24 Signed Ray Packing Code).

[F2]

At width $W$ , a length- $j$ circuit has at most $(C_{k} A W^{k})^{j}$ descriptions, with $C_{k} = k + 1$ (QC24 Finite Width Topology Count).

[F3]

$d_{c h} ([u], [v]) = \sqrt{2 - 2 ∣ ⟨ u, v ⟩_{r o o t} ∣}$ and the phase-minimum is attained (Projective Chord Distance Formula).

[F4]

The Euclidean norm induced by the root inner product satisfies the triangle inequality (The inner-product norm is definite, homogeneous, and satisfies the triangle inequality).

Proof

Given: As in Facts & Assumptions.

1.1F1F3F4givenalgebracontradiction

A single output ray cannot be within $ε$ of two distinct packed rays. Indeed, if $d_{c h} ([u], [q]) \leq ε$ and $d_{c h} ([v], [q]) \leq ε$ , [F3] gives unit phases $λ, μ$ with $∥ u - λ q ∥_{2} \leq ε$ and $∥ v - μ q ∥_{2} \leq ε$ ; then [F4] gives $∥ u - (λ / μ) v ∥_{2} \leq 2 ε < 2 \sqrt{δ}$ , contradicting [F1]. Thus each circuit covers at most one packed ray.

2.1F1F2step 1.1algebra

Put $B = C_{k} A W^{k} \geq 2$ . By [F2], the number of descriptions of length at most $g$ is $\sum_{j = 0}^{g} B^{j} \leq B^{g + 1}$ . If these circuits approximate all packed rays, step 1.1 implies $\exp (c_{δ} D) \leq B^{g + 1}$ , so $g \geq c_{δ} D / \log B - 1$ .

3.1givenF1step 2.1algebracases∎

Since $A, k$ are fixed and $W \geq 2$ , there is a constant $K > 0$ with $\log B = \log (C_{k} A) + k \log W \leq K \log W$ . Put $X = c_{δ} D / (K \log W)$ . Step 2.1 gives $g + 1 \geq X$ . If $X \geq 2$ , then $g \geq X - 1 \geq X / 2$ . If $X < 2$ , a family with $g = 0$ has only the single zero-gate output ray, whereas the packing in [F1] contains at least two rays for $D \geq 4$ ; hence $g \geq 1 > X / 2$ . Thus $g \geq X / 2 = Ω (D / \log W)$ . If $W = poly (n)$ , then $\log W = O (\log n)$ and also $W \geq n$ , so $\log W = Θ (\log n)$ , giving $Ω (2^{n} / \log n)$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

26 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

John Preskill, Quantum Computation, Chapter 5, Classical and Quantum Circuits (standard reference, not scraped)
John Watrous, The Theory of Quantum Information (standard reference, not scraped)