Predicting Magic from Very Few Measurements

• URL: http://arxiv.org/abs/2602.18939v1
• Date: Sat, 21 Feb 2026 19:13:43 GMT
• Title: Predicting Magic from Very Few Measurements
• Authors: J. M. Varela, L. L. Keller, A. de Oliveira Junior, D. A. Moreira, R. Chaves, R. A. Macêdo,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of $m$ $n$-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements $m$ and polynomial in the number of qubits $n$. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless $\mathrm{P} = \mathrm{NP}$, no algorithm polynomial in $m$ can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.

Related papers

• Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness [9.107796201474187]
  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.
  arXiv  Detail & Related papers  (2026-01-02T17:37:04Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Analytic and Stochastic Approach to Quantum Advantages in Ground State and Quantum State Preparation Problems [5.458506740538826]
  We study the problems of state preparation, ground state preparation and quantum state preparation.<n>We propose an analytic approach to a quantum algorithm which prepares the ground state for $n$qubit Hamiltonian that is represented by $textpoly(n)$ Pauli operators.
  arXiv  Detail & Related papers  (2025-10-02T01:17:22Z)
• Grassmann Variational Monte Carlo with neural wave functions [45.935798913942904]
  We formalize the framework introduced by Pfau et al.citepfau2024accurate in terms of Grassmann geometry of the Hilbert space.<n>We validate our approach on the Heisenberg quantum spin model on the square lattice, achieving highly accurate energies and physical observables for a large number of excited states.
  arXiv  Detail & Related papers  (2025-07-14T13:53:13Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition.<n>We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Sample-Efficient Estimation of Nonlinear Quantum State Functions [5.641998714611475]
  We introduce the quantum state function (QSF) framework by extending the SWAP test via linear combination of unitaries and parameterized quantum circuits.<n>Our framework enables the implementation of arbitrarily normalized degree-$n$ functions of quantum states with precision.<n>We apply QSF for developing quantum algorithms for fundamental tasks, including entropy, fidelity, and eigenvalue estimations.
  arXiv  Detail & Related papers  (2024-12-02T16:40:17Z)
• 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)
• Exponentially improved efficient machine learning for quantum many-body states with provable guarantees [0.0]
  We provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications. Our results provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications.
  arXiv  Detail & Related papers  (2023-04-10T02:22:36Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantifying nonstabilizerness of matrix product states [0.0]
  We show that nonstabilizerness, as quantified by the recently introduced Stabilizer R'enyi Entropies (SREs), can be computed efficiently for matrix product states (MPSs) We exploit this observation to revisit the study of ground-state nonstabilizerness in the quantum Ising chain, providing accurate numerical results up to large system sizes.
  arXiv  Detail & Related papers  (2022-07-26T17:50:32Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)

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.