Abstract and §2, pp. 1–4 — every single-qubit unitary within ε by O(log(1/ε)) H, T, CNOT gates and two |0⟩ ancillas
ProvedCliffordTApprox.Ancilla.main_resultThere is an absolute constant such that for every unitary matrix and every there is a circuit of gates from on three wires, the data qubit followed by two ancillas initialized to , such that
This is the paper's main result: single-qubit unitaries are approximated to precision with Clifford and T gates using two ancillary qubits, which matches the lower bound and improves on the of the Solovay–Kitaev algorithm.
Formalization Note. The error is the Frobenius norm of the difference of two linear maps from one qubit to three qubits: it is sensitive to the global phase of and charges any amplitude left on the ancillas, and it dominates the per-state distance used on the page. "Up to two ancillary qubits" is formalized as exactly two ancilla wires (an unused one is idle). The gate set is (, ). The page's is pinned as with quantified before and ; the makes the bound meaningful for near .
import Mathlib import Definitions.Def_CliffordTApprox_Ancilla_Setting
namespace CliffordTApprox.Ancilla
open QAlgorithms
open QAlgorithms.Papers.Independent.Renew46.P12
/-- Abstract, p. 1; §2, pp. 2–4: there is an absolute constant `A` such that every single-qubit
unitary `U` is approximated to precision `ε ∈ (0, 1]` (Frobenius norm of the initialized map,
phase-sensitive, ancilla leakage charged) by an `{H, T, CNOT}` circuit on the data wire and two
ancillas initialized to `|0⟩`, with at most `A (log₂(1/ε) + 1)` gates. -/
theorem main_result :
∃ A : ℝ, 0 < A ∧ ∀ U : Matrix (Qubits 1) (Qubits 1) ℂ,
U ∈ Matrix.unitaryGroup (Qubits 1) ℂ →
∀ ε : ℝ, 0 < ε → ε ≤ 1 →
∃ c : Circuit htcxGateSet (1 + 2),
frobNorm (initializedMap c.unitary - idealMap U 2) ≤ ε ∧
(c.size : ℝ) ≤ A * (Real.log (1 / ε) / Real.log 2 + 1) := by sorry
end CliffordTApprox.Ancilla
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.