Concept icon
Concept

Recovering a local expansion from fixed substitutions and restricted sums

For each E with |E|<=q and each subset U of E, fix X=1_U and use the measurement algorithm to sum G_x(1_U,z) only over x with x_i=1 for i in E. Store only powers below J=q+1. Multiply this restricted sum by (-1)^(|E|-|U|) and add all results. To see why, apply the alternating-evaluation formula to each p_x(X)=[z^j]G_x(X,z). After Boolean reduction, p_x(x) is the sum of c_{x,E} times the product of x_i in E. That product selects exactly the restricted assignments. Thus the combined result is H(t+z) modulo z^J. X is fixed before enumeration; no full multivariable expansion is stored.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math