HW6 - Problem 3

Problem 3: Fourier Transform of Factors

Recall the periodic states defined for fixed \(N\) and some \(r\) that divides \(N\):

\(\left|\phi_r\right> := \sqrt{\frac{r}{N}} \sum_{k=0}^{\frac{N}{r} - 1} \left|kr\right>.\)

In this problem we will convince ourselves that

\(QFT_N \left|\phi_r\right> = \left|\phi_{N/r}\right>.\)

Instead of proving it generally, we will look at the case where \(N = 21\) and \(r = 3\) that we studied in class.

  1. Write the state \(\left|\phi_3\right>\).
  2. Apply \(QFT_{21}\) to \(\left|\phi_3\right>\). We know the solution will be \(\left|\phi_7\right>\), but for this problem, write the state as a sum of states with Fourier amplitudes. Your solution should be in the form

\(\frac{1}{?}\sum_y \sum_k \omega^{?} \left|y\right>.\)

  1. There are two cases to analyze. For certain values of \(y\), the amplitude of \(\left|y\right>\) will be 1. What values of \(y\) is this for?
  2. The other case is when the previous statement is NOT true. What happens in this case? Pick the smallest value of \(y\) that was not chosen in the previous part, and draw all the values that appear with this \(y\) in the complex plane. What can you say about the amplitude of \(\left|y\right>\) in this case?