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.

QC24 Finite Alphabet Exact Nonuniversality

Statement

Fix integers $n \geq 1$ , $A \geq 0$ , $k \geq 1$ , and $W \geq n$ , with $D = 2^{n}$ , a gate alphabet of size $A$ and maximum arity $k$ . Each circuit starts on $∣ 0^{n} ⟩ ∣ 0^{W - n} ⟩$ and is counted as an exact state-preparation circuit only when its unconditional output is $λ ∣ ψ ⟩ ∣ 0^{W - n} ⟩$ for a unit scalar $λ$ and a unit data vector $ψ \in C^{D}$ . The set of data rays exactly reachable by finite circuits is countable, so it is not the full ray space.

Facts & Assumptions

Given: A finite gate alphabet of size $A \geq 0$ and maximum arity $k \geq 1$ , fixed finite width $W \geq n$ , $n \geq 1$ , and the stated clean-workspace output convention.

[F1]

If $A \geq 1$ , at fixed width and finite alphabet there are finitely many circuit descriptions of each length (QC24 Finite Width Topology Count).

[F2]

The real numbers are uncountable, so an injective copy of $R$ in the ray space witnesses its uncountability ( $R$ is uncountable (Cantor's nested intervals, 1874)).

[F3]

Pure-state rays identify nonzero vectors exactly up to nonzero scalar multiplication (Pure state and ray).

[F4]

A fixed bijection $π : N^{2} \to N$ codes a pair of natural numbers as one natural ( $N \times N \approx N$ ).

Proof

Given: As in Facts & Assumptions.

1.1givenF1F4constructcases

If $A = 0$ , the empty alphabet allows only the empty circuit, so at most one ray is reachable. If $A \geq 1$ , put $B = (k + 1) A W^{k} \geq 2$ . Fix a finite listing of the alphabet and order wire tuples lexicographically; then [F1] gives at most $B^{g}$ descriptions of length $g \in N$ . Code each description by its length and its base- $B$ index, then apply the fixed pairing bijection of [F4] to these two natural numbers; this gives an injection of all finite descriptions into $N$ . In either case the reachable rays form a countable set without a choice principle.

2.1givenF2F3step 1.1algebra∎

The map $t \mapsto [e_{0} + t e_{1}]$ from $R$ into the rays of $C^{D}$ is injective: if $e_{0} + t e_{1} = λ (e_{0} + s e_{1})$ , comparison of the $e_{0}$ coordinate gives $λ = 1$ , then comparison of the $e_{1}$ coordinate gives $t = s$ . These nonzero vectors define rays by [F3]. By [F2], the ray space is uncountable and cannot equal the countable reachable set.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

56 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)
Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov, Synthesis of Quantum Logic Circuits (standard reference, not scraped)