Graph Theoretic Approach to Quantum Nonstabilizerness

Abstract:Detecting nonstabilizerness requires full tomography and an optimization over exponentially many stabilizer states. A limited Pauli measurement set promises resource-efficient magic certification, yet the resulting reduced stabilizer polytope is generally difficult to characterize. We trace this difficulty into two coupled obstructions: the simultaneous measurability of measurements captured by their frustration graph structure, and the consistency of sign dependencies from stabilizer formalism. We show that the sign dependencies can be discarded exactly whenever active dependencies are absent, and that perfect frustration graphs then make this reduced polytope efficiently solvable. This solvable regime derives a closed form bounded by the clique number of the frustration graph, revealing a tradeoff between witness capacity and simultaneous measurability. Clifford covariance allows rotated measurement sets to enlarge the detectable state space without raising the capacity. Graph structure therefore emerges as both a certificate of tractability and a design principle for scalable magic resource detection.

arXiv:2607.26154 [quant-ph]

(or arXiv:2607.26154v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2607.26154 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.