DefinitionDefinition: AI-adaptedProof: Not applicablePipeline-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 gate library and exact matrices

Definition

Let $ω = e^{i π / 4}$ . The one-qubit generators and exact matrices in the ordered computational basis are

$H = \frac{1}{\sqrt{2}} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}), T = (\begin{array}{cc} 1 & 0 \\ 0 & ω \end{array}), T^{†} = (\begin{array}{cc} 1 & 0 \\ 0 & ω^{- 1} \end{array}) .$

On basis vectors, $H ∣ q ⟩ = (∣ 0 ⟩ + (- 1)^{q} ∣ 1 ⟩) / \sqrt{2}$ and $T^{k} ∣ q ⟩ = ω^{k q} ∣ q ⟩$ for $q \in {0, 1}$ .

Write $S = T^{2} = diag (1, i)$ and $Z = T^{4} = diag (1, - 1)$ . Pauli $X, Y, Z$ are as in The Pauli matrices. On two ordered wires, $CNOT ∣ a, b ⟩ = ∣ a, b \oplus a ⟩$ ; the first wire is control and the second target. A circuit is a finite chronological word of these gates at stated wire positions; its matrix is the product with later gates on the left. No extra wire or controlled- $T$ operation is implicit.

The scalar phase $ω I$ is an allowed Clifford phase in the one-qubit matrix-word convention. Its scalar factor is retained in exact matrix products; the convention that an overall scalar does not affect a resource count is stated separately from matrix equality. It does not grant a controlled- $T$ operation or allow a scalar on a target wire to be discarded under control.

The exact one-qubit H/T algebra is generated by $H, T, T^{†}$ ; $S$ and $Z$ are aliases for the displayed powers. The distinction between exact matrix equality and global-phase equivalence is maintained. Resource costs are supplied by Finite circuit resource accounting and remain separate from this matrix definition.

Unresolved supplier checks

The actual QC07 Pauli/gate bodies and QC08 controlled-unitary body were inspected; their displayed matrices and control-first phase convention agree with this definition. The actual QC09 resource-vector body was inspected: it defines size, depth, width, and separately declared weighted/query costs. Scalar phase remains a matrix-word convention and is not an extra QC09 gate call. The actual QC07/08 gate interfaces and QC09 resource interface agree; this is reconciliation, not acceptance of their draft content.

Depends on

Used by

Ancilla-free Clifford+T Rz approximation Algorithm
Basic Clifford T Rewrite Algorithm
Bounded-error repetition amplification Algorithm
Controlled T using a clean ancilla Algorithm
Exact single-qubit Clifford+T synthesis Algorithm
Simon promise decision by sampled rank Algorithm
Ancilla-free Rz approximation problem and T-count Definition
Circuit Optimization Task Definition
EQP on promise problems in the QC14 model Definition
Full-list uniform quantum circuit family Definition
ZQP on promise problems with bounded failure Definition
A one-query exact algorithm on a two-point OR promise Example
Exact T period and a non-exact Rz phase Example
Promise, query and cost-model examples Example
Acceptance is invariant under an unconditional global phase Lemma
Boolean circuits compile exactly into the QC14 gate alphabet Lemma
Clifford+T circuit entries lie in the dyadic cyclotomic ring Lemma
Clifford+T denominator descent and finite base table Lemma
Determinant-one Clifford+T words are dense in SU(2) Lemma
Determinant-one reduction for optimal Rz approximation Lemma
Determinants of one-qubit Clifford+T words are eighth roots Lemma
Every Rz epsilon region contains an exact norm-solvable grid point Lemma
Reduced Hadamard words and their exact denominators Lemma
Clean ancilla controlled T circuit is exact Proposition
BQP to PP and PSPACE proof obligations in the exact QC14 basis Remark
Basic Rewrite Correct And Terminating Theorem
Bounded-error repetition amplification is correct and uniform Theorem
BQTISP to Derived-Basis PrTISP Simulation Theorem
H-count and T-count optimality of exact Clifford+T synthesis Theorem
PromiseP is contained in PromiseBPP and PromiseBPP in BQP Theorem
Simon rank test correctness and linear query cost Theorem
The exact single-qubit compiler returns the input matrix Theorem
The Rz approximation procedure is correct when it returns Theorem
Two-phase reduction for Clifford+T Rz synthesis up to phase Theorem
Two-qubit determinant obstruction to controlled T Theorem

Dependency tree · two levels

18 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, Practical approximation of single-qubit unitaries by single-qubit quantum circuits (standard reference, not scraped)
de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)