Concept icon
Concept

When the shared-measurement enumeration can be small

Let n be the number of Boolean variables and c the number of measurement rows. Assume every measurement is an integer in [-B,B], with integer B>=0. A sufficient condition is that each row has integer coefficients whose absolute values sum to at most B; bounding each coefficient separately is not enough. There are at most (2B+1)^c candidate tuples. At each tuple, two scans examine at most 2 times the sum of 2^(group size) local assignments. Thus at most 2*(2B+1)^c*[sum over groups of 2^(group size)] local vectors are examined. This is not total runtime: measurement calculation, factor evaluation and exact arithmetic must also be counted. Small groups alone do not ensure a speedup. One row with coefficients 1,2,4,... distinguishes all assignments but has exponentially large B.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math