  Quantum states that possess negative conditional von Neumann entropy provide
quantum advantage in several information-theoretic protocols including
superdense coding, state merging, distributed private randomness distillation
and one-way entanglement distillation. While entanglement is an important
resource, only a subset of entangled states have negative conditional von
Neumann entropy. Despite this utility, a proper resource theory for conditional
von Neumann entropy has not been developed, unlike that of entanglement. We
pave the way for such a resource theory by characterizing the class of free
states (density matrices having non-negative conditional von Neumann entropy)
as convex and compact. This allows us to prove the existence of a Hermitian
operator (a witness) for the detection of states having negative conditional
entropy for bipartite systems in arbitrary dimensions. We construct a family of
such witnesses and prove that the expectation value of any of them in a state
is an upper bound to the conditional entropy of the state. We pose the problem
of obtaining a tight upper bound to the set of conditional entropies of states
in which an operator gives the same expectation value as a convex optimization
problem. We solve it numerically for a two qubit case and find that this
enhances the usefulness of our witnesses. We also find that for a particular
witness, the estimated tight upper bound matches the value of conditional
entropy for Werner states. We explicate the utility of our work in the
detection of useful states in the above-mentioned protocols.
