Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2207.13076 · Physical review. B./Physical review. B

Quantifying nonstabilizerness of matrix product states

Tobias Haug, Lorenzo Piroli

Published Jan 27, 2023• 151 citations
arXivHTMLPDF

Abstract

Nonstabilizerness, also known as magic, quantifies the number of non-Clifford operations needed to prepare a quantum state. As typical measures either involve minimization procedures or a computational cost exponential in the number of qubits $N$, it is notoriously hard to characterize for many-body states. In this paper, we show that nonstabilizerness, as quantified by the recently introduced stabilizer R\'enyi entropies (SREs), can be computed efficiently for matrix product states (MPSs). Specifically, given an MPS of bond dimension $\ensuremath{\chi}$ and integer R\'enyi index $n>1$, we show that the SRE can be expressed in terms of the norm of an MPS with bond dimension ${\ensuremath{\chi}}^{2n}$. For translation-invariant states, this allows us to extract it from a single tensor, the transfer matrix, while for generic MPSs this construction yields a computational cost linear in $N$ and polynomial in $\ensuremath{\chi}$. We exploit this observation to revisit the study of ground-state nonstabilizerness in the quantum Ising chain, providing accurate numerical results up to large system sizes. We analyze the SRE near criticality and investigate its dependence on the local computational basis, showing that it is, in general, not maximal at the critical point.

DOI
10.1103/physrevb.107.035148

Related papers

Efficient mutual magic and magic capacity with matrix product states

Poetri Sonya Tarabunga, Tobias Haug

Stabilizer Rényi entropies (SREs) probe the non-stabilizerness (or “magic”) of many-body systems and quantum computers. Here, we introduce the mutual von-Neumann SRE and magic capacity, which can be efficiently computed in time O(N\chi^3) O ( N χ 3 ) for matrix product states (MPSs) of bond dimension \chi χ . We find that mutual SRE characterizes the critical point of ground states of the transverse-field Ising model, independently of the chosen local basis. Then, we relate the magic capacity to the anti-flatness of the Pauli spectrum, which quantifies the complexity of computing SREs. The magic capacity characterizes transitions in the ground state of the Heisenberg and Ising model, randomness of Clifford+T circuits, and distinguishes typical and atypical states. Finally, we make progress on numerical techniques: we design two improved Monte-Carlo algorithms to compute the mutual 2 2 -SRE, overcoming limitations of previous approaches based on local update. We also give improved statevector simulation methods for Bell sampling and SREs with O(8^{N/2}) O ( 8 N / 2 ) time and O(2^N) O ( 2 N ) memory, which we demonstrate for 24 24 qubits. Our work uncovers improved approaches to study the complexity of quantum many-body systems.

arXiv:2504.07230•SciPost Physics•Oct 6, 2025•38 citations

Nonstabilizerness via Perfect Pauli Sampling of Matrix Product States

Guglielmo Lami, Mario Collura

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.

arXiv:2303.05536•Physical Review Letters•Oct 31, 2023•130 citations

Spectral signatures of nonstabilizerness and criticality in infinite matrix product states

Andrew Hallam, Ryan Smith, Zlatko Papić

While nonstabilizerness (''magic'') is a key resource for universal quantum computation, its behavior in many-body quantum systems, especially near criticality, remains poorly understood. We develop a spectral transfer-matrix framework for the stabilizer Rényi entropy (SRE) in infinite matrix product states, showing that its spectrum contains universal subleading information. In particular, we identify an SRE correlation length -- distinct from the standard correlation length -- which diverges at continuous phase transitions and governs the spatial response of the SRE to local perturbations. We derive exact SRE expressions for the bond dimension $χ=2$ MPS ''skeleton'' of the cluster-Ising model, and we numerically probe its universal scaling along the $\mathbb{Z}_2$ critical lines in the phase diagram. These results demonstrate that nonstabilizerness captures signatures of criticality and local perturbations, providing a new lens on the interplay between computational resources and emergent phenomena in quantum many-body systems.

quant-pharXiv:2602.15116•Physical review. B./Physical review. B•Feb 18, 2026•10 citations

Nonstabilizerness via Matrix Product States in the Pauli Basis

Poetri Sonya Tarabunga, Emanuele Tirrito, Mari Carmen Bañuls +1 more

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.

arXiv:2401.16498•Physical Review Letters•Jul 1, 2024•103 citations

Stabilizer Rényi entropy for translation-invariant matrix product states

L. Liu, Su Yi, Jian Cui

Magic, capturing the deviation of a quantum state from the stabilizer formalism, is a key resource underpinning the quantum advantage. The recently introduced stabilizer Rényi entropy (SRE) offers a tractable measure of magic, avoiding the complexity of conventional methods. We study SRE in translation-invariant matrix product states (MPS), deriving exact expressions for representative states and introducing a numerically stable algorithm, named bond-DMRG, to compute the SRE density in infinite systems. Applying this method, we obtain high-precision SRE densities for the ground state of the one-dimensional Ising model. We also analyze non-local SRE density, showing it is bounded by a universal function of entanglement entropy, and further prove that two-site mutual SRE vanishes asymptotically in injective MPS. Our work not only introduces a powerful method for extracting the SRE density in quantum many-body systems, but also numerically reveals a fundamental connection between magic and entanglement, thereby paving the way for deeper theoretical investigations into their interplay.

arXiv:2508.03534•Physical Review A•May 14, 2026•5 citations

Predicting Magic from Very Few Measurements

J. M. Varela, L. L. Keller, A. de Oliveira Junior +3 more

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 $m$ $n$-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 $\mathrm{P} = \mathrm{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.

quant-pharXiv:2602.18939•PRX Quantum•Feb 24, 2026•11 citations
Nonstabilizerness, also known as magic, quantifies the number of non-Clifford operations needed to prepare a quantum state. As typical measures either involve minimization procedures or a computational cost exponential in the number of qubits NNN, it is notoriously hard to characterize for many-body states. In this paper, we show that nonstabilizerness, as quantified by the recently introduced stabilizer R'enyi entropies (SREs), can be computed efficiently for matrix product states (MPSs). Specifically, given an MPS of bond dimension \ensuremathχ\ensuremath{\chi}\ensuremathχ and integer R'enyi index n>1n>1n>1, we show that the SRE can be expressed in terms of the norm of an MPS with bond dimension \ensuremathχ2n{\ensuremath{\chi}}^{2n}\ensuremathχ2n. For translation-invariant states, this allows us to extract it from a single tensor, the transfer matrix, while for generic MPSs this construction yields a computational cost linear in NNN and polynomial in \ensuremathχ\ensuremath{\chi}\ensuremathχ. We exploit this observation to revisit the study of ground-state nonstabilizerness in the quantum Ising chain, providing accurate numerical results up to large system sizes. We analyze the SRE near criticality and investigate its dependence on the local computational basis, showing that it is, in general, not maximal at the critical point.
Stabilizer Rényi entropies (SREs) probe the non-stabilizerness (or “magic”) of many-body systems and quantum computers. Here, we introduce the mutual von-Neumann SRE and magic capacity, which can be efficiently computed in time O(N\chi^3) O ( N χ 3 ) for matrix product states (MPSs) of bond dimension \chi χ . We find that mutual SRE characterizes the critical point of ground states of the transverse-field Ising model, independently of the chosen local basis. Then, we relate the magic capacity to the anti-flatness of the Pauli spectrum, which quantifies the complexity of computing SREs. The magic capacity characterizes transitions in the ground state of the Heisenberg and Ising model, randomness of Clifford+T circuits, and distinguishes typical and atypical states. Finally, we make progress on numerical techniques: we design two improved Monte-Carlo algorithms to compute the mutual 2 2 -SRE, overcoming limitations of previous approaches based on local update. We also give improved statevector simulation methods for Bell sampling and SREs with O(8^{N/2}) O ( 8 N / 2 ) time and O(2^N) O ( 2 N ) memory, which we demonstrate for 24 24 qubits. Our work uncovers improved approaches to study the complexity of quantum many-body systems.
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.
While nonstabilizerness (''magic'') is a key resource for universal quantum computation, its behavior in many-body quantum systems, especially near criticality, remains poorly understood. We develop a spectral transfer-matrix framework for the stabilizer Rényi entropy (SRE) in infinite matrix product states, showing that its spectrum contains universal subleading information. In particular, we identify an SRE correlation length -- distinct from the standard correlation length -- which diverges at continuous phase transitions and governs the spatial response of the SRE to local perturbations. We derive exact SRE expressions for the bond dimension χ=2χ=2χ=2 MPS ''skeleton'' of the cluster-Ising model, and we numerically probe its universal scaling along the Z2\mathbb{Z}_2Z2​ critical lines in the phase diagram. These results demonstrate that nonstabilizerness captures signatures of criticality and local perturbations, providing a new lens on the interplay between computational resources and emergent phenomena in quantum many-body systems.
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.
Magic, capturing the deviation of a quantum state from the stabilizer formalism, is a key resource underpinning the quantum advantage. The recently introduced stabilizer Rényi entropy (SRE) offers a tractable measure of magic, avoiding the complexity of conventional methods. We study SRE in translation-invariant matrix product states (MPS), deriving exact expressions for representative states and introducing a numerically stable algorithm, named bond-DMRG, to compute the SRE density in infinite systems. Applying this method, we obtain high-precision SRE densities for the ground state of the one-dimensional Ising model. We also analyze non-local SRE density, showing it is bounded by a universal function of entanglement entropy, and further prove that two-site mutual SRE vanishes asymptotically in injective MPS. Our work not only introduces a powerful method for extracting the SRE density in quantum many-body systems, but also numerically reveals a fundamental connection between magic and entanglement, thereby paving the way for deeper theoretical investigations into their interplay.
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 mmm nnn-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 mmm and polynomial in the number of qubits nnn. 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\mathrm{P} = \mathrm{NP}P=NP, no algorithm polynomial in mmm 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.