Quantum computers could soon be able to solve genuinely useful mathematical problems faster than classical computers, claims quantum computing firm Quantinuum. It would be the first example of these exotic machines showing a true advantage over ordinary devices.
Such problems relate to a branch of mathematics called knot theory, which is used to classify knots by the number and nature of the points at which they cross over. The concept has been applied to cryptography, physics and molecular biology; it has even been suggested as a way for spacecraft to navigate and as the basis for a new type of quantum money.
The calculations involved grow extremely difficult for classical computers as the crossovers number increases, but now at Quantinuum and his colleagues have developed a quantum algorithm to do the job. What is more, they have also created a model that calculates how long the algorithm will take to solve a problem, based on both its size and the error rate and power of the quantum computer running the algorithm.
Advertisement
Using this model, the researchers have determined exactly where the threshold of quantum advantage lies for knot theory problems. For Quantinuum鈥檚 Apollo computer, , this point arrives at knot problems with just 2800 crossings.
Previous claims of quantum advantage have involved solving largely useless problems, but聽 at the University of Oxford says Quantinuum鈥檚 work suggests quantum computers could soon demonstrate genuine usefulness.
鈥淚f they run this on the next [Quantinuum] model and they can really outpace supercomputers, I would say that is going to be one of the first instances of quantum advantage for a problem that they didn鈥檛 just invent for the sake of running on quantum computers, you know? This is a pre-existing problem that people care about,鈥� says Kissinger. 鈥淚t gives me some confidence that we will see these kinds of interesting proofs of advantage within a year or two.鈥�
Another issue with previous claims, like Google鈥檚 first declaration of quantum supremacy in 2019, is that they are often later overturned by improved classical algorithms. Meichanetzidis says that he is keen to avoid such a scenario, and in fact, his team worked to improve the state-of-the-art classical algorithms for knot problems ahead of publication, to ensure that their model was as robust as possible.
鈥淚f we are brave enough to say that we are quantifying where advantage happens, where it kicks in, we have to be very stringent,鈥� says Meichanetzidis. 鈥淨uantifying quantum advantage should be done as rigorously, at least as rigorously, as we do it [at Quantinuum]. I think the quantum community should increase their standards for when they should say such words such as advantage.鈥�
arXiv
