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