Problem 579231 · medium · Quantum Computing · Level 05 Fourier and Phase

Where the Counting Register Lands

phase estimation · inverse QFT · Born rule · outcome distribution · approximation

Phase estimation reads an eigenphase off a quantum register. A unitary U has an eigenvector |u\rangle with U|u\rangle = e^{2\pi i\varphi}|u\rangle, \varphi in [0, 1). With t counting qubits, after the H gates and the controlled powers U^{2^{t-1}}, \dots, U^2, U, the counting register holds (N = 2^t)

|\psi\rangle = \frac{1}{\sqrt N}\sum_{y=0}^{N-1} e^{2\pi i\varphi y}\,|y\rangle .

Then comes the inverse QFT, the inverse of the quantum Fourier transform \mathrm{QFT}|j\rangle = \frac{1}{\sqrt N}\sum_k e^{2\pi i jk/N}|k\rangle. It has the opposite sign: on any state with amplitudes a_y it gives the amplitudes

b_x = \frac{1}{\sqrt N}\sum_{y=0}^{N-1} a_y\, e^{-2\pi i\,xy/N}.

Finally the counting register is measured, and outcome x comes up with probability |b_x|^2; the estimate of the phase is x/2^t. Bit order: qubit 0 is the leftmost bit of x (for t = 3, |011\rangle is x = 3).

Write pe_outcomes(phi, t) that returns the list of the 2^t outcome probabilities, entry x for outcome x.

Press Run with plot(range(32), pe_outcomes(0.3, 5), kind="bar") to see the outcomes pile up around 0.3\cdot 32 = 9.6. The two outcomes on either side of \varphi\cdot 2^t always share at least 8/\pi^2\approx 0.81 of the probability (wrapping around from 2^t-1 to 0).

Examples

Input:  phi = 0.375, t = 3
Output: [0, 0, 0, 1, 0, 0, 0, 0]
Explanation: 0.375 = 3/8, so outcome 3 comes up with certainty (your numbers may show
rounding noise such as 1e-32).

Input:  phi = 0.3, t = 2
Output: [0.03299150281252629, 0.8823735987409788, 0.06250000000000003, 0.022134898446495133]
Explanation: 0.3 * 4 = 1.2, so outcome 1 (estimate 0.25) is the most likely.

Input:  phi = 0.3, t = 3
Output: [0.021593218925782892, 0.05176812953552157, 0.5775210180698607, 0.2593356191884277, 0.04090678107421711, 0.01944021679795826, 0.014487479117612886, 0.014947537290618514]
Explanation: 0.3 * 8 = 2.4: outcomes 2 and 3 together have 0.837.

Constraints

  • 1 <= t <= 10; probabilities are compared with a tolerance of 1e-6
  • the tests with t > 6 look at a slice of your list, such as pe_outcomes(0.1234, 10)[120:130]

Goals

  • Apply the inverse QFT to the counting register of phase estimation
  • See that $\varphi = k/2^t$ gives outcome $k$ with certainty
  • See the probability spread over neighbours when $\varphi\cdot 2^t$ is not a whole number
Starting Python…