4 ms·

> 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 nondeterminist

> 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)

Filligree 13y ago
The latter of which sounds suspiciously like what a quantum computer does. How sure are we that BQP != NP?
- mcppherrinrinm 13y ago
  We aren't: https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP 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.
  - Filligree 13y ago
    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.
- gizmo686 13y ago
  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.
mcppherrinrinm 13y ago
Yes, and that part of his comment would also imply P != NP: > Fortunately, there are problems which are NOT in BQP We don't know yet if NP \ BQP is non-empty (and neither do we know if BQP \ NP is non-empty).
- mcherm 13y ago
  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.
  - mcppherrinrinm 13y ago
    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?
mcherm 13y ago
Oops... my bad. Sorry.

Filligree 13y ago

The latter of which sounds suspiciously like what a quantum computer does. How sure are we that BQP != NP?

mcppherrinrinm 13y ago
We aren't: https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP 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.
- Filligree 13y ago
  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.
gizmo686 13y ago
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.

mcppherrinrinm 13y ago

Yes, and that part of his comment would also imply P != NP: > Fortunately, there are problems which are NOT in BQP We don't know yet if NP \ BQP is non-empty (and neither do we know if BQP \ NP is non-empty).

mcherm 13y ago
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.
- mcppherrinrinm 13y ago
  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?

mcherm 13y ago

Oops... my bad. Sorry.