Can Quantum Computers Solve Optimisation Problems? An Honest Look

Optimisation means finding the best option among a huge number of possibilities: the shortest delivery route, the cheapest schedule or the best mix of investments. Many of these problems grow explosively. A van visiting just 20 stops has more than 60 quadrillion possible round trips.

• ◆Quantum annealing, used by D-Wave’s machines, turns the problem into an energy landscape and lets the system settle into a low-energy state, ideally a good solution.
• ◆QAOA (the Quantum Approximate Optimisation Algorithm), proposed in 2014, runs on gate-based quantum computers and alternates between quantum steps and classical fine-tuning.
• ◆Grover-style search could, in theory, give a square-root speed-up for some search problems on future error-corrected machines.

Despite many experiments, there is not yet a convincing demonstration of a quantum computer beating the best classical methods on a real-world optimisation problem at practical scale. Classical solvers are extremely good, improve every year, and often find solutions that are close enough to perfect.

Theory also suggests caution: for the hardest general problems, quantum computers are not expected to give exponential speed-ups. Any advantage is more likely to be modest and specific to certain problems.

Optimisation matters so much to logistics, energy, finance and manufacturing that even small improvements could be valuable. Research into “quantum-inspired” classical algorithms has also produced useful tools. The practical approach is to run small, well-measured experiments and compare them fairly with strong classical baselines.