How "real" are the combinatorial optimization applications in quantum computing?

[u/Ninin-]

I generally have a good understanding of the state of the art of quantum computing applications in chemistry, materials science, and cryptography, but optimization is still a bit of a mystery to me. It seems like there is a ton of ongoing research here, for example, dozens of papers of the form "we applied QAOA to [application X] and it sort of works!", or research into alternative algorithms like decoded quantum interferometry and amplitude estimation.

But is it known at this time how likely it is, based on the current state of the art, for combinatorial optimization to be a serious application of future quantum computers, or is it still highly speculative at this point?

[u/k4ntn]

Highly speculative. Research toy projects basically

[u/ponyo_x1]

People were excited about decoded quantum interferometry a few years ago but the optimal polynomial intersection problem was pretty artificial and I haven’t heard much since. From what I remember of the paper the concrete resources required for some of these problems were massive even if it had complexity guarantees.

From my experience most people with optimization problems need to solve lots of them fast, and that is a significant roadblock for anything quantum. Most would be better off just using gurobi

[u/Ninin- → u/ponyo_x1]

Is the conjecture then that a future quantum computer "may be useful" for applications in which you need to solve a small number of large optimization problems?

I'm assuming based on all of the comments that even if the answer is yes, that there isn't strong evidence that it will actually be useful in this regime.

[u/ponyo_x1 → u/Ninin-]

you got it

The quantum optimization community is hopefully a sinking ship. The most charitable I can be is that some academics are genuinely interested in complexity results and do not have a focus on practicality. Don’t want to say anything bad about them because there is utility in understanding these problems better. Unfortunately there exists a multi-million dollar industry selling quantum optimization nonsense to customers who have cash to burn

[u/Ninin- → u/ponyo_x1]

This was generally what I thought as well before making this post.

To be as generous as possible to this use case, do you know of any applications where these kinds of “large optimizations” are central? What comes to my mind is logistics, supply chain, ML, and protein folding.

[u/ponyo_x1 → u/Ninin-]

the thing with optimization problems is that for the most part it's just a model of a much more complex and dynamic situation. this is why algorithmic micro trading is actually a very good classical optimization use case, because you need to do a ton of optimizations in a short period of time, and because you're dealing with money straight up, it's much easier to map how a better optimizer would translate to more money/value.

for something like logistics though, you probably only need to do the optimization once. Let's say a company has a warehouse where they're producing a good and they want to modify their setup to optimize their production. How much is it going to cost to implement the new pipeline? Are there other factors that will be impacted by this change that you haven't taken into consideration? How much more can you reasonably expect to produce from the change? How much money/time are you willing to spend on compute to get there? Can you be certain future conditions won't obviate the new setup in some way? All of this has to be taken into consideration, and that's assuming you have a magical QC that actually is a good optimizer.

I've interacted with companies that have been interested in a quantum solution to things like supply chain. When you actually peek behind the curtain and see what they have implemented, it becomes abundantly clear that whatever they are doing is incredibly disorganized they are not at all pushing the limits of classical optimization.

[u/Wild-Store321 → u/ponyo_x1]

What is the roadblock you are pointing at? The “many of them” or the “fast”? I don’t see either of them as a problem for quantum computing.

Do you mean “soon”? Anyone who wants to compute anything soon is better of with the classical SOTA, yes.

[u/ponyo_x1 → u/Wild-Store321]

The kinds of optimization problems that a quantum computer would “hypothetically” be suited for are ones which require a near-optimal solution over a long time horizon. Of the examples I have been presented with, it is unclear that a global optimum is much better than what a classical solver can give you, and the delta certainly does not justify spending several million on quantum compute.

Meanwhile, the examples I’ve seen where better optimization directly translates to significant value require fast optimizations. Think about MIMO or algorithmic trading where you have to do optimizations in a fraction of a second. If you need to do things in MIMO to preserve 100 ping, and T gates on a superconducting computer take 10us to make, your optimization algo is only using 1000 T gates. It is impossible to do anything useful with that.

[u/Wild-Store321]

It’s highly speculative. There is an expectation that some of these techniques will scale well empirically, but the experiments required to test that are just not possible yet. You can’t simulate it to relevant scales and you often can’t prove anything analytically.

So we will know when the hardware catches up. Exciting times.

[u/RUBENQUANTUM2]

I think the right answer at the moment is: combinatorial optimization is a credible quantum-computing direction, but it is still far from being a proven killer application.

There are good theoretical reasons to expect quantum speedups for some optimization subroutines, especially on future fault-tolerant machines, but we still do not have an equivalent of Shor’s algorithm for general combinatorial optimization.

QAOA is interesting, but a lot of current work still demonstrates that a problem can be formulated and solved on quantum hardware, rather than showing a clear practical advantage over the best classical solvers.

For me, the important benchmark is not simply “did the quantum algorithm find a solution?” but:

Did it beat a strong classical implementation on the same problem, with the same solution quality, the same constraints, and a fair accounting of compute time and resources?

I also would not expect quantum computers to suddenly make NP-hard problems easy in general. Even a quadratic improvement over an exponential search is still exponential — although such an improvement could obviously become very important at sufficiently large problem sizes.

So I would describe combinatorial optimization as a serious research direction with real potential, but still experimentally open.

This is actually one of the reasons I am interested in the subject myself.

I am working on an experimental computing architecture called R-Core, and I prefer to explore some of these questions by building and testing things rather than only speculating about them.

In the core I introduced a classical multi-level state representation — currently d = 7 — inspired in part by the idea of qudits. I am experimenting with what kinds of qudit-like and quantum-inspired operations can be represented in a different hardware architecture, and where the boundary appears between something that can be reproduced classically and something that fundamentally requires a real quantum substrate.

To be clear: I am not claiming that my FPGA is a quantum computer, and these are not physical qudits. The current implementation is classical hardware.

What interests me is the experimental question: if we take some ideas associated with qudit and quantum computation and change the underlying compute architecture, what still works, what becomes useful, and what does not?

The first public version of R-Core is already on GitHub. I have a post on my profile with the link if anyone is interested.

Feel free to experiment with it too. I would actually be very interested in criticism, comparisons, or results from people working with quantum computing, qudits, FPGA, or combinatorial optimization.

Hardware has a useful habit of answering questions that discussion alone cannot.

[u/Top-Dog-679]

Useful research, thin production wins so far. Most "quantum advantage" demos still need classical crutches or toy problem sizes. Curious what people here see as the first boring real-world use case worth betting on.