pull down to refresh
There's no single-sentence answer to "which problems have a fast quantum algorithm?," in exactly the same way as there's no single-sentence answer to "which problems have a fast CLASSICAL algorithm?" The answer is a course or a textbook, not a sentence!
Having said that, the problem solved by Grover's algorithm is actually exceedingly general: it's simply searching through a list of n items for a desired item. And it can be generalized even further than that. The trouble with Grover's algorithm is not at all its generality; rather, it's that the speedup is "merely" quadratic.
Ah, I know it's too late since you already signed off, but on the off chance that you see this, I thought I should clarify. I was referring more to the generalizability of the physically built system and not the algorithm. For example, does a different physical system need to be built to do Shor's Algorithm vs Grover's Algorithm, or can one physical system do both? And then to generalize that further, can a single physical system be built that can implement arbitrary quantum algorithms? Thanks.
I've watched some videos about how Grover's Algorithm works and found it to be an ingenious, but also highly specific design for solving a particular kind of problem.
How should a layperson like myself understand quantum computing in terms of generalizability? Is there a "general quantum computer" design that can be applied for all kinds of computational tasks, like modern electronic computers do? Or does a different specialized system have to be designed for different tasks?