No, a true quantum computer will not necessarily solve NP-complete (NPC) problems efficiently. Quantum algorithms like Grover’s provide quadratic speedups, but this is insufficient to turn exponential-time solutions into polynomial-time ones. While quantum computers excel in specific tasks (e.g., Shor’s algorithm for factoring), there’s no evidence they can solve all NP-complete problems efficiently.
Current complexity theory suggests that , the class of problems solvable by quantum computers, does not encompass . Quantum computers may aid in approximations or heuristics for NPC problems but won’t fundamentally resolve them in polynomial time unless , which remains unlikely.
Factoring. Reversing ECC operations. Decrypting all the data thought to be safely stored at rest in any non quantum resistant storage.
I do think ai algorithms could be built that quantum gates could be fast at, but I don’t have any ideas off the top of my head this morning. If you think of AI training as searching the space of computational complexity and quantum algorithms as accessing a superposition of search states I would guess there’s an intersection. Google thinks so too - the lab is called quantum ai.
It is unknown whether quantum computing makes NP-complete problems easier to solve. There is a complexity class for problems that can be solved "efficiently" on using quantum computing, called BQP. How BQP and NP are related is unknown. In particular, if an NP-complete problem was shown to be solvable efficiently with Quantum Computing (and thus in BQP), this open (and hard) research question would be solved (or at least half of it).
Note that BQP is not "efficient" in a real-word fashion, but for theoretical study of Quantum computing, it's a good first guess
AFAIK, which is not much, I believe it is problems that you can turn in to a cycle. Right now we pull out answers from quantum computers at random, but typically do not know what the inputs were that got that answer. But if you can get the answers from the quantum computer to be cyclical you can use that symmetry to get all the information you need.
