A fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm

• URL: http://arxiv.org/abs/2512.24685v2
• Date: Mon, 05 Jan 2026 07:05:46 GMT
• Title: A fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm
• Authors: Xuyang Huang, Han-Ze Li, Jian-Xin Zhong,
• Abstract summary: Quantum advantage is widely understood to rely on key quantum resources beyond entanglement.<n>However, a direct brute-force of all Pauli strings and the corresponding expectation values from a length-$2N$ state vector, where $N$ is the system size, yields an overall computational cost scaling as $O(8N)$.<n>Here we reformulate the second-order stabilizer Rényi entropy in a bitstring language, expose an underlying XOR-convolution structure on $mathbb ZN$, and reduce the computation to $2N$ fast Walsh-Hadamard transforms of length
• Score: 0.5735035463793009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum advantage is widely understood to rely on key quantum resources beyond entanglement, among which nonstabilizerness (quantum ``magic'') plays a central role in enabling universal quantum computation. However, a direct brute-force enumeration of all Pauli strings and the corresponding expectation values from a length-$2^N$ state vector, where $N$ is the system size, yields an overall computational cost scaling as $O(8^N)$, which quickly becomes infeasible as the system size grows. Here we reformulate the second-order stabilizer Rényi entropy in a bitstring language, expose an underlying XOR-convolution structure on $\mathbb Z_2^N$, and reduce the computation to $2^N$ fast Walsh-Hadamard transforms of length, together with pointwise operations, yielding a deterministic and exact XOR fast Walsh-Hadamard transforms algorithm with runtime scaling $O(N4^N)$ and natural parallelism. This algorithm enables high-precision, medium-scale exact calculations for generic state vectors. It provides a practical tool for probing the scaling, phase diagnostics, and dynamical fine structure of quantum magic in many-body systems.

Related papers

• Computing quantum magic of state vectors [0.0]
  Non-stabilizerness, also known as magic,'' quantifies how far a quantum state departs from the stabilizer set.<n>Standard magic quantifiers, such as the stabilizer Rényi entropy (SRE) for qubits and the mana for qutrits, are costly to evaluate numerically.<n>Here we introduce efficient, numerically exact algorithms that exploit the fast Hadamard transform to compute the SRE for qubits.
  arXiv  Detail & Related papers  (2026-01-12T18:58:06Z)
• Qudit-based scalable quantum algorithm for solving the integer programming problem [0.0]
  programming (IP) is an NP-hard optimization problem that is widely used to represent a diverse set of real-world problems.<n>Most quantum algorithms for solving IP are highly resource inefficient because they encode integers into qubits.<n>In this work, a circuit-based scalable quantum algorithm is presented using multiple interacting qudits for which we show a quantum speed-up.
  arXiv  Detail & Related papers  (2025-08-19T15:06:49Z)
• Quantum Algorithms for Finite-horizon Markov Decision Processes [40.812944518646006]
  We design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs)<n>In the exact dynamics setting, we prove that our $textbfQVI-1$ algorithm achieves a quadratic speedup in the size of the action space $(A)$.<n>In the generative model setting, we prove that our algorithms $textbfQVI-3$ and $textbfQVI-4$ achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm.
  arXiv  Detail & Related papers  (2025-08-07T09:00:23Z)
• Generalized tensor transforms and their applications in classical and quantum computing [0.0]
  We introduce a novel framework for Generalized Transforms (GTTs), constructed through an $n$-fold tensor product of an arbitrary $b times b$ unitary matrix $W$.<n>For quantum applications, our GTT-based algorithm achieves both gate complexity and circuit depth of $O(log_b N)$, where $N = bn$ denotes the length of the vector input.<n>We explore diverse applications of GTTs in quantum computing, including quantum state compression and transmission, function encoding and quantum digital signal processing.
  arXiv  Detail & Related papers  (2025-07-03T08:28:00Z)
• Sublinear Classical-to-Quantum Data Encoding using $n$-Toffoli Gates [3.0711566483997066]
  A common strategy is amplitude encoding, which embeds a classical input vector of size N=2textsuperscriptn in the amplitudes of an n-qubit register.<n>We propose a general-purpose procedure with sublinear average depth in N, increasing the window of utility.<n>Our amplitude encoding method encodes arbitrary complex vectors of size N=2textsuperscriptn at any desired binary precision using a register with n qubits plus 2 ancillas and a sublinear number of multi-controlled NOT (MCX) gates.
  arXiv  Detail & Related papers  (2025-05-09T13:49:16Z)
• Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla [18.660349597156266]
  We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms.<n>Our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance.
  arXiv  Detail & Related papers  (2025-04-03T08:24:15Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD.<n>Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers.<n>Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
  arXiv  Detail & Related papers  (2024-04-30T23:55:03Z)
• Efficient parallelization of quantum basis state shift [0.0]
  We optimize the state shift algorithm by incorporating the shift in different directions in parallel. This provides a significant reduction in the depth of the quantum circuit in comparison to the currently known methods. We focus on the one-dimensional and periodic shift, but note that the method can be extended to more complex cases.
  arXiv  Detail & Related papers  (2023-04-04T11:01:08Z)
• K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
  Quantum state tomography (QST) for reconstructing pure states requires exponentially increasing resources and measurements with the number of qubits. QST reconstruction for any pure state composed of the superposition of $K$ different computational basis states of $n$bits in a specific measurement set-up is presented.
  arXiv  Detail & Related papers  (2021-11-08T09:43:12Z)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.