We introduce a monotone to quantify the amount of nonstabilizerness in mixed quantum states. The monotone gives a necessary and sufficient criterion for detecting the presence of nonstabilizerness for both pure and mixed states. The monotone is based on determining the boundaries of the stabilizer polytope in the space of Pauli string expectation values. The boundaries can be described by a set of hyperplane inequations, where violation of any one of these gives a necessary and sufficient condition for nonstabilizerness. The monotone is constructed by finding the hyperplane with the maximum violation and is a type of Minkowski functional. We also introduce a faithful witness based on similar methods. The approach is more computationally efficient than existing faithful mixed state monotones such as robustness of magic due to the smaller number and discrete nature of the parameters to be optimized.
We introduce a monotone to quantify the amount of nonstabilizerness in mixed quantum states. The monotone gives a necessary and sufficient criterion for detecting the presence of nonstabilizerness for both pure and mixed states. The monotone is based on determining the boundaries of the stabilizer polytope in the space of Pauli string expectation values. The boundaries can be described by a set of hyperplane inequations, where violation of any one of these gives a necessary and sufficient condition for nonstabilizerness. The monotone is constructed by finding the hyperplane with the maximum violation and is a type of Minkowski functional. We also introduce a faithful witness based on similar methods. The approach is more computationally efficient than existing faithful mixed state monotones such as robustness of magic due to the smaller number and discrete nature of the parameters to be optimized.
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.
We introduce a monotone to quantify the amount of non-stabilizerness (or magic for short), in an arbitrary quantum state. The monotone gives a necessary and sufficient criterion for detecting the presence of magic for both pure and mixed states. The monotone is based on determining the boundaries of the stabilizer polytope in the space of Pauli string expectation values. The boundaries can be described by a set of hyperplane inequations, where violation of any one of these gives a necessary and sufficient condition for magic. The monotone is constructed by finding the hyperplane with the maximum violation and is a type of Minkowski functional. We also introduce a witness based on similar methods. The approach is more computationally efficient than existing faithful mixed state monotones such as robustness of magic due to the smaller number and discrete nature of the parameters to be optimized.
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 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 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’, is a crucial resource for quantum computation, but quantifying the magic of mixed states has been a notoriously difficult task. We introduce efficient magic witnesses based on stabilizer Rényi entropy that both robustly indicate magic and quantitatively estimate magic monotones. Building on these witnesses, we design testing algorithms that distinguish high- and low-magic states under entropy constraints and apply them to certify the number of noisy T-gates for a broad class of noise models. Using the IonQ quantum computer, we experimentally verify magic in noisy random circuits and find that magic remains robust, persisting even under depolarizing noise with probability exponentially close to one. Our witnesses are efficiently computable for matrix product states, showing that subsystems of many-body states can host extensive magic even when the system is entangled. Finally, we show that mimicking high-magic states with minimal magic requires an extensive amount of entropy, implying that entropy is a necessary cryptographic resource for hiding magic from eavesdroppers. Our results provide practical tools for characterizing the complexity of noisy quantum systems.
Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits n, even approximately. We reduce the problem to solving a 3-\class{SAT} instance on n2 variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.
Abstract We introduce a nonstabilizerness monotone which we name basis-minimized stabilizerness asymmetry (BMSA). It is based on the notion of G-asymmetry, a measure of how much a certain state deviates from being symmetric with respect to a symmetry group G. For pure states, we show that the BMSA is a strong monotone for magic-state resource theory, while it can be extended to mixed states via the convex roof construction. We discuss its relation with other magic monotones, first showing that the BMSA coincides with the recently introduced basis-minimized measurement entropy, thereby establishing the strong monotonicity of the latter. Next, we provide inequalities between the BMSA and other nonstabilizerness measures such as the robustness of magic, stabilizer extent, stabilizer rank, stabilizer fidelity and stabilizer Rényi entropy. We also prove that the stabilizer fidelity, stabilizer Rényi entropy and BMSA with index α ⩾ 2 have the same asymptotic scaling with qubit number. Finally, we present numerical methods to compute the BMSA, highlighting its advantages and drawbacks compared to other nonstabilizerness measures in the context of pure many-body quantum states. We also discuss the importance of additivity and strong monotonicity for measures of nonstabilizerness in many-body physics, motivating the search for additional computable nonstabilizerness monotones.