Theorem 2: reversible computation of an observable function
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.observable_function_reversibleLet be finite orthogonal subspace families, let , and let a unitary compute with error at most on every normalized vector in each input subspace (embedded with initial work zero). Let be a measurement operator for , and define . Extend by identity on its support complement and extend by identity on its extra register. Then, on the full input support tensored with that extra register,
This is a phase-sensitive operator bound uniform over all coherent label combinations and entangled extra-register states. Neither family need be complete and need not be injective.
It quantifies the approximate cleanup achieved by compute, control and uncompute.
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 pp.20–21, Theorem 2: compute, apply a measurement-controlled operator, uncompute.
Omega is already embedded in the full computer memory with clean initial work; the bound
holds on its entire support tensor D, including entangled states and coherent label mixtures.
No completeness or injectivity of the observable function is assumed. -/
theorem observable_function_reversible {I : Type*} [Fintype I] [DecidableEq I]
(r s d : ℕ) (O : OrthogonalProjectorFamily I r) (Theta : OrthogonalProjectorFamily I s) (F : Fin r → Fin s)
(U : Matrix I I ℂ) (hU : U ∈ Matrix.unitaryGroup I ℂ)
(V : Fin s → Matrix (Qubits d) (Qubits d) ℂ)
(hV : ∀ v, V v ∈ Matrix.unitaryGroup (Qubits d) ℂ)
(epsilon : ℝ) (he : 0 ≤ epsilon)
(hcomputes : ∀ (v : Fin r) (x : EuclideanSpace ℂ I), IsState x → act (O.proj v) x = x →
1 - epsilon ≤ subspaceProbability (pureDensity (act U x)) (Theta.proj (F v))) :
∀ x : EuclideanSpace ℂ (I × Qubits d),
act (O.support ⊗ₖ (1 : Matrix (Qubits d) (Qubits d) ℂ)) x = x →
‖act ((Uᴴ ⊗ₖ (1 : Matrix (Qubits d) (Qubits d) ℂ)) * measurementMatrix Theta V *
(U ⊗ₖ (1 : Matrix (Qubits d) (Qubits d) ℂ))) x -
act (measurementMatrix O (fun v => V (F v))) x‖ ≤
2 * Real.sqrt ((r : ℝ) * epsilon) * ‖x‖ := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a finite index type with decidable equality, let , and put . Let and be two families of complex matrices on , each consisting of Hermitian idempotents whose products at distinct indices are zero. Let , let be a unitary matrix on , and let be unitary matrices on . Suppose satisfies , and suppose that for every and every with and ,
Set , ,
Then every vector satisfying obeys
Neither projector family is required to sum to the identity, and the concluding vector need not be normalized. For a zero projector , its norm-one test-vector hypothesis is impossible and the corresponding assumption is vacuous. Zero values of the natural-number parameters are included; if , the support condition forces , while existence of with forces .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.