ExampleConstruction: AI-adaptedVerification: 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 SK level and symbolic gate budget

Example

Take the fixed SK recurrence with $η_{0} = 2^{- 13}$ and requested tolerance $ε = 2^{- 14}$ . This is a symbolic certificate example: the finite base-net list and its maximum length $L_{0}$ are supplied compiler data, not computed here. The exact recurrence gives $J = 2$ and output length at most $25 L_{0}$ . For a finite QSD factor list of size $M > 0$ on $n \geq 1$ qubits, use a triple code with nonzero spectator space and assume ${A C}_{ω}$ as in Arbitrary-size triple-encoded projective braid approximation. Allocate each factor $δ = \min {ε / (2 M), η_{0} / 2}$ ; then the sum of the factor errors is at most $ε / 2$ , relative to the recorded product phase. The two-qubit B6 search, measurement outcomes, preparation and ancilla use, Hamiltonian evolution, and phase correction are separate ledger coordinates. The supplied base-net certificate is fixed input data counted in $L_{i n}$ ; this example does not compute it. No B6 search-length bound follows from the SK calculation.

Facts & Assumptions

Given: The SK recurrence and length estimate, the compiler cost ledger, and a finite exact QSD factor list on an admissible triple code; assume ${A C}_{ω}$ for the existence of the compiled factors.

[F1]

The error recurrence and word-length estimate are $η_{j + 1} = 64 η_{j}^{3 / 2}$ and $L_{j} \leq L_{0} 5^{j}$ . Fibonacci SU(2) compiler error, length, and bit cost

[F2]

The per-operation costs are separate coordinates; an absent bound is not zero. Anyon compiler resource ledger

[F3]

The exact QSD supplies a finite factorization into one-qubit gates and CNOTs. Exact QSD CNOT Upper Bound

[F4]

Operator error in a finite product of unitary factors is bounded by the sum of factor errors. Operator error adds under finite unitary products

[F5]

Under ${A C}_{ω}$ , every logical $n$ -qubit unitary on the triple code has a physical categorical braid approximation, with logical block error and leakage amplitude each at most any prescribed positive tolerance, relative to a recorded unit scalar. Arbitrary-size triple-encoded projective braid approximation

Verification

1.1F1givenalgebra

Compute $η_{1} = 64 (2^{- 13})^{3 / 2} = 2^{6} 2^{- 39 / 2} = 2^{- 27 / 2} > 2^{- 14}$ , while $η_{2} = 64 (2^{- 27 / 2})^{3 / 2} = 2^{6} 2^{- 81 / 4} = 2^{- 57 / 4} < 2^{- 14}$ . Therefore $J = 2$ is the least level meeting the tolerance, and [F1] gives $L_{2} \leq L_{0} 5^{2} = 25 L_{0}$ .

1.2F3F5givenalgebra

Write the QSD factors from [F3] as $G_{1}, \dots, G_{M}$ , acting on the full logical register. Let $E$ be the code isometry and $P = E E^{*}$ . For each factor, apply [F5] with tolerance $δ / 2$ to obtain a unitary braid operator $B_{j}$ and a unit scalar $ω_{j}$ . Put ${\hat{G}}_{j} = ω_{j} (G_{j} \otimes I_{s p e c t a t o r})$ . The code and leakage components of $B_{j} E - E {\hat{G}}_{j}$ each have norm at most $δ / 2$ : they are $E (E^{*} B_{j} E - {\hat{G}}_{j})$ and $(I - P) B_{j} E$ . Their sum therefore has norm at most $δ$ .

2.1F2F4step 1.1step 1.2algebra∎

The telescoping expansion underlying [F4] applies with the isometry inserted: $B_{M} \dots B_{1} E - E {\hat{G}}_{M} \dots {\hat{G}}_{1} = \sum_{j = 1}^{M} B_{M} \dots B_{j + 1} (B_{j} E - E {\hat{G}}_{j}) {\hat{G}}_{j - 1} \dots {\hat{G}}_{1} .$ Every outer factor is unitary, so step 1.2 and the triangle inequality bound its norm by $M δ$ . This also bounds logical error and leakage, since compression and orthogonal projection do not increase norm; the target product carries the recorded phase $\prod_{j} ω_{j}$ . The minimum defining $δ$ gives $M δ \leq ε / 2$ , including equality of its two candidates. By [F2], SK length, B6 search work, measurement and phase correction remain separate costs. The supplied $L_{0}$ and the numerical level calculation give no B6 length bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

45 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)
Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov, Synthesis of Quantum Logic Circuits (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)