Graph Theoretic Approach to Quantum Nonstabilizerness

• URL: http://arxiv.org/abs/2607.26154v1
• Date: Tue, 28 Jul 2026 18:01:16 GMT
• Title: Graph Theoretic Approach to Quantum Nonstabilizerness
• Abstract summary: We show how to characterize a reduced stabilizer polytope.<n>We show that the sign dependencies can be discarded exactly whenever active dependencies are absent.<n>This solvable regime derives a closed form bounded by the clique number of the frustration graph.
• Score: 2.780058343472781
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Bridging the Gap Between Plausibility and Admissibility: Constraint-Aware Flow Maps for Dynamic Graph Systems [2.7644691581661287]
  Generative models can support decision-making under uncertainty by producing ensembles of plausible future system trajectories.<n>This study investigates whether post-sampling symbolic constraints can improve the reliability of generative trajectory modeling.
  arXiv  Detail & Related papers  (2026-07-23T15:25:42Z)
• What Accuracy and Gradient Cosine Miss: Evaluating Feedback Alignment via Scale Stability, Reference Validity, and Depth Utility [48.10132234701036]
  We propose a diagnostic evaluation protocol based on three checks -- scale stability, reference validity, and depth utility -- together with per-layer rather than aggregate cosine reporting.<n>Across multiple architectures and methods, our protocol identifies all failures with wide calibration margins.
  arXiv  Detail & Related papers  (2026-06-19T06:04:17Z)
• When Do Autoregressive Sequence Models Forecast Physical Wavefields? A Controlled Study on Synthetic Seismograms [43.8784307709823]
  Long-horizon autoregressive forecasting of physical signals is limited by error accumulation.<n>We ask when such rollout stays stable using synthetic three-component seismograms as a physically structured testbed.
  arXiv  Detail & Related papers  (2026-06-09T13:46:14Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Generalizing GNNs with Tokenized Mixture of Experts [75.8310720413187]
  We show that improving stability requires reducing reliance on shift-sensitive features, leaving an irreducible worst-case generalization floor.<n>We propose STEM-GNN, a pretrain-then-finetune framework with a mixture-of-experts encoder for diverse computation paths.<n>Across nine node, link, and graph benchmarks, STEM-GNN achieves a stronger three-way balance, improving robustness to degree/homophily shifts and to feature/edge corruptions while remaining competitive on clean graphs.
  arXiv  Detail & Related papers  (2026-02-09T22:48:30Z)
• Phase Transitions and Noise Robustness of Quantum Graph States [0.0]
  We show that the fidelity between any ideal graph state and its noisy counterpart under IID Pauli noise can be mapped to the partition function of a classical spin system.<n>We uncover the emergence of phase transitions in fidelity between the pure-state regime and the noise-dominated regime governed by both the connectivity (degree) and spatial dimensionality of the graph state.
  arXiv  Detail & Related papers  (2025-10-01T06:08:47Z)
• Randomized Space-Time Sampling for Affine Graph Dynamical Systems [3.8379346559198235]
  We consider signals evolving over time according to a linear dynamical system on a graph, where both the initial state and the source term are bandlimited.<n>We introduce two random space-time sampling regimes and analyze the conditions under which stable recovery is achievable.
  arXiv  Detail & Related papers  (2025-09-20T21:43:05Z)
• Rise and fall of nonstabilizerness via random measurements [0.27988103729716907]
  We investigate the dynamics of nonstabilizerness in quantum circuits composed of random Clifford unitaries and local projective measurements.<n>For measurements performed in rotated non-Clifford bases, measurements can both create and destroy nonstabilizerness.<n>Our results uncover sharp distinctions between coarse and fine-grained nonstabilizerness diagnostics.
  arXiv  Detail & Related papers  (2025-07-15T18:01:02Z)
• Regulating Model Reliance on Non-Robust Features by Smoothing Input Marginal Density [93.32594873253534]
  Trustworthy machine learning requires meticulous regulation of model reliance on non-robust features. We propose a framework to delineate and regulate such features by attributing model predictions to the input.
  arXiv  Detail & Related papers  (2024-07-05T09:16:56Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  We study the type of solutions to which gradient descent converges when used to train a single hidden-layer multivariate ReLU network with the quadratic loss. We prove that although shallow ReLU networks are universal approximators, stable shallow networks are not.
  arXiv  Detail & Related papers  (2023-06-30T09:17:39Z)
• Quantifying non-stabilizerness via information scrambling [0.6993026261767287]
  A method to quantify quantum resources is to use a class of functions called magic monotones and stabilizer entropies. We numerically show the relation of these sampled correlators to different non-stabilizerness measures for both qubit and qutrit systems. We put forward and simulate a protocol to measure the monotonic behaviour of magic for the time evolution of local Hamiltonians.
  arXiv  Detail & Related papers  (2022-04-24T10:12:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.