§5.2, unnumbered: controlled X,H,T with one ancilla
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.controlledGates_oneAncillaLet be a number of positive controls and let . Let apply to its target precisely when every control is , and otherwise act as the identity. There is an elementary Clifford+T circuit on wires such that, for every input vector on the data wires,
The helper is trailing and returns exactly to zero. With , the controlled operation is simply . These implementations establish the one-ancilla sufficiency step.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P85
open scoped Classical BigOperators
open QAlgorithms
open QAlgorithms.Papers.Independent.Gap48.P10
(InZomega InDomega Residue bits residue residueMultiply Reducible)
open QAlgorithms.Papers.Independent.Support21.P13
(synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)
local notation "omega" => QAlgorithms.gateT true true
local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)
/-- Section 5.2, PDF p.5: all positive multiply-controlled X,H,T gates use one clean helper. -/
theorem controlledGates_oneAncilla :
∀ r : ℕ, ∀ M ∈ ({pauliX, hadamard, gateT} : Set (Matrix Bool Bool ℂ)),
∃ c : Circuit gateSet ((r + 1) + 1),
ImplementsWithCleanAncillas c.unitary (multiplyControlled r M) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P85
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let . For every natural number and every matrix
there exists a finite circuit on wires using , , , CNOT, and the zero-wire scalar gate , such that
Here is the set of length- Boolean strings; the last wire is the appended wire; is the reverse-ordered product of the gate matrices embedded on injectively assigned wires, with all unassigned bits preserved; and CNOT sends to . The matrix preserves the first bits and applies to the last bit precisely when all first input bits are true, applying the identity to that bit otherwise. The zero-wire gate embeds as . The equality is required for every vector , without a normalization assumption. When , the condition on the controls is vacuous and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.