Fine-Grained Complexity via Quantum Natural Proofs
By: Yanlin Chen , Yilei Chen , Rajendra Kumar and more
Potential Business Impact:
Makes computers harder to trick with quantum computers.
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].
Similar Papers
Compressed Permutation Oracles
Quantum Physics
Makes secret codes harder for future computers.
On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
Quantum Physics
Makes quantum computers solve harder problems.
On Limits on the Provable Consequences of Quantum Pseudorandomness
Quantum Physics
Makes quantum randomness harder to fake.