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

The exact single-qubit compiler returns the input matrix

Statement

For every unitary $U \in M_{2} (D)$ , the procedure in Exact single-qubit Clifford+T synthesis terminates and returns a finite one-qubit Clifford+T word whose exact matrix is $U$ .

Facts & Assumptions

Given: A unitary $U \in M_{2} (D)$ , exact rational coefficient arithmetic, the descent procedure, and the finite base-column certificate.

[F1]

Exact single-qubit Clifford+T synthesis: the procedure tests unitarity, repeatedly applies $M \leftarrow H T^{- k} M$ for a $k$ lowering the squared-entry denominator exponent, looks up a base-column word $W_{0}$ , and returns the matrix factorization determined by the recorded $k$ values and $W_{0} T^{j}$ .

[F2]

Clifford+T denominator descent and finite base table: each normalized $D$ -column above exponent $3$ has a reducing $k \in {0, 1, 2, 3}$ , and the certificate supplies an exact H/T preparation word for every normalized column in the base regime.

[F3]

Unit-modulus elements of the dyadic cyclotomic ring: if $λ \in D$ and $λ \overset{ˉ}{λ} = 1$ , then $λ = ω^{j}$ for some $j \in {0, \dots, 7}$ .

[F4]

Smallest square root of two denominator exponent: the squared-entry statistic is $sde (∣ M_{00} ∣^{2})$ , with $sde (0) = - \infty$ .

[F5]

Clifford+T gate library and exact matrices: $H, T, T^{†}$ have the displayed exact matrices, and the matrix of a chronological word is the product with later gates on the left.

[F6]

Denotational semantics of a finite layered circuit: for chronological layers $L_{1}, \dots, L_{d}$ , the circuit matrix is $U_{L_{d}} \dots U_{L_{1}}$ .

[F7]

Reduced Hadamard words and their exact denominators: the final reduction preserves exact matrix equality, retaining its scalar phase.

Proof

1.1F1F5givenalgebra

Initially $U = I \cdot M$ with $M = U$ . If a loop iteration records $k$ and sets $M^{'} = H T^{- k} M$ , then $M = T^{k} H M^{'}$ . Therefore, after $r$ reductions, the recorded sequence $K = (k_{1}, \dots, k_{r})$ satisfies $U = (T^{k_{1}} H) \dots (T^{k_{r}} H) M$ .

2.1F2F4F5step 1.1algebra

At every iteration, $M$ remains unitary with entries in $D$ , since the matrices in [F5] are unitary over $D$ . If its exponent exceeds $3$ , [F2] ensures that the finite search over $k = 0, 1, 2, 3$ finds a value reducing that integer exponent by exactly one. Thus the loop terminates after finitely many iterations with exponent at most $3$ .

3.1F1F2F3step 2.1algebra

Let $W_{0}$ be the table word for the first column of the terminal $M$ . Then $W_{0}^{*} M$ is unitary with first column $(1, 0)^{T}$ , hence is $diag (1, λ)$ for a unit scalar $λ$ . Its entries lie in $D$ , so [F3] gives $λ = ω^{j}$ for some $j \in {0, \dots, 7}$ . Consequently $M = W_{0} T^{j}$ .

4.1F1F6F7step 1.1step 3.1algebra∎

Substituting this identity into step 1.1 yields exactly the matrix factorization returned in [F1]. The algorithm emits its factors from right to left as a chronological gate list; [F6] says later gates multiply on the left, so that list has the displayed matrix. The final reduction preserves this matrix by [F7], including its scalar factor. Hence the returned word implements $U$ exactly.

Unresolved supplier checks

The actual QC07 gate matrices and QC09 chronological circuit semantics were inspected. The emitted factor order agrees with the supplier convention. The local exact synthesis proof and finite table are complete; this records interface reconciliation, not independent acceptance of QC07/QC09 drafts.

Depends on

Used by

The Rz approximation procedure is correct when it returns Theorem

Dependency tree · two levels

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