2
$\begingroup$

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?

$\endgroup$
0

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.