Lemma 4.7 — Total influence
ProvedRandomOracleUnitarySynthesis.synthesis_total_influencep2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracles
Let be a fixed circuit on qubits, with system qubits and oracle length , and let be any Boolean truth table. For the two-sided influence of Definition 4.6,
This deterministic identity controls the total influence over every oracle input; no randomness in is assumed.
Differences from the source:
- encoding: binary computational bases, Boolean truth tables, and the stated register inequalities → Fin n → Fin 2 bases, Bool-valued truth tables, and a circuit type carrying n ≤ m and m₀ ≤ m; reason: these are bijective finite encodings of exactly the source registers and functions
Preamble
import Definitions.Def_RandomOracleUnitarySynthesis_synthesis_circuit open scoped Matrix ComplexConjugate open MeasureTheory Filter Classical noncomputable section
Formal statement
namespace RandomOracleUnitarySynthesis
theorem synthesis_total_influence {n m m₀ k : ℕ}
(C : synthesis_Circuit n m m₀ k) (f : synthesis_Oracle m₀) :
(∑ x, synthesis_influence C f x) = 2 * (k : ℝ) * (2 : ℝ)^n := by sorry
end RandomOracleUnitarySynthesis
Source
Andrew Huang, Akshar Ramkumar, John Wright, STOC 2027 submission #157 (October 2026), Lemma 4.7, printed p. 18 (PDF p. 20); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/157.pdf#page=20; PDF SHA256 2f2d7fa67fe2665257ec12cb0d11d7e2a80752cdecc0484b26a311d1223c5d11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.