  When is decoherence "effectively irreversible"? Here we examine this central
question of quantum foundations using the tools of quantum computational
complexity. We prove that, if one had a quantum circuit to determine if a
system was in an equal superposition of two orthogonal states (for example, the
$|$Alive$\rangle$ and $|$Dead$\rangle$ states of Schr\"{o}dinger's cat), then
with only a slightly larger circuit, one could also $\mathit{swap}$ the two
states (e.g., bring a dead cat back to life). In other words, observing
interference between the $|$Alive$\rangle$and $|$Dead$\rangle$ states is a
"necromancy-hard" problem, technologically infeasible in any world where death
is permanent. As for the converse statement (i.e., ability to swap implies
ability to detect interference), we show that it holds modulo a single
exception, involving unitaries that (for example) map $|$Alive$\rangle$ to
$|$Dead$\rangle$ but $|$Dead$\rangle$ to -$|$Alive$\rangle$. We also show that
these statements are robust---i.e., even a $\mathit{partial}$ ability to
observe interference implies partial swapping ability, and vice versa. Finally,
without relying on any unproved complexity conjectures, we show that all of
these results are quantitatively tight. Our results have possible implications
for the state dependence of observables in quantum gravity, the subject that
originally motivated this study.
