Added 2016-06-04: Although I wrote this at the bottom, to be extra clear I’m writing this at the top: After further investigation, the method I described was found not to work.
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.
Added 2014-01-01: Two problems were found in this method. First of all, this method
relies on the fact that and have the same
square-status. However, more is true. If is the
decomposition of into cycles and given any with each equal to either or , then still and have the same
square-status. Then picking a with many cycles and sampling randomly
from is a way to sample from where if
is a square and otherwise.
This alternate process has around possible outcomes while the
process for sampling has possible outcomes.
This suggests a possible resolution of this problem, namely, fine-tuning so that the latter has enough entropy to sample randomly, while the former
does not. To investigate weather this works, I analyzed more carefully how
random is using a Fourier analysis. I discovered a second
problem: My method does not perfectly sample , but
creates a small correlation between the elements of this pair which decrease
polynomially in rather than exponentially in .