We design an algorithm for learning the coefficients of an $n$-qubit constant-local Lindbladian to $\varepsilon$ error with $O(g d^2 \log(n) / \varepsilon^2)$ total evolution time, where $g$ is the single-site energy and $d$ is the (approximate) degree of the interaction graph. Though Lindbladians present new challenges not present in the special case of Hamiltonians, our algorithm achieves the suite of desiderata attained by state-of-the-art Hamiltonian learning algorithms: (1) it uses non-adaptive, ancilla-free randomized Pauli measurement circuits with a time resolution of only $Θ(1/g)$; (2) it works without knowledge of the structure of the unknown Lindbladian; (3) it depends on a smooth form of degree, thereby supporting the learning of quasi-local and power-law Lindbladians. Moreover, we prove a lower bound showing that our algorithm is optimal in each parameter up to logarithmic factors.
Our algorithm is a simple iterative method, where the objective function consists of Fourier coefficients of the Lindbladian restricted to few-site regions. Its analysis identifies the difficulty unique to open systems, which we call "confusing" terms. For settings where the "confusion" is limited, the performance of the algorithm improves. We demonstrate this for the case of structure learning of Hamiltonians from access to real-time evolution, where we obtain a new algorithm that is significantly simpler than previous work. In addition, using the same iterative method, we design the first efficient algorithm for structure learning Hamiltonians from high-temperature Gibbs states.
We design an algorithm for learning the coefficients of an n-qubit constant-local Lindbladian to ε error with O(gd2log(n)/ε2) total evolution time, where g is the single-site energy and d is the (approximate) degree of the interaction graph. Though Lindbladians present new challenges not present in the special case of Hamiltonians, our algorithm achieves the suite of desiderata attained by state-of-the-art Hamiltonian learning algorithms: (1) it uses non-adaptive, ancilla-free randomized Pauli measurement circuits with a time resolution of only Θ(1/g); (2) it works without knowledge of the structure of the unknown Lindbladian; (3) it depends on a smooth form of degree, thereby supporting the learning of quasi-local and power-law Lindbladians. Moreover, we prove a lower bound showing that our algorithm is optimal in each parameter up to logarithmic factors.
Our algorithm is a simple iterative method, where the objective function consists of Fourier coefficients of the Lindbladian restricted to few-site regions. Its analysis identifies the difficulty unique to open systems, which we call "confusing" terms. For settings where the "confusion" is limited, the performance of the algorithm improves. We demonstrate this for the case of structure learning of Hamiltonians from access to real-time evolution, where we obtain a new algorithm that is significantly simpler than previous work. In addition, using the same iterative method, we design the first efficient algorithm for structure learning Hamiltonians from high-temperature Gibbs states.
We study the problem of learning local Lindbladians from black-box access to the physical evolution, where the goal is to estimate all Hamiltonian and dissipative coefficients. For local Lindbladians with low-intersection dissipators and local dynamical strength at most Λ, we design an algorithm that learns the coefficients to target accuracy ε, whose number of channel uses and total evolution time scale as O(Λ2/ε2) and O(Λ/ε2), respectively, with only logarithmic dependence on the number of qubits. The algorithm is built directly from finite-time channel probes. It runs the unknown evolution for short times, estimates the corresponding Pauli transfer matrices from classical shadows, and converts these estimates into Lindbladian coefficients by stable local Fourier inversions.
The algorithm is non-adaptive, uses no ancillas, and requires only random product states as inputs followed by random Pauli measurements. The method does not require knowing the structure of the Lindbladian in advance. We prove matching lower bounds that establish the near-optimality of the algorithm in both resources. By constructing a family of single-qubit dephasing Lindbladians, we show that any algorithm, even an adaptive one with arbitrary ancillas and measurements, requires Ω(Λ2/ε2) channel uses and Ω(Λ/ε2) total evolution time. In particular, the lower bounds imply that the Heisenberg-limited scaling achievable for Hamiltonian learning is information-theoretically impossible once dissipative coefficients must be estimated.
We study the problem of learning an unknown Markovian open-system generator from access to its physical time evolution. This generator, called a Lindbladian, contains Hamiltonian and dissipative coefficients indexed by an exponentially large family of possible Pauli terms. We propose an efficient algorithm that learns arbitrary Lindbladians from time evolution under minimal assumptions. For a Lindbladian of dynamical strength at most Λ, the algorithm estimates every coefficient to error ε using O(Λ2/ε2) experiments and O(Λ/ε2) total evolution time, together with polynomial classical running time. The algorithm consists of two nonadaptive, ancilla-free, and control-free stages: 1. The support-learning stage outputs a candidate support of size poly(Λ/η) that contains every Hamiltonian and dissipative coordinate of magnitude at least η, using O(Λ2/η2) experiments with preparations of product Pauli eigenstates and single-qubit Pauli measurements. 2.The coefficient-learning stage estimates all coefficients in any candidate support of size M to error ε, using O(Λ2logM/ε2) experiments with preparations of random stabilizer states and measurements in random Clifford bases. Composing the two stages identifies and estimates every coefficient of an arbitrary Lindbladian in polynomial time. The experiment-count and total-evolution-time scalings match the lower bounds up to logarithmic factors, so the algorithm is nearly optimal for learning arbitrary Lindbladians.
We present an efficient protocol for learning an unknown k-local Lindblad generator on n qubits using only product-state preparations, short-time evolution, and single-qubit Pauli measurements, without prior knowledge of the interaction structure. For fixed k and a supplied weighted interaction-strength bound αˉ, the protocol estimates all Hamiltonian and dissipative Pauli--GKSL coefficients with total coefficient error at each site at most ε with probability at least 1−δ using Ok(αˉ2n2k−2ε−2log(n/δ)) samples and polylogarithmically many distinct evolution times. This guarantee requires no degree, sparsity, or tail promise. A convex optimization converts these estimates into a valid k-local Lindblad generator with diamond-norm error at most ε using Ok(αˉ2n2kε−2log(n/δ)) samples and polynomial-time classical postprocessing. With a supplied local effective-sparsity bound r and a sufficiently small sitewise subthreshold tail Ok(ε), coefficient recovery requires only Ok(αˉ2r2ε−2log(n/δ)) samples, without a supplied threshold or coefficient locations and without a coefficient-gap assumption. In particular, exactly sparse bounded-degree models have logarithmic sample dependence on n. We also provide guard-band support recovery and complementary supplied-candidate guarantees, extend the guarantees to model misspecification, and prove complementary sample-complexity lower bounds.
We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to applye−iHtfor an unknown local HamiltonianH=Σa=1mλaEaonnqubits, the goal is to recoverH. This problem is already well-understood under the assumption that the interaction terms,Ea, are given, and only the interaction strengths,λa, are unknown. But how efficiently can we learn a local Hamiltonian without prior knowledge of its interaction structure? We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian toεerror with total evolution timeO(log(n)/ε), and has the following appealing properties: 1)It does not need to know the Hamiltonian terms; 2)It works beyond the short-range setting, extending to any HamiltonianHwhere the sum of terms interacting with a qubit has bounded norm; 3)It evolves according toHin constant timetincrements, thus achieving constant time resolution. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracyεwith total evolution time beating the standard limit of1/ε2.
Learning the generator of an open many-body system is more challenging than Hamiltonian learning: local responses, which can directly reveal coherent interaction terms in closed-system dynamics, may also contain dissipative contributions in open-system dynamics. In this paper, we address this challenge by developing an efficient Lindbladian learning framework for a known local candidate generator dictionary with bounded dissipative support and either bounded dual-interaction-graph degree or bounded unweighted local strength. The framework resolves the coherent-dissipative ambiguity by treating local Pauli responses as a linear system over both types of generator terms. Inverting this response system separates their contributions and makes the individual Lindbladian coefficients accessible from local response data in a fixed short-time window. Within this framework, we develop two efficient learning algorithms: Chebyshev--Lobatto response interpolation, which uses logarithmically many short evolution times and has a post-mean cost linear in M, with the stated dependence on ε, and Single-time projected response contraction, which uses a single fixed evolution time and globally inverts a truncated response function. Both procedures estimate M candidate coefficients to entrywise accuracy ε using O(M/ε2) sample and classical post-processing complexity. Our theoretical results establish local response inversion as a scalable paradigm for learning, calibrating, and diagnosing complex quantum systems from experimentally accessible short-time data.
Characterizing the dynamics of open quantum systems at the level of microscopic interactions and error mechanisms is essential for calibrating quantum hardware, designing robust simulation protocols, and developing tailored error-correction methods. Under Markovian noise/dissipation, a natural characterization approach is to identify the full Lindbladian generator that gives rise to both coherent (Hamiltonian) and dissipative dynamics. Prior protocols for learning Lindbladians from dynamical data assumed pre-specified interaction structure, which can be restrictive when the relevant noise channels or control imperfections are not known in advance. In this paper, we present a sample-efficient protocol for learning sparse Lindbladians without assuming any a priori structure. Our protocol is ancilla-free, uses only product-state preparations and Pauli-basis measurements, admits provably stable coefficient reconstruction, and achieves near-optimal time resolution, making it compatible with near-term experimental capabilities. Together, this provides a systematic route to scalable characterization of open-system quantum dynamics, especially in settings where the error mechanisms of interest are unknown.