Quantum computing will soon have its AI moment—this has been the kind of optimism from both within and outside the community around the subject. But now there is a study arguing that one of the primary algorithms offered as evidence showing the potential of quantum provides no practical speed-up when compared to classical systems. 

“The cases where mathematicians have proof that quantum computers would be faster than classical ones are out of range now, or will be out of range at least for decades,” said Xavier Waintal, one of the authors of the study. “This means that we are left with cases where we have absolutely no reason to believe that we will have an advantage, but maybe if we are lucky, it can be faster for some problems.”

Out of range because the current technologies simply don’t enable that. Even the best quantum computer right now—say of 5, 10, or 20 qubits, using advanced error mitigation techniques—fails to solve problems which classical systems can do in milliseconds. On top of that, it provides the correct answer only 15% of the time. 

Over-optimistic? 

The kind of algorithms supposed to run on quantum computers are very few, and they solve very specific problems. It’s also very difficult to imagine that there will be an industry only for specific problems, considering the difficulty in building a quantum computer. So, for this to happen, we must find at least a large spectrum of applications—maybe not as large as what classical computers do today. 

“Grover’s algorithm gives exactly that,” said Waintal. “The so-called NP complete problems, which are a large set of hard problems, can be solved in principle with this algorithm.” So, it plays an important role especially on the side of the mathematicians writing quantum algorithms. 

Grover’s algorithm uses a concept called an ‘Oracle’, which is essentially a function. It takes an argument ‘x’ and returns ‘1’ if x is a solution, and ‘0’ if x is not a solution. A very important assumption that Grover makes is that you can only call this function—“It’s like having some photocopies of [some place] that you can only connect through some quantum channel.” 

But, as the researchers argue in their paper, if you can only call the function, there is nothing else you can do except for calling the function for every single input ‘x’ until you find that one x which gives the output value as ‘1’. 

“It is an abstract speed-up that considers the oracle as a black box function and counts the computational cost solely in terms of the number of calls to the oracle,” they assert.  

No quantum advantage

To test whether quantum really is useful, researchers built a classical algorithm and pitched it against a quantum-inspired algorithm—which basically mimics Grover’s algorithm for a classical computer—for a particularly large problem. In addition, they made all kinds of hardware assumptions when implementing the quantum algorithm. The assumptions include taking a quantum computer of up to 70 qubits, and putting some number on it—say, make it “ten times faster” using the best quantum technology—and ignoring that it is error-prone at all. 

They found that even if they somehow manage to “reduce the error rate by a factor of 10,000 (which is too optimistic a claim)”, they’re still looking at some “astronomical computing time” before the proposed theoretical quantum advantage can be seen. 

Hence, while it makes sense for the algorithm to be perfectly fine from a theoretical perspective, its actual implementation—which would require defining a particular problem—“will have no real quantum advantage to be seen”. 

“Maybe there are problems somewhere out there where we can really see a quantum advantage, but we don’t know them yet,” Waintal emphasised. 

The paper essentially rules out the possibility of a quantum computer that can serve as a general-purpose computer. “Thinking about it,” he reflects, “While quantum science will continue forever, quantum computing will not necessarily be so”.

Amidst all this, in the background, reports speculate that the quantum computing market size will hit USD 125 billion by 2030. It seems as if much of the quantum wave is riding on the horse of these over-optimistic numbers—not only from market research companies, but also from researchers—irrespective of its practical application. 

The practical question  

Computer scientist Scott Aaranson, in his blog, criticised the researchers’ claim that a fault-tolerant quantum computer, which can reduce noise and decoherence in these systems, would require an enormous overhead, thus pushing a practical Grover speed-up far into the future. According to Aaranson, “If Grover’s algorithm can yield any practical advantage in the medium term, it will either be because we’ve discovered much cheaper ways to do quantum fault-tolerance, or because we’ve discovered ‘NISQy’ ways to exploit the Grover speed-up, which avoid the need for full fault-tolerance—for example, via quantum annealing”.

In response to the critics, Waintal said that while many of the people [critics] are interested in abstract statements, their paper asks if it’s practical or not, and so far they see no window as to how it will work in practice. 

“I think these people are not interested in this question, or they kind of know or agree with us, but they don’t want it to be advertised,” Waintal concluded.