Phase estimation starts by copying an eigenphase onto a register of control qubits. The target register (the last m qubits) holds an eigenvector |u\rangle of the unitary U: U|u\rangle = e^{2\pi i\varphi}|u\rangle with \varphi in [0, 1). In front of it sit t counting qubits, qubits 0 to t-1, all starting in |0\rangle. Then:
- H on every counting qubit, so the counting register is an even mix of all 2^t basis states.
- For each counting qubit j, a controlled-U^{2^{t-1-j}}: if qubit j is 1, apply U to the target 2^{t-1-j} times. So qubit 0 controls U^{2^{t-1}} and the last counting qubit controls U itself.
Bit order: qubit 0 is the leftmost bit, the most significant. A counting basis state |y\rangle is |b_0 b_1 \dots b_{t-1}\rangle with y = int("b0b1...", 2) (for t = 3, |011\rangle is y = 3), and the whole system's amplitude for counting value y and target basis state w sits at index y * 2**m + w.
The target remains |u\rangle throughout, so the output is a product: (counting register state) \otimes\,|u\rangle.
Write counting_register(U, u, t) that returns the counting register's state after step 2, a list of 2^t amplitudes indexed by y. U is a 2^m\times 2^m unitary (a list of rows, acting as new = U @ state) and u one of its eigenvectors. Any global phase is accepted: [0.5j, 0.5j, 0.5j, 0.5j] is the same state as [0.5, 0.5, 0.5, 0.5].
Examples
Input: U = [[1, 0], [0, (0.7071067811865476+0.7071067811865476j)]], u = [0, 1], t = 2
Output: [0.5, (0.35355339059327373+0.35355339059327373j), 0.5j, (-0.35355339059327373+0.35355339059327373j)]
Explanation: T|1> = e^(i pi/4)|1>, phi = 1/8. y = 1 (|01>) applies U once: an eighth of a turn.
y = 2 (|10>) applies U twice: a quarter turn, the factor i. y = 3 applies U three times.
Input: U = [[1, 0], [0, -1]], u = [0, 1], t = 1
Output: [0.7071067811865476, -0.7071067811865476]
Input: U = [[1, 0], [0, 1j]], u = [0, 1], t = 3
Output: [0.3535533905932738, 0.3535533905932738j, -0.3535533905932738, -0.3535533905932738j, 0.3535533905932738, 0.3535533905932738j, -0.3535533905932738, -0.3535533905932738j]
Explanation: phi = 1/4, so the factor turns by a quarter turn from each y to the next.
Constraints
1 <= t <= 6;Uis 2\times 2 or 4\times 4; amplitudes are compared with a tolerance of1e-6
Goals
- Apply controlled-$U^{2^k}$ gates from a register of control qubits to an eigenvector
- Recognise the counting register's state $\frac{1}{\sqrt{2^t}}\sum_y e^{2\pi i\varphi y}|y\rangle$
- Match each counting qubit to its power of $U$ with qubit 0 as the most significant bit