§4.1, p.27 —
ProvedPelagicFF.quantum_amplitudescommunication-complexityfourier-analysisp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let , and . Applying the diagonal unitary and then to the phase state gives
So Bob's measurement in the computational basis outputs with probability ; with the mass bound of §4.1 this is the -qubit protocol of Theorem 4.2.
Formalization Note The identity is stated coordinatewise, for the amplitude of each basis vector , as a complex number.
Differences from the source:
- encoding: Boolean functions with values in {−1,1} → Bool-valued functions read through OAI.Cotype.sign (false ↦ 1, true ↦ −1); reason: a bijection of value sets; same instances
- encoding: states and operators in Dirac notation → amplitude vectors (Fin n → Bool) → ℂ and matrices; H^{⊗n} by its entries 2^{−n/2}(−1)^{x·y}; reason: the computational-basis representation; same vectors
Preamble
import Mathlib import Definitions.Def_PelagicFF_PFF import Definitions.Def_PelagicFF_hadamardN open OAI.Cotype
Formal statement
namespace PelagicFF
/-- **Bob's output amplitudes (§4.1, p.27).** Applying `U_g` and then `H^{⊗n}` to the phase state
`|ψ_f⟩` gives `∑_y ĥ(y)|y⟩` with `h = f·g`: the amplitude of `|y⟩` is the Fourier coefficient
`ĥ(y)`.
arXiv:2610.05585 (held version, sha256 4564aef3…), §4.1, p.27: "|ψ_f⟩ = (1/√N) ∑ₓ f(x)|x⟩ ↦(U_g)
(1/√N) ∑ₓ f(x)g(x)|x⟩ ↦(H^{⊗n}) (1/N) ∑_y ∑ₓ f(x)g(x)(−1)^{x·y}|y⟩ = ∑_y ĥ(y)|y⟩".
**Formalization Note.** States are amplitude vectors indexed by `Fin n → Bool`; `Matrix.mulVec` is the
matrix–vector product. -/
theorem quantum_amplitudes (n : ℕ) (f g : BoolFn n) (y : Fin n → Bool) :
(hadamardN n).mulVec ((signDiag g).mulVec (phaseState f)) y =
((OAI.Cotype.fourier (fun x => sign (f x) * sign (g x)) y : ℝ) : ℂ) := by sorry
end PelagicFF
Source
Anselm, Ding, Gilboa, Grewal, Optimal and Verifiable Quantum Advantages in Communication Complexity, arXiv:2610.05585 (held version, sha256 4564aef3…), §4.1, p.27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.