TransWikia.com

Relation between approximate counting and sampling

Quantum Computing Asked on July 14, 2021

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?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP