Consider the following statement of Stockmeyer counting theorem.

Given as input a function $f:\{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$ and $y \in \{0, 1\}^{m}$, there is a procedure that runs in randomized polynomial time, with access to an $\text{NP}^{f}$ oracle (that is, in $\text{FBPP}^{\text{NP}^{f}})$, and output an estimate $\alpha$ such that \begin{equation} (1 - \epsilon)p \leq \alpha \leq (1 + \epsilon)p, \end{equation} for \begin{equation} p= \frac{1}{2^{n}}\sum_{x \in \{0, 1\}^{n}}f(x). \end{equation}

This version can be found in Theorem 21 this paper.

Here are my two questions:

  1. Consider a quantum circuit $C$ run on the all $|0^{n}\rangle$. For $x \in \{0, 1\}^{n}$, consider an output probability \begin{equation} p_x = |\langle x|C|0^{n}\rangle|^{2}. \end{equation} Because of Stockmeyer's theorem, for any quantum circuit $C$ can we multiplicatively estimate $p_x$ to error $\epsilon$, for any $x \in \{0, 1\}^{n}$, in $\text{FBQP}^{\text{NP}^{S}}$, where $S$ is an exact sampler from the output distribution of $C$?

    Note that it is trivial to sample from the output distribution of a quantum circuit in quantum randomized polynomial time, so, if the answer to this question is yes, does it mean we can compute this estimate in $\text{FBQP}$ itself and not need the oracle?

  2. Can we multiplicatively estimate $p_x$, to error $\epsilon$, for a uniformly randomly chosen $x$, in $\text{FBQP}^{\text{NP}^{S}}$? The paper I linked seems to indicate that we can, in Lemma 23, but I do not see how.

Basically, I do not understand what $f$ of Stockmeyer's counting theorem is in either of these cases. How does the existence of a sampler $S$, for the output distribution of a quantum circuit, relate to the $f$ in Stockmeyer's theorem --- can we construct an explicit $f$ using the circuit and the sampler $S$? Does sampling imply approximate counting by Stockmeyer's argument?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.