> Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP
Incorrect, well mostly. The deal is that there are problems that can be done in "polynomial time" (how long it takes is not exponential in the size of they key) for a normal computer (or person); the set of these is called "P", the ones that CANNOT be done on polynomial time is "NP". And there are problems that can be done in "polynomial time" (with reasonable limits on errors) by a quantum computer; the set of these is called "BQP". If P = BQP it would mean that quantum computers can (in reasonable time) solve all the same problems that classical computers can. But in fact, P is a subset of BQP: there are problems that are "hard" for classical computers but "easy" for quantum computers.
An example of this is factoring numbers. Shor's algorithm is a way to factor numbers using a quantum computer and it runs in polynomial time. Now it isn't practical today: the biggest quantum computers in existence are hard put to factor the number "10", much less some 40-digit monstrosity. But computers only get better.
Fortunately, there are problems which are NOT in BQP -- problems that are hard even for quantum computers. And these are the ones you want (not those in NP) if you want to stymie a quantum computer.
> the ones that CANNOT be done on polynomial time is "NP".
I see you've solved one of the great open problems!
NP is defined as problems that a nondeterministic turing machine can solve in polynomial time. Imagine, if you will, a turing machine that when it "branches" always chooses the right path (Or: chooses "both" without overhead)
But we do know that BQP \ P is non-empty, which is what I was trying to say. In fact, factoring large integers lies in BQP \ P, and is also the basis of some commonly used encryption algorithms.
No, we don't know that either. For all we know, we could have BQP = P: today, we don't know any algorithm in P to factor integers, but that's not a proof that it doesn't exist. If we had such a proof, as mcpherrinm points out this would directly lead to a proof that P != NP (since we DO know that factoring is in NP).
Also, I don't mean to pile on, but this wasn't what you were trying to say in the paragraph I quoted: in that paragraph, you said that we just had to pick problems outside BQP to make cryptography work despite quantum computers. I don't know if that's what you had in mind, but for such an algorithm to be tractable, it should at least be in NP (nobody with a deterministic computer wants to spend an exponential amount of time establishing an SSL connection): so the mathematical statement is whether NP \ BQP is non-empty. Did I miss something?
However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies your analogy.
I don't know much about quantum physics or quantum computing, so I may be mistaken, but it seems to me that post-selection is more of a philosophical construct than something that is physically possible, though.
I've seen post-selection demonstrated in a laboratory. It definitely isn't just a philosophical construct, except inasmuch as what it says about time making people want it to be less than real, and logic doesn't work that way.
As for whether you could make a PostBQP-capable computer, though.. I don't think so, at least in the most general case. I don't understand this nearly well enough to be sure, but from what I've heard, tricking causality like that has the problem that you're increasing the chance of your circuitry failing right along with the chance of getting the right result, and quantum computers are already hard enough.
The latter of which is exactly what a quantom computer does. The problem is that when we make a measurement, we randomly select one of the execution paths and see its result. The problem is that once we make a measurement, we would have to repeat the experiment in order to make another measurement.
Correct (except for the spelling of "Quantum").
> Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP
Incorrect, well mostly. The deal is that there are problems that can be done in "polynomial time" (how long it takes is not exponential in the size of they key) for a normal computer (or person); the set of these is called "P", the ones that CANNOT be done on polynomial time is "NP". And there are problems that can be done in "polynomial time" (with reasonable limits on errors) by a quantum computer; the set of these is called "BQP". If P = BQP it would mean that quantum computers can (in reasonable time) solve all the same problems that classical computers can. But in fact, P is a subset of BQP: there are problems that are "hard" for classical computers but "easy" for quantum computers.
An example of this is factoring numbers. Shor's algorithm is a way to factor numbers using a quantum computer and it runs in polynomial time. Now it isn't practical today: the biggest quantum computers in existence are hard put to factor the number "10", much less some 40-digit monstrosity. But computers only get better.
Fortunately, there are problems which are NOT in BQP -- problems that are hard even for quantum computers. And these are the ones you want (not those in NP) if you want to stymie a quantum computer.
For more details, see http://www.scottaaronson.com/papers/bqpph.pdf or frankly ANYTHING written by Scott Aaronson (http://www.scottaaronson.com/blog/).