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:
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?
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?
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP