Almost every oracle algorithm starts and ends with a Hadamard gate on every qubit, H^{\otimes n}, where H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}. On a basis state it gives an even spread with a sign pattern:
which is bin(x & z).count("1") in Python. On a general state, by linearity, the new amplitude of |z\rangle is \frac{1}{\sqrt{2^n}}\sum_x (-1)^{x\cdot z}\,\texttt{state}[x].
A state of n qubits is a list of 2^n amplitudes, amplitude i for basis state i, with qubit 0 as the leftmost bit (in 3 qubits, |011\rangle is index 3). Since every qubit gets the same gate, the answer here does not depend on that order.
Write hadamard_all(state) that returns the state after H^{\otimes n}. 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].
The larger tests use the helper random_state(n, seed), which returns a normalised random state of n qubits, and look at only a few amplitudes of your answer; you may use it with Run.
Examples
Input: state = [1, 0]
Output: [0.7071067811865475, 0.7071067811865475]
Input: state = [0, 0, 0, 1]
Output: [0.5, -0.5, -0.5, 0.5]
Explanation: x = 3; z = 1 and z = 2 share one 1 with x, z = 3 shares two.
Input: state = [0.6, 0, 0, 0.8j]
Output: [(0.3+0.4j), (0.3-0.4j), (0.3-0.4j), (0.3+0.4j)]
Constraints
- 1 to 14 qubits; amplitudes are compared with a tolerance of
1e-6 - with 14 qubits a 2^n\times 2^n matrix has 268 million entries, and a double loop over all pairs
(x, z)takes as many steps: both are far too slow in the browser
Goals
- Apply H to every qubit of an n-qubit state without building the 2^n x 2^n matrix
- Connect the gate-by-gate picture with the sign pattern (-1)^(x . z)