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

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.

• could you highlight the difference between this and quantumcomputing.stackexchange.com/q/23553/55?
– glS
Commented Jan 5, 2022 at 14:48
• @glS I think in this question I specified in a better way of which expectation value I'm talking about and what's the goal (efficient compute the result knowing these expectation values). I can delete the question I asked yesterday without any problem. Thank you. Commented Jan 5, 2022 at 14:57
• Notice that Grover does not give you an exponential advantage so it is not possible to measure expectation values of the qubits (in the number of qubits) because not even the quantum algorithm can do so. Commented Jan 12, 2022 at 22:54
• One very cool case is a method that allows you to solve graph isomorphism (or any hidden subgroup problem) in log^2 |G| measurements of states that can be efficiently generated. However, classically postprocessing the measurements is exponentially complicated. See Theorem 3.1.4 in arxiv.org/abs/1607.05256 Commented Jan 12, 2022 at 22:57

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 $$$$|\psi\rangle = c_{00}|00\rangle + c_{01}|01\rangle + c_{10} |10\rangle + c_{11}|11\rangle$$$$

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{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}$$$$

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.

• Thank you. Yes, for this reason I'm pretty sure that there are a lot of algorithms for which I can't find the same solution by using a polynomial number of expectation values. But I would like to know which one can be solved instead. Thanks again! Commented Jan 5, 2022 at 19:48

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 $$$$\rho \approx \frac{1}{T}\sum_{t=0}^{T-1}\sigma_1^{(t)}\otimes ... \otimes \sigma_n^{(t)}$$$$ 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.

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