Suppose you had an oracle that could efficiently compute matrix elements (in the computational basis) $\langle x | C | y \rangle$ for arbitrary polynomial-size circuits $C$. Is there a name for the complexity class of decision problems that could be efficiently solved using such an oracle? Has this complexity class been studied before?
More precisely: let $x$ and $y$ be arbitrary bitstrings of length $n$, and let $C$ be an arbitrary unitary circuit whose number of gates is polynomial in $n$. Let $O$ be a black-box function that inputs $x$, $y$, $C$, and binary fractions $\alpha, \beta$ with $\beta - \alpha > 2^{-\text{poly}(n)}$, and outputs 1 if $\mathrm{Re}(\langle x | C | y \rangle) > \beta$ or 0 if $\mathrm{Re}(\langle x | C | y \rangle) < \alpha$ under the promise that one of those two inequalities holds, and likewise for the imaginary part. The complexity class in question is the class of problems that could be solved by calling such an oracle a number of times that grows polynomially in $n$. (I think I formalized that problem correctly, but let me know if not.)
Intuitively, I first expected that this complexity class seems vastly large than (Promise)BQP, because (unlike with regular BQP) you can efficiently compute the value of even exponentially small amplitudes. But then I realized that this complexity class doesn't obviously contain BQP, because you may need to "manually search" for any anomalously large amplitudes, whereas for regular BQP you can find them efficiently by just applying the circuit and then measuring in the computational basis. (I.e. you need to "guess and (efficiently) check" the answer, instead of just sampling the probability distribution $P(x,y) = |\langle x | C | y \rangle|^2$.) So it isn't obvious to me whether such an oracle would be strictly more powerful than a standard quantum computer.
