We develop a framework for learning from noisy quantum experiments, focusing on fault-tolerant devices accessing uncharacterized systems through noisy couplings. Our starting point is the complexity class $\textsf{NBQP}$ ("noisy BQP"), modeling noisy fault-tolerant quantum computers that cannot, in general, error-correct the oracle systems they query. Using this class, we show that for natural oracle problems, noise can eliminate exponential quantum learning advantages of ideal noiseless learners while preserving a superpolynomial gap between NISQ and fault-tolerant devices. Beyond oracle separations, we study concrete noisy learning tasks. For purity testing, the exponential two-copy advantage collapses under a single application of local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient structure restores a quantum learning advantage in a noisy regime. We then analyze noisy Pauli shadow tomography, deriving lower bounds that characterize how instance size, quantum memory, and noise control sample complexity, and design algorithms with parametrically similar scalings. Together, our results show that the Bell-basis and SWAP-test primitives underlying most exponential quantum learning advantages are fundamentally fragile to noise unless the experimental system has latent noise-robust structure. Thus, realizing meaningful quantum advantages in future experiments will require understanding how noise-robust physical properties interface with available algorithmic techniques.
We develop a framework for learning from noisy quantum experiments, focusing on fault-tolerant devices accessing uncharacterized systems through noisy couplings. Our starting point is the complexity class NBQP ("noisy BQP"), modeling noisy fault-tolerant quantum computers that cannot, in general, error-correct the oracle systems they query. Using this class, we show that for natural oracle problems, noise can eliminate exponential quantum learning advantages of ideal noiseless learners while preserving a superpolynomial gap between NISQ and fault-tolerant devices. Beyond oracle separations, we study concrete noisy learning tasks. For purity testing, the exponential two-copy advantage collapses under a single application of local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient structure restores a quantum learning advantage in a noisy regime. We then analyze noisy Pauli shadow tomography, deriving lower bounds that characterize how instance size, quantum memory, and noise control sample complexity, and design algorithms with parametrically similar scalings. Together, our results show that the Bell-basis and SWAP-test primitives underlying most exponential quantum learning advantages are fundamentally fragile to noise unless the experimental system has latent noise-robust structure. Thus, realizing meaningful quantum advantages in future experiments will require understanding how noise-robust physical properties interface with available algorithmic techniques.
Quantum computers may reveal features of Nature inaccessible to conventional experiments, but manipulating raw quantum data introduces noise that degrades inference even when the processor is fault-tolerant, creating a data-input bottleneck for robust quantum learning. Here we show that quantum fault tolerance can substantially improve the sample complexity of learning from noisy experiments. We encode unknown quantum states from physical experiments into protected quantum memory, enabling fault-tolerant implementations of quantum learning algorithms otherwise degraded by errors. Using this quantum uploading procedure, we prove that noisy randomized measurement and multi-copy learning tasks can be performed exponentially faster than by any adaptive strategy that does not immediately encode physical states into error-corrected memory. These separations are not simply due to a reduced effective noise rate: they hold even when uploading is substantially noisier than the bare experimental interface, rigorously establishing immediate encoding as the optimal approach to noise-robust learning. We numerically illustrate the speedups in astronomical imaging, where quantum processing of uploaded photons locates an exoplanet obscured by a bright star using orders of magnitude fewer shots than unencoded baselines. Our results establish a robust interface between quantum computers and natural systems, enabling powerful and practical quantum-enhanced experiments.
Learning unknown noise processes in quantum systems reveals their physical origin and informs error suppression, mitigation, and correction. Characterizing a general quantum process requires exponentially many parameters inferred from noncommuting measurements. Because these measurements cannot be performed simultaneously, the sample complexity grows exponentially. For Pauli channels, quantum memory and entangling operations can transform this task into measurements of commuting observables, reducing complexity exponentially. However, noise in these resources increases the overhead, leaving open whether any advantage remains in realistic devices. Here, we introduce error-mitigated entanglement-enhanced learning, analyze it theoretically, and demonstrate it experimentally. We quantify the noise-induced overhead, perform hypothesis testing with up to 64 qubits, and learn intrinsic noise in parallel-gate layers using up to 16 qubits of a superconducting processor. We show that noisy quantum memory provides a learning advantage, with a current experimental overhead of 1.33 ± 0.05 per qubit, below the no-entanglement lower bound of 2. The authors show that entanglement with noisy quantum memory can significantly speed up learning of quantum processes. With error mitigation, their method characterizes quantum noise at scale and outperforms entanglement-free approaches.
Noisy Intermediate-Scale Quantum (NISQ) devices show great promise for quantum advantage via Parametrized Quantum Circuits (PQCs) and Variational Quantum Algorithms (VQAs). Due to hardware imperfections, however, especially barren plateaus and environmental Pauli noise, the cost landscape is highly distorted, resulting in inaccurate classical optimization during training. To overcome these challenges, a robust quantum gradient descent framework is presented with the integration of error mitigation directly within the optimization loop. A noise-resilient parameter-shift rule is defined and modeled analytically, as is a variant of stochastic gradient descent with real-time Pauli noise mitigation. The framework is based on a 6-qubit system, which is tested on the Max-Cut problem in the presence of different amounts of depolarizing noise. It is shown experimentally that the proposed algorithm is able to achieve the final cost error of 0.045 under significant noise, whereas the standard quantum gradient descent fails to achieve better than 0.320 under this noise. Moreover, the methodology is consistent, converging without a noise-induced flat landscape and without local minima. The method offers a scalable route towards future applications of quantum machine learning on non-fault-tolerant hardware that does not suffer from the large sampling overhead often associated with conventional error mitigation techniques.
Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy n-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit (γ=0) and the strong-decoherence regime (γ=Θ(1)). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.
As quantum devices grow in size while remaining affected by noise, a key challenge is to determine when and how they can surpass classical computation on practical tasks. This requires the development of highly efficient classical simulation algorithms. Pauli backpropagation algorithms are among the most promising, having shown efficiency in simulating certain classes of parameterized quantum circuits, strong candidates for near‑term quantum advantage, under random circuit assumptions and depolarizing noise. However, their efficiency had not been demonstrated for more realistic nonunital noise models, such as amplitude damping, which better capture the behaviour of current hardware. We close this gap by adapting Pauli backpropagation to most single‑qubit noise channels, including nonunital noise, and proving that it remains efficient under these conditions. Our algorithm is parallelizable, memory‑efficient, and requires no assumptions on the locality of the observable, the geometry of the hardware, or the depth of the circuit. While hardware noise can strongly affect computational power in highly structured, fault‑tolerant circuits, our findings indicate little difference for most near‑term variational architectures. This establishes Pauli backpropagation as an efficient method for simulating noisy quantum devices under realistic noise assumptions.While these advances improve our ability to reproduce noisy expectation values of observables, many practical applications, including combinatorial optimization, require direct access to the bitstrings output by quantum circuits, as these encode candidate solutions. Classical replication of such noisy samples has so far been limited beyond the random circuit setting. To bridge this gap, we first focus on problems whose objective functions depend only on two‑body correlations, such as Max‑Cut, and apply Gaussian randomized rounding to the circuit's two‑qubit marginals. This produces classical samples whose expected cost is provably close to that of the noisy quantum device. Large‑scale simulations and experiments on IBMQ hardware confirm that the rounded samples reproduce the full energy distribution, with similar behaviour under various noise models. Coupled with Pauli backpropagation for efficiently estimating noisy marginals, this yields an end‑to‑end classical sampler operating in polynomial time for a broad class of variational circuits. Our results therefore show that sufficiently noisy quantum circuits for combinatorial optimization can be sampled from classically, clarifying where near‑term hardware may or may not outperform classical algorithms.Finally , we go beyond one and two‑body marginals and present an algorithm that samples valid bitstrings directly from a maximum‑entropy distribution matching the given expectation values of the quantum circuit. This method does not rely on the locality or sparsity of the problem's Hamiltonian and performs well across a variety of quantum circuits, including deep circuits on many qubits. When combined with Pauli propagation or error mitigation, it provides a practical pipeline for obtaining samples from quantum circuits in the near term, where full error correction might not yet be available.
Understanding what can be learned from experiments is central to scientific progress. In this work, we use a learning-theoretic perspective to study the task of learning physical operations in a quantum machine when all operations (state preparation, dynamics, and measurement) are a priori unknown. We prove that, without any prior knowledge, if one can explore the full quantum state space by composing the operations, then every operation can be learned. When one cannot explore the full state space but all operations are approximately known and noise in Clifford gates is gate-independent, we find an efficient algorithm for learning all operations up to a single unlearnable parameter characterizing the fidelity of the initial state. For learning a noise channel on Clifford gates to a fixed accuracy, our algorithm uses quadratically fewer experiments than previously known protocols. Under more general conditions, the true description of the noise can be unlearnable; for example, we prove that no benchmarking protocol can learn gate-dependent Pauli noise on Clifford+T gates even under perfect state preparation and measurement. Despite not being able to learn the noise, we show that a noisy quantum computer that performs entangled measurements on multiple copies of an unknown state can yield a large advantage in learning properties of the state compared to a noiseless device that measures individual copies and then processes the measurement data using a classical computer. Concretely, we prove that noisy quantum computers with two-qubit gate error rate ε can achieve a learning task using N copies of the state, while NΩ(1/ε) copies are required classically.