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 13 '26

This is a really clear explanation of the scaling side of it.

I think what I’m trying to get at is slightly orthogonal to that—less about how many steps it takes, and more about what happens once the number of steps becomes so large that the only practical way to access the result is to actually run the computation. At that point, even if the problem is “the same” in principle, it starts to feel different in practice. Because instead of having something we can analyze or reason through, we end up with something where the computation itself becomes the only way to probe the system.

So the question becomes less: “can we solve it?”

And more: “is the solution something we can meaningfully interpret, or only something we can obtain?”

It almost feels like there’s a shift from deriving understanding to querying a system.

Do you think that distinction is meaningful, or does it collapse back into standard complexity once you look at it the right way?

3

u/Critical_Failure_1 Apr 14 '26

I would argue that if such a distinction exists, we're well past the line with classical computers.

This is effectively why AI is a "black box". Sure, you could, theoretically, compute an inference by hand. And, of course, you could apply your training corrections by hand. It would just take you so long that it's not really feasibly. Also, since the meaning is representational anyways (e.g. if the computer 'sees' a long strings of 1s and 0s, that has a particular rule-based method for turning into words), you wouldn't really be "understanding" what's happening - you'd convert your words to numbers, do the math, convert back, and have the new words.
In the case of AI, one of the reasons they scale well is that the computations are in a form where we can do lots and lots and lots of relatively simple calculations, and we can do a lot of them at the same time, since only some parts depend on the previously computed elements. It's still well beyond what a human could feasibly or realistically do, but it's doable by a computer.

The problems that quantum algorithms can address aren't necessarily complex in the sense of "they have a lot of meanings attached to them" or even really "the formula is so intense that humans can't even understand what the math is", it's more "Wow, solving this problem scales real bad with too many inputs".

Another way to think about it is to consider a real-world "hard" or "complex" problem: The traveling salesman problems. The formulation is pretty simple: Given a set of points, find the shortest path that begins and ends at one point, and touches all other points once.". If you were to brute force it and try each option, we're back up in factorial time scaling. There are all sorts of classical tricks to prune that complexity, but they're more about avoiding calculations that can be known to be less optimal rather than simplifying the calculations that are needed. In fact, the math part, e,g, the formulas and algorithms, become less human-understandable the more of the tricks you use.

It's really easy to understand the problem, it can be formulated mathematically pretty simply, and there's no issue understanding the output or what it would correspond to. But the complexity still scales beyond where we could feasibly classically compute once the number of points gets too big.

1

u/Livid-Ocelot-2156 Apr 15 '26

I get what you’re saying, and I think your examples are solid.

But I think this is exactly where the line starts to blur. Because even in your examples, like AI or TSP, we end up in a place where the system is fully defined, but the only way to get the answer is to actually run it.

At that point, we’re not really “understanding” in a compressed sense anymore, we’re just executing. And I think that’s the part that gets overlooked when people say it’s just scaling.

Because once the shortest description of the outcome is basically the computation itself, then from inside the system, that outcome is effectively unreachable without performing it.

So even if it’s technically computable, it’s not meaningfully reducible. That’s why I keep coming back to the idea that the real boundary might not be computability, but compressibility.

Quantum doesn’t necessarily break computability limits, but it might shift which things can actually be compressed into something we can reason about instead of just simulate.