A simulator logs the state of its qubits after every run, but different runs can multiply the whole amplitude list by different unit factors, so the log looks more varied than it is. Before you file a bug, find out which entries are really the same state.
A state is a list of complex amplitudes with \sum_i |a_i|^2 = 1. Multiplying every amplitude by the same unit complex number e^{i\varphi} (a number of size 1, such as -1, 1j or complex(math.cos(0.7), math.sin(0.7))) changes no probability of any measurement, in any basis, so it gives the same state. Such a common factor is called a global phase. A factor on only some of the amplitudes, a relative phase, does change the state: [0.6, 0.8] and [0.6, -0.8] are different states, although measuring them gives 0 and 1 equally often.
Two entries a and b of the log are the same state when there is one real \varphi with |a_k - e^{i\varphi} b_k| \le 10^{-9} for every k.
Write first_match(log) that returns a list with one number per entry: for entry i, the smallest index j <= i such that log[j] is the same state as log[i] (so i itself when no earlier entry matches).
Examples
Input: log = [[1, 0], [0.6, 0.8], [-1, 0], [0.6, -0.8], [0.6j, 0.8j]]
Output: [0, 1, 0, 3, 1]
Explanation: [-1, 0] is (-1) * [1, 0], a global phase. [0.6, -0.8] differs from
[0.6, 0.8] by a relative phase: a new state. [0.6j, 0.8j] is 1j * [0.6, 0.8].
Input: log = [[0, 1j], [0, 1], [1, 0]]
Output: [0, 0, 2]
Explanation: [0, 1j] = 1j * [0, 1].
Constraints
1 <= len(log) <= 30; all entries have the same length 2^n (1 to 8 qubits) and are normalised- the tests stay far from the tolerance: entries that are the same agree to about
1e-12, and entries that are different differ by more than1e-4in some amplitude, whatever phase you try
Goals
- Recognise that multiplying a whole state by one unit complex number changes nothing measurable
- Tell a global phase apart from a relative phase between amplitudes
- Match each logged state to the first earlier copy of the same state