Mind the gap! New algorithm speeds up the quantum computations 

The paper presents a quantum algorithm to help boost the speed of the optimisation problems that quantum computers will solve.

These quantum algorithms are like going hunting for treasure in a deep, dark forest. You want to search quickly but you don’t want to be so quick that you miss the treasure. Depending on the algorithm you choose to guide you through this forest, there are also many walking paces and paths to choose from.

One such quantum algorithm, Grover’s algorithm, allows you to walk at a slow, methodical pace. Essentially, it allows you to walk in straight line search pattern around the forest as you search for a solution to your problem.

In contrast, the adiabatic algorithm is a bit more clever. It allows you to take a path and then vary your walking pace, only going slowly near dangerous “energy gaps” so you don’t fall down them and get totally lost!

But with the adiabatic algorithm you might not see these energy gaps. So, you may need to go, really, really slow to avoid the pitfalls.

In our “Mind the Gap” paper, we propose new algorithms with rigorous analysis that predict where the gaps are and, at these danger moments, we literally “jump” over the gap.

These algorithms can run faster that Grover’s algorithm while also providing you with the means to avoid those energy gaps.

The starting point for this work was Matt Hasting’s “shortest path” algorithm – we’ve contributed some new paths and proofs techniques. I began this work during by time at AWS and it was a joint project with Alex Dalzell, Nicola Pancotti and Fernando Brandão.

This work is a step forward but I believe we’ll still need to run faster through the forest, providing an even bigger speed up for these algorithms to unlock practical use cases.

The forest is vast and we’re only just beginning to cut some smart routes through it. Watch this space (and don’t forget to mind the gaps).