Section II, (29), p. 7 — hypercontractivity: E_z|c|^{k+2} ≤ (k+1)^{k+2}(E_z c²)^{(k+2)/2} for degree-2 c
ProvedQAOAE3Lin2.General.eq_29boolean-functionshypercontractivitymax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be uniform in and let
be any real polynomial of degree at most . Then for every natural number ,
This is the hypercontractive (Bonami) inequality for degree and , cited by the paper as Theorem 5 of Dinur–Friedgut–Kindler–O'Donnell. It controls high moments of the clause arguments by their second moments.
Formalization Note. Every function on of degree at most has the multilinear form above, since . The inequality is stated for every , not only the odd the paper uses. is written as .
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_29 (n k : ℕ) (a₀ : ℝ) (a₁ : Fin n → ℝ) (a₂ : Fin n → Fin n → ℝ) :
let c : QAlgorithms.Qubits n → ℝ := fun x =>
a₀ + ∑ v, a₁ v * spin x v +
∑ u, ∑ v, (if u < v then a₂ u v * spin x u * spin x v else 0)
avgZ (fun x => |c x| ^ (k + 2)) ≤
((k : ℝ) + 1) ^ (k + 2) * Real.sqrt (avgZ (fun x => c x ^ 2)) ^ (k + 2) := by sorry
end QAOAE3Lin2.General
Source
Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, arXiv:1412.6062v2, p. 7, Section II, (29) (citing Dinur, Friedgut, Kindler, O'Donnell, Theorem 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.