Quantum communication channels suffer from various noises, which are mathematically modelled by error super-operators. To combat these errors, it is necessary to design recovery super-operators. We aim to construct the optimal recovery that maximizes the minimum fidelity through the noisy channel. It is typically a MAX-MIN problem, out of the scope of convex optimization. Compared to existing methods, our method is exact and complete by a reduction to quantifier elimination over real closed fields in a fragment of two alternative quantifier blocks. Finally, the complexity is shown to be in EXP.