AncientRickles

I asked this last night and it got some interesting discussion. I would like your guys' take on it:

If Shor's algorithm turns factoring large composite numbers into a polynomial time problem, is it possible that a quantum computing algorithm could be found with sufficient to solve any NP problem (P=NP)? Are there any NP problems that we know for certain, say with mathematical proof, for which no polynomial time quantum computing algorithm can exist?

Not to mention the Millennium Prize. Mmmm 2 million dollars....

Neat answer. So if QBP = NP, then P=NP, yet all evidence seems to point to QBP only being a subset of NP. Yet, there is no problem in NP space that we are certain is not in QBP (how would you even prove this?).

Thanks for the insight.

Indeed that seems to be the key takeaway from this discussion. Thanks. I guess the question isn't whether P=NP, but does QBP = NP.

The answer is that cryptography benefits from many eyes. People learned hundreds if not thousands of years ago that security by obscurity just doesn't work. The whole goal of cryptography is to invent systems where your opponent knows all the rules of your system and still can't computationally break it.

Think about it this way. You are at some meeting of 20 people discussing a new encryption scheme. If the system relies only on nobody but the people in the room knowing how the system works, only 1 needs to be a spy for the whole system to be a failure.

If the system is secure even when the attacker knows how it works in detail, then every other person in the room but the guy you want to send your message to can be a spy and your message would still go unbroken.