One T Gate Makes Distribution Learning Hard.

Area of Science:

• Quantum Computing
• Machine Learning
• Computational Complexity

Background:

• Learning probability distributions from samples is fundamental in natural sciences.
• Output distributions of local quantum circuits are crucial for quantum advantage proposals and quantum machine learning (QML).
• Understanding the learnability of these distributions is key to assessing quantum computational power.

Purpose of the Study:

• To extensively characterize the learnability of output distributions generated by local quantum circuits.
• To contrast learnability with simulatability in the context of quantum circuits.
• To investigate the hardness of generative and density modeling tasks for quantum circuits.

Main Methods:

• Theoretical analysis of quantum circuit output distributions.
• Complexity-theoretic arguments to establish hardness results.
• Comparison of learning capabilities for Clifford circuits versus circuits with T gates and universal circuits.

Main Results:

• Clifford circuit output distributions are efficiently learnable.
• Introducing a single T gate makes density modeling intractable for circuits of depth d=n^{Ω(1)}.
• Generative modeling of universal quantum circuits at depth d=n^{Ω(1)} is hard for all learning algorithms (classical and quantum).
• Even depth d=ω[log(n)] Clifford circuits are hard to learn for statistical query algorithms.

Conclusions:

• Local quantum circuit output distributions cannot demonstrate a separation between quantum and classical generative modeling power.
• These findings provide evidence against practical quantum advantages in probabilistic modeling tasks.
• The computational complexity of learning quantum distributions depends critically on circuit structure and depth.