Learn Before
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
Tags
Math
Related
Why the shared-measurement algorithm includes each contribution once
A worked weighted sum using shared measurements
Restricting the measurement sum to assignments with selected bits equal to one
Keeping polynomial corrections fixed while summing assignments
Splitting the constructed measurements into independent group contributions
Learn After
Learn After
Related
Why the shared-measurement algorithm includes each contribution once
A worked weighted sum using shared measurements
Restricting the measurement sum to assignments with selected bits equal to one
Keeping polynomial corrections fixed while summing assignments
Splitting the constructed measurements into independent group contributions