Quantum Pseudorandomness and Classical Complexity

Abstract

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.

31 pages. V2: added a new result about Haar random oracles (Corollary 5); various writing improvements. V3: added a new section about t-designs and corrected some proofs involving the use of t-designs. V4: corrected Lemma 25. V5: major changes to Section 5; the proof uses a new oracle construction after a bug was discovered in the previous version

References in corpus (1)

• Parameters of Pseudo-Random Quantum Circuits

Cited by in corpus (11)

• Quantum Cryptography in Algorithmica
• Improved Stabilizer Estimation via Bell Difference Sampling
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Unconditionally secure quantum commitments with preprocessing
• Quantum search-to-decision reductions and the state synthesis problem
• On the Computational Hardness of Quantum One-Wayness
• Quantum Unpredictability
• Quantum-Computable One-Way Functions without One-Way Functions
• A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• Cryptographic Characterization of Quantum Advantage