Strengths and weaknesses of quantum algorithms

Although building a large practical quantum computer is still a long-term project, over the past two decades researchers have made great progress in building rudimentary quantum hardware and in developing quantum algorithms, the computational recipes that can run on quantum hardware. This progress has created a lot of interest from various industries to investigate whether quantum computers can solve their computational problems much faster. The big question is which problems can be solved faster and when this is going to become reality.

Investigating which problems can be solved on a quantum computer and determining when a quantum computer will outperform a classical computer, is a research field in which CWI excels. In recent years, CWI researchers have determined limits of what quantum computers can and cannot solve. Ronald de Wolf, senior researcher at CWI: “The complexity of solving a problem on a quantum computer has an upper and a lower bound. Finding a quantum algorithm gives you an upper bound: you can show that you can solve a certain problem with a certain efficiency on a quantum computer. At CWI we have developed a number of new quantum algorithms for some optimization problems and other tasks, using tools like quantum amplitude amplification and quantum random walks.”

Large computational problems

Harry Buhrman, former Algorithms & Complexity group leader at CWI and executive director of QuSoft, has discovered a fundamental lower bound of quantum algorithms: even a quantum computer cannot solve a given problem faster than this lower bound. Buhrman: “Assuming a quantum version of the so called exponential-time hypothesis, which says that brute-force search is the best one can do for certain constraint-satisfaction problems, we have shown that for many problems quantum computers give at best a quadratic, and often even less, speedup in the time needed to solve them. For many computational problems such quantum fine-grained complexity explains why a quantum computer doesn’t give you more than quadratic speedup.”

De Wolf: “A practical quantum computer needs a lot of error correction which basically slows down its computational speed a lot: one basic quantum operation is a lot slower and more expensive than one basic operation on a classical computer. Because for many problems a quantum computer gives at most a quadratic speedup, you can calculate that you only get to the crossover point after which the quantum computer beats the best possible classical computer for really large computational problems.”

In a way this new result is bad news for companies and academic researchers that were hoping to solve those problems soon on a quantum computer, because a sufficiently large quantum computer quite probably will not arrive in the next twenty to thirty years. “But it is our mission to find the truth, no matter how hard it hits”, says de Wolf.

Leading role

Exploring the strengths and weaknesses of quantum algorithms perfectly fits into CWI’s long history in the field of quantum computing. Ever since the birth of the field in the mid-1990s, CWI researchers have played a leading role. In 2015 CWI and the University of Amsterdam (UvA) jointly established the world's first quantum software research centre, called QuSoft. “Here we combine research in mathematics, computer science and physics in order to build the foundations of quantum informatics”, says Buhrman. “QuSoft presently has around seventy junior and senior researchers, some twenty of whom are employed by CWI, but many of the others also have an office at CWI.”

For the near future de Wolf and Buhrman have a few ideas to explore the boundaries of quantum computing further. One idea is to look for useful applications of quantum computers with a few hundred qubits, which may already be able to outperform classical computers for certain chemistry problems. “We think that we might be able to reach large quantum speedup there, but we are not sure yet”, says Buhrman. “If so, this could lead to very useful applications within ten to fifteen years.”

Another idea is to develop quantum algorithms that give a more than quadratic speedup for certain optimization problems. De Wolf: “I would also like to try to break cryptographic systems that are based on recently chosen new post-quantum cryptography standards, similarly to how Shor’s quantum algorithm breaks well-established cryptography such as RSA.”

Buhrman would like to look beyond the worst-case analysis that led him to discover a lower bound for the performance of quantum algorithms: “It could be that there are particular problems for which quantum algorithms can do better than in the general worst-case analysis that we have done. An example could be deep learning neural networks. It is known that these networks in general cannot be trained efficiently in the worst case. But in practice they can be trained well because people don’t solve the worst-case instances. I would like to investigate whether we can find more problems for which a quantum heuristic leads to more than quadratic speedup.”

Author: Bennie Mols