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!

]]>