Lemma 6: one-call controlled U when U fixes zero
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.controlled_partial_unitaryFor every , a fixed sequence over and one plain partial-unitary oracle call implements controlled whenever contains and fixes the computational zero state. It uses clean work and satisfies
On the valid controlled domain , it maps to itself and to , returning work exactly to zero on every superposition. Its range is . Every partial oracle call is defined on its incoming vector.
The sequence is chosen before the oracle, with no free controlled or inverse call.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
noncomputable section
open scoped Matrix ComplexConjugate Kronecker
namespace QAlgorithms.Papers.Independent.Intakethird100.P03
open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)
attribute [local instance] Classical.propDecidable
/-- PDF p.13, Lemma 6: one plain U call and four controlled-XOR sweeps (4n Toffolis).
U fixes zero exactly; all work is clean on the whole valid controlled subspace. The gate
list is chosen before the oracle, and every partial call is checked on its actual input. -/
theorem controlled_partial_unitary (n : ℕ) :
∃ (w : ℕ) (c : List (PartialOracleStep n ((n + 1) + w))),
c.length = 4 * n + 1 ∧ partialOracleCount c = 1 ∧
∀ (U : PartialUnitary (Qubits n)) (hzero : zeroKet n ∈ U.domain),
(U.iso ⟨zeroKet n, hzero⟩ : EuclideanSpace ℂ (Qubits n)) = zeroKet n →
∀ v : EuclideanSpace ℂ (Qubits (n + 1)), ControlledDomain U v →
ValidPartialExecution c U (cleanVector w v) ∧
act (partialOracleMatrix c U) (cleanVector w v) =
cleanVector w (act (controlledQubits U.matrix) v) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number , there exist a natural number and a list of steps on wires, chosen independently of the partial unitary and input vector, such that has exactly entries and exactly one oracle-call entry. Known entries are injectively placed arbitrary one-wire unitaries, controlled NOT gates, or three-wire gates ; a call entry injectively places the oracle wires. For every partial unitary , consisting of a complex linear isometry between subspaces of , every proof that the all-zero coordinate basis vector belongs to , and the hypothesis , the following holds for every vector whose two slices , for both Boolean values , belong to . Let be the matrix of , where is orthogonal projection onto , and extend by zero ancillas to the vector when every bit of is false, and otherwise. Executing on preserves the norm at every oracle call, and its final vector is
Here is the reverse-ordered product of the step matrices, so the list acts in its written order; embedding a local matrix along a wire injection uses its entry on the selected bits when input and output agree on every unselected wire, and uses otherwise. Norm preservation at a call means that its embedded matrix preserves the norm of the vector obtained from all preceding steps. No normalization of is assumed. The claim includes , when the list has length and that sole entry is an oracle call; it also permits .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.