Nonstabilizerness, commonly referred to as magic, is essential for universal quantum computation. Yet, for pure $n$-qubit states this property is directly linked to the hardness of direct fidelity estimation. We propose a scheme to bound the fidelity on non-stabilizer states by choosing operators with low measurement overhead and using parallel local Pauli measurements to estimate compatible observables. We selectively measure operators that share a permutational symmetry without imposing any assumption on the physical system. This selection reduces the optimization to a linear program with only $O(n)$ variables for bounding fidelity. Our methods can be extended to bound nonlinear quantities like the purity via convex quadratic programs. For hypergraph states that can exhibit extensive nonstabilizerness, we demonstrate for up to $n=500$ qubits that our framework substantially reduces the measurement overhead under both local and global depolarizing noise. These results show that symmetry induced by measurement selection reduces both measurement and computational costs, enabling scalable characterization of magic resources in quantum computing and quantum networks.
AI Summary
The paper asks how to bound fidelity to non-stabilizer pure states using incomplete local Pauli measurement data, without assuming a noise model or symmetry of the prepared state. It writes a target as the unique common $+1$ eigenstate of commuting generalized stabilizers $g_i=UZ_iU^\dagger$, and groups their products into order-$k$ moments $S^{(k)}$.
These moments depend only on the Hamming weight of the common-eigenbasis label. Their joint numerical range is therefore the convex hull of $n+1$ points, reducing worst-case fidelity minimization and maximization to linear programs with $n+1$ probability variables. This reduction is exact for the retained moment constraints. Finite-sample uncertainty enters through inequality constraints; replacing the objective with $\sum_m p_m^2/\binom{n}{m}$ gives a convex quadratic program for a purity lower bound.
For hypergraph states, each order-$k$ stabilizer requires at most $2^{k-1}$ parallel local Pauli settings. Randomly sampling constituent stabilizers estimates moments through order $K$ to additive error $\epsilon$, jointly with confidence $1-\delta$, using $O(2^K\ln(K/\delta)/\epsilon^2)$ copies. The guarantee follows from concentration inequalities and a variance identity. Noise-model calculations up to $n=500$ compare fidelity-interval costs with standard direct fidelity estimation, including examples at true fidelity $0.6$.
The measurement bound is independent of $n$ only at fixed $K$ and $\epsilon$; it does not guarantee a prescribed fidelity precision universally. Interval tightness depends on the observed moments, and stronger noise can require larger $K$ or yield trivial lower bounds. Numerical comparisons use model-predicted expectation values rather than simulated finite-shot datasets.
Little sign of AI-generated textMissing comparison
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Nonstabilizerness, commonly referred to as magic, is essential for universal quantum computation. Yet, for pure n-qubit states this property is directly linked to the hardness of direct fidelity estimation. We propose a scheme to bound the fidelity on non-stabilizer states by choosing operators with low measurement overhead and using parallel local Pauli measurements to estimate compatible observables. We selectively measure operators that share a permutational symmetry without imposing any assumption on the physical system. This selection reduces the optimization to a linear program with only O(n) variables for bounding fidelity. Our methods can be extended to bound nonlinear quantities like the purity via convex quadratic programs. For hypergraph states that can exhibit extensive nonstabilizerness, we demonstrate for up to n=500 qubits that our framework substantially reduces the measurement overhead under both local and global depolarizing noise. These results show that symmetry induced by measurement selection reduces both measurement and computational costs, enabling scalable characterization of magic resources in quantum computing and quantum networks.
The paper asks how to bound fidelity to non-stabilizer pure states using incomplete local Pauli measurement data, without assuming a noise model or symmetry of the prepared state. It writes a target as the unique common +1 eigenstate of commuting generalized stabilizers gi=UZiU†, and groups their products into order-k moments S(k).
These moments depend only on the Hamming weight of the common-eigenbasis label. Their joint numerical range is therefore the convex hull of n+1 points, reducing worst-case fidelity minimization and maximization to linear programs with n+1 probability variables. This reduction is exact for the retained moment constraints. Finite-sample uncertainty enters through inequality constraints; replacing the objective with ∑mpm2/(mn) gives a convex quadratic program for a purity lower bound.
For hypergraph states, each order-k stabilizer requires at most 2k−1 parallel local Pauli settings. Randomly sampling constituent stabilizers estimates moments through order K to additive error ϵ, jointly with confidence 1−δ, using O(2Kln(K/δ)/ϵ2) copies. The guarantee follows from concentration inequalities and a variance identity. Noise-model calculations up to n=500 compare fidelity-interval costs with standard direct fidelity estimation, including examples at true fidelity 0.6.
The measurement bound is independent of n only at fixed K and ϵ; it does not guarantee a prescribed fidelity precision universally. Interval tightness depends on the observed moments, and stronger noise can require larger K or yield trivial lower bounds. Numerical comparisons use model-predicted expectation values rather than simulated finite-shot datasets.
The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of mn-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements m and polynomial in the number of qubits n. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless P=NP, no algorithm polynomial in m can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.
Nonstabilizerness or magic resource characterizes the amount of non-Clifford operations needed to prepare quantum states.It is a crucial resource for quantum computing and a necessary condition for quantum advantage.However, quantifying magic resource beyond a few qubits has been a major challenge.Here, we introduce efficient measures of magic resource for pure quantum states with a sampling cost that is independent of the number of qubits.Our method uses Bell measurements over two copies of a state, which we implement in experiment together with a cost-free error-mitigation scheme.We show the transition of classically simulable stabilizer states into intractable quantum states on the IonQ quantum computer.For applications, we efficiently distinguish stabilizer and nonstabilizer states with low measurement cost even in the presence of experimental noise.Further, we propose a variational quantum algorithm to maximize our measure via the shift rule.Our algorithm can be free of barren plateaus even for highly expressible variational circuits.Finally, we experimentally demonstrate a Bell-measurement protocol for the stabilizer Rényi entropy as well as the Wallach-Meyer entanglement measure.Our results pave the way to understanding the nonclassical power of quantum computers, quantum simulators, and quantum many-body systems.
Direct fidelity estimation (DFE) is a famous tool for estimating the fidelity with a target pure state. However, such a method generally requires exponentially many sampling copies due to the large magic of the target state. This work proposes a sample- and gate-efficient fidelity estimation algorithm that is affordable within feasible quantum devices. We show that the fidelity estimation with pure states close to the structure of phase states, for which sample-efficient DFE is limited by their strong entanglement and magic, can be done by using O(poly(n)) sampling copies, with a single n-qubit fan-out gate. As the target state becomes a phase state, the sampling complexity reaches O(1). Such a drastic improvement stems from a crucial step in our scheme, the so-called phase stripping, which can significantly reduce the target-state magic. Furthermore, we convert a complex diagonal gate resource, which is needed to design a phase-stripping-adapted algorithm, into nonlinear classical post-processing of Pauli measurements so that we only require a single fan-out gate. Additionally, as another variant using the nonlinear post-processing, we propose a nonlinear extension of the conventional DFE scheme. Here, the sampling reduction compared to DFE is also guaranteed, while preserving the Pauli measurement as the only circuit resource. We expect our work to contribute to establishing noise-resilient quantum algorithms by enabling a significant reduction in sampling overhead for fidelity estimation under the restricted gate resources, and ultimately to clarifying a fundamental gap between the resource overhead required to understand complex physical properties and that required to generate them.
Magic, or nonstabilizerness, characterizes the deviation of a quantum state from the set of stabilizer states, playing a fundamental role in quantum state complexity and universal fault-tolerant quantum computing. However, analytical and numerical characterizations of magic are very challenging, especially for multi-qubit systems, even with a moderate qubit number. Here, we systemically and analytically investigate the magic resource of archetypal multipartite quantum states—quantum hypergraph states, which can be generated by multi-qubit controlled-phase gates encoded by hypergraphs. We first derive the magic formula in terms of the stabilizer Rényi- α entropies for general quantum hypergraph states. If the average degree of the corresponding hypergraph is constant, we show that magic cannot reach the maximal value, i.e., the number of qubits n . Then, we investigate the statistical behaviors of random hypergraph states' magic and prove a concentration result, indicating that random hypergraph states typically reach the maximum magic. This also suggests an efficient way to generate maximal magic states with random diagonal circuits. Finally, we study hypergraph states with permutation symmetry, such as 3 -complete hypergraph states, where any three vertices are connected by a hyperedge. Counterintuitively, such states can only possess constant or even exponentially small magic for α≥2 . Our study advances the understanding of multipartite quantum magic and could lead to applications in quantum computing and quantum many-body physics.
Magic (nonstabilizerness) is a necessary but "expensive" kind of "fuel" to drive universal fault-tolerant quantum computation.To properly study and characterize the origin of quantum "complexity" in computation as well as physics, it is crucial to develop a rigorous understanding of the quantification of magic.Previous studies of magic mostly focused on small systems and largely relied on the discrete Wigner formalism (which is only well behaved in odd prime power dimensions).Here we present an initiatory study of the magic of genuinely many-body quantum states that may be strongly entangled, with focus on the important case of many qubits, at a quantitative level.We first address the basic question of how "magical" a many-body state can be, and show that the maximum magic of an n-qubit state is essentially n, simultaneously for a range of "good" magic measures.As a corollary, the resource theory of magic has asymptotic golden currency states.We then show that, in fact, almost all n-qubit pure states have magic of nearly n.In the quest for explicit, scalable cases of highly entangled states whose magic can be understood, we connect the magic of hypergraph states with the second-order nonlinearity of their underlying Boolean functions.Next, we go on and investigate many-body magic in practical and physical contexts.We first consider a variant of measurement-based quantum computation where the client is restricted to Pauli measurements, in which magic is a necessary feature of the initial "resource" state.We show that n-qubit states with nearly n magic, or indeed almost all states, cannot supply nontrivial speedups over classical computers.We then present an example of analyzing the magic of "natural" condensed matter systems of physical interest.We apply the Boolean function techniques to derive explicit bounds on the magic of certain representative two-dimensional symmetry-protected topological states, and comment on possible further connections between magic and the quantum complexity of phases of matter.
Direct fidelity estimation provides a way to estimate the fidelity between an experimentally prepared state and a desired pure target state without performing full tomography. Two influential formulations were introduced in 2011 by Flammia and Liu and by da Silva, Landon-Cardinal, and Poulin. In these protocols, the total estimation error is controlled through two distinct probabilistic steps: first, the fidelity is approximated using randomly sampled Pauli observables; second, each sampled expectation value is estimated from finitely many measurement outcomes. In this work we show that additional structural information about the noise can substantially sharpen the corresponding resource bounds. In particular, for some canonical channels the effective number of sampled Pauli settings can be reduced, leading to lower measurement cost both in the general pure-state setting and in the case of a stabilizer state. These results illustrate a broader point: worst-case confidence bounds in direct fidelity estimation can be significantly conservative when experimentally relevant structure is ignored. As a technical ingredient, we also revisit the allocation of the total accuracy and confidence budgets between the two probabilistic steps. Reformulating the analysis in terms of separate error parameters yields a constrained optimization problem whose solution lowers the average number of measurements in the general pure-state setting. Numerical simulations based on quantum circuits implemented in Qiskit illustrate both the improvement obtained under structured-noise assumptions and the conservativeness of the original worst-case bounds.