Curing the sign problem from a computational complexity perspective

Quantum many-body systems with Hamiltonians that have positive off-diagonal elements in a given basis pose a significant obstacle for quantum Monte Carlo simulations. This challenge, widely known as the sign problem, severely impacts the efficiency and accuracy of these computational techniques. In this talk, I will review recent progress in understanding the complexity of finding and implementing faithful transformations that convert a given representation of the Hamiltonian into sign-problem-free ones, i.e., curing them. I will discuss both the potential and computational hardness of employing various families of transformations, including local and global Clifford transformations, and highlight examples of non-Clifford transformations that can offer advantages in simulating quantum many-body systems. Finally, I will discuss the implications of these findings for the verification of quantum computation.