  We construct a quantum oracle relative to which $\mathsf{BQP} = \mathsf{QMA}$
but cryptographic pseudorandom quantum states and pseudorandom unitary
transformations exist, a counterintuitive result in light of the fact that
pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We
explain how this nuance arises as the result of a distinction between
algorithms that operate on quantum and classical inputs. On the other hand, we
show that some computational complexity assumption is needed to construct
pseudorandom states, by proving that pseudorandom states do not exist if
$\mathsf{BQP} = \mathsf{PP}$. We discuss implications of these results for
cryptography, complexity theory, and quantum tomography.
