Viewing a single comment thread. View all comments

noideaman t1_j1ngjvs wrote

Reply to comment by nagareteku in An IBM Quantum Computer Will Soon Pass the 1,000-Qubit Mark by giuliomagnifico

Notice, you didn’t reduce complexity to polynomial switching to quantum. We still don’t know if NP-Complete problems can be solved in polynomial time on a quantum computer. If I recall, the top theoreticians think no.

8

nicuramar t1_j1nv1yn wrote

Yeah, BQP (the problem class solved by quantum computers) is generally believed to be disjunct from NPC.

2