The quantum Fourier transform on n qubits (N = 2^n) sends a state with amplitudes a_j to the state with amplitudes
(plus sign in the exponent, factor 1/\sqrt N). Measuring afterwards gives outcome k with probability |b_k|^2 (the Born rule).
This is the step that makes period finding work. A state is periodic with period r when its amplitudes repeat every r places: a_{x+r} = a_x for every x with x + r < N, where r divides N. For example [0.5, 0, 0.5, 0, 0.5, 0, 0.5, 0] has period 2, and so does the same comb shifted by one place.
Write fourier_peaks(state) that applies the QFT to state (a normalised list of 2^n amplitudes) and returns a dict mapping every outcome k whose probability is greater than 1e-6 to that probability. Press Run with plot(range(len(state)), probs, kind="stem") on a list of all the probabilities to see where they land.
Examples
Input: state = [0.5, 0, 0.5, 0, 0.5, 0, 0.5, 0]
Output: {0: 0.5, 4: 0.5}
Input: state = [0, 0.5, 0, 0.5, 0, 0.5, 0, 0.5]
Output: {0: 0.5, 4: 0.5}
Explanation: shifting the comb by one place turns some amplitudes (b_4 becomes -0.7071...),
but the probabilities stay the same.
Input: state = [0.5, 0.5j, 0, 0, 0.5, 0.5j, 0, 0]
Output: {0: 0.25, 4: 0.25, 6: 0.5}
Explanation: period 4 in N = 8. The pattern leaves outcome 2 empty and puts the most on 6.
Constraints
1 <= n <= 8; the state is normalised- in every test each probability is either below
1e-9or above1e-5, so rounding never decides which outcomes are listed - probabilities are compared with a tolerance of
1e-6
Goals
- Find the measurement probabilities after a quantum Fourier transform
- See that a state repeating with period r puts all its probability on multiples of N/r
- Notice that shifting a pattern changes only phases, not probabilities