  Several information measures have recently been defined which capture the
notion of "recoverability." In particular, the fidelity of recovery quantifies
how well one can recover a system $A$ of a tripartite quantum state, defined on
systems $ABC$, by acting on system $C$ alone. The relative entropy of recovery
is an associated measure in which the fidelity is replaced by relative entropy.
In this paper, we provide concrete operational interpretations of the
aforementioned recovery measures in terms of a computational decision problem
and a hypothesis testing scenario. Specifically, we show that the fidelity of
recovery is equal to the maximum probability with which a computationally
unbounded quantum prover can convince a computationally bounded quantum
verifier that a given quantum state is recoverable. The quantum interactive
proof system giving this operational meaning requires four messages exchanged
between the prover and verifier, but by forcing the prover to perform his
actions in superposition, we construct a different proof system that requires
only two messages. The result is that the associated decision problem is in
QIP(2) and another argument establishes it as hard for QSZK (both classes
contain problems believed to be difficult to solve for a quantum computer). We
finally prove that the regularized relative entropy of recovery is equal to the
optimal Type II error exponent when trying to distinguish many copies of a
tripartite state from a recovered version of this state, such that the Type I
error is constrained to be no larger than a constant.
