§IV, unnumbered: logarithmic quantum preparation lower bound
OpenQAlgorithms.Papers.Independent.Intakenext100.P61.harmonic_quantum_costFix and put . Let , where . There are and , chosen before , the finite EPR supply and the protocol, such that every deterministic quantum protocol preparing with squared fidelity at least satisfies
The constants may depend on the fixed error. The leading coefficient is positive in the smaller regime .
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P61
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P61
open scoped Matrix ComplexConjugate
open QAlgorithms.Papers.Independent.Information100.P63 (logTwo)
open QAlgorithms.Papers.Independent.Dependency50.P35 (supportRank)
open QAlgorithms.Papers.Independent.Bridge50.P40 (entropyInfinity)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
attribute [local instance] Classical.propDecidable
/-- PDF p.8, unnumbered quantum preparation bound: for each fixed epsilon,
the O(log log n) constant and threshold are uniform over every EPR supply and
protocol. The leading coefficient is positive when delta<1/2. -/
theorem harmonic_quantum_cost (epsilon : ℝ) (hzero : 0 ≤ epsilon) (hsmall : epsilon < 1 / 4) :
∃ K : ℝ, 0 < K ∧ ∃ N : ℕ, 4 ≤ N ∧ ∀ n ≥ N, ∀ (k : ℕ) (cost : ℝ),
QuantumPrepares (eprPairs k) (harmonicState n) epsilon cost →
(1 / 2 - smoothingError epsilon) * logTwo n - K * logTwo (logTwo n) ≤ cost := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P61
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every real satisfying , there exist a real and a natural number such that, for every natural number , every natural number (including ), and every real cost , the following holds. Let
Suppose there is an output matrix on obtainable from by the following finite execution rules: identity and local maps , with , cost zero; transferring a register of any positive integer dimension from either party to the other costs ; and sequential executions have their costs added. Finite registers are identified with enumerated coordinate registers, and the execution must have exactly the reported cost . Suppose also that
where matrix square roots are given by continuous functional calculus and has entries . Then
Here ; the hypothesis includes , and it does not require the coefficient to be positive.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.