  Quantum computational complexity estimates the difficulty of constructing
quantum states from elementary operations, a problem of prime importance for
quantum computation. Surprisingly, this quantity can also serve to study a
completely different physical problem - that of information processing inside
black holes. Quantum computational complexity was suggested as a new entry in
the holographic dictionary, which extends the connection between geometry and
information and resolves the puzzle of why black hole interiors keep growing
for a very long time. In this pedagogical review, we present the geometric
approach to complexity advocated by Nielsen and show how it can be used to
define complexity for generic quantum systems; in particular, we focus on
Gaussian states in QFT, both pure and mixed, and on certain classes of CFT
states. We then present the conjectured relation to gravitational quantities
within the holographic correspondence and discuss several examples in which
different versions of the conjectures have been tested. We highlight the
relation between complexity, chaos and scrambling in chaotic systems. We
conclude with a discussion of open problems and future directions. This article
was written for the special issue of EPJ-C Frontiers in Holographic Duality.
