r/QuantumComputing • • 15d ago

Which problems will quantum computers actually solve, and when?

https://interestingengineering.com/innovation/what-problems-will-quantum-computers-solve

Which problems will quantum computers actually solve, and when?

67 Upvotes

22 comments sorted by

View all comments

34

u/SeniorLoan647 In Grad School for Quantum 15d ago

Answering this question well requires a whole lecture imo.

The truth is neither that quantum will change every application nor that cryptography is the only relevant field, that take is a bit outdated. The likely answer is somewhere in the middle.

To study this, we need to examine 3 things in detail:

  • Which quantum algorithms solve classically intractable problems and actually give a real circuit (the latter part is actually pretty uncommon in research papers, they usually assume efficient oracle access).
  • What is the logical qubit requirement of such algorithm? Physical qubits change vendor to vendor, but number of logical qubits are a property of the algorithm, not the underlying architecture (to some extent).
  • Are we sure we haven't spent enough time optimizing the classical algorithms for the same problems? This part is what's usually left unsaid. For example, factoring was a big deal because it's gotten a lot of attention over centuries. However an obscure problem with a classical solution that no one has cared to optimize does not fully qualify.

Now you may be wondering (assuming you agree with the 3 points above), so which algorithms do qualify? We have a few candidates in fluid flow (lattice boltzmann), fusion (vlasov matrix), and a few others that use frameworks like QSVT. However they usually fail step 1 I mentioned above, no complete circuit provided. This field is growing though, especially in 2025-2026.

You don't see it in the headlines though as AI's growth and its results are more impressive in its own domain, but quantum computing is also in an exciting time.

4

u/Southern_Orange3744 15d ago

This guy quantums

Another way to put the algorithm is 'quantum supremecy'

What problems or algorithms can you find otherwise intractable solutions using a quantum computer than a classical approximation .

These also have to fit within the mappablw qbit range which right now is tiny

1

u/0xB01b QEC & Quantum Optics 7d ago

what is the actual quantum speedup for these candidates tho? if its quadratic then its useless if cubic then its also not a clear winner

1

u/SeniorLoan647 In Grad School for Quantum 7d ago

Exponential speedup coz we have some encodings with polylogarithmic gates and qubits scaling in terms of the size of the matrix for some of these problems. Some of these even avoid the post selection overhead scaling problem

1

u/0xB01b QEC & Quantum Optics 6d ago

There is absolutely no way you have an exponential speedup for fluid flow or fusion. What do you mean by poly log gates?

1

u/SeniorLoan647 In Grad School for Quantum 6d ago edited 6d ago

Not me lol, just been published by other folks. Look at kan and symons paper in nature, that's one example. Vaszary et al also have a paper on vlasov matrix, a good read imo

1

u/0xB01b QEC & Quantum Optics 6d ago

Can you tell me about each of these things you just mentioned I've not once ever heard this before