In the step “Let F denote the distribution given by choosing an s ~_u [p], and choosing a column from …”. I think there shouldn’t be a tilde over A_{i_s}. Because if there is a tilde we would be sampling from a vector with one element. Is my interpretation correct ?

And can you clarify why W is called a submatrix ?

]]>from DA ˜i”. Are we sampling column indices from a distribution of row l2-norms ?

And one more question what does “choosing a column from DA ˜i” mean ?

]]>1) Yes. Forrelation, the Childs et al. glued trees problem, the vanDam-Hallgren-Ip shifted quadratic character problem, and probably at least a half-dozen others. (Here I’m not counting the simulation of quantum physics and chemistry, estimation of the Jones polynomial, or anything else BQP-complete, since in some sense those are near-tautological examples.)

2) No, we don’t know how to prove such a statement. The closest we can get, in some sense, is to prove that there’s no polynomial-time classical algorithm to sample exactly from the BosonSampling distribution unless the polynomial hierarchy collapses (and similar statements for other sampling-based quantum supremacy proposals). Of course, Shor’s algorithm solves something classically hard if you assume that factoring is not in P. 🙂

]]>2) Given P/=NP, is there a proof that Shor or Simon (or any other such problem) is classically exponentially hard?

Thanks!

]]>In other cases, I guess it makes more sense to view the content on its original website instead of YouTube. Take for example Robert Lawrence Kuhn’s Closer To Truth interviews or Sean Carroll’s new Mindscape Podcast. Those original websites contain explaining text and links to related content, and a matching atmosphere. (Those are interviews/conversations with really interesting people in a very relaxed atmosphere, so it is nice to consume them in a context where that relaxed atmosphere is not disturbed.)

]]>Many of us cling to obsolete technology because we enjoy being reminded of the good old days. E.g., I have just given up my last standard transmission vehicle.

A common, if inexplicable, manifestation of this phenomena is presenting highly math oriented topics on chalk boards rather than whiteboards. A reasonable analogy is preferring graphics on a B&W CGA monitor rather than a modern monitor — except this does not capture icky “chalk dust on hands” aspect.

]]>