Quantum Automating $\mathbfTC^0$-Frege Is LWE-Hard
<|reference_start|>Quantum Automating $\mathbfTC^0$-Frege Is LWE-Hard: 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 Kraj\'i\v{c}ek and Pudl\'ak (Information and Computation, 1998), Bonet, Pitassi, and Raz (FOCS, 1997), and Bonet, Domingo, Gavald\`a, Maciel, and Pitassi (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.<|reference_end|>
@article{arteche2024quantum,
    title={Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard},
    author={Noel Arteche, Gaia Carenini, Matthew Gray},
    journal={arXiv preprint arXiv:2402.10351},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10351},
    primaryClass={cs.CC}
}