What is the "Quantum mean value problem"? A definition I found was that it is "estimating the expected value of the tensor product observable on the output state of a quantum circuit". Does this mean that given some set of bits that we pass through some circuit, we try and guess what comes out of the other side?
If anyone knows of any papers introducing this idea, that'd be awesome.
The (additive) quantum mean value problem can be defined this way:
Given any constant $\epsilon > 0$, Hermitian observables $O_1,...,O_n$, and constant depth quantum circuit $U$ on $n$ qubits, output any $\tilde{\mu}$ such that $| \tilde{\mu} - \langle0^n|U^{\dagger} (O_1 \otimes ... \otimes O_n)U |0^n \rangle| < \epsilon$.
This is very different from "guess[ing] what comes out the other side" given some set of input bits because, for example, we can have $O_i = |0\rangle\langle0|$ for all $i$, which would amount to estimating the probability of measuring $0^n$ when measuring in the computational basis at the end of the circuit. Notice how this is a different task than "guessing what comes out the other side."
For a reference take a look at this paper: https://arxiv.org/abs/1909.11485
