Issues of complexity are at the root of almost all theoretical aspects of quantum information science and correspondingly, concepts from theoretical computer science have provided a strikingly novel perspective on the foundations of quantum physics itself. For the theory of algorithms and computing, the formalism of 'classical simulation of quantum circuits' provides a mathematically precise tool for studying the rich relations between classical and quantum complexity. We will give an overview of this subject, indicating some elegant mathematical ingredients and implications for physics. Along the way we will mention some striking results for quantum Clifford circuits and matchgate circuits.