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.”