Fine-Grained Complexity via Quantum Natural Proofs

• URL: http://arxiv.org/abs/2504.10363v1
• Date: Mon, 14 Apr 2025 16:09:55 GMT
• Title: Fine-Grained Complexity via Quantum Natural Proofs
• Authors: Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman,
• Abstract summary: We show how part of the QSETH conjecture that requires properties to be compression oblivious' can in many cases be replaced by assuming the existence of quantum-secure pseudorandom functions.
• Score: 5.306949367777188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it the QSETH framework. In this paper, using a notion of quantum natural proofs (built from natural proofs introduced by Razborov and Rudich), we show how part of the QSETH conjecture that requires properties to be `compression oblivious' can in many cases be replaced by assuming the existence of quantum-secure pseudorandom functions, a standard hardness assumption. Combined with techniques from Fourier analysis of Boolean functions, we show that properties such as PARITY and MAJORITY are compression oblivious for certain circuit class $\Lambda$ if subexponentially secure quantum pseudorandom functions exist in $\Lambda$, answering an open question in [Buhrman-Patro-Speelman 2021].

Related papers

• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
  arXiv  Detail & Related papers  (2024-09-23T17:45:33Z)
• 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)
• A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
  We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making unboundedly many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense.
  arXiv  Detail & Related papers  (2024-01-25T17:13:51Z)
• Connecting classical finite exchangeability to quantum theory [45.76759085727843]
  Exchangeability is a fundamental concept in probability theory and statistics.<n>It allows to model situations where the order of observations does not matter.<n>It is well known that both theorems do not hold for finitely exchangeable sequences.
  arXiv  Detail & Related papers  (2023-06-06T17:15:19Z)
• On Kirkwood--Dirac quasiprobabilities and unravelings of quantum channel assigned to a tight frame [0.0]
  Using vectors of the given tight frame to build principal Kraus operators generates quasiprobabilities with interesting properties. New inequalities for characterizing the location of eigenvalues are derived. A utility of the presented inequalities is exemplified with symmetric informationally complete measurement in dimension two.
  arXiv  Detail & Related papers  (2023-04-27T09:11:11Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Why we should interpret density matrices as moment matrices: the case of (in)distinguishable particles and the emergence of classical reality [69.62715388742298]
  We introduce a formulation of quantum theory (QT) as a general probabilistic theory but expressed via quasi-expectation operators (QEOs) We will show that QT for both distinguishable and indistinguishable particles can be formulated in this way. We will show that finitely exchangeable probabilities for a classical dice are as weird as QT.
  arXiv  Detail & Related papers  (2022-03-08T14:47:39Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
  Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions. We introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions. Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography.
  arXiv  Detail & Related papers  (2021-03-16T11:05:48Z)
• Quantum Chaos and the Spectrum of Factoring [0.9023847175654603]
  We show that a function $E$, that may take only discrete values, should be the analogous of the energy from a confined system of charges in a magnetic trap. This is the quantum factoring simulator hypothesis connecting quantum mechanics with number theory.
  arXiv  Detail & Related papers  (2020-08-24T19:40:28Z)
• Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
  We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values. We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
  arXiv  Detail & Related papers  (2018-03-10T05:31:38Z)

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.