For which quantum algorithms is it sufficient to know $\langle \sigma_1...\sigma_{N} \rangle$ and/or $\langle \sigma_i \rangle$?

Question

In which known quantum algorithms is sufficient to know $\langle \sigma_1...\sigma_{N} \rangle$ and/or $\langle \sigma_i \rangle$ $\forall i$ in order to solve the problem that the same algorithm would have solved? Where $\sigma=X$,$Y$ or $Z$.

$N$ can be for example the total number of qubits that describe the circuit (see below).

I try to explain the question with some examples:

1. In Bernstein Vazirani, if I know $\langle Z_i \rangle$ $\forall i$ I get the result since I have only one possible outcome, same with Grover with only 1 searched item.

2. In VQE (and also in Quantum machine learning algorithms I think), what is important for the algorithm is $\langle \sigma_1...\sigma_{N} \rangle$.

3. In Shor I think that I can't find the period by knowing the expectation values, same with Grover with 2 or more searched items. I don't know if this is true.

In general $\langle \sigma_1...\sigma_{N} \rangle$ can also not regard all the qubits, but for example all the qubits minus the last one ($\langle \sigma_1...\sigma_{N-1} \rangle$), or also $\langle \sigma_1...\sigma_{N-2} \rangle$, or $\langle \sigma_2...\sigma_{N} \rangle$ and so on. I would like to know the results that i can achieve by knowing some of these expectation values. The impotant thing is that the number of expectation values that I need to know is polynomial with respect to the number of qubits, i.e. is efficient to compute the result knowing these expectation values.

Answer 1

This is not a complete answer but describes a case where knowing polynomially many Pauli expectation values is not sufficient to solve the same problem. Consider that the set of expectation values for all length-$n$ strings containing Pauli-Z operators is related to the set of probabilities for observing computational basis states by a system of linear equations. For instance if we have a wavefunction \begin{equation} |\psi\rangle = c_{00}|00\rangle + c_{01}|01\rangle + c_{10} |10\rangle + c_{11}|11\rangle \end{equation}

Then we can compute expectation values like \begin{align} \langle Z_0 \rangle = \langle \psi| (I \otimes Z)|\psi\rangle &= |c_{00}|^2 -|c_{01}|^2 +|c_{10}|^2 - |c_{11}|^2 \\&= p_{00} - p_{01} + p_{10} - p_{11} \end{align}

Repeating this for the remainder of expectation values we find \begin{equation} \begin{pmatrix} 1 \\ \langle Z_0 \rangle \\ \langle Z_1 \rangle \\ \langle Z_0 Z_1\rangle \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & \text{-}1 & 1 & \text{-}1\\ 1 & 1 & \text{-}1 & \text{-}1\\ 1 & \text{-}1 & \text{-}1 & 1 \end{pmatrix}\begin{pmatrix} p_{00} \\ p_{01} \\ p_{10} \\ p_{11} \end{pmatrix} \end{equation}

and one can show this to generalize to arbitrary $n$. Observe that each probability depends nontrivially on every possible pauli-Z string. This suggests that for any algorithm where the task is to determine the probability $p_k$ of measuring a specific bitstring $k = k_1 k_2 \dots k_n$, a polynomial number of pauli-Z strings will not be sufficient.

Answer 2

I think that something that may answer your question is the technique named `classical shadows' (introduced in https://www.nature.com/articles/s41567-020-0932-7). The key idea is understand that the state $\rho$ can be approximated as \begin{equation} \rho \approx \frac{1}{T}\sum_{t=0}^{T-1}\sigma_1^{(t)}\otimes ... \otimes \sigma_n^{(t)} \end{equation} with $\sigma_i^{(t)} =|s_i^{(t)}\rangle \langle s_i^{(t)}| - \mathbf{1} $, and $|s_i^{(t)}\rangle$ are randomized measurements in the $X$, $Y$ and $Z$ basis of the $i$-th qubit. Further, they claim that for $T= O( C^r\log n \epsilon^{-2})$, for the achieve $\epsilon$ accuracy in all $r$-body density matrices, where $C$ is a constant.

You can learn more about this in Provably efficient machine learning for quantum many-body problems.

So, using this, the question is: when do you need good accuracy for large $r$ density matrices?