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

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 strengthening of the result of Kretschmer, Qian, Sinha, and Tal (STOC 2023), which only achieved single-copy pseudorandom quantum states relative to an oracle that collapses mathsf{NP} to mathsf{P}. For example, our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes relative to an oracle on which mathsf{P}=mathsf{NP}. Hence, in our new relativized world, classical computers live in "Algorithmica" whereas quantum computers live in "Cryptomania," using the language of Impagliazzo's worlds. Our proof relies on a new distributional block-insensitivity lemma for mathsf{AC⁰} circuits, wherein a single block is resampled from an arbitrary distribution.