Quantum Speedup Found for Huge Class of Hard Problems
1 min read
Summary
The development of quantum algorithms that can outperform existing classical ones is seen as a key step in harnessing the potential of quantum computing.
Last year a paper was posted on the scientific preprint site arxiv.org describing decoded quantum interferometry (DQI), a quantum algorithm that works faster than any known classical equivalent at finding good solutions to a wide range of optimisation problems.
So far, no classical algorithm has been found that can outperform DQI, although it will be some time before the algorithm can be tested on quantum machines.
DQI works on a particular problem that requires finding a suitable function that passes through various points on a graph, with the ideal being a curved line that touches each point on the graph.
The significance of this particular problem is that it can be used in fields such as encryption and other areas of computer science.
Even if DQI remains theoretical rather than practical it could still inspire new work on classical algorithms.
