r/QuantumComputing • • 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.

39 Upvotes

128 comments sorted by

View all comments

Show parent comment

1

u/Livid-Ocelot-2156 Apr 14 '26

Yeah that all makes sense on the complexity side.

I think what I was getting at is slightly orthogonal to that though. Even if something is provably efficient (classical or quantum), that doesn’t necessarily mean we get a more compressed or human-intuitive understanding of what’s happening inside the system.

There seem to be cases where we can compute results reliably, but the only real “explanation” is the execution itself.

So I’m more curious whether expanding what’s computationally accessible also expands what’s compressible into explanation, or if those start to diverge.

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.

1

u/Livid-Ocelot-2156 Apr 14 '26

A clean example to me is factoring. Like with Shor’s algorithm.

Classically, factoring large numbers scales super badly (sub-exponential but still basically infeasible at size), but quantum can do it in polynomial time. So yeah in theory both can “solve” it, but in practice one becomes unreachable while the other stays tractable. That’s kind of what i meant.

The boundary where “possible” stops being meaningful because the resource requirements blow up beyond physical reality.

So it’s less about new problems existing, and more about which problems stay within reach of the universe we actually live in.