Having said that, I’m virtually certain that the answer to your question is yes. I.e., if BosonSampling could be done classically in 1.00001^{n} time, even up to 1/poly(n) error in variation distance, then surely we could convert that into a BPTIME(c^{n})^{NP} algorithm to approximate the permanents of i.i.d. Gaussian matrices, for some c<2—which is something that seems pretty implausible.

But I’d need to go through the reduction carefully in order to estimate what value of c we can get out the other end when we do this. If I get around to doing such an estimate, I can post an update here (or send me an email if you want me to email you).

]]>Maybe the best way to summarize the situation is as follows.

We’ve long known that if scalable QCs are built, then RSA as we all know it collapses. This paper doesn’t *challenge* that conclusion, so much as study the question of how much cryptographic security could still be salvaged from the heap of charred rubble that was once RSA. (The answer, as it turns out, is “possibly some but at any rate not much.”)

I don’t agree with the closing quote that “the conventional wisdom is wrong.” This seems to me more like an elaboration of the conventional wisdom (which long allowed for the possibility of “merely-polynomial” public-key security, as for example with Merkle puzzles, even supposing that factoring and discrete log were solvable in polynomial time).

]]>As I’ve said loudly and clearly many, many times, it’s an open problem whether the ability to solve BosonSampling implies the ability to solve any classically-hard *decision* problems. Certainly we don’t know how to do (e.g.) factoring or discrete log this way, or anything else of relevance to cryptography. On the other hand, if we just want something that’s classically hard, the case that BosonSampling is classically hard is arguably *stronger* than the case that factoring and discrete log are.

How do you feel about the characterization “Scott is thinking in a theoretical sense”?

(As if 1TB keys and 100 hours of CPU time for single message description, let alone quantum computers, are not theoretical)

]]>