A Pauli string such as "XZI" names one gate per qubit: here X on qubit 0, Z on qubit 1 and nothing (the identity I) on qubit 2. The leftmost character belongs to qubit 0. As a gate on basis states, letter by letter:
I: nothing;X: flips the qubit's bit;Z: multiplies by -1 when the bit is 1;Y: flips the bit and multiplies by i when the bit was 0, by -i when it was 1 (Y|0\rangle = i|1\rangle, Y|1\rangle = -i|0\rangle).
The expectation of a Pauli string P in a state |\psi\rangle is the real number
the average of the \pm1 readings the string would give over many measurements. Many algorithms score a state with a weighted sum of such terms, H = \sum_k c_k P_k, often called a Hamiltonian; its value \langle H\rangle = \sum_k c_k \langle\psi|P_k|\psi\rangle is called the energy (no physics needed: it is a weighted sum of expectations).
Write energy(state, terms) that returns \langle H\rangle as a float, where terms is a list of pairs (coefficient, string); each string has one letter per qubit. An empty list gives 0. The same string may appear more than once.
Conventions: amplitude i belongs to basis state i; qubit 0 is the leftmost bit, so in 3 qubits |011\rangle is index 3. Qubit k of n is bit (i >> (n - 1 - k)) & 1 of index i.
Examples
Input: state = [0.6, 0.8], terms = [(1, "Z"), (0.5, "X")]
Output: 0.2
Explanation: <Z> = 0.36 - 0.64 = -0.28 and <X> = 2 * 0.6 * 0.8 = 0.96; -0.28 + 0.5 * 0.96 = 0.2.
Input: state = [0.7071067811865476, 0.7071067811865476j], terms = [(2, "Y")]
Output: 2.0
Input: state = [0, 1, 0, 0], terms = [(1, "ZI"), (2, "IZ")]
Output: -1.0
Explanation: |01>: qubit 0 reads +1, qubit 1 reads -1; 1 * 1 + 2 * (-1) = -1.
Answers are compared with a tolerance of 1e-6.
Goals
- Apply a Pauli string such as `"XZI"` to an $n$-qubit state
- Compute $\langle\psi|P|\psi\rangle$ and a weighted sum of such expectations