Can we amplify BPP algorithms with a random quantum circuit?

Question

Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample $n$ bits, drawing a number $r$ uniformly from $[0,S]$; we can plug $r$ into $P$ to see if $P(r)=0$. If we only perform the above test one time, we would be "fooled" into thinking the polynomial is $0$ when it's not only $d/S$ times. However, we can rinse and repeat $k$ times to amplify our success probability, and our probability of being "fooled" is at most $(d/S)^k$.

As an alternative to drawing uniformly from $[0,S]$, we could also perform random circuit sampling on an $n$-qubit random quantum circuit $U$. That is, we measure $U\vert 00\cdots0\rangle$ for some fixed random quantum circuit $U$.

For each sample, the output of $U$ will most definitely not be uniformly distributed; it's more likely that most states are never sampled, a good number of states having a reasonable probability of being sampled, and a small number of states having a large probability of being sampled. This is according to the Porter-Thomas distribution as I understand it.

If we were to sample $n$ qubits $k$ times from a random quantum circuit $U$, and use these $r_1,r_2,\cdots, r_k$ as a test that a polynomial is $0$, what is our soundness probability?

Could it be more efficient to repeatedly sample $n$ qubits from the same random quantum quantum circuit to determine guesses $r_1,r_2,\cdots,r_k$ drawn from the Porter-Thomas distribution determined by $U|00\cdots 0\rangle$ than to repeatedly sample $n$ bits at random to determine guesses $r_1,r_2,\cdots,r_k$ drawn from the uniform distribution?

Answer 1

In essence you are asking could it be more efficient to use non-uniform distribution (instead of uniform) to pick numbers $r_i$ from $[0,S]$ for testing. Quantum circuit here just encodes the distribution, essentially it has no other use.

Well, it depends on how we model our probability space for all polynomials. In some models it could be better to pick numbers closer to 0, in some others it's better to pick uniformly and in some models it's better to use some specific distribution.

And this is really hard task to correctly define probability space for all polynomials (that will be "uniform" in some sense). Note that it's even impossible to define uniform distribution over real line compatible with standard Kolmogorov axioms of probability.