In quantum theory, whenever we make a measurement, the outcomes will be random samples, distributed according to a distribution that is determined by the Born rule. On a high level, this probability distribution arises via high-dimensional interference of paths in quantum state space. Often, this 'sign problem' is made responsible for the hardness of classical simulations on the one hand, and the power of quantum computers on the other hand. In my talk, I will provide different perspectives and results on the sign problem and ponder the question inhowfar it might serve as a delineator between quantum and classical computing. In the first part of the talk, I will motivate the emergence of the sign problem from a physics perspective, and briefly discuss how a hardness argument for sampling from the output of generic quantum computations exploits the sign problem. In the second part of the talk, I will take on a computational-physics perspective. Within the framework of Monte Carlo simulations of complex quantum systems, I will discuss the question: Can we mitigate or *ease* the sign problem computationally by finding a perhaps more suitable basis in which to describe a given system? Specifically, I will discuss various measures of the sign problem, how they are related, and how to optimize them -- practically and in principle.