Colloquium

Quantum computation generalizes the classical model of machine computation (a la Turing). The computational process which classically is the sequential action of logical gates on a bit string in {0,1}^N is replaced by a unitary transformation acting on a set of quantum bits described by a vector in the tensor product of N copies of the two-dimensional complex Hilbert space. There is good evidence that quantum computation is significantly more powerful than the classical model.

An important implication, worked out in a sequence of works by several authors in recent years, is that estimating the extremal eigenvalue of a Hermitian matrix is a universal problem for all "reasonable" computational problems, classical or quantum. We will explain this connection and discuss some related recent work on the ground state problem of quantum spin systems.