Say I have an algorithm over N qubits and I want to find the expectation value of an operator $O$ composed of a sum of mterms, each of which is the tensor product of some number of single-qubit Pauli operators:
$$ O = \sum_{i=1}^m \alpha_i \prod_{j=1}^N \sigma_{\beta(i,j)}^{(j)} $$
where $\beta(i,j) \in \{{0,1,2,3}\}$ determines the identity of the j-th Pauli operator in the i-th product in the sum ($\sigma_0 \equiv I$, $\sigma_1 \equiv X$, ...) and $\sigma^{(j)}$ denotes a Pauli operator acting on the j-th qubit. The goal is to determine the following:
- What is the minimum number of circuit experiments needed to completely evaluate $\langle O \rangle$ (a "circuit experiment" means as many measurements as I want for a given configuration of measurement bases over all N qubits)
- How do I find the elements of the maximally reduced set of measurement bases that accomplish (1).
Example a: $$ O = Z_1 + Z_2 + Z_3 + Z_1 Z_2 $$
The minimum number of experiments is 1.
The maximally reduced set of measurement operators is $\{Z_1 Z_2 Z_3\}$, which corresponds to measuring all three qubits in the Z-basis. From outcomes of these measurement bases, I can separately compute $\langle Z_1 \rangle $, $\langle Z_2 \rangle $, $\langle Z_3 \rangle $, and $\langle Z_1 Z_2 \rangle $ and then add the results to find $\langle O \rangle$. In general, I'm allowed to combine terms that have identical Pauli products on their overlapping subspace.
Example b: $$ O = X_1 Y_2 + Y_1 X_2 + X_1 X_2 + Y_1 Y_2 $$
- The minimum number of experiments is 4.
- The maximally reduced set is $\{ X_1 Y_2 , Y_1 X_2 , X_1 X_2 , Y_1 Y_2\}$. Even though in the course of measuring $\langle X_1 Y_2 \rangle$ and $\langle Y_1 X_2\rangle$ I measured both qubits in both bases, I cannot reuse the results from those measurements to determine $\langle X_1 X_2 \rangle$ because I lose any information about classical correlations in the outcomes of $X_1$ and $X_2$ (i.e. entanglement) if I try to combine their outcomes taken in two separate experiments.
So, given an arbitrary $O$ how do I find the minimum number of experiments and the corresponding maximally reduced set of measurements