Concept icon
Concept

Counting the exceptional measurement directions

At one position, a fraction p=(r-1)/(2r) of the r^2 basis choices are negative. Choosing a product-basis vector uniformly makes the number j of negative choices binomial with Q trials and probability p: choices at different positions are independent. Thus C has exactly D times Pr[j outside I_set] rows when every outside direction is retained. The choice is used for counting; C itself is deterministic. For r=2,Q=3,I_set={0,1}, D=64 and each position has three positive choices and one negative choice. There are 3 choices of which position is positive when j=2, with 3 positive vectors there, giving 9 directions; j=3 gives 1, giving 10 rows. This small example proves no asymptotic speedup. Making the fraction very small while keeping R<Q requires a suitable interval and a tail bound.

0

1

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math