  It has been recently proposed that the naive semiclassical prediction of
non-unitary black hole evaporation can be understood in the fundamental
description of the black hole as a consequence of ignorance of high-complexity
information. Validity of this conjecture implies that any algorithm which is
polynomially bounded in computational complexity cannot accurately reconstruct
the black hole dynamics. In this work, we prove that such bounded quantum
algorithms cannot accurately predict (pseudo)random unitary dynamics, even if
they are given access to an arbitrary set of polynomially complex observables
under this time evolution; this shows that "learning" a (pseudo)random unitary
is computationally hard. We use the common simplification of modeling black
holes and more generally chaotic systems via (pseudo)random dynamics. The
quantum algorithms that we consider are completely general, and their attempted
guess for the time evolution of black holes is likewise unconstrained: it need
not be a linear operator, and may be as general as an arbitrary (e.g.
decohering) quantum channel.
