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

The Whole Phase Reader on a Small Chip

phase estimation · state-vector simulation · inverse QFT · partial measurement · superposition of eigenvectors

Time to run phase estimation in the simulator you are building, on a real gate. A unitary U on m qubits (a 2^m\times 2^m list of rows, acting as new = U @ state) and a normalised target state |u\rangle are given. When |u\rangle is an eigenvector, U|u\rangle = e^{2\pi i\varphi}|u\rangle with \varphi in [0, 1), and outcome y estimates \varphi\approx y/2^t. Here |u\rangle need not be an eigenvector.

The circuit has t counting qubits (qubits 0 to t-1, all starting in |0\rangle) followed by the m target qubits (starting in |u\rangle):

  1. H on every counting qubit.
  2. For each counting qubit j: controlled-U^{2^{t-1-j}} (if qubit j is 1, apply U to the target 2^{t-1-j} times). Qubit 0 controls the largest power.
  3. The inverse QFT on the counting register. With N = 2^t it maps the counting basis state |y\rangle to \frac{1}{\sqrt N}\sum_x e^{-2\pi i\,xy/N}|x\rangle (the inverse of \mathrm{QFT}|j\rangle = \frac{1}{\sqrt N}\sum_k e^{2\pi i jk/N}|k\rangle) and leaves the target alone.
  4. Measure the counting register only.

Bit order: qubit 0 is the leftmost bit, the most significant. The amplitude of counting value y with target basis state w sits at index y * 2**m + w (for t = 3, the counting state |011\rangle is y = 3).

Write pe_probabilities(U, u, t) that returns the list of the 2^t probabilities of the counting outcomes, entry y for outcome y (the probability of y adds |{\rm amplitude}|^2 over every target basis state w).

Examples

Input:  U = [[1, 0], [0, (0.7071067811865476+0.7071067811865476j)]], u = [0, 1], t = 3
Output: [0, 1, 0, 0, 0, 0, 0, 0]
Explanation: T|1> = e^(2 pi i/8)|1>, phi = 1/8, so outcome 1 is certain (up to rounding noise).

Input:  U = [[1, 0], [0, (0.7071067811865476+0.7071067811865476j)]], u = [0.7071067811865476, 0.7071067811865476], t = 3
Output: [0.5, 0.5, 0, 0, 0, 0, 0, 0]
Explanation: u is half |0> (phi = 0) and half |1> (phi = 1/8).

Input:  U = [[0, 1], [1, 0]], u = [1, 0], t = 2
Output: [0.5, 0, 0.5, 0]
Explanation: |0> = (|+> + |->) / sqrt 2, and X has eigenphase 0 on |+> and 0.5 on |->.

Constraints

  • 1 <= t <= 6; U is 2\times 2 or 4\times 4 and unitary; u is normalised
  • probabilities are compared with a tolerance of 1e-6

Goals

  • Simulate phase estimation end to end: H gates, controlled powers, inverse QFT, measurement
  • Measure only the counting register by summing over the target's basis states
  • See that a target that is not an eigenvector gives a mixture of each eigenphase's outcomes
Starting Python…