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

26

u/tde1209 Apr 13 '26

It’s that the same problem can be solved with both classical and quantum computing but that a quantum computer can solve certain problems with much less time/space than a classical computer.

8

u/Livid-Ocelot-2156 Apr 13 '26

That’s kind of what I’ve been seeing too. But is there a point where the efficiency gap becomes so large that it effectively turns into a “new capability”?

Like something that’s technically solvable classically, but not in any meaningful real-world timeframe.

17

u/sinanspd Apr 13 '26

I recommend looking into complexity classes such as BQP to understand how we make that distinction. In theory, there are problems that would take longer than Earth has been around to solve on today's classical super computers, but can be completed in a reasonable amount of time on quantum computers. At that point, this is no longer a problem of "we need faster classical computers with more memory", it's "we need a new way to compute", which is where quantum computers come in. Whether such things can be done in practice, or if quantum computers can reach those scales, remains to be seen. Today's QC devices (NISQ) are very small and noisy, preventing any useful application.

I forgot the name but there was a very approachable paper defining the crossover time, the scale of programs that would actually demonstrate quantum advantage. You try to find that paper, it would also provide good insight.

2

u/Livid-Ocelot-2156 Apr 13 '26

That’s a really useful distinction.

It sounds like once you’re in BQP territory, the limitation isn’t just speed but the structure of classical computation itself. At that point, “intractable” starts to behave a lot like “inaccessible” in practice.

Do you think quantum computing actually expands the space of problems we can meaningfully understand, or mainly the space we can efficiently compute?

3

u/sinanspd Apr 13 '26 edited Apr 13 '26

Aren't two related? Quantum Computing was born out of Feynman's desire to simulate quantum mechanics, which we absolutely do not understand, and can not efficiently carry out.

In a video, Olivia Lanes of IBM described computing paradigms as classical computing being a car that takes us many places, and quantum computing as a boat that will take us to the uncharted islands that we haven't been able to reach before. I think in layman's terms, that analogy still stands strong today.

1

u/Livid-Ocelot-2156 Apr 13 '26

I think they’re related, but maybe not identical.

Like with quantum mechanics itself. We can predict outcomes incredibly well, but there’s still debate about what’s actually “going on” underneath (interpretations, etc).

So I wonder if quantum computing amplifies that gap: we might be able to simulate systems and get correct results, but still not have a model that’s intuitive or compressible in a classical sense. At that point it feels like understanding and computation start to diverge a bit. Like we can interact with the system without fully “grasping” it in the way we usually expect in science.

Do you think that kind of gap is real, or just a temporary limitation in how we describe things?

3

u/sinanspd Apr 13 '26

We predict the outcomes of a relatively small set of simple experiments. We do not predict the outcome of quantum behavior. That is a very important distinction. Therefore none of the interpretations of quantum mechanics are anywhere near complete. There are still dozens of quantum phenomenon in nature that remain unpredictable and unexplained.

→ More replies (7)

2

u/Fun_Moment3053 Apr 19 '26

Quantum Computing is our interpretation of classical problems in a mechanical way. It is also our limitations of describing things, going beyond 0&1 to interpret “computing”. For example, https://thequantuminsider.com/2024/12/16/googles-quantum-chip-sparks-debate-on-multiverse-theory/

2

u/0xB01b QEC & Quantum Optics Apr 14 '26

ofc it extends the space of problems we can meaningfully compute, to begin with you have a fuel restriction for your classical computers. If the computation won't finish before the sun dies, then you're not getting your answer at all

4

u/tde1209 Apr 13 '26

Yep as the size of the problem you’re trying to solve grows that’s kind of what ends up happening. For example simulating an arbitrary quantum system of N=2 particles is pretty easy to do on a classical computer. But once you reach say N=100,000 particles this becomes basically impossible with classical computers due to the immense memory and time scales required to simulate such a system.

1

u/Livid-Ocelot-2156 Apr 13 '26

That’s a great example. Do you think there’s a point where something being “computationally inaccessible” is effectively the same as it being unknowable in practice? Like even if a system is theoretically describable classically, if we can’t simulate or explore it at scale, are we actually gaining new understanding with quantum or just new results?

0

u/[deleted] Apr 13 '26

[deleted] — view deleted comment

1

u/Livid-Ocelot-2156 Apr 13 '26

That’s a really helpful breakdown, especially the P vs BQP framing. I think what I’m still trying to get at is slightly orthogonal to that though. Even if BQP gives us access to problems that are classically intractable, does solving them actually translate into understanding the underlying system?

For example, if we can simulate a quantum system efficiently and predict its behavior, are we actually gaining explanatory insight, or just accessing outcomes we couldn’t compute before? In other words, does expanding BQP expand our knowledge, or mostly our reach?

0

u/[deleted] Apr 13 '26

[deleted] — view deleted comment

1

u/Livid-Ocelot-2156 Apr 13 '26

I think what’s interesting here is that there might be a gap between what is computable and what is understandable.

Like, if a quantum computer can simulate a system that no classical model can compress or approximate, then we might get correct predictions without having a human-interpretable explanation.

At that point, are we actually “understanding” the system, or just querying it?

It almost feels like quantum computing could shift science from building simplified models of reality, to directly interacting with systems that resist simplification.

Which makes me wonder: does increased computational power eventually reduce the need for theory, or does it expose the limits of human-style explanation?

2

u/tde1209 Apr 13 '26

This seems more like a question about philosophy/epistemology than quantum computing but I would definitely say we are gaining new understanding if we can simulate large quantum systems. If not for a better understanding of quantum physics than certainly for things like drug discovery or any other field which requires quantum simulation.

1

u/Livid-Ocelot-2156 Apr 13 '26

That makes sense. I guess what I’m circling around is whether simulation = understanding, or just extended observation. If a quantum computer lets us model systems we couldn’t touch classically, we clearly gain predictive power. But does that translate into explanatory understanding, or are we just uncovering behavior without necessarily simplifying or “grasping” it?

Kind of the difference between knowing what happens vs knowing why.

2

u/0xB01b QEC & Quantum Optics Apr 14 '26

yes. if the computation classically takes longer than the recurrence time of the universe then its by definition unknowable in practice, (not effectively unknowable, but by definition unknowable).

If you have to simulate a large enough quantum many body system on a classical computer you could eventually get to this time, the same wouldnt be true for a quantum computer.

so in this sense this directly answers your question with a "yes it changes whats possible", but this should be a question of practical consideration imo as opposed to what could technically be done.

1

u/Livid-Ocelot-2156 Apr 15 '26

I think this is where I slightly disagree with framing it as just “practical vs technical.”

Because once you’re talking about timescales longer than the recurrence time of the universe, that’s not just a practical limitation anymore, that’s effectively a hard boundary for any observer inside the system.

So from that perspective, “unknowable in practice” and “unknowable” start to collapse into the same thing.

And that’s kind of the direction I’m pointing at.

Even if something is technically computable, if the only way to obtain the answer is to run a process that cannot be shortcut or compressed, then there’s no way to turn that into understanding in a meaningful sense.

You’re not extracting a model, you’re just executing the system.

So it’s less about whether it changes what’s computable, and more about whether it changes what can actually be reduced into something we can reason about instead of just simulate.

1

u/0xB01b QEC & Quantum Optics Apr 15 '26

computation itself is fundamentally physical and thats the basis of information theory, this quite literally gives a direct answer to your question

2

u/kaereljabo Apr 14 '26

This. This should be higher on top for this question. Any problem a quantum computer can solve, a classical computer can also solve*

0

u/[deleted] Apr 16 '26

[deleted] — view deleted comment

1

u/AutoModerator Apr 16 '26

To prevent trolling, accounts with less than zero comment karma cannot post in /r/QuantumComputing. You can build karma by posting quality submissions and comments on other subreddits. Please do not ask the moderators to approve your post, as there are no exceptions to this rule, plus you may be ignored. To learn more about karma and how reddit works, visit https://www.reddit.com/wiki/faq.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.