Scott Aaronson has a post in his blog, Projects aplenty, where he proposes many research problems for students. One of them is:
20. Do there exist probability distributions , over n-bit strings such that (an equal mixture of two independent samples from and two independent samples from ) is efficiently samplable, even though and themselves are not efficiently samplable? (This is closely-related to a beautiful question posed by Daniel Roy, of whether the de Finetti Theorem has a “polynomial-time analogue.”)
In the comments, I proposed one solution to the problem. Scott Aaronson sent me an email pointing out that the conditions in which the solution work are so strong that the solution is effectively trivial. I have thought about the problem more and I believe I have found a much better solution.
To be specific, what I have is: Given data there are distributions and such that it is possible to efficiently approximately sample given . However, neither nor are efficiently approximately sampleable, even given bits of advice. Moreover, it is easy to generate appropiate , in the sense that there is a polynomial-time probablistic algorithm which given creates an with and satisfies these properties.
Before I present the solution, some definitions: If and are prime with and , then I define . When is an odd number, not necessarily prime, and , then is the Jacobi symbol of mod .
Now, to generate : first, pick primes , , and with approximately bits. Let and be primes with and . Set . Set to be a natural number with , and . Set to be a random th root of unity. Set to be a random of elements of subject to these properties:
- For all , and is a square.
- For any , we have .
- Similarly, for any , we have .
- For any , , where is chosen randomly from the binomial distribution .
Given and a permutation , define the value . Then for random , samples from a distribution , which constists of random with and and such that where is sampled from .
It is possible to split the distribution , where consists of sampling and post-selecting for squares, and consists of sampling and post-selecting for nonsquares. Then it is possible to sample as follows: Pick a random permutation and take . However, as far as I can tell, it is impossible to sample either or individually.
Note that must be large. Otherwise, there is a nonnegligable probability that , in which case both and can be sampled by taking for appropiate and large random .
One concern with this approach is that is not being sampled exactly. However, I believe what is being sampled has a neglible statistical distance from , at least for large enough . However, I haven’t proven this.
Added 2013-10-25: I have now written an implementation of this distribution. Find it here.