For computer scientists, solving problems is a bit like mountaineering. First they must choose a problem to solve — akin to identifying a peak to climb — and then they must develop a strategy to solve it. Classical and quantum researchers compete using different strategies, with a healthy rivalry between the two. Quantum researchers report a fast way to solve a problem — often by scaling a peak that no one thought worth climbing — then classical teams race to see if they can find a better way.
This contest almost always ends as a virtual tie: When researchers think they’ve devised a quantum algorithm that works faster or better than anything else, classical researchers usually come up with one that equals it. Just last week, a purported quantum speedup, published in the journal Science (opens a new tab), was met with immediate skepticism from two separate groups who showed how to perform similar (opens a new tab) calculations (opens a new tab) on classical machines.
But in a paper posted on the scientific preprint site arxiv.org last year, researchers described what looks like a quantum speedup that is both convincing and useful (opens a new tab). The researchers described a new quantum algorithm that works faster than all known classical ones at finding good solutions to a wide class of optimization problems (which look for the best possible solution among an enormous number of choices).
So far, no classical algorithm has dethroned the new algorithm, known as decoded quantum interferometry (DQI). It’s “a breakthrough in quantum algorithms,” said Gil Kalai (opens a new tab), a mathematician at Reichman University and a prominent skeptic of quantum computing. Reports of quantum algorithms get researchers excited, partly because they can illuminate new ideas about difficult problems, and partly because, for all the buzz around quantum machines, it’s not clear which problems will actually benefit from them. A quantum algorithm that outperforms all known classical ones on optimization tasks would represent a major step forward in harnessing the potential of quantum computers.
To read more, click here.