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?


1 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.

  • $\begingroup$ 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$. $\endgroup$
    – Mark S
    Jul 1, 2019 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.