Quantum purity amplification (QPA) provides a novel approach to counteracting the pervasive noise that degrades quantum states. We present the optimal QPA protocol for general quantum systems and global noise, resolving a two-decade open problem. Under strong depolarization, our protocol achieves an exponential reduction in sample complexity over the best-known methods. We provide an efficient implementation of the protocol based on generalized quantum phase estimation. Additionally, we introduce SWAPNET, a sparse and shallow circuit that enables QPA for near-term experiments. Simulations in both digital and analog quantum settings, along with experiments on superconducting quantum processors, confirm the protocol's robustness and practical utility. Our findings suggest that QPA could improve the performance of quantum information processing tasks, particularly in the context of Noisy Intermediate-Scale Quantum (NISQ) devices, where reducing the effect of noise with limited resources is critical.
Quantum purity amplification (QPA) provides a novel approach to counteracting the pervasive noise that degrades quantum states. We present the optimal QPA protocol for general quantum systems and global noise, resolving a two-decade open problem. Under strong depolarization, our protocol achieves an exponential reduction in sample complexity over the best-known methods. We provide an efficient implementation of the protocol based on generalized quantum phase estimation. Additionally, we introduce SWAPNET, a sparse and shallow circuit that enables QPA for near-term experiments. Simulations in both digital and analog quantum settings, along with experiments on superconducting quantum processors, confirm the protocol's robustness and practical utility. Our findings suggest that QPA could improve the performance of quantum information processing tasks, particularly in the context of Noisy Intermediate-Scale Quantum (NISQ) devices, where reducing the effect of noise with limited resources is critical.
Quantum purity amplification (QPA) is the task of coherently transforming n copies of a mixed state into high-fidelity copies of a chosen eigenstate. We develop a general theory of QPA for n input copies, m output copies, and arbitrary choices of target eigenstate, local dimension d, and input spectrum. We introduce the overhang-removal protocol, derive its all-site and one-site fidelities across output regimes, and show that it is optimal in several regimes, both asymptotically and nonasymptotically. For the asymptotic analysis, we use a path-graph parametrization to show that, when the target eigenvalue has a constant spectral gap Dk,min, achieving worst-case all-site error ε scales as O(m/(εDk,min2)). When m/n approaches a constant, the performance exhibits phase-like regimes, which we characterize explicitly. For the nonasymptotic analysis, we develop a theory of generalized Young diagrams that yields tight sample complexity bounds and provides the first tight dimension-uniform guarantee for optimal QPA. We also provide asymptotically efficient implementations of the overhang-removal protocol. Together, these results establish QPA as a rigorous example of coherent quantum information processing with dimension-uniform sample complexity, supplying the technical foundation for the coherent-incoherent separation developed in the companion work.
Standard quantum inference converts quantum data into classical outputs. We study an alternative inference setting in which the desired output is quantum. Such settings include quantum purity amplification (QPA), random purification and approximate cloning, and density matrix exponentiation. We show that such protocols can achieve exponentially lower sample complexity than incoherent, measurement-mediated protocols, establishing, to the best of our knowledge, the first nontrivial separations between dimension-independent coherent and dimension-dependent incoherent sample complexity. For QPA with principal-eigenstate targets and d-dimensional inputs, at fixed output number and spectral gap, coherent processing achieves error ε using O(1/ε) copies, whereas any incoherent protocol requires Ω(d/ε) copies. Together, these separations motivate a unified picture of coherent quantum inference, in which an entanglement-breaking limit identifies the optimal incoherent counterpart.
As quantum processors move into the noisy intermediate-scale quantum (NISQ) era, the central question is no longer whether a quantum algorithm is asymptotically faster than its classical counterpart, but whether it can retain a meaningful speedup under realistic noise, compilation, and measurement constraints. This work develops a quantitative framework for characterizing the noise resilience of quantum advantage. We introduce the advantage robustness function RA(ε), which measures how the asymptotic and concrete performance of an algorithm A degrades with physical error rate ε, and we compute it analytically or numerically for twelve representative algorithm families, including Grover search, amplitude estimation, phase estimation, HHL, VQE/QAOA, Hamiltonian simulation, and sampling algorithms. For each class, we derive critical noise thresholds and depth limits beyond which classical algorithms regain supremacy, explicitly incorporating realistic connectivity and compilation overheads. We show that algorithms based on coherent amplitude amplification are more fragile to coherent errors than depolarizing noise, while variational algorithms display a tradeoff between expressivity and robustness. By combining these algorithm-specific robustness curves with current and projected hardware error rates for superconducting, trapped-ion, neutralatom, and photonic platforms, we map out a phase diagram of practical quantum advantage that links problem size, noise rate, and algorithm type. Our analysis identifies promising near-term application windows in risk analytics, small-molecule chemistry, and structured optimization, and also delineates regions where no advantage is realistic, providing valuable guidance for both algorithm designers and hardware architects.
Suppressing noise in physical systems is of fundamental importance.As quantum computers mature, quantum error correcting codes (QECs) will be adopted in order to suppress errors to any desired level.However in the noisy, intermediate-scale quantum (NISQ) era, the complexity and scale required to adopt even the smallest QEC is prohibitive: a single logical qubit needs to be encoded into many thousands of physical qubits.Here we show that, for the crucial case of estimating expectation values of observables (key to almost all NISQ algorithms) one can indeed achieve an effective exponential suppression.We take n independently prepared circuit outputs to create a state whose symmetries prevent errors from contributing bias to the expected value.The approach is very well suited for current and near-term quantum devices as it is modular in the main computation and requires only a shallow circuit that bridges the n copies immediately prior to measurement.Using no more than four circuit copies, we confirm error suppression below 10 -6 for circuits consisting of several hundred noisy gates (2-qubit gate error 0.5%) in numerical simulations validating our approach.
In quantum purity amplification, one is given n copies of a noisy quantum state ρ∈Cd×d and asked to prepare k copies of its principal eigenstate ∣vd⟩. Several prior works have derived information-theoretically optimal algorithms for this problem, but the bounds they prove are only shown in the asymptotic regime as the number of samples n tends to infinity. In this paper, we establish the following nonasymptotic guarantee: if ρ's eigenvalues are sorted p1≤⋯≤pd and pd−1<pd, then \begin{equation*}
n = O\Big(k + \frac{k}δ \cdot \frac{1-p_d}{(p_d-p_{d-1})^2}\Big)
\end{equation*} copies suffice to output a state with fidelity at least 1−δ with ∣vd⊗k⟩. Our bound holds for arbitrary spectra, and is independent of the dimension d. In the case of depolarizing noise, our finite-sample guarantee matches the optimal asymptotic scaling. Our proof is based on the combinatorics of random Young diagrams.
Analog quantum simulation has been proposed as an efficient approach for
probing classically intractable many-body physics. In contrast to digital,
gate-based quantum simulation, the analog approach involves configuring the
quantum hardware to directly mimic the physics of the target system. This
reduces the level of control required and can offer a degree of inherent
robustness, but it comes at the cost that known error-handling techniques may
be inapplicable. Accumulation of error is thus a major challenge facing
medium-scale and large-scale analog quantum simulation with current and
near-term noisy quantum (NISQ) devices. Here we propose a hybrid error
mitigation scheme that can suppress general local Markovian noise in analog
quantum simulators. We employ stochastic error mitigation for physical noise
and use Richardson extrapolation to compensate for model estimation error. We
numerically test the error mitigation scheme for an Ising-type Hamiltonian with
energy relaxation and dephasing noise, and show an improvement of simulation
accuracy by two orders. We assess the resource cost of our error mitigation
scheme and conclude that analog quantum simulation at scale is feasible with
NISQ hardware.