Computational complexity is a field of computer science that aims to understand the resources needed to solve computational problems. Researchers Anirban Chowdhury and David Gosset at the Institute for Quantum Computing (IQC) have been collaborating with IBM researchers Sergey Bravyi and Pawel Wocjan to explore the exciting interface between computational complexity and quantum many-body physics.
They have been studying the computational complexity of approximating a quantity known as the quantum partition function. This quantity holds all the information about variables like energy and magnetization for any specific set of quantum particles interacting with its surrounding environment without any transfer of heat, a state known as thermal equilibrium.
“Partition functions are sort of like a master key for thermal equilibrium properties,” says Chowdhury, a postdoctoral fellow at IQC and the Department of Combinatorics and Optimization at the University of Waterloo. “Once you know the partition function, you know, or can calculate in a small number of steps, almost everything else about the system.”
The problem of exactly computing the partition function is already understood to be extraordinarily hard. Therefore, the focus of Chowdhury and Gosset’s latest research was to understand whether the problem is easier if one only asks for a good approximation.
“In computer science, if you want to understand how difficult a problem is, first you show that it’s equivalent to some other problem that’s better understood,” says Gosset, faculty member at IQC and Waterloo’s Department of Combinatorics and Optimization. “We have found that the partition function approximation is equivalent in complexity to several other problems, which can be called approximate counting problems, where the goal is to approximately count some quantum mechanical quantity.”
By establishing an equivalence between these computational problems, Gosset and Chowdhury are building up an understanding of not only the partition function approximation algorithms, but also of this entire class of complex problems.
Another finding of their research was showing a new efficient approximation algorithm for computing the quantum partition function for a specific subset of cases known as dense local Hamiltonians, a case where every particle interacts with almost every other. Finally, the researchers also made improvements to existing classical and quantum algorithms for the partition function of general locally interacting quantum systems. Although these algorithms have an exponential runtime in the worst case, it is nevertheless of interest to decrease the resource requirements to improve their performance.
“Our hope is that other researchers can use the progress we made in this research and build upon it,” says Chowdhury. “Then, we might be able to precisely understand the computational complexity class that characterizes the difficulty of the partition function approximation problem.”
The paper Quantum Hamiltonian Complexity in Thermal Equilibrium was published in Nature Physics on October 6, 2022 by Chowdhury and Gosset from IQC along with their collaborators Sergey Bravyi and Pawel Wocjan from IBM Thomas J. Watson Research Center. This research was funded by a grant from the Army Research Office.
“In computer science, if you want to understand how difficult a problem is, first you show that it’s equivalent to some other problem that’s better understood."
Étudier la complexité des propriétés thermiques
La complexité algorithmique est un domaine de l’informatique qui vise à connaître les ressources nécessaires pour résoudre des problèmes de calcul. Anirban Chowdhury et David Gosset, chercheurs à l’Institut d’informatique quantique (IQC), collaborent avec Sergueï Bravyi et Pavel Wocjan, chercheurs chez IBM, à l’étude des liens passionnants entre la complexité algorithmique et la physique des systèmes quantiques à N corps.
Ils étudient la complexité algorithmique de l’approximation d’une grandeur appelée fonction de séparation quantique. Cette grandeur contient toute l’information sur des variables telles que l’énergie et la magnétisation, pour tout ensemble donné de particules quantiques interagissant avec son milieu sans transfert de chaleur, état appelé équilibre thermique.
« Une fonction de séparation est comme un passe-partout qui donne accès aux propriétés d’un équilibre thermique », dit M. Chowdhury, boursier postdoctoral à l’IQC ainsi qu’au Département de combinatoire et d’optimisation de l’Université de Waterloo. « Une fois qu’on connaît la fonction de séparation, on connaît ou on peut calculer rapidement presque toutes les autres propriétés du système. » [traduction]
On sait déjà que le problème du calcul exact d’une fonction de séparation est extraordinairement difficile. Dans leurs plus récents travaux, MM. Chowdhury et Gosset se sont donc attachés à comprendre si le problème est plus facile lorsque l’on recherche plutôt une bonne approximation.
« En informatique, pour connaître le degré de difficulté d’un problème, on commence par montrer qu’il est équivalent à un autre problème que l’on comprend mieux », dit M. Gosset, professeur à l’IQC ainsi qu’au Département de combinatoire et d’optimisation de l’Université de Waterloo. « Nous avons constaté que l’approximation d’une fonction de séparation est d’une complexité équivalente à celle de plusieurs autres problèmes, que l’on peut appeler problèmes de calcul approximatif. Ceux-ci visent à calculer une approximation d’une certaine grandeur quantique. » [traduction]
En établissant une équivalence entre ces problèmes de calcul, MM. Gosset et Chowdhury contribuent à une meilleure compréhension non seulement des algorithmes d’approximation de fonctions de séparation, mais aussi de toute cette classe de problèmes complexes.
Leurs recherches ont également donné un nouvel algorithme efficace d’approximation de la fonction de séparation quantique dans un sous-ensemble précis de cas, dits hamiltoniens de densité locale, où chaque particule interagit avec pratiquement toutes les autres. Enfin, les chercheurs ont apporté des améliorations à des algorithmes classiques et quantiques existants pour la fonction de séparation de systèmes quantiques généraux interagissant localement. Même si ces algorithmes ont dans le pire des cas un temps de calcul exponentiel, il est néanmoins intéressant de diminuer les ressources nécessaires pour en améliorer la performance.
« Nous espérons que d’autres scientifiques pourront pousser plus loin les progrès que nous avons réalisés grâce à ces recherches, dit M. Chowdhury. Nous pourrons alors peut-être connaître avec précision la classe de complexité algorithmique qui caractérise la difficulté du problème de l’approximation d’une fonction de séparation. » [traduction]
L’article intitulé Quantum Hamiltonian Complexity in Thermal Equilibrium (Complexité d’un hamiltonien quantique à l’équilibre thermique) a été publié le 6 octobre 2022 dans Nature Physics. MM. Chowdhury et Gosset, de l’IQC, ont écrit cet article en collaboration avec Sergueï Bravyi et Pavel Wocjan, du Centre de recherche Thomas-J.-Watson d’IBM. Ces recherches ont été financées par une subvention du Bureau de la recherche de l’armée des États-Unis.
« En informatique, pour connaître le degré de difficulté d’un problème, on commence par montrer qu’il est équivalent à un autre problème que l’on comprend mieux. » [traduction]