Quantum fidelity estimation is essential for benchmarking quantum states and processes on noisy quantum devices. While stabilizer operations form the foundation of fault-tolerant quantum computing, nonstabilizer resources further enable universal quantum computation through state injection. In this work, we propose several efficient quantum fidelity estimation protocols for both quantum states and channels within the resource theory of nonstabilizerness, focusing on qudit systems with odd prime dimensions. Our fidelity estimation algorithms require measuring only a constant number of phase-space point operator expectation values, with operators selected randomly according to an importance weighting scheme tailored to the target state. Notably, we demonstrate that mathematically defined nonstabilizerness measures---such as Wigner rank and mana---quantify the sample complexity of the proposed protocols, thereby endowing them with a clear operational interpretation in the fidelity estimation task. This connection reveals a fundamental trade-off: while fidelity estimation for general quantum states and channels requires resources that scale exponentially with their nonstabilizerness, the task remains tractable for states and channels that admit efficient classical simulation.
Quantum fidelity estimation is essential for benchmarking quantum states and processes on noisy quantum devices. While stabilizer operations form the foundation of fault-tolerant quantum computing, nonstabilizer resources further enable universal quantum computation through state injection. In this work, we propose several efficient quantum fidelity estimation protocols for both quantum states and channels within the resource theory of nonstabilizerness, focusing on qudit systems with odd prime dimensions. Our fidelity estimation algorithms require measuring only a constant number of phase-space point operator expectation values, with operators selected randomly according to an importance weighting scheme tailored to the target state. Notably, we demonstrate that mathematically defined nonstabilizerness measures---such as Wigner rank and mana---quantify the sample complexity of the proposed protocols, thereby endowing them with a clear operational interpretation in the fidelity estimation task. This connection reveals a fundamental trade-off: while fidelity estimation for general quantum states and channels requires resources that scale exponentially with their nonstabilizerness, the task remains tractable for states and channels that admit efficient classical simulation.
We propose an efficient protocol to estimate the fidelity of an n-qubit entangled measurement device, requiring only qubit state preparations and classical data post-processing. It works by measuring the eigenstates of Pauli operators, which are strategically selected according to their importance weights and collectively contributed by all measurement operators. We rigorously analyze the protocol's performance and demonstrate that its sample complexity is uniquely determined by the number of Pauli operators possessing non-zero expectation values with respect to the target measurement. Moreover, from a resource-theoretic perspective, we introduce the stabilizer Rényi entropy of quantum measurements as a precise metric to quantify the inherent difficulty of estimating measurement fidelity.
To achieve universal quantum computation via general fault-tolerant schemes, stabilizer operations must be supplemented with other non-stabilizer quantum resources. Motivated by this necessity, we develop a resource theory for magic quantum channels to characterize and quantify the quantum 'magic' or non-stabilizerness of noisy quantum circuits. For qudit quantum computing with odd dimension d, it is known that quantum states with non-negative Wigner function can be efficiently simulated classically. First, inspired by this observation, we introduce a resource theory based on completely positive-Wigner-preserving quantum operations as free operations, and we show that they can be efficiently simulated via a classical algorithm. Second, we introduce two efficiently computable magic measures for quantum channels, called the mana and thauma of a quantum channel. As applications, we show that these measures not only provide fundamental limits on the distillable magic of quantum channels, but they also lead to lower bounds for the task of synthesizing non-Clifford gates. Third, we propose a classical algorithm for simulating noisy quantum circuits, whose sample complexity can be quantified by the mana of a quantum channel. We further show that this algorithm can outperform another approach for simulating noisy quantum circuits, based on channel robustness. Finally, we explore the threshold of non-stabilizerness for basic quantum circuits under depolarizing noise.
Fidelity estimation is a fundamental tool for assessing quantum resource states across quantum information science. For small infidelity ε, tomography and direct fidelity estimation (DFE) have worst-case sample complexity O(1/ε2) at fixed relative accuracy and confidence. Direct target projections achieve O(1/ε) but generally require non-Clifford operations whose reliability depends on the resource states that are typically the target of benchmarking. Here, we introduce the Bell--coherence fidelity estimation (BCFE) with optimal sample complexity Θ(1/ε) using only Clifford gates and Pauli measurements. We prove that BCFE is applicable to arbitrary pure targets, possibly multi-qubit, with the statistical error of the single-copy coherence part explicitly controlled. To evaluate BCFE in a practical setting, we apply BCFE to analog rotation resource states in the candidate early-FTQC architecture called the Space-Time Efficient Analog Rotations (STAR) architecture. In the simulations using surface codes, BCFE is estimated to require up to approximately 27 times fewer resource states than DFE for the same standard error in the infidelity estimate, while its estimates remain close to reference values despite circuit-level noise in the additional Bell measurement operations. These results support efficient resource benchmarking within fault-tolerant quantum computing.
Quantum state purification aims to recover higher-fidelity quantum states from multiple noisy copies and is a fundamental primitive for quantum information processing. Magic resources enable operations beyond classically simulable dynamics and are central to universal fault-tolerant quantum computation. Recent no-go results show that classically simulable operations cannot achieve a nontrivial universal fidelity gain. This motivates a quantitative theory of the magic required for purification at prescribed success probability and target fidelity. For universal purification with two input copies, we prove an exact linear mana law in odd dimensions and a two-sided linear robustness law for multi-qubit systems, which becomes exact for a single qubit. We also identify an explicit successful purification map that makes the tradeoff transparent. These results establish universal purification as a task obeying a quantitative magic-fidelity law and link magic resources to error mitigation and fault-tolerant quantum information processing.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown n-qudit pure state ∣ψ⟩ that has fidelity τ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension d is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
Abstract To achieve universal quantum computation via general fault-tolerant schemes, stabilizer operations must be supplemented with other non-stabilizer quantum resources. Motivated by this necessity, we develop a resource theory for magic quantum channels to characterize and quantify the quantum ‘magic’ or non-stabilizerness of noisy quantum circuits. For qudit quantum computing with odd dimension d , it is known that quantum states with non-negative Wigner function can be efficiently simulated classically. First, inspired by this observation, we introduce a resource theory based on completely positive-Wigner-preserving quantum operations as free operations, and we show that they can be efficiently simulated via a classical algorithm. Second, we introduce two efficiently computable magic measures for quantum channels, called the mana and thauma of a quantum channel. As applications, we show that these measures not only provide fundamental limits on the distillable magic of quantum channels, but they also lead to lower bounds for the task of synthesizing non-Clifford gates. Third, we propose a classical algorithm for simulating noisy quantum circuits, whose sample complexity can be quantified by the mana of a quantum channel. We further show that this algorithm can outperform another approach for simulating noisy quantum circuits, based on channel robustness. Finally, we explore the threshold of non-stabilizerness for basic quantum circuits under depolarizing noise.