Many classes of complex computational problems admit no efficient solution or even approximation, yet have a vast reach in applications across science and industry. From a physics perspective, computational complexity originates from strong correlations between bits of information. It is reasonable to ask whether computational approaches to quantum many-body problems can be practically useful in this context. In this talk, I will present newly found cases where the answer is affirmative. I will introduce constraint satisfaction problems (CSPs) and reformulate them as interacting models whose ground states represent the solution manifold. A procedure that reaches the ground states of these models implements a protocol of computation. In some protocols, the complexity that arises during computation can be viewed as quantum entanglement, and efficiency is achieved by controlling its growth. Using this reasoning, I will introduce practical methods for solving CSPs based on tensor network contraction and demonstrate that they outperform state-of-the-art solvers for some of these problems by a significant margin. I will conclude with an outline of ongoing work on extensions and applications to problems of current interest, such as the simulation of existing and near-term quantum circuits.