Quantum-Computable One-Way Functions without One-Way Functions

William Kretschmer, Luowen Qian, Avishay Tal

We construct a classical oracle relative to which $\mathsf{P}=\mathsf{NP}$ but quantum-computable quantum-secure trapdoor one-way functions exist. This is a substantial strengthe…