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?
To find the probability of observing the hidden string s when running Fourier sampling on the quantum state |ϕ⟩, we need to compute the probability amplitude (βs)² associated with the state |s⟩.
The Fourier sampling algorithm involves applying the Quantum Fourier Transform (QFT) to the state |ϕ⟩. The QFT can be implemented using a sequence of Hadamard gates and controlled phase gates.
Let's start by expressing the initial state |ϕ⟩ in terms of the computational basis states |y⟩:
|ϕ⟩ = ∑y∈{0,1}n βy|y⟩
Given the definitions of βy in the question, we can rewrite the initial state as:
|ϕ⟩ = ∑y∈{0,1}n βy|y⟩ = ∑y:s·y=1 mod 2 βy|y⟩ + ∑y:s·y=0 mod 2 βy|y⟩ = ∑y:s·y=0 mod 2 1/2(n-1)/2|y⟩
Since we are interested in the probability of observing the hidden string s, we need to compute the probability amplitude βs associated with the state |s⟩. We can do this by calculating the inner product between |s⟩ and |ϕ⟩:
βs = ⟨s|ϕ⟩ = ∑y:s·y=0 mod 2 1/2(n-1)/2⟨s|y⟩
The inner product ⟨s|y⟩ gives us 1 if s=y and 0 otherwise. Therefore, the sum simplifies to:
βs = 1/2(n-1)/2
Now that we have the probability amplitude βs, we can compute the probability P(s) by taking the square of the absolute value of βs:
P(s) = |βs|² = |1/2(n-1)/2|² = 1/2(n-1)
Therefore, the probability of observing the hidden string s when running Fourier sampling on |ϕ⟩ is 1/2(n-1).