The quantum Fourier transform on n qubits (N = 2^n) sends a state with amplitudes a_j to the state with amplitudes b_k = \frac{1}{\sqrt N}\sum_j a_j\, e^{2\pi i\,jk/N} (plus sign in the exponent, factor 1/\sqrt N); measuring then gives outcome k with probability |b_k|^2.
Period finding prepares a comb: equal amplitudes on the basis states x = \mathrm{offset},\ \mathrm{offset} + r,\ \mathrm{offset} + 2r, \dots (every x < N of that form), 0 everywhere else. If M states are on the comb, each has amplitude 1/\sqrt M. When r divides N, all the probability after the QFT lands on the multiples of N/r. But the period of a real problem is rarely a power of 2, and then the ideal peaks sN/r (s = 0, 1, \dots, r) fall between whole numbers and the probability spreads around them.
Write near_peak_prob(n, r, offset) that builds the comb, applies the QFT and returns the total probability of the outcomes k (in 0 \le k < N) that lie within distance 1 of an ideal peak: |k - sN/r| \le 1 for some s in 0, 1, \dots, r. In whole numbers this is |k\,r - s\,N| \le r. The peak s = r sits at N itself, so k = N - 1 is close to it. Press Run with plot(range(N), probs, kind="stem") on a list of all the probabilities to see the spread.
Examples
Input: n = 4, r = 3, offset = 0
Output: 0.9232303918865017
Explanation: N = 16, the comb is 0, 3, 6, 9, 12, 15 (M = 6). The ideal peaks are 0, 5.33, 10.67
and 16, so the outcomes that count are 0, 1, 5, 6, 10, 11 and 15.
Input: n = 4, r = 3, offset = 2
Output: 0.9154036610793104
Explanation: the comb is 2, 5, 8, 11, 14: one state fewer, so the spread is a little different.
Input: n = 3, r = 2, offset = 1
Output: 1.0
Explanation: r divides N; all the probability is on 0 and 4.
Constraints
2 <= n <= 10;2 <= r <= 2**(n - 1);0 <= offset < r- the answer is compared with a tolerance of
1e-6 - with n = 10, a plain double loop over all N^2 \approx 10^6 pairs may be slow in the browser: loop only over the M states of the comb, or use numpy
Goals
- Build an evenly spaced state and find its outcome probabilities after a quantum Fourier transform
- See how the probability spreads around the ideal peaks s N / r when r does not divide N
- Test closeness to a fractional peak exactly, with integers