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 Width Topology Count

Statement

Fix integers $W \geq 1$ , $A \geq 1$ , $k \geq 1$ , and $g \geq 0$ , and an ordered-wire circuit model with a finite gate alphabet of size $A$ and maximum arity $k$ . A serial length- $g$ description is an ordered list of $g$ gate labels and ordered tuples of at most $k$ distinct wire positions; its denotation is the ordered product of the corresponding local gate embeddings. Each parallel layer consists of pairwise wire-disjoint occurrences and denotes their product. With $C_{k} = k + 1$ , the number of length- $g$ serial descriptions is at most $(C_{k} A W^{k})^{g}$ . Any parallel circuit with $g$ total occurrences has a serial ordering with the same gate count and denotation.

Facts & Assumptions

Given: The finite alphabet, maximum arity, ordered wire positions and width specified in the Statement.

[F1]

Ordered tensor registers, their inner product, and wire permutations fixes the ordered tensor factors, product basis and wire permutations.

[F2]

A tensor map acts factorwise on elementary tensors, so an operator embedded on selected factors and an operator on disjoint factors commute (Tensor products of finitely many linear maps).

[F3]

A circuit layer denotes the ordered product of its local gate embeddings; its layers are applied chronologically (Denotational semantics of a finite layered circuit).

Proof

Given: As in Facts & Assumptions.

1.1givenalgebra

A gate of arity $r \leq k$ has at most $W^{r}$ ordered wire tuples. Summing over possible arities $0 \leq r \leq k$ gives at most $\sum_{r = 0}^{k} W^{r} \leq (k + 1) W^{k}$ tuples because $W \geq 1$ ; including its label gives at most $C_{k} A W^{k}$ choices for one occurrence.

2.1givenF1F2F3step 1.1algebra∎

A length- $g$ serial description is an ordered list of $g$ such choices, so there are at most $(C_{k} A W^{k})^{g}$ descriptions. For two gates on disjoint supports, reorder the tensor factors as the first support, the second support, and the remaining wires. Their embeddings are then $G \otimes I \otimes I$ and $I \otimes H \otimes I$ . By [F2], both compositions act as $G x \otimes H y \otimes z$ on elementary tensors, which span the register; thus they commute. By [F3], serially listing each layer therefore preserves its operator; listing the layers in circuit order preserves the full denotation and adds no occurrence.

Depends on

Used by

Dependency tree · two levels

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