# Can we amplify BPP algorithms with a random quantum circuit?

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?

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.
• I like this, you've given it a lot of thought. The quantum circuit does just encode the distribution, in a way that's known to be (or at least highly likely to be) difficult to encode classically. Otherwise it serves no purpose. The Porter-Thomas distribution feels "almost but not quite uniform." We could also ask for $r_i$ to be chosen uniformly from the set of numbers from $[0,S]$ such that $H(r_i)\le d$, for some cryptographic hah $H$ and some target $d$. Jul 1 '19 at 22:22