Why are states that are separable but not simply separable considered to be unentangled? For pure states $|\psi\rangle$, entanglement is straightforward.  Given two Hilbert spaces $\mathcal{H}_A$ and $\mathcal{H}_B$, a pure state $|\psi\rangle \in \mathcal{H}_A \otimes \mathcal{H}_B$ is a product state iff it can written as $|\psi\rangle = |a\rangle \otimes |b\rangle$ for some $|a\rangle \in \mathcal{H}_A$ and $|b\rangle \in \mathcal{H}_B$.  Otherwise, $|\psi\rangle$ is entangled.  Easy-peasy.
For mixed states $\rho$ (i.e. trace-$1$ positive semidefinite Hermitian operators), things are much more complicated, because there's a weird intermediate case:


*

*A "product state" (or "simply separable state") can be written as $\rho = \rho_A \otimes \rho_B$, where $\rho_A$ and $\rho_B$ are states acting on $\mathcal{H}_A$ and $\mathcal{H}_B$ respectively.

*A "separable state" can be written as $\rho = \sum \limits_k^N p_k \rho_A^{(k)} \otimes \rho_B^{(k)}$, where the $\rho^{(k)}$ are all states and the $p_k$ form a discrete probability distribution (i.e. they are all nonnegative and sum to $1$).  (Note that $N$ can be arbitrarily large - e.g. larger than the product of the dimensions of $\mathcal{H}_A$ and of $\mathcal{H}_B$.  We can always Schmidt decompose the $\rho^{(k)}$ and redefine the index $k$ (potentially increasing $N$) to make the new $\rho^{(k)}$'s pure.)

*An "entangled state" is a state that is not separable; it can be written in the form above, but the $p_k$'s and the spectra of the $\rho^{(k)}$ cannot all be probability distributions.


Why are non-product separable states considered to be unentangled? I understand why we can intuitively think of a separable state $\rho$ as a classical mixture of product states, but to me, the overwhelmingly natural definition of an "entangled state" would be "not a product state." The requirement that the coefficients $p_k \geq 0$ seems very strange to me, since inequalities rarely come up in the foundations of quantum mechanics.
More concretely, the fact that non-product separable states can have positive quantum dischord is often cited as evidence that there can exist purely quantum correlations that are impossible in a classical system but do not rely on entanglement.  But to me, that's merely evidence that you've chosen a poor definition of the word "entanglement."  Moreover, checking whether a state is entangled under the definition above is NP-hard. while I believe that checking whether it's a product state is known to be efficient.  If the standard definition of "entanglement" is incredibly difficult to check for a particular system and doesn't even capture all the quantum correlations anyway, then what is it good for?
 A: To see why it can't be entangled it is first best to think of the sum in the density matrix $\rho$ of the second case as having been constructed randomly in a classical way. There is some probability $p_{k}$ associated with getting the product state $\rho_{A}^{(k)}\otimes \rho_{B}^{(k)}$ and a random product state is given to you based on those probabilities.
So regardless of which $k$ value you end up getting, you get a state generated for you that has no correlations between sites A and B. This means any correlations between the sites that you get when looking at $\rho$ is purely due to a classical construction method. There is no quantum entanglement between the two sites.
EDIT: Think about it this way, for any single run you are going to get one of the product states $\rho_{A}^{(k)}\otimes \rho_{B}^{(k)}$. This is what is physically going on and it is just your lack of knowledge about reality which is leading to you having state $\rho$. This means that physically there is no sense in which any measurement in site $A$ could lead to a change in the state of site $B$. From a point of view of what information you can learn when you do a measurement of the A subsystem of $\rho$ you can change your internal belief of the probability weights of the different $k$s and that would change your knowledge about the state of site B. But this is only updating your internal knowledge, nothing as spooky as entanglement.
Now for discord, to preface this I don't have a good handle on discord and haven't really studied it and so might get a couple things wrong but I will share my intuition. Even though I've implied that correlations can only be classical for this case there is still the infinite number of choices of basis that a quantum system has as opposed to the single basis that a classical system. To think about this more concretely I'll focus on the smallest systems, comparing quantum bits (qubits) and classical bits.
If I have two bits then I can describe their correlation with no more then 4 numbers, indicating the probability of getting 00,01,10,11 as the bit values. For two qubits I can have the same numbers describing their correlations, however there are more correlations then this without entanglement. For example I could choose the state which is an equal distribution between $|0\rangle\langle 0|\otimes |+\rangle\langle +|$ and $|+\rangle\langle +|\otimes |0\rangle\langle 0|$ which has correlations in excess of the classical example. Quantum discord is an attempt to measure these correlations.
As to why we care about the distinction, we want to think about these things as a resource that can be used. These resources once produced can then be used for different protocols. Entanglement turns out to be a resource when all you can do is local unitary operators and can classically communicate (LOCC) between the states and so never increases under these operations. On the other hand discord can increase under these LOCC operations which means it is a "less expensive" resource then entanglement is meaning we should be careful to keep these ideas distinct.
