Quantum Pessiland
Abstract
Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which UP∩ coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which UP∩ coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of UP∩ coUP implies P#Pnot⊆ i.o.BQP/qpoly, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from P#Pnot⊆ i.o.BQP/qpoly, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].
Related
- Charging of a quantum battery by a two-photon quantum pulse
- Quantum computing and quantum optics with recoiled free electrons
- Resource-efficient quantum-walker quantum random access memory
- Bosonic quantum error correction with microwave cavities for quantum repeaters
- Reflections on quantum Reflectometry: Quantum and tunneling capacitances as well as sisyphus and hermes resistances
BibTeX
@misc{chen2026quantum,
title = {{Quantum Pessiland}},
author = {Boyang Chen and Tomoyuki Morimae and Takashi Yamakawa},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29493},
eprint = {2608.29493},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29493},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Pessiland
AU - Boyang Chen
AU - Tomoyuki Morimae
AU - Takashi Yamakawa
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29493
UR - https://arxiv.org/abs/2608.29493
AB - Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which UP∩ coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which UP∩ coUP is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of UP∩ coUP implies P^#Pnot⊆ i.o.BQP/qpoly, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from P^#Pnot⊆ i.o.BQP/qpoly, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].
ER -