The Sycamore processor, which is a rectangular array of 54 qubits connected to its four nearest neighbors with couplers, contains one inoperable qubit, leading to an effective 53 qubit quantum computer. The optical image shown here illustrates the scale and color of the Sycamore chip as seen in optical light. (GOOGLE AI QUANTUM AND COLLABORATORS, RETRIEVED FROM NASA)

This 90 Year Old Math Problem Shows Why We Need Quantum Computers

To find the optimal route between many different locations, we need the power of quantum computers.

It’s time to run your errands, and you’ve got multiple stops to make. From your house, you have to hit the supermarket, the gas station, and the hardware store, all before returning home. Assuming you know that you begin and end at your home, there are six possible routes you can take, as you can either hit:

• first the supermarket, next the gas station, and then the hardware store,
• first the supermarket, next the hardware store, and then the gas station,
• first the gas station, next the supermarket, and then the hardware store,
• first the gas station, next the hardware store, and then the supermarket,
• first the hardware store, next the supermarket, and then the gas station, or
• first the hardware store, next the gas station, and then the supermarket.

But which one of these routes will be the most efficient path? This is known, in the field of mathematics, as the travelling salesman problem. To solve it for more than a handful of “stops,” it will almost certainly require a quantum computer. Here’s why.

For the ‘travelling salesman problem,’ a very large number of possible solutions exist, representing all the possible combinations of routes linking up a set number of points. For more than just a few destinations, the number of possible solutions to consider increases too quickly for a brute force approach to be effective. (SAURABH.HARSH / WIKIMEDIA COMMONS)

If you have any number of destinations that you have to visit, there will be one travel route that’s more efficient than all the rest: that wastes the least amount of time and distance travelling between them. The above example — about your home, the supermarket, the gas station, and the hardware store — had a total of four destinations, but only six possible paths. As it turns out, only three of those paths are unique, because each option (e.g., home ⇨ supermarket ⇨ gas station ⇨ hardware store ⇨ home) is one of the other options in reverse (e.g., home ⇨ hardware store ⇨ gas station ⇨ supermarket ⇨ home).

This is pretty straightforward for only a few stops, but the number of possible paths grows extremely rapidly: like a mathematical factorial. For 5 destinations…