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.
(a) If we run Fourier sampling on |ϕ⟩, what is the probability that we see s?
I had the same question, can anyone help us ASAP
did you get the answer pls?
1/2
To determine the probability of observing the hidden string s when running Fourier sampling on the state |ϕ⟩, we need to calculate the probability amplitude of the state |s⟩ in the transformed basis.
In Fourier sampling, we apply the n-qubit Fourier transform to the initial state |ϕ⟩. The Fourier transform is defined by the unitary matrix F:
F = (1/√2^n) ∑x,y ω^(x⋅y) |x⟩⟨y|
where ω is the n-th root of unity.
To calculate the probability amplitude of the state |s⟩ in the transformed basis, we need to find the coefficient associated with the state |s⟩ after applying the Fourier transform. Let's denote this coefficient as γs.
To find γs, we can express |ϕ⟩ in the computational basis as follows:
|ϕ⟩ = ∑y∈{0,1}^n βy |y⟩.
Next, we apply the Fourier transform to the state |ϕ⟩:
F|ϕ⟩ = ∑x,y ω^(x⋅y) βy |x⟩.
Now, we can isolate the coefficient γs by taking the inner product of the transformed state with |s⟩:
⟨s|F|ϕ⟩ = ∑x,y ω^(x⋅y) βy ⟨s|x⟩.
Since we are only interested in the probability, we can square the absolute value of the coefficient γs to find the probability of observing the hidden string s:
P(s) = |γs|^2 = |⟨s|F|ϕ⟩|^2.
By simplifying the above expression and taking into account the specific values of βy given in the question, we can determine the probability of observing s.