ECCC-Report TR24-029https://eccc.weizmann.ac.il/report/2024/029Comments and Revisions published for TR24-029en-usFri, 24 May 2024 20:10:16 +0300
Revision 1
| Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard |
Noel Arteche,
Gaia Carenini,
Matthew Gray
https://eccc.weizmann.ac.il/report/2024/029#revision1We 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\text{-Frege}}$. This extends the line of results of Krají?ek and Pudlák (\emph{Information and Computation}, 1998), Bonet, Pitassi, and Raz (\emph{FOCS}, 1997), and Bonet, Domingo, Gavaldà, Maciel, and Pitassi (\emph{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.Fri, 24 May 2024 20:10:16 +0300https://eccc.weizmann.ac.il/report/2024/029#revision1
Paper TR24-029
| Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard |
Noel Arteche,
Gaia Carenini,
Matthew Gray
https://eccc.weizmann.ac.il/report/2024/029We 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.Tue, 20 Feb 2024 13:38:52 +0200https://eccc.weizmann.ac.il/report/2024/029