Quantum Pseudorandomness and Classical Complexity

Understand

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 shadow tomography.