3 ms·
Shor's algorithm absolutely does not reduce NP hard problems to P (or BQP). These kinds of problems with quantum speedups reside in an intermediate class of dif
by yarvos 4y ago
Shor's algorithm absolutely does not reduce NP hard problems to P (or BQP). These kinds of problems with quantum speedups reside in an intermediate class of difficulty sometimes called NP-intermediate which may or may not already be in P, and which NP complete problems do not reduce to.
- Pepe1vo 4y agoYou're correct, I got some of the terminology mixed up. It's after all been a long time since I've been in the field :p