Graph Theoretic Approach to Quantum Nonstabilizerness

arXiv (Cornell University)

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.

Authors 6

1. Yingjian Liu Aachen Instituut-Lorentz

   Leiden University

   Affiliation as printed

   Instituut-Lorentz , Universiteit Leiden , P.O. Box 9506 , 2300 RA Leiden , The Netherlands

   ⟨aQa L

2. Albert Gasull Aachen Instituut-Lorentz

   Leiden University

   Affiliation as printed

   Instituut-Lorentz , Universiteit Leiden , P.O. Box 9506 , 2300 RA Leiden , The Netherlands

   ⟨aQa L

3. Mengyao Hu

   Centre for Quantum Technologies · National University of Singapore

   Affiliation as printed

   Centre for Quantum Technologies , National University of Singapore , 3 Science Drive 2 , Singapore 117543 , Singapore

4. Ruiyun Zhang

   Hong Kong University of Science and Technology

   Affiliation as printed

   Applied Quantum Algorithms , Leiden University , The Netherlands

   The Hong Kong University of Science and Technology , Clear Water Bay , Kowloon , Hong Kong

5. Flávio Baccari Júnior

   University of Padua

   Affiliation as printed

   Dipartimento di Fisica e Astronomia "G. Galilei" , Università di Padova , I-35131 Padova , Italy

   Padua Quantum Technologies Research Center , Università degli Studi di Padova , I-35131 Padova , Italy

6. Jordi Tura Aachen Instituut-Lorentz

   Leiden University

   Affiliation as printed

   Instituut-Lorentz , Universiteit Leiden , P.O. Box 9506 , 2300 RA Leiden , The Netherlands

   ⟨aQa L