A sending station encodes each symbol as one of a few qubit states. The receiver wants to know which pairs it can always tell apart and which pairs it will sometimes confuse. The measure of this is the overlap of two states u and v:
where \overline{u_k} is the complex conjugate u[k].conjugate() and both u and v are normalised (\sum_k |u_k|^2 = 1). A test that asks "is it u?" answers yes for v with probability F(u, v). An overlap of 1 means the same state (up to a global phase), and an overlap of 0 means the states are orthogonal: one measurement always tells them apart.
The station's table lists its states unnormalised: each list is the state times some nonzero factor. Write overlap_table(states) that returns the square table F with F[i][j] the overlap of the normalised states[i] and states[j].
Examples
Input: states = [[1, 1j], [1, -1j]]
Output: [[1.0, 0.0], [0.0, 1.0]]
Explanation: <u|u> = conj(1) * 1 + conj(1j) * 1j = 1 + 1 = 2, so u normalised has
overlap 1 with itself; <u|v> = 1 + (-1j)(-1j) = 1 - 1 = 0: orthogonal.
Input: states = [[3, 4], [1, 0]]
Output: [[1.0, 0.36], [0.36, 1.0]]
Explanation: [3, 4] normalised is [0.6, 0.8], and its overlap with [1, 0] is 0.6 ** 2.
Input: states = [[1, 0], [0, 1], [1, 1], [1, 1j]]
Output: [[1.0, 0.0, 0.5, 0.5], [0.0, 1.0, 0.5, 0.5], [0.5, 0.5, 1.0, 0.5], [0.5, 0.5, 0.5, 1.0]]
Constraints
1 <= len(states) <= 8; all states have the same length 2^n (1 to 4 qubits), and none is all zeros- answers are compared with a tolerance of
1e-6
Goals
- Compute the overlap |<u|v>|^2 of two states, conjugating the first
- Normalise vectors before comparing them as states
- Recognise orthogonal states (overlap 0) as the ones that can be told apart perfectly