We present a novel classical algorithm designed to learn the stabilizer group-namely, the group of Pauli strings for which a state is a ±1 eigenvector-of a given matrix product state (MPS). The algorithm is based on a clever and theoretically grounded biased sampling in the Pauli (or Bell) basis. Its output is a set of independent stabilizer generators whose total number is directly associated with the stabilizer nullity, notably a well-established nonstabilizer monotone. We benchmark our method on T-doped states randomly scrambled via Clifford unitary dynamics, demonstrating very accurate estimates up to highly entangled MPS with bond dimension χ∼10^{3}. Our method, thanks to a very favorable scaling O(χ^{3}), represents the first effective approach to obtain a genuine magic monotone for MPS, enabling systematic investigations of quantum many-body physics out of equilibrium.
We present a novel classical algorithm designed to learn the stabilizer group -- namely the group of Pauli strings for which a state is a
±1 eigenvector -- of a given Matrix Product State (MPS). The algorithm is based on a clever and theoretically grounded biased sampling in the Pauli (or Bell) basis. Its output is a set of independent stabilizer generators whose total number is directly associated with the stabilizer nullity, notably a well-established nonstabilizer monotone. We benchmark our method on
T-doped states randomly scrambled via Clifford unitary dynamics, demonstrating very accurate estimates up to highly-entangled MPS with bond dimension
χ∼103. Our method, thanks to a very favourable scaling
O(χ3), represents the first effective approach to obtain a genuine magic monotone for MPS, enabling systematic investigations of quantum many-body physics out-of-equilibrium.
We introduce a novel approach to evaluate the nonstabilizerness of an N-qubits matrix product state (MPS) with bond dimension χ. In particular, we consider the recently introduced stabilizer Rényi entropies (SREs). We show that the exponentially hard evaluation of the SREs can be achieved by means of a simple perfect sampling of the many-body wave function over the Pauli string configurations. The sampling is achieved with a novel MPS technique, which enables us to compute each sample in an efficient way with a computational cost O(Nχ^{3}). We benchmark our method over randomly generated magic states, as well as in the ground-state of the quantum Ising chain. Exploiting the extremely favorable scaling, we easily have access to the nonequilibrium dynamics of the SREs after a quantum quench.
Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical framework for computing stabilizer Rényi entropies and stabilizer nullity of generic
N-qubit wavefunctions. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators, reducing the average cost per sampled Pauli string from
O(2N) to
O(N). We further develop a Monte Carlo estimator with Clifford preconditioning and find that the required number of samples shows no visible growth with
N in our benchmarks. Applying the method to
T-doped random Clifford circuits, we identify the scrambling ratio
η (Clifford gates per
T gate) as the key parameter governing magic growth. Each
T gate approaches its dilute-limit nonstabilizerness power with only modest Clifford scrambling. Our approach enables quantitative studies of magic in highly entangled states and long-time nonequilibrium dynamics.
Bell sampling efficiently learns the stabilizer group, and hence the stabilizer nullity, of pure states with little magic, a primitive underlying tomography and certification of low-magic states. Real devices, however, only prepare noisy images of the target, which we model as a Pauli channel acting on the ideal state; the resulting noisy state generically has no exact Pauli stabilizers. Existing structure learners for mixed states rely on such exact stabilizers. Agnostic tomography does not, but its guarantees scale exponentially in the nullity
t. We show that the ideal stabilizer group remains encoded in the noisy state as the set of Pauli operators under which it is invariant. We give Bell-sampling algorithms that learn the group to accuracy
ε for states of nullity at most
t. The difficulty is that noisy samples break the group structure pure-state learners rely on, so more samples can erase structure rather than reveal it. We resolve this with a finder-verifier scheme that extracts stabilizer structure from partially corrupted sample batches while certifying proposed updates. For sufficiently weak global depolarizing noise, both samples and runtime are
poly(n,t,1/ε) when the channel's total error probability is at most of order
εn/t. Up to a constant total error probability (
≈0.16), samples remain polynomial while classical processing costs
2t, and for any error probability below one a
4t overhead suffices. Arbitrary Pauli channels exhibit the same three regimes, with more restrictive thresholds. For weak Pauli noise, this closes much of the gap between agnostic learners such as stabilizer bootstrapping and polynomial pure-state algorithms.
Nonstabilizerness, also known as "magic," stands as a crucial resource for achieving a potential advantage in quantum computing. Its connection to many-body physical phenomena is poorly understood at present, mostly due to a lack of practical methods to compute it at large scales. We present a novel approach for the evaluation of nonstabilizerness within the framework of matrix product states (MPSs), based on expressing the MPS directly in the Pauli basis. Our framework provides a powerful tool for efficiently calculating various measures of nonstabilizerness, including stabilizer Rényi entropies, stabilizer nullity, and Bell magic, and enables the learning of the stabilizer group of an MPS. We showcase the efficacy and versatility of our method in the ground states of Ising and XXZ spin chains, as well as in circuits dynamics that has recently been realized in Rydberg atom arrays, where we provide concrete benchmarks for future experiments on logical qubits up to twice the sizes already realized.
Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical framework for computing stabilizer Rényi entropies and stabilizer nullity of generic N-qubit wave functions. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators, reducing the average cost per sampled Pauli string from O(2^{N}) to O(N). We further develop a Monte Carlo estimator with Clifford preconditioning and find that the required number of samples shows no visible growth with N in our benchmarks. Applying the method to T-doped random Clifford circuits, we identify the scrambling ratio η (Clifford gates per T gate) as the key parameter governing magic growth. Each T gate approaches its dilute-limit nonstabilizerness power with only modest Clifford scrambling. Our approach enables quantitative studies of magic in highly entangled states and long-time nonequilibrium dynamics.