Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness

• URL: http://arxiv.org/abs/2601.00761v1
• Date: Fri, 02 Jan 2026 17:37:04 GMT
• Title: Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness
• Authors: Zhenyu Xiao, Shinsei Ryu,
• Abstract summary: Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups.<n>We introduce an efficient classical algorithm that exactly computes stabilizer Rényi entropies and stabilizer nullity for generic many-body wavefunctions of $N$ qubits.
• Score: 9.107796201474187
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical algorithm that exactly computes stabilizer Rényi entropies and stabilizer nullity for generic many-body wavefunctions of $N$ qubits. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators. It achieves an exponential speedup over direct approaches, reducing the average cost per sampled Pauli string from $O(2^N)$ to $O(N)$. Building on this framework, we further develop a Monte-Carlo estimator for stabilizer Rényi entropies together with a Clifford-based variance-reduction scheme that suppresses sampling fluctuations. We benchmark the accuracy and efficiency on ensembles of random magic states, and apply the method to random Clifford circuits with doped $T$ gates, comparing different doping architectures. Our approach applies to arbitrary quantum states and provides quantitative access to magic resources both encoded in highly entangled states and generated by long-time nonequilibrium dynamics.

Related papers

• Predicting Magic from Very Few Measurements [0.0]
  We show that nonstabilizerness can be witnessed and quantified using any set of $m$ $n$-qubit Pauli measurements.<n>We also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard.<n>In particular, unless $mathrmP = mathrmNP$, no algorithm in $m$ can solve the problem in full generality.
  arXiv  Detail & Related papers  (2026-02-21T19:13:43Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Enhancing Kerr-Cat Qubit Coherence with Controlled Dissipation [64.05054054401175]
  Kerr-cat qubit (KCQ) is a bosonic quantum processor.<n>KCQs are experimentally compatible with on-chip architectures and high-fidelity operations.<n>We present direct evidence that the bit-flip time in a KCQ is limited by leakage out of the qubit manifold.
  arXiv  Detail & Related papers  (2025-11-02T17:58:36Z)
• An efficient algorithm to compute entanglement in states with low magic [11.189994857052634]
  Efficient extraction of entanglement can inform our understanding of dynamical quantum processes.<n>We develop an efficient classical algorithm to compute the von Neumann entropy and entanglement spectrum for such states.
  arXiv  Detail & Related papers  (2025-10-07T18:00:01Z)
• Efficient mutual magic and magic capacity with matrix product states [0.0]
  We introduce the mutual von-Neumann SRE and magic capacity, which can be efficiently computed in time.<n>We find that mutual SRE characterizes the critical point of ground states of the transverse-field Ising model.<n>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.
  arXiv  Detail & Related papers  (2025-04-09T19:12:26Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• State Estimation and Control for Stochastic Quantum Dynamics with Homodyne Measurement: Stabilizing Qubits under Uncertainty [1.4811951486536687]
  This paper introduces a Lyapunov-based control approach with homodyne measurement. We study two filtering approaches: (i) the traditional quantum filtering and (ii) a modified version of the extended Kalman filtering.
  arXiv  Detail & Related papers  (2024-03-09T22:29:00Z)
• Learning the stabilizer group of a Matrix Product State [0.0]
  We present a novel classical algorithm designed to learn the stabilizer group of a given Matrix Product State (MPS) We benchmark our method on $T$-doped states randomly scrambled via Clifford unitary dynamics. Our method, thanks to a very favourable scaling $mathcalO(chi3)$, represents the first effective approach to obtain a genuine magic monotone for MPS.
  arXiv  Detail & Related papers  (2024-01-29T19:00:13Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Quantum Magic via Perfect Pauli Sampling of Matrix Product States [0.0]
  We consider the recently introduced Stabilizer R'enyi 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.
  arXiv  Detail & Related papers  (2023-03-09T19:00:41Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
  We show how to efficiently simplify stabilizer states to canonical form. We characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
  arXiv  Detail & Related papers  (2021-09-20T05:56:25Z)
• Coherent randomized benchmarking [68.8204255655161]
  We show that superpositions of different random sequences rather than independent samples are used. We show that this leads to a uniform and simple protocol with significant advantages with respect to gates that can be benchmarked.
  arXiv  Detail & Related papers  (2020-10-26T18:00:34Z)

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.