[ksaj]

This is where I always wish they demonstrated some of the mathematical notation with some variant of quantum Lisp (even if it couldn't be executed in any practical way). The Regetti guys are always around here, so maybe one of them can chime in.

I skimmed the PDF, and it's more than a tad heavier than my usual fodder.

What I think I understood from the document, keeping in mind that given enough time a complete Turing Machine by definition should be able to emulate anything a quantum computer can accomplish, is that a quantum computer should be able to efficiently identify whether a problem run on a classical computer will exit without achieving a complete result. Not that you'll actually get to the result itself, but whether you should expect to be able to, given enough time and compute power.

Because of the density of the paper, maybe I only picked up on a tiny piece of the puzzle. And even then I probably botched it.

[m-p-3]

So it basically tells you if you're going to waste your time looking for an answer that doesn't exist.