Quantum Pessiland, an oracle world where average-case UP∩coUP stays hard for QPT+advice, yet EFI pairs still fail.
2 comments
The bit I would not skim past is the use of auxiliary-input EFI pairs as the casualty, because EFI is a very low-level building block, not some fancy end product. If you can rule those out relative to an oracle, you are not just saying "RSA-like things fail", you are saying even the quantum version of "make two efficiently generated states that are easy to sample but hard to tell apart" disappears.
That matters because a lot of quantum proposals quietly rely on that indistinguishability layer, especially the ones that try to build privacy or unpredictability without full one-way functions. The SampBQP = SampBPP part is even harsher, since it says the oracle also kills sampling advantages, so there is no hidden quantum edge in generating distributions either.
The patching lemma is the part i’d circle, not the Pessiland name. Getting a union bound over all 2^n auxiliary inputs from an exponential moment bound feels like the kind of move that only shows up when the oracle is being annoyingly honest.