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 Continuous-Parameter State Preparation Lower Bound

Statement

Let integer $n \geq 1$ , $D = 2^{n}$ , integer workspace count $a \geq 0$ , and total width $W = n + a$ . Fix integers $k \geq 1$ and $p \geq 1$ and a countable library of gate families of arity at most $k$ , each represented by a countable atlas of $C^{\infty}$ parameter charts that are open subsets of $R^{q}$ with integer $q$ satisfying $0 \leq q \leq p$ . For a nonnegative integer gate budget $g$ , each circuit topology selects at most $g$ such gates and wire placements; its gate matrices depend smoothly on their parameters. For each fixed topology and parameter-chart tuple, its denotation is the ordered product of the corresponding fixed local gate embeddings, with each embedding acting on its assigned ordered tensor factors and as the identity on the remaining wires, as specified by Denotational semantics of a finite layered circuit. Circuits act on the fixed input $∣ 0^{n} ⟩ ∣ 0^{a} ⟩$ and exactly prepare a target unit data vector with declared workspace output $λ ∣ ψ ⟩ ∣ 0^{a} ⟩$ for a unit scalar $λ$ . In every standard chart of ${C P}^{D - 1}$ , the exactly preparable rays obtainable with at most $g$ gates form a null set whenever $p g < 2 D - 2$ . Thus they cannot cover all rays. For fixed $p$ , in each standard chart all rays outside a null coordinate subset require at least $⌈ (2 D - 2) / p ⌉$ gates. Thus almost every target in chart coordinates has exact preparation cost $Ω (D)$ .

Facts & Assumptions

Given: $D \geq 2$ , fixed finite width $W$ , a fixed countable gate-family library and countable smooth parameter atlases as in the Statement, with each family using at most $p$ real parameters per gate. The considered circuits have exact clean-workspace output.

[F1]

The standard projective patches have smooth coordinates in $R^{2 D - 2}$ (QC24 Projective Chart Dimension).

[F2]

If $f : U \subseteq R^{q} \to R^{m}$ is $C^{r}$ with $r > \max {q - m, 0}$ , its critical value set is null (Morse-Sard for Euclidean maps).

[F3]

A countable union of compact null subsets of Euclidean space is null; the proof selects finite rational-cube covers by their least codes without choice (Countable Union of Compact Null Sets Is Null).

[F4]

A continuous image of a compact space is compact (A continuous image of a compact space is compact; a continuous real-valued map on a nonempty compact space attains a maximum and a minimum; and a continuous bijection from a compact space to a Hausdorff space is a homeomorphism).

[F5]

A nonempty Euclidean open set is not null in the closed-cube-cover sense (A Nonempty Euclidean Open Set Is Not Null).

[F6]

Projecting the circuit output onto the all-zero workspace branch yields the data vector used for its projective chart coordinates (QC24 Clean Ancilla Output Projection).

[F7]

Nullity in the closed-cube-cover definition passes to subsets (Measure zero and content zero in $R^{m}$ by countable and finite cube covers).

[F8]

A tensor map acts factorwise on elementary tensors, and the fixed register order determines each local gate embedding (Tensor products of finitely many linear maps).

[F9]

A finite circuit denotes the ordered product of its local gate embeddings in chronological layer order (Denotational semantics of a finite layered circuit).

[F10]

Rational numbers are countable and dense in the reals, so for each integer $q \geq 1$ rational open cubes form a countable basis for $R^{q}$ , and every open subset is covered by countably many rational closed cubes contained in it ( $Q$ is countably infinite, The rationals embed densely in the reals).

[F11]

There is a fixed pairing bijection $π : N^{2} \to N$ ( $N \times N \approx N$ ). For a tuple $(a_{0}, \dots, a_{r - 1})$ , set $c_{0} = 0$ and $c_{j + 1} = π (a_{j}, c_{j})$ for $j < r$ , then encode the tuple as $π (r, c_{r})$ . Injectivity of $π$ makes this an injection of all finite tuples into $N$ .

[F12]

A singleton in $R^{m}$ , $m \geq 1$ , is compact and null: every open cover has a one-set subcover, and the singleton itself is a degenerate closed cube of zero volume (Measure zero and content zero in $R^{m}$ by countable and finite cube covers).

[F13]

Every closed cube in $R^{q}$ , $q \geq 1$ , is compact by Heine–Borel (Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line).

Proof

Given: As in Facts & Assumptions.

1.1givenF1F6F8F9construct

Fix one gate topology, one choice of its gate-family parameter charts, and one standard target patch $U_{j}$ from [F1]. The product $Ω$ of the finitely many selected open parameter charts is open in $R^{q}$ . By [F8] and [F9], each local embedding has matrix entries that are fixed finite linear combinations of the local gate entries, and the circuit matrix is a finite ordered product of those embeddings. Its entries are therefore finite sums of products of smooth gate-matrix entries. The projected data vector $v (θ)$ from [F6] depends smoothly on $θ \in Ω$ . The set $Ω_{j} = {θ \in Ω : v_{j} (θ) \neq 0}$ is open. Under the fixed real/imaginary identification $C^{D - 1} ≅ R^{2 D - 2}$ , the chart map $f_{j} (θ) = (v_{i} (θ) / v_{j} (θ))_{i \neq j}$ is $C^{\infty}$ on $Ω_{j}$ .

2.1givenF2step 1.1algebra

The parameter dimension $q$ is at most $p g < 2 D - 2$ , so the derivative of $f_{j}$ has rank at most $q$ at every point; every point is critical. With target dimension $m = 2 D - 2$ and $r = 1$ , the hypothesis $r > \max {q - m, 0} = 0$ holds, and [F2] makes $f_{j} (Ω_{j})$ null.

3.1F3F4F7F10F11F12F13step 1.1step 2.1construct

The gate-family choices and parameter charts are countable, and at fixed $W, g$ there are finitely many wire placements. By [F11], finite tuples of their natural codes, with their tuple length, form a countable set. For a fixed tuple, if its parameter dimension is $q = 0$ , then $Ω_{j}$ is empty or a singleton, whose image is compact null by [F12]; these images are indexed by the countable topology/chart-tuple codes. If $q \geq 1$ , rational coordinates are coded by [F11], and [F10] gives a countable cover of the open set $Ω_{j}$ by rational closed cubes whose closures lie in $Ω_{j}$ . By [F13], each such cube is compact, so its image is compact by [F4] and null as a subset of the Sard-null image in step 2.1 by [F7]. Pairing each topology/chart-tuple code with each rational-cube code by [F11] makes this part of the entire family countable as well. Together with the $q = 0$ singleton images, these form a countable family of compact null sets. Applying [F3] to this family shows that all exactly preparable rays in the patch have a null coordinate image.

4.1F1F5step 3.1contradiction

If every ray were exactly preparable with $g$ gates, then the coordinate image of all rays in the chosen standard patch would be $R^{2 D - 2}$ and hence would contain a nonempty open cube. Step 3.1 makes that image null, while [F5] says a nonempty open cube is not null. This contradiction proves the noncoverage claim for each patch.

5.1givenstep 3.1algebra∎

Set $g_{0} = ⌈ (2 D - 2) / p ⌉ - 1$ . Then $p g_{0} < 2 D - 2$ , so steps 1.1–2.1 with budget $g_{0}$ show that the targets exactly preparable with at most $g_{0}$ gates form a null set in each chart. Every target outside this null coordinate subset therefore requires at least $g_{0} + 1 = ⌈ (2 D - 2) / p ⌉$ gates. For fixed $p$ , this is $Ω (D)$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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