The search for a ‘quantum advantage’
Proving a quantum computer to be quicker than a normal one is one step closer. After a breakthrough in speeding up classical algorithms, researchers Vedran Dunjko and Casper Gyurik showed that only one quantum algorithm could beat its classical counterpart. They discuss their discovery in Quanta Magazine.
There is a class of algorithms for machine learning that was considered most promising to have a so-called quantum advantage: these could be much faster on a quantum computer than would ever be possible on a classical machine. But in 2018, the 18-year-old Ewin Tang found a new way for classical computers to perform many of these calculations, eliminating the potential quantum advantage. Gyurik and Dunjko showed in collaboration with the Dutch quantum software research centre QuSoft that one algorithm was left standing: one for topological data analysis (TDA). Dunjko: ‘There were reasons to believe that this one maybe survives the “Tangization”.’
‘We had to be flexible in our approach’
‘The topic of my PhD research is quantum machine learning,’ says Gyurik. ‘Trying to find out how quantum computing could improve machine learning methods is important since they are employed all around us in daily life.’ Gyurik provided most of the proof to show TDA could not be beaten by Tang’s method. ‘It was a very cool experience,’ he says. ‘The fact that we did not know the answer to the question “Is there a classical algorithm or not?” when we started looking into this was exciting. We had to be flexible in our approaches and leave both answers open as a possibility.’
There is still a chance that new classical methods will be developed that truly put quantum TDA to the test. But both researchers are excited about the future. ‘It is a story, not history,’ says Dunjko. Gyurik adds: ‘It feels like just the beginning of much more interesting research to be done!’