Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Quantum Automating TC0-Frege Is LWE-Hard

Arteche, Noel LU ; Carenini, Gaia and Gray, Matthew (2025) In Computational Complexity 34(2).
Abstract

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, Domingo, Gavaldá, Maciel, and Pitassi (Computational Complexity, 2004), who showed that ExtendedFrege, TC0-Frege and AC0-Frege, respectively, cannot be weakly automated by classical algorithms ifeither the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge,this is the first interaction... (More)

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, Domingo, Gavaldá, Maciel, and Pitassi (Computational Complexity, 2004), who showed that ExtendedFrege, TC0-Frege and AC0-Frege, respectively, cannot be weakly automated by classical algorithms ifeither 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.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
03F20, 68Q01, 68Q12, automatability, feasible interpolation, post-quantum cryptography, proof complexity
in
Computational Complexity
volume
34
issue
2
article number
16
publisher
Birkhäuser
external identifiers
  • scopus:105019759100
ISSN
1016-3328
DOI
10.1007/s00037-025-00271-w
language
English
LU publication?
yes
id
4cc14fb2-a2ce-4844-aee4-f24d5a86a61c
date added to LUP
2025-12-10 11:25:43
date last changed
2025-12-10 11:28:06
@article{4cc14fb2-a2ce-4844-aee4-f24d5a86a61c,
  abstract     = {{<p>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, Domingo, Gavaldá, Maciel, and Pitassi (Computational Complexity, 2004), who showed that ExtendedFrege, TC0-Frege and AC0-Frege, respectively, cannot be weakly automated by classical algorithms ifeither 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.</p>}},
  author       = {{Arteche, Noel and Carenini, Gaia and Gray, Matthew}},
  issn         = {{1016-3328}},
  keywords     = {{03F20; 68Q01; 68Q12; automatability; feasible interpolation; post-quantum cryptography; proof complexity}},
  language     = {{eng}},
  number       = {{2}},
  publisher    = {{Birkhäuser}},
  series       = {{Computational Complexity}},
  title        = {{Quantum Automating TC<sup>0</sup>-Frege Is LWE-Hard}},
  url          = {{http://dx.doi.org/10.1007/s00037-025-00271-w}},
  doi          = {{10.1007/s00037-025-00271-w}},
  volume       = {{34}},
  year         = {{2025}},
}