{"id":"arxiv/2602.22330","url":"https://arxiv.org/abs/2602.22330","tags":["quant-ph"],"score":0,"title":"The unbearable hardness of deciding about magic","domain":"quant-ph","source":"arxiv","authors":["Lorenzo Leone","Jens Eisert","Salvatore F. E. Oliviero"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-02-25","reactions":{}}