"Quantum Necromancy and the Hardness of Observing Schrodinger's Cat"

When applied to macroscopic scales, the unitarity of quantum mechanics leads to paradoxes such as Schrodinger's cat and Wigner's friend. The question of when and how superpositions of macroscopic states become "effectively measured" is fundamental in quantum mechanics. Here, we examine this question using the tools of quantum computational complexity. We prove that if one had a quantum circuit to determine whether a system was in an equal superposition of two orthogonal states (for example, the |Alive> and |Dead> states of Schrodinger's cat), then with only a slightly larger circuit, one could also swap the two states (e.g., bring a dead cat back to life). In other words, observing interference between the |Alive> and |Dead> states is a "necromancy-hard'' problem: technologically infeasible in any world where death is permanent. We also show that this statement is robust---i.e., even a 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.