Every time this comes up people say they're not actually useful for ML. Is that true? And if not what would they be useful for
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.
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.
Note that BQP is not "efficient" in a real-word fashion, but for theoretical study of Quantum computing, it's a good first guess