Quantum Pessiland

• URL: http://arxiv.org/abs/2608.29493v1
• Date: Sun, 30 Aug 2026 01:04:52 GMT
• Title: Quantum Pessiland
• Abstract summary: Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist.<n>We show that such a miserable world, Quantum Pessiland, exists.
• Score: 12.90382979353427
• License: http://creativecommons.org/licenses/by/4.0/
• 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\cap 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\cap 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\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure [52.51019642214249]
  We construct a family of 2D-local constant-depth quantum circuits whose entanglement entropy across a cut cannot be estimated in quantum time.<n>As constant-depth quantum circuits can be learned from specifiedly many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom.
  arXiv  Detail & Related papers  (2026-05-29T15:43:00Z)
• Quantum Cryptography and Hardness of Non-Collapsing Measurements [10.237675529033163]
  One-way puzzles (OWPuzzs) are a quantum analogue of one-way functions (OWFs)<n>In this paper, we base OWPuzzs on hardness of non-collapsing measurements.<n>We introduce a new primitive, distributional collision-resistant puzzles (dCRPuzzs)
  arXiv  Detail & Related papers  (2025-10-06T02:42:20Z)
• From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation [8.093227427119325]
  Indistinguishability obfuscation (iO) has emerged as a powerful cryptographic primitive with many implications.<n>In this work, we initiate a study of the power of quantum iO.
  arXiv  Detail & Related papers  (2025-06-24T11:50:33Z)
• Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
  We construct a classical oracle relative to which $mathsfP = mathsfNP$ but quantum-computable quantum-secure trapdoor one-way functions exist. Our result implies multi-copy pseudorandom states and pseudorandom unitaries, but also classical-communication public-key encryption, signatures, and oblivious transfer schemes.
  arXiv  Detail & Related papers  (2024-11-04T19:40:01Z)
• Quantum Cryptography and Meta-Complexity [2.6089354079273512]
  In classical cryptography, one-way functions (OWFs) are the minimal assumption, while it is not the case in quantum cryptography. We show that one-way puzzles (OWPuzzs) exist if and only if GapK is weakly-quantum-average-hard. We also show that if quantum PRGs exist then GapK is strongly-quantum-average-hard.
  arXiv  Detail & Related papers  (2024-10-02T09:30:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.