A classical algorithm to evaluate the performance of quantum computers

Diagram showing the upper and lower limits of magnetisation for the thermal equilibrium state

Omar Fawzi is a director of research with the project team QInfo (Optimal Information Processing with Quantum Devices) a joint undertaking with ENS de Lyon, Claude Bernard University Lyon 1 (UCBL) and Grenoble Alpes University. In 2021 he was awarded a five-year European Research Council (ERC) grant to fund the development of classical algorithms for use in quantum computing, which runs until 2026.   

One of the most exciting results from this project was recently published in the prestigious journal Nature Communications. 

“I am conducting this research alongside my brother Hamza, who is a researcher within the Department of Applied Mathematics and Theoretical Physics at the University of Cambridge”, explains Omar Fawzi. “Together with his PhD student Samuel Scalet, we discovered a family of algorithms capable of calculating the properties of quantum systems, the goal being to evaluate them and produce a benchmark for quantum simulation algorithms.” 

Before going any further, it’s time for a quick refresh of the basics of quantum theory. Developed in the 20th century, it describes the behaviour of particles. Unlike classical physics, in which a system can only be in one state in a specific location at a given time, quantum systems can simultaneously be in a coherent superposition of all possible states, which is what makes describing them so difficult. 

“Imagine a system with n particles”, says Omar Fawzi. “Each particle has a “spin”, the value of which is either “up” or “down”. If I am to describe this system, I need 2 (up and down) to the power n = (2n) parameters.” As this shows, the exponential nature of quantum systems makes them much more complex than classical systems, which are binary (made up of 0s and 1s).

This complexity makes it harder to predict (and therefore to understand) the behaviour of quantum systems made up of multiple particles. Faced with this obstacle to the use of quantum mechanics, in the 1980s physicist Richard Feynman came up with the idea of designing a computer capable of simulating these systems by harnessing the laws of quantum physics. 

The following decade saw a minor revolution as computer scientist  Peter Shor designed a quantum algorithm capable of expressing very large numbers as a product of their prime factors in record time. No classical method has been developed that is capable of doing this quicker.

However, only the mathematical model for quantum computers is effective, hence the reason why they are still very much in the development phase. How will the breakthrough made by Omar Fawzi and his team help move things along? 

“We came at the problem from a different angle, employing the use of a classical algorithm”, explains the researcher. “This isn’t an entirely new idea - many physicists use them to identify the physical properties of the quantum systems that they're studying What sets our research apart is the ‘generality’ of our algorithm.” The main advantage with this algorithm is that it can be used to calculate the physical properties of any quantum system.

Another advantage is that it has the capacity to certify the results obtained. “In response to this complex problem, we developed an algorithm capable of producing acceptable results within a limited time”, explains Omar Fawzi. “This algorithm is ‘certified’, meaning we can be sure that the value is an accurate reflection of reality, within a specific interval.

Although what it produces is a relative approximation, the algorithm requires the selection of a finite number of parameters, the aim being to solve the problem in a controlled way. 

“The development of this algorithm is a particularly important contribution to quantum theory”, adds Omar Fawzi. “It means the problem of calculating the physical properties of quantum systems is now "decidable", i.e. we have an algorithm with the capacity to solve this problem in a finite number of steps which wasn't previously the case

 The journal Nature Communications shone a spotlight on this breakthrough: for the first time, an algorithm has been developed with the capacity to calculate the physical properties of any quantum system within specific limits.

Omar Fawzi's research remains preliminary and theoretical. What are the next steps? “Our goal is to make our algorithm more efficient by the time it is operational”, explains the researcher. This should enable us to produce a benchmark for evaluating the performance of quantum computers in the future. By comparing the performance levels of classical and quantum algorithms, we will be able to identify specific problems for which quantum holds the advantage.”  

Quantum computers might not yet be with us, but each breakthrough brings us another step closer.