Quantum Automating TC0-Frege Is LWE-Hard
We prove the first hardness results against efficient proof search by quantum algorithms. We show that underLearning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weaklyautomate TC0-Frege. This extends the line of results of Krajííček and Pudlík(Information and Computation, 1998), Bonet, Pitassi, and Raz (SIAM Journal on Computing, 2000),and Bonet
