Suppose we have |ϕ⟩=∑y∈{0,1}nβy|y⟩ such that βy=0 if s⋅y=1mod2 and βy=12(n−1)/2 if s⋅y=0mod2, where s is some hidden n-bit string. Assume that s is not the all-zero string 00⋯0.
(a) If we run Fourier sampling on |ϕ⟩, what is the probability that we see s?
3 answers