Let |α⟩=1M√∑M−1j=0αj|j⟩ and let |β⟩=1M√∑M−1j=0βj|j⟩ be its QFTM. Suppose we shift the superposition |α⟩ to produce |α′⟩=1M√∑M−1j=0αj|j+1(modM)⟩, and let |β′⟩=1M√∑M−1j=0βj′|j⟩ be the QFTM of |α′⟩. Derive an expression for β′j as a function of βj. You can use e, j, pi, and M in your response.
Got this result for above question:
exp(2ðji/M)âj
However it is graded as wrong, can someone help?
exp(2piji/M)beta j
In this problem, we will carry out some steps of the quantum factoring algorithm for N = 15
(a) What is the period k of the periodic superposition set up by the quantum factoring algorithm if it chooses x = 2 ?
(b) Assume that we found this k using period finding algorithm. Use k to find a non-trivial square root of 1(mod 15) . Write your answer as an integer between 0 and 15.
(c) Then, the algorithm proceeds by computing gcd (x,y) for some integers x and y . List these two numbers separated by a comma.
If there are more than one correct solution, provide any one of them.
WHAT IS THE ANSWER FOR:
Let |α⟩=1M√∑M−1j=0αj|j⟩ and let |β⟩=1M√∑M−1j=0βj|j⟩ be its QFTM. Suppose we shift the superposition |α⟩ to produce |α′⟩=1M√∑M−1j=0αj|j+1(modM)⟩, and let |β′⟩=1M√∑M−1j=0βj′|j⟩ be the QFTM of |α′⟩. Derive an expression for β′j as a function of βj. You can use e, j, pi, and M in your response.
To derive the expression for β'ᵢ in terms of βᵢ, we need to consider the relationship between |α⟩ and |α'⟩.
We know that |α'⟩ is obtained by shifting the superposition |α⟩ by 1 mod M. This means that each basis state in |α⟩ is shifted by 1, and we need to determine how this affects the coefficients α.
Let's consider the coefficient αᵢ of the basis state |i⟩ in |α⟩. The corresponding basis state in |α'⟩ is |i+1(mod M)⟩. Therefore, we want to find the coefficient β'ⱼ of the basis state |j⟩ in |β'⟩ that corresponds to the basis state |i+1(mod M)⟩ in |α'⟩.
To find β'ⱼ, we need to express |i+1(mod M)⟩ in terms of |j⟩:
|i+1(mod M)⟩ = (|j⟩ + 1)(mod M)
= (j + 1)(mod M)
Now, let's consider the QFTM of |α'⟩, which is |β'⟩. It is given by:
|β'⟩ = QFTM(|α'⟩)
= QFTM(1/√M ∑ₖ αₖ |k+1(mod M)⟩)
Using the definition of the Quantum Fourier Transform:
QFTM(|k⟩) = 1/√M ∑ₓ e^((2πi/m)kx) |x⟩
We can rewrite |β'⟩ using the QFTM definition:
|β'⟩ = 1/√M ∑ₖ αₖ QFTM(|k+1(mod M)⟩)
= 1/√M ∑ₖ αₖ (1/√M ∑ᵧ e^((2πi/M)((k+1)ᵧ)) |ᵧ⟩)
Now, let's focus on the coefficient β'ⱼ of the basis state |j⟩ in |β'⟩.
Since the sum over ᵧ is a superposition of basis states, we can rewrite it as:
(1/√M ∑ᵧ e^((2πi/M)((k+1)ᵧ)) |ᵧ⟩) = 1/√M ∑ᵧ ∑ p e^((2πi/M)((k+1)ᵧ)) |p⟩
We can rearrange the terms:
∑ p e^((2πi/M)((k+1)ᵧ)) = ∑ p e^((2πi/M)kp) e^((2πi/M)ᵧ)
Now, we can compare this expression to the definition of the QFTM:
QFTM(|p⟩) = 1/√M ∑ζ e^((2πi/M)(pζ)) |ζ⟩
From the comparison, we can see that:
∑ p e^((2πi/M)((k+1)ᵧ)) = (√M e^((2πi/M)((k+1)j))) QFTM(|j⟩)
Substituting this back into the expression for |β'⟩, we have:
|β'⟩ = 1/√M ∑ₖ αₖ (1/√M (√M e^((2πi/M)((k+1)j))) QFTM(|j⟩))
= 1/√M ∑ₖ αₖ e^((2πi/M)(kj)) QFTM(|j⟩)
Finally, we can express β'ⱼ as a function of βⱼ:
β'ⱼ = 1/√M ∑ₖ αₖ e^((2πi/M)(kj)) * QFTM(|j⟩)
Note that in this expression, αₖ are the coefficients of |α⟩, β'ⱼ are the coefficients of |β'⟩, βⱼ are the coefficients of |β⟩, and j ranges from 0 to M-1.