Finding quantum advantage has become a defining aspect of today’s quantum computing research. But when we find quantum solutions to problems, how will we actually know whether or not the solutions we’ve found have a meaningful computational advantage?
One promising advantage area is estimating the ground state energy, or lowest-energy, of a system — a hard problem for which we hope quantum computing will provide some benefits. In a collective effort published in the most recent issue of Science, researchers from 29 institutions, including IBM, worked to answer this question.
In this paper, we have defined a quality metric called the V-score, useful for benchmarking our ability to approximate ground states of quantum systems. We used it for the most comprehensive set of many-body problems to date with state-of-the-art classical techniques, and hope it will help with defining quantum advantage for future quantum computing calculations.
What is quantum advantage?
You might hear the words “quantum advantage” tossed around in various contexts. Its meaning is based on the three parameters that define any computation: accuracy, runtime, and cost. A quantum advantage is a demonstration of a solution for a problem for which a quantum computer can provide a demonstrable improvement over any classical method and classical resources in terms of accuracy, runtime or cost requirements. It’s not about being faster one time — it’s about quantum (or quantum in combination with classical) being the objectively better tool for solving the problem, versus classical computing alone.
In the search for quantum advantage, the emphasis often falls on the quantum runtime to achieve a certain computation compared to the runtime of classical state-of-the-art techniques. However, runtime is only one metric by which quantum advantage is benchmarked. Achieving quantum advantage requires the addition of quantum subroutines to make an algorithm cheaper, faster, or more accurate.
While runtime is an easy metric to measure, measuring cost and accuracy requires more effort. A systematic analysis of the resources used in the computation, despite requiring some non-trivial work, will inevitably come to a good measure of the total cost. This leaves us with the third metric, accuracy. Defining a metric for accuracy can be a challenging problem, since it depends on the computational task at hand and the user’s specific reasons for using a specific algorithm for solving the task.
A sought-after advantage: ground state calculations
One class of problems that is universally considered interesting is finding the ground state of local Hamiltonians. Instances of ground state problems are ubiquitous everywhere in computational quantum sciences, with a vast range of applications, from high-energy physics to chemistry and materials science.
It is a natural question to consider the definition of an accuracy metric for coming up with solutions to the ground state problem. Defining accuracy metrics for hard tasks with no exact solutions is a difficult problem in general, but the nature of the ground state problem helps with the definition.
Today, algorithms designed to solve this problem mostly rely on what we call variational methods, which are algorithms guaranteed to output an energy for a target system which cannot be lower than the exact solution — or the deepest valley — up to statistical uncertainties. An ideal quality metric for the ground state problem would not only allow the user to benchmark different methods against the same problem, but also different target problems when tackled by the same method.
So, how can such an absolute metric be defined? And what would be the consequences of finding this absolute accuracy metric?
Estimating and comparing variational (V) scores
We construct our accuracy metric from an estimation of the energy and its variance for any specific algorithm used to solve the ground state problem, with additional parameters of the system such as the size and the nature of its interactions. We call this metric “variational-score,” or “V-score,” and show that it is an absolute metric for this benchmark.
Once we defined our metric, we had to assess how well it would benchmark the ground state problem in the most exhaustive way. So, we tested it against the largest and most complete set of local Hamiltonian problems to date, which can be found online. We found that the V-score correlates very well with the hardness of these problems and the ability of different methods to address them.
For quantum computing practitioners and algorithm developers, there are some important implications: First, the V-score can be used to benchmark existing classical algorithms. This will enable us then to assess which ground state problems are the hardest for classical algorithms, and therefore best poised for quantum advantage. Second, the identification of hard problems flags systems for which modeling is potentially incomplete. In turn, this means that these systems hold the most potential for new discoveries. Third, the V-score can be used as a quality metric to assess quantum advantage of quantum computing algorithms for cases where classical verifiability is not available.
In short, once new quantum algorithms are discovered, the V-score can be used as a tool to assess the quality of their output, and to identify quantum advantage.
