Because of this fundamental importance and difficulty, much of the knowledge we’ve built has focused on simulating this simplified model of nature. However, studying higher-temperature systems in thermal equilibrium has received much less attention, even though it’s more typical of real-life scenarios.

As of now, the computational hardness of simulating quantum systems in thermal equilibrium with either classical or quantum computers remains poorly understood. A recent work^{1} from a team including ourselves and scientists at the University of Waterloo took on the challenge of investigating its complexity using tools from theoretical computer science. In doing so, we discovered a deep link between the problem of simulating these thermalized quantum systems and a seemingly unrelated problem — that of counting how many possible input states of a quantum computing program would result in a particular outcome.

## Quantum approximate counting

And this problem, dubbed “Quantum Approximate Counting,” is shown to be of equivalent computational complexity to many natural problems studied in condensed matter physics, such as mapping out the phase diagram of complex materials, or estimating the density of states, magnetization, or electrical conductance. Further, the new work discovered an efficient classical algorithm for simulating thermalized quantum systems whose interaction network is sufficiently dense, potentially providing a way for us to better-simulate these systems in the future.

Simulating thermalized quantum systems focuses on calculating a quantity called the free energy, or the energy available to do thermodynamic work. Free energy is kind of like the leftover money that remains once the system has paid off its required expenses. At very low temperatures, the free energy becomes the ground state energy. Our algorithm calculates a mathematical object called the partition function, an equation that includes both the temperature and the physical description of the system, called the Hamiltonian. One can view the partition function as a weighted sum over all energy eigenstates that the system can occupy. The weights in the sum favor low-energy states while high-energy states are exponentially suppressed. The free energy is simply related to the partition function.

This problem has received much attention from physicists and computer scientists attempting to devise a solution, and understand its computational hardness. However, a physical system reaches the ground state only when it is cooled down to the absolute zero. Studying higher-temperature systems in thermal equilibrium has received much less attention, even though it's much more typical of real-life scenarios.

For the first part of our paper, we found an efficient classical algorithm to approximate the free energy for a new class of densely interacting 2-local qubit Hamiltonians. The 2-local qubit Hamiltonian is one acting on quantum states with n qubits, but which only acts on any two of the state’s qubits at once. Densely interacting means that every one of the system’s qubit is capable of talking to a large number of its other qubits. These specific Hamiltonians are similar in structure to telephone networks where everyone is connected with everyone else, but specific phone calls only happen between two people.

Our classical algorithm produces an estimate of the free energy for just this specific instance of quantum systems. If we removed the denseness condition and considered general Hamiltonians with (sparse) two-qubit interactions, the resulting problem would fall into a class of much harder problems for which it is believed that even a quantum computer cannot efficiently find a solution.

Given that this algorithm can only tackle a small subset of all possible systems, we went on to consider the computational complexity of approximating the free energy for more general systems with multi-qubit interactions, known as k-local qubit Hamiltonians. Such systems are analogous to telephone networks where conversations can happen between more than two people at once. Our study revealed a surprising connection between several seemingly unrelated problems: the free energy estimation, approximating the number of energy levels in a given energy window, and a problem which we call Quantum Approximate Counting. The latter aims to estimate the number of input states of a quantum circuit that result in a particular outcome of the final measurement. We found that all these problems are equivalent to each other, as far as the computational complexity is concerned. In other words, given a subroutine solving one of these problems, any other problem can be efficiently solved by calling the subroutine a few times.

Our study revealed a surprising connection between several seemingly unrelated problems: the free energy estimation, approximating the number of energy levels in a given energy window, and a problem which we call Quantum Approximate Counting.

We were also able to to devise better classical and quantum algorithms that could estimate the free energy of k-local qubit Hamiltonians. These algorithms are still inefficient; their runtime grows exponentially with the number of qubits. However, given the importance of these problems, any runtime or memory improvements can be useful. We used a technique called “Clifford compression” from quantum information theory in a novel way to obtain a reduce the memory requirements of a quantum algorithm. This same techniques produced a faster classical algorithm, too — showing how studying quantum information theory can provide deep insight even beyond quantum computing.

This work demonstrates that, all-in-all, simulating the physical world is still really hard. How hard, we still don’t know; but we’re starting to get a handle on it thanks to this most recent work. Not only that, but we’re continuing to find new ways of tackling this problem that perform better than previous methods, bringing the potential of simulating these kinds of systems ever closer to our reach. And, by linking this problem to other problems in the quantum space, we hope to open up further improvements to algorithms across the field.

But more than anything, this work is a call to action that leaves plenty of unanswered questions. Can our classical algorithm apply to systems that obey less strict qubit connectivity requirements? And most importantly, just how complex is it to approximate the free energy? Performing deep-dives into these kinds of problems may be heady work, but it’s crucial as we build our understanding of quantum computers’ capabilities.