We develop a framework for learning from noisy quantum experiments in which fault-tolerant devices access uncharacterized systems through noisy couplings. Introducing the complexity class $\textsf{NBQP}$ ("noisy BQP''), we model noisy fault-tolerant quantum computers that cannot generally error-correct the oracle systems they query. Using this class, we prove that while noise can eliminate the exponential quantum learning advantages of unphysical, noiseless learners, a superpolynomial gap remains between $\textsf{NISQ}$ and fault-tolerant devices. Turning to canonical learning tasks in noisy settings, we find that the exponential two-copy advantage for purity testing collapses under local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient physical structure restores this quantum learning advantage. We then analyze noisy Pauli shadow tomography, deriving lower bounds characterizing how instance size, quantum memory and noise jointly control sample complexity, and design algorithms with parametrically matching scalings. We study similar tradeoffs in quantum metrology, and show that the Heisenberg-limited sensitivity of existing error-correction-based protocols persists only up to a timescale inverse-polynomial in the error rate per probe qubit. Together, our results demonstrate that the primitives underlying quantum-enhanced experiments are fundamentally fragile to noise, and that realizing meaningful quantum advantages in future experiments will require interfacing noise-robust physical properties with available algorithmic techniques.
We develop a framework for learning from noisy quantum experiments in which fault-tolerant devices access uncharacterized systems through noisy couplings. Introducing the complexity class NBQP ("noisy BQP''), we model noisy fault-tolerant quantum computers that cannot generally error-correct the oracle systems they query. Using this class, we prove that while noise can eliminate the exponential quantum learning advantages of unphysical, noiseless learners, a superpolynomial gap remains between NISQ and fault-tolerant devices. Turning to canonical learning tasks in noisy settings, we find that the exponential two-copy advantage for purity testing collapses under local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient physical structure restores this quantum learning advantage. We then analyze noisy Pauli shadow tomography, deriving lower bounds characterizing how instance size, quantum memory and noise jointly control sample complexity, and design algorithms with parametrically matching scalings. We study similar tradeoffs in quantum metrology, and show that the Heisenberg-limited sensitivity of existing error-correction-based protocols persists only up to a timescale inverse-polynomial in the error rate per probe qubit. Together, our results demonstrate that the primitives underlying quantum-enhanced experiments are fundamentally fragile to noise, and that realizing meaningful quantum advantages in future experiments will require interfacing noise-robust physical properties 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.
Classical verification of quantum learning allows classical clients to reliably leverage quantum computing advantages by interacting with untrusted quantum servers. Yet, current quantum devices available in practice suffers from a variety of noises and whether existed classical verification protocols carry over to noisy scenarios remains unclear. Here, we propose an efficient classical error rectification algorithm to reconstruct the noise-free results given by the quantum Fourier sampling circuit with practical constant-level noises. In particular, we prove that the error rectification algorithm can restore the heavy Fourier coefficients by using a small number of noisy samples that scales logarithmically with the problem size. We apply this algorithm to the agnostic parity learning task with uniform input marginal and prove that this task can be accomplished in an efficient way on noisy quantum devices with our algorithm. In addition, we prove that a classical client with access to the random example oracle can verify the agnostic parity learning results from the noisy quantum prover in an efficient way, under the condition that the Fourier coefficients are sparse. Our results demonstrate the feasibility of classical verification of quantum learning advantages with noises, which provide a valuable guide for both theoretical studies and practical applications with current noisy intermediate scale quantum devices.
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.
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.
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.