The unbearable hardness of deciding about magic

• URL: http://arxiv.org/abs/2602.22330v2
• Date: Fri, 27 Feb 2026 13:31:22 GMT
• Title: The unbearable hardness of deciding about magic
• Authors: Lorenzo Leone, Jens Eisert, Salvatore F. E. Oliviero,
• Abstract summary: We show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time.<n>We also show that deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Identifying the boundary between classical and quantum computation is a central challenge in quantum information. In multi-qubit systems, entanglement and magic are the key resources underlying genuinely quantum behaviour. While entanglement is well understood, magic - essential for universal quantum computation - remains relatively poorly characterised. Here we show that determining membership in the stabilizer polytope, which defines the free states of magic-state resource theory, requires super-exponential time $\class{exp} ( n^2)$ in the number of qubits $n$, even approximately. We reduce the problem to solving a $3$-\class{SAT} instance on $n^2$ variables and, by invoking the exponential time hypothesis, the result follows. As a consequence, both quantifying and certifying magic are fundamentally intractable: any magic monotone for general states must be super-exponentially hard to compute, and deciding whether an operator is a valid magic witness is equally difficult. As a corollary, we establish the robustness of magic as computationally optimal among monotones. This barrier extends even to classically simulable regimes: deciding whether a state lies in the convex hull of states generated by a logarithmic number of non-Clifford gates is also super-exponentially hard. Together, these results reveal intrinsic computational limits on assessing classical simulability, distilling pathological magic states, and ultimately probing and exploiting magic as a quantum resource.

Related papers

• Magic state cultivation on a superconducting quantum processor [108.15404500422814]
  We present an experimental study of magic state cultivation on a superconducting quantum processor.<n>Cultivation reduces the error by a factor of 40, with a state fidelity of 0.9999(1).
  arXiv  Detail & Related papers  (2025-12-15T21:29:40Z)
• Quantum States with Maximal Magic [0.0]
  We show that if a Weyl-Heisenberg (WH) covariant Symmetric Informationally Complete (SIC) quantum measurement exists, its states uniquely maximize the stabilizer entropies by saturating the bound.<n>Our result may have implications for quantum computation at a practical level, as it demonstrates that this notion of maximal magic inherits all the difficulties of the 25-year-old SIC existence problem, along with the deep questions in number theory associated with it.
  arXiv  Detail & Related papers  (2024-12-30T17:02:22Z)
• Experimental Demonstration of Logical Magic State Distillation [62.77974948443222]
  We present the experimental realization of magic state distillation with logical qubits on a neutral-atom quantum computer.<n>Our approach makes use of a dynamically reconfigurable architecture to encode and perform quantum operations on many logical qubits in parallel.
  arXiv  Detail & Related papers  (2024-12-19T18:38:46Z)
• Noise robustness and threshold of many-body quantum magic [0.5524804393257919]
  We investigate how noise affects magic properties in entangled many-body quantum states. We show that interactions facilitated by high-degree gates are fragile to noise. We also discuss the qudit case based on the discrete Wigner formalism.
  arXiv  Detail & Related papers  (2024-10-28T17:01:47Z)
• Magic spreading in random quantum circuits [0.0]
  We show how rapidly do generic many-body dynamics generate magic resources under the constraints of locality and unitarity.<n>We demonstrate that magic resources equilibrate on timescales logarithmic in the system size, akin to anti-concentration and Hilbert space delocalization phenomena.<n>As random circuits are minimal models for chaotic dynamics, we conjecture that our findings describe the phenomenology of magic resources growth in a broad class of chaotic many-body systems.
  arXiv  Detail & Related papers  (2024-07-04T13:43:46Z)
• Unconditional quantum magic advantage in shallow circuit computation [2.517043342442487]
  Quantum theory promises computational speed-ups over classical approaches.<n>The Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of "magic" states.<n>In this work, we demonstrate the first unconditional magic advantage.
  arXiv  Detail & Related papers  (2024-02-19T15:59:48Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Many-body quantum magic [0.609170287691728]
  We show that the maximum magic of an $n$-qubit state is essentially $n$, simultaneously for a range of "good" magic measures. In the quest for explicit, scalable cases of highly entangled states whose magic can be understood, we connect the magic of hypergraph states with the second-order nonlinearity of their underlying Boolean functions. We show that $n$-qubit states with nearly $n$ magic, or indeed almost all states, cannot supply nontrivial speedups over classical computers.
  arXiv  Detail & Related papers  (2020-10-26T18:06:45Z)
• Operational Resource Theory of Imaginarity [48.7576911714538]
  We show that quantum states are easier to create and manipulate if they only have real elements. As an application, we show that imaginarity plays a crucial role for state discrimination.
  arXiv  Detail & Related papers  (2020-07-29T14:03:38Z)
• 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.