# Where is the quantum advantage?

Quantum computing promises to elevate our ability to solve major optimization problems. As shown in this post, a traveling salesman problem with just 50 cities already has an intractable amount of possible paths ($\mathcal{O}(n!)$). There are better exact algorithms than simply bruteforcing - for instance, the Held–Karp algorithm has a time complexity of $\mathcal{O}(n^2 2^n)$. This is still extremely bad and exponential. There are heuristics and approximation algorithms however, that find a sensible solution (with it being for example less than 5% away from the optimal solution) in a reasonable time. These algorithms find solutions for problems of sizes with tens of thousands of cities. Combinatorial optimization problems all share the same issue of scaling very badly, as shown with the traveling salesman example.

In the following, related work is listed that suggests that quantum computing not only promises a quantum advantage in the (potentially far) future, but already shows first successes and signs of it happening in the next years. However, a few challenges are also noted.

Guerreschi et al.¹ show that for Maximum Cut, QAOA will likely exhibit a quantum speedup against AKMAXSAT (one of the best classical Maximum Cut solvers) - though it will likely be achieved at multiple hundred QuBits, i.e. the scaling is very favorible in the limit, but with the current NISQ compute, smaller problem instances are best solved with classical compute.

Calaza et al.⁵ show a clear advantage of hybrid solvers and qbsolv against tabu search in terms of the energy attained when solving the garden optimization problem. While the execution time is larger, the scaling is better.

An even clearer advantage of the 2000 QuBit machine of D-Wave is shown when solving Maximum Clique. Djidjev et al.⁸ benchmark QBSolv (with D-Wave 2000Q) against a set of classical solvers (fmc, PPHa, SA-clique) and show that QBSolv completely outperforms after graph size 800 in terms of the solution quality. While this requires a larger benchmark against more Maximum Clique solvers, this is an indication of a clear quantum (hybrid) advantage, at least for the single problem Maximum Clique. The following Figure shows the advantage.

• Figure from Djidjev et al.

Another problem type that fits quantum comptue well is Graph Partitioning. Ushijima-Mwesigwa et al.⁹ show that pure quantum matches top Graph Partitioning solvers (METIS, KaHIP), and hybrid quantum methods (QBSolv) even outperform. Similarly to the Maximum Clique problem, this problem scales linearly with the number of edges.

Willsch et al.³ show that the 5000 QuBit machine by D-Wave can solve exact cover problems with up to 120 logical QuBits. This allows finding the exact cover of 120 flight routes and 472 flights. This is something the 2000 QuBit machine is not able to do. Willsch et al. also show a multitude of other factors that lead to the conclusion that the 5000 QuBit machine is a major step-up from the 2000 QuBit machine. If this trend continues, a similar law (for quantum compute) as to Moore's Law (for classical compute) may arise.

It should be noted that while this is a very interesting use case, not all problem types allow such a scaling right now. Stollenwerk et al.⁴ for instance show that for the flight gate assignment problem, on the 2000 QuBit machine, only up to 10 flights/gates are possible to be solved.

Phillipson et al.⁶ show that a hybrid quantum solver on the latest D-Wave machine (5000 QuBits) comes very close to optimal solutions (3% away from it) for portfolio optimization problems of larger sizes, while not increasing the time to solution (the computation time) much at all. In contrast, for the best solver, LocalSearch, which is a classical one, though it always finds the optimal solution, it begins to scale badly the larger the problem sizes get. At least with hybrid algorithms, this suggests that a quantum advantage and interesting business use cases may arrive very soon.

Perdomo-Ortiz et al.⁷ show a very interesting result that again underlines the very favorable scaling of quantum (or hybrid) algorithms versus classical ones.

Still, quantum compute is not the holy grail - Vert et al.² show multiple cases of the bipartite matching problem that indicate that quantum annealing also has the same pitfalls as classical simulated annealing, namely, by getting stuck in local minima that result in a suboptimal solution returned by the hardware.

Ajagekar et al.¹⁰ show that QBSolv with the D-Wave 2000Q machine completely fails on the unit commitment problem and the heat exchanger network synthesis problem in terms of both solution quality and runtime. The same work shows a clear quantum advantage for Quadratic Assignment though. It is quite interesting that for these problems the QUBO scaling is very unfavorable.. While this does not imply a causation, it is a very interesting observation.

Also, since we are currently in the NISQ era, hybrid approaches are currently mostly interesting (as seen in the paragraphs above, they even sometimes show a quantum advantage) - the interested reader is refered to this post for a list of hybrid approaches.

To summarize: There is still no definitive quantum advantage for a problem type, but there are first problem instances and indications where hybrid approaches outperform classical ones. The developments of the next few years (and not the far future) will be extremely interesting.

Note: I will update this post when I see new interesting papers in this direction.