Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood

Sitan Chen, Weiyuan Gong, Jonas Haferkamp +1

In a variety of physically relevant settings for learning from quantum data, designing protocols that can computationally efficiently extract information remains largely an art, an…