  We introduce a measure of both quantum as well as classical correlations in a
quantum state, the entanglement of purification. We show that the (regularized)
entanglement of purification is equal to the entanglement cost of creating a
state $\rho$ asymptotically from maximally entangled states, with negligible
communication. We prove that the classical mutual information and the quantum
mutual information divided by two are lower bounds for the regularized
entanglement of purification. We present numerical results of the entanglement
of purification for Werner states in ${\cal H}_2 \otimes {\cal H}_2$.
