Quantum Cryptography in Algorithmica

William Kretschmer, Luowen Qian, Makrand Sinha +1

We construct a classical oracle relative to which $\mathsf{P}=\mathsf{NP}$ yet single-copy secure pseudorandom quantum states exist. In the language of Impagliazzo's five worlds,…