Weiyuan Gong

In a variety of physically relevant settings for learning from quantum data, there is an established recipe for measuring polynomially many copies of that data such that the resulting measurement readouts contain enough information to reconstruct the underlying system. Yet designing protocols that can computationally efficiently extract that information remains largely an art, and there are important cases where we believe this to be impossible, that is, where there is an information-computation gap. While there is a large array of tools in the classical literature for giving evidence for average-case hardness of statistical inference problems, the corresponding tools in the quantum literature are far more limited. One such framework in the classical literature, the low-degree method, makes predictions about hardness of inference problems based on the failure of estimators given by low-degree polynomials. In this work, we extend this framework to the quantum setting and show a number of new information-computation gaps for quantum learning. We establish a general connection between state designs and low-degree hardness. We use this to obtain the first information-computation gaps for learning Gibbs states of random, sparse, non-local Hamiltonians. We also use it to prove hardness for learning random shallow quantum circuit states in a challenging model where states can be measured in adaptively chosen bases. To our knowledge, the ability to model adaptivity within the low-degree framework was open even in classical settings. In addition, we also obtain a low-degree hardness result for quantum error mitigation against strategies with single-qubit measurements. We define a new quantum generalization of the planted biclique problem and identify the threshold at which this problem becomes computationally hard for protocols that perform local measurements. Interestingly, the complexity landscape for this problem shifts when going from local measurements to more entangled single-copy measurements. We show average-case hardness for the ``standard'' variant of Learning Stabilizers with Noise and for agnostically learning product states.

Identifying the interactions and dynamics of open quantum systems is essential for characterizing quantum hardware, designing robust simulation protocols, and developing tailored error-correction approaches. Motivated by this, we study the task of learning an unknown Lindbladian generator — a superoperator that fully specifies both coherent (Hamiltonian) and dissipative dynamics. Prior protocols assume known interaction structure, which can be restrictive when the relevant error mechanisms or control imperfections are not known in advance. In this paper, we present the first efficient protocol for learning sparse Lindbladians without any structural or locality assumptions. Our protocol is ancilla-free and uses only product-state preparations and Pauli-basis measurements, making it compatible with near-term experimental capabilities. Moreover, it achieves a nearly optimal time resolution in the regime where the Lindbladian contains at most polynomially many terms. Together, this provides a systematic route to scalable characterization of open-system quantum dynamics, especially when the error mechanisms of interest are not known in advance.