In AdS/CFT the Engelhardt-Wall prescription states that the entanglement entropy of a boundary subregion is given by the generalized entropy of a minimal quantum extremal surface. Since quantum extremal surfaces are not constrained to one time slice proving certain consistency conditions such as strong subadditivity has remained an open problem. We formulate a quantum generalization of maximin surfaces and show that a quantum maximin surface is identical to the minimal quantum extremal surface. Using quantum maximin surfaces, we give the first general proof that the EW prescription satisfies entanglement wedge nesting and the strong subadditivity inequality.