§2.2, p. 3 and §2.3, p. 4 — a two-qubit state with entries in Z[i]/2^k is prepared, controlled, by O(k) H, T, CNOT gates with no further ancilla
ProvedCliffordTApprox.Ancilla.controlled_preparationThere is an absolute constant with the following property. Let and let be a unit vector of two qubits each of whose four entries has the form with . Then there is a circuit of gates from on three wires (the data qubit and the two ancillas, and no other wire) such that
where is the number of gates.
This is the exact-synthesis step of the algorithm: the circuit that prepares (Giles–Selinger's column lemma), taken controlled on the data qubit, with gates and without a third ancilla. It is what makes two ancillas suffice in total.
Formalization Note. Each gate is or on one wire or CNOT on an ordered pair of distinct wires; and , so the Clifford and T library differs from in gate counts by a constant factor only. The page writes ; the constant is quantified before and , so it does not depend on them, and the covers . Entries are Gaussian integers over , exactly as for the paper's . The page cites this step from Giles–Selinger (Lemma 20, Lemma 24) and from its reference [9] (Theorem 1).
import Mathlib import Definitions.Def_CliffordTApprox_Ancilla_Setting
namespace CliffordTApprox.Ancilla
open QAlgorithms
open QAlgorithms.Papers.Independent.Renew46.P12
/-- §2.2, p. 3 and §2.3, p. 4: every unit vector of two qubits whose entries are Gaussian
integers over `2^k` is prepared, controlled on the data qubit, by an `{H, T, CNOT}` circuit on the
three wires (data + two ancillas, no further ancilla) with `O(k)` gates; the constant `A` is
absolute. -/
theorem controlled_preparation :
∃ A : ℝ, 0 < A ∧ ∀ (k : ℕ) (v : EuclideanSpace ℂ (Qubits 2)), IsState v →
(∀ z, ∃ a b : ℤ, v z = ((a : ℂ) + (b : ℂ) * Complex.I) / (2 : ℂ) ^ k) →
∃ c : Circuit htcxGateSet (1 + 2), PreparesControlled c.unitary v ∧
(c.size : ℝ) ≤ A * ((k : ℝ) + 1) := by sorry
end CliffordTApprox.Ancilla
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.