# How to determine the minimum number of experiments needed to compute m-many k-local Pauli expectations?

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:

1. 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)
2. 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$$

1. The minimum number of experiments is 1.

2. 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$$

1. The minimum number of experiments is 4.
2. 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

• I am confused with $O$, if it's an operator its expectation value depends upon the state/density matrix. – Hemant May 31 '19 at 3:15
• without restrictions on the possible type of circuit, I would argue that the answer is always one. If I understand what you are saying, you can always use a circuit that "spreads" the correlation over a big number of modes, and then a single measurement configuration is enough to fully characterise the output states. See e.g. references in arxiv.org/abs/1806.02436 – glS Jun 3 '19 at 14:16
• @glS I'm skeptical about "spreading" the information around in this context (no-cloning theorem) but haven't read the full paper, but either way the goal here is to avoid ancillas and just prepare another copy of $|\psi\rangle$ if necessary. – forky40 Jun 5 '19 at 0:24
• Although if its easy to demonstrate that the answer is "1" for example b I would be interested in seeing that method – forky40 Jun 5 '19 at 0:25
• Again it seems my lazy notation is to blame. For the state you gave, If I perform an experiment where I measure both qubits and record the outcome bitstring, with enough statistics I would compile a histogram that looks like {"00": $|a|^2$, "01" $|b|^2$, ...}. This histogram contains all of the information needed to compute <Z1Z2>, <Z1>, <Z2>. The number of histograms I need to do this (and their measureemnt bases) is what I meant by the "maximally reduced set of measurement bases". – forky40 Jun 6 '19 at 15:28