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.

Fibonacci SU(2) compiler error, length, and bit cost

Statement

Let $G_{F i b}$ be the fixed Fibonacci SU(2) alphabet with a supplied finite base-net certificate of radius $0 < η_{0} < 64^{- 2}$ and maximum word length $L_{0}$ . For every exact target $S \in S U (2)$ and rational $0 < ε \leq η_{0}$ , let $η_{j + 1} = 64 η_{j}^{3 / 2}, J = \min {j \geq 0 : η_{j} \leq ε} .$ The ideal SK recursion returns a normalized braid word $W$ with $∥ S - W ∥_{o p} \leq ε$ and length at most $L_{0} 5^{J}$ ; hence its length is $O (\log^{\log_{3 / 2} 5} (1 / ε)) = O (\log^{3.97} (1 / ε))$ . If each real and imaginary gate coordinate is supplied by its minimal polynomial and rational isolating interval with the endpoint/root conditions of the published finite-precision theorem, the base certificate is fixed, and $S$ has a polynomial-time Cauchy name with query cost at most $(b + 1)^{c}$ , the finite implementation additionally has the bit-time bound $O ((N + s_{ε})^{c + 10})$ from the cited theorem, where $N = ⌈ \log_{2} (2 / ε) ⌉$ and $s_{ε}$ is the binary encoding length of the rational tolerance. The lifted physical braid carries $(R_{1} z^{- 1})^{k}$ and that phase is not part of the normalized error.

Facts & Assumptions

Given: The Fibonacci SU(2) gate package, its fixed certified base net, an exact target $S \in S U (2)$ and rational tolerance $0 < ε \leq η_{0}$ . For the finite bit bound also assume the algebraic coordinate descriptions and polynomial-name conditions stated above.

[F1]

The Fibonacci lifted generators form a finite inverse-closed alphabet in $S U (2)$ with algebraic entries, and the subgroup they generate is dense in $S U (2)$ . Fixed SU(2) Fibonacci braid gate alphabet

[F2]

The SU(2) SK recursion returns error at most $ε$ at the least level $J$ and length at most $L_{0} 5^{J}$ . Solovay–Kitaev Error and Resource Bound

[F3]

For algebraic gate entries and a polynomial-time Cauchy target name, the finite implementation has the stated polynomial bit-time bound. Finite-Precision Bit Complexity of the SU(2) Solovay–Kitaev Compiler

[F4]

The exact-real target and finite Cauchy-name conventions are distinct; each precision query and rational encoding cost is explicit. Certified fixed-dimensional special-unitary input

[F5]

For a braid word, the physical and normalized operators differ by the exact scalar determined by exponent sum; the extra $z^{- k}$ is recorded for the lifted alphabet. Standalone and controlled phase accounting for a fixed-sector braid

[A1]

The density premise is inherited under exactly ACω from the lifted Fibonacci density lemma. The Axiom of Countable Choice ( ${A C}_{ω}$ )

Proof

1.1A1F1F2givenalgebra

By [A1] and [F1], the alphabet satisfies the dense inverse-closed SU(2) hypothesis of the published SK estimate. Put $q_{j} = 64^{2} η_{j}$ . The recurrence gives $q_{j + 1} = q_{j}^{3 / 2}$ , so $q_{j} = (64^{2} η_{0})^{(3 / 2)^{j}} \to 0$ because $0 < 64^{2} η_{0} < 1$ . Hence a finite least $J$ with $η_{J} \leq ε$ exists; the supplied SK theorem [F2] gives the error and $L_{0} 5^{J}$ length bounds. Taking logarithms in the formula for $q_{J}$ gives $J = O (\log \log (1 / ε))$ and $5^{J} = O (\log^{\log_{3 / 2} 5} (1 / ε))$ .

2.1A1F1F3F4F5step 1.1∎

Under the extra finite-input hypotheses, [F3] applies because the lifted Fibonacci entries are algebraic by [F1] and the target is supplied through [F4]'s polynomial Cauchy interface. It gives the stated bit-time bound, including precision input and output word. [F5] supplies the exact exponent-sum phase scalar, which does not change the normalized operator error. Only ACω is inherited for density; no full AC is used.

Depends on

Used by

Dependency tree · two levels

38 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

Christopher M. Dawson and Michael A. Nielsen, The Solovay–Kitaev Algorithm (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)