LemmaStatement: AI-adaptedProof: 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.

Clifford+T circuit entries lie in the dyadic cyclotomic ring

Statement

Every finite circuit on $n$ ordered wires using only the matrices in Clifford+T gate library and exact matrices has all matrix entries in $D$ .

Facts & Assumptions

Given: $n \geq 1$ , chronological gate order, and the exact matrices in the gate-library definition.

[F1]

Dyadic cyclotomic ring for Clifford+T synthesis: $D = Z [ω, 1 / 2]$ is a subring of $C$ and contains $ω$ and $1 / 2$ .

[F2]

Clifford+T gate library and exact matrices: $H$ has entries $\pm 1 / \sqrt{2}$ , $T, T^{†}, S, Z$ have entries in ${0} \cup {ω^{j} : j \in Z}$ , and CNOT is a computational-basis permutation matrix.

[F3]

A local gate has a unique global wire embedding: each gate occurrence acts on its named ordered wires and as identity on the complementary wires.

[F4]

Denotational semantics of a finite layered circuit: a circuit matrix is the finite product of its layer matrices, with later chronological layers multiplying on the left.

Proof

1.1F1F2F3givenalgebra

Since $1 / \sqrt{2} = \sqrt{2} / 2 = (ω - ω^{3}) / 2 \in D$ , every entry of $H$ lies in $D$ . The displayed diagonal gates have entries $0$ or powers of $ω$ , the scalar Clifford phases have entries powers of $ω$ , and the displayed CNOT has entries $0$ or $1$ , so each primitive gate matrix has entries in $D$ by [F1] and [F2]. The embeddings in [F3] are obtained from tensoring with identity matrices and permuting factors; these operations only insert zeros and copy entries, hence preserve membership in $D$ .

2.1F1F4step 1.1algebra∎

The product of two matrices with entries in a subring has entries that are finite sums of products in that subring. By the finite product interpretation [F4], induction on the circuit's finite gate list therefore places every entry of its matrix in $D$ ; the empty word is the identity matrix and also has entries in $D$ .

Unresolved supplier checks

The actual QC07 matrices and the QC09 syntax, local-wire-embedding, and denotational-semantics bodies were inspected. Their ordered-factor and chronological-product conventions match the local closure argument. This is interface reconciliation only, not acceptance of the supplier drafts.

Depends on

Used by

Dependency tree · two levels

20 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

Kliuchnikov, Maslov, and Mosca, Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates (standard reference, not scraped)
de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)