  Partition functions of certain classes of "spin glass" models in statistical
physics show strong connections to combinatorial graph invariants. Also known
as homomorphism functions they allow for the representation of many such
invariants, for example, the number of independent sets of a graph or the
number nowhere zero k-flows. Contributing to recent developments on the
complexity of partition functions we study the complexity of partition
functions with complex values. These functions are usually determined by a
square matrix A and it was shown by Goldberg, Grohe, Jerrum, and Thurley that
for each real-valued symmetric matrix, the corresponding partition function is
either polynomial time computable or #P-hard. Extending this result, we give a
complete description of the complexity of partition functions definable by
Hermitian matrices. These can also be classified into polynomial time
computable and #P-hard ones. Although the criterion for polynomial time
computability is not describable in a single line, we give a clear account of
it in terms of structures associated with Abelian groups.
