Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-029 | 16th February 2024 00:42

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard

RSS-Feed




TR24-029
Authors: Noel Arteche, Gaia Carenini, Matthew Gray
Publication: 20th February 2024 13:38
Downloads: 112
Keywords: 


Abstract:

We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $\mathbf{TC}^0$-Frege. This extends the line of results of Kraí?ek and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Ray (FOCS, 1997), and Bonet et al. (Computational Complexity, 2004), who showed that Extended Frege, $\mathbf{TC}^0$-Frege and $\mathbf{AC}^0$-Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.



ISSN 1433-8092 | Imprint