Interesting papers this week:
http://arxiv.org/abs/1009.5104 -- Scott Aaronson on sampling
http://arxiv.org/abs/1005.1750 -- Revisions to position-based crypto.
Sarah Mostame told us about adiabatic QC and phase transitions.
Scott told us about sampling, briefly. The really big question is:
does BPP = BQP. We might also ask: Does SampBPP = SampBQP? (These
are problems where we try to sample some distribution with some
error.) SampBPP = SampBQP implies both BPP = BQP and FBPP = FBQP. An
older paper gave evidence that SampBPP != SampBQP. It would be nice
to have a similar argument for FBPP != FBQP.
Scott proved a Sampling/Searching Equivalence Theorem: Let S be a
sampling problem, where the goal is to sample D_x for input x. Then we
can define a search problem R_S that's "equivalent" to S in the sense
that, for any reasonable complexity class C, S in SampC iff R_S in FC.
First suppose that D_x is close to the uniform distribution of A. Then
the search problem is to find T strings in A such that the combined
Kolmogorov complexity of the x_1 .. x_T is almost T log_2 |T|. You can
then replace Kolmogorov complexity with something that's a little less
undecidable.
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip