5 ms·
> Would it only be possible to use quantum computing to defend against quantum computing? Not at all. As it is believed currently, there are a few problems (BQ
by dcosson 10y ago
> Would it only be possible to use quantum computing to defend against quantum computing?
Not at all. As it is believed currently, there are a few problems (BQP space) such as the discreet logarithm that quantum computers can solve quickly. But lots of other hard problems, probably including all NP problems, cannot be solved exponentially faster by a quantum computer.
See also http://security.stackexchange.com/questions/48022/what-kinds-of-encryption-are-not-breakable-via-quantum-computers http://security.stackexchange.com/questions/48022/what-kinds...
- ikeboy 10y agoYou mean NP-complete, right?
- PeCaN 10y agoNo, he means all problems without a (known) polynomial time solution.
- ikeboy 10y agoThat's still not NP, that's NPI+NP-complete.
- lorenzhs 10y agoAs ikeboy implied, NP does not stand for non-polynomial, but for non-deterministic polynomial. Thus the open question whether the two are equal. In particular, it is clear that P is a subset of NP, as any problem that is polynomially computable with a deterministic machine is immediately also polynomially computable with a non-deterministic one by just not using the non-determinism
- dcosson 10y agoYeah, NP-complete.