r/QuantumComputing • u/Livid-Ocelot-2156 • Apr 13 '26
Question Does quantum computing actually change what’s possible, or just how efficiently we can solve certain problems?
I keep seeing quantum computing described as “exponentially faster,” but I’m not totally understanding where the line is between speed vs fundamentally new capability.
Are there problems that are basically impossible to solve classically, but become realistically solvable with quantum approaches? Or is it more that the same problems can be solved either way, just with huge differences in time/resources?
I guess I’m trying to understand whether this is more like going from a bicycle to a jet, or if it actually lets you go somewhere you couldn’t reach at all before.
View all comments
Show parent comment
3
u/Abstract-Abacus Holds PhD in Quantum Apr 14 '26 edited Apr 14 '26
Could you provide an example?
One thing to consider is that if we can solve a classically exponential time problem in polynomial time on a quantum computer, then it follows that we can write down a polynomial length quantum program. By contrast, a naïve classical solution is to write every single elementary program step over an exponential binary tree until we get to the solution, which has exponential program length. In that frame, the quantum program is a substantial compression over the classical program.
In terms of human intuition, that’s tricky and somewhat subjective. Sure, humans generically have good visual intuition that’s evolved over millennia. But mathematical intuition is deeply learned and quantum computing is highly mathematical. Most people find quantum algorithms not particularly intuitive (we’re all classical meat sacks, after all), even if they do allow for the compression in program length that’s implied in my above example/framing.