Section V A, Eqs.(19)–(20): worst-case function-computation error bounds
ProvedQAlgorithms.Papers.Independent.Advance50.P17.worstFunctionErrorLet be fixed CPTP maps on a positive finite-dimensional register with computational basis indexed by , and let be the desired basis outcome. For , put . With the input-sized-ancilla maximum of half trace norm, the corresponding minimum squared fidelity, and , both bounds hold:
These give worst-case operational error guarantees for a fixed real and ideal computation.
import Definitions.Def_QAlgorithms_Papers_Independent_Advance50_P17
noncomputable section
open MeasureTheory Filter
open scoped Matrix ComplexConjugate Topology
namespace QAlgorithms.Papers.Independent.Advance50.P17
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
open QAlgorithms.Papers.Independent.Information100.P08 (canonicalPurification)
open QAlgorithms.Papers.Independent.Information100.P75 (hermitianReal)
variable {I J K : Type} [Fintype I] [Fintype J] [Fintype K]
[DecidableEq I] [DecidableEq J] [DecidableEq K]
[Nonempty I] [Nonempty J] [Nonempty K]
/-- Section V A, PDF p.9, Eqs.(19)--(20), Appendix B1, p.13: BOTH worst-case
function-computation guarantees, using actual uniform worst-case ideal error. -/
theorem worstFunctionError (E F : FiniteProcess I I) (f : I → I) :
worstFunctionErrorProbability E.val f ≤ worstFunctionErrorProbability F.val f + stabDistance (stateDistance .trace) E.val F.val ∧
worstFunctionErrorProbability E.val f ≤ (Real.sqrt (worstFunctionErrorProbability F.val f) + stabC E.val F.val) ^ 2 := by sorry
end QAlgorithms.Papers.Independent.Advance50.P17
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a finite nonempty index type with decidable equality, let be channels on its complex matrices, and let be any function. A channel admits a finite representation with . For the standard basis vector , define
Write , let identity extension apply a channel to each reference-indexed matrix block, and define
where , , and square roots use matrix functional calculus. Then both bounds hold:
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.