Quantum hardness of learning shallow classical circuits

Understand

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning.

• In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems.
• We then achieve the following results.
• 1) Hardness of learning AC$^0$ and TC$^0$ under the uniform distribution.