Skip to content
OpenContext

← Problem 5: Test problem: Hilbert–Schmidt inradius of the multiqubit stabilizer polytope

An earlier version. Problem 5 as it stood from 18 Nov 2026; it has changed since.Go to the current version →
Changed by
The editors
What changed
Improved the problem's background

Problem 5: Test problem: Hilbert–Schmidt inradius of the multiqubit stabilizer polytope (edit)

Is every nn-qubit state ρ\rho of purity Tr[ρ2]\mathrm{Tr}[\rho^2] at most 1/(2n−1/2)1/(2^n-1/2) a convex mixture of stabilizer states, i.e., not a magic state?

In other words, let d=2nd=2^n and

STABn=conv{∣s⟩⟨s∣ : ∣s⟩ is an n-qubit stabililzer state}.\mathrm{STAB}_n = \mathrm{conv}\{ \vert s \rangle \langle s \vert \ : \ \vert s \rangle \text{ is an }n\text{-qubit stabililzer state}\}.

Is the following implication valid for every n≥1n\geq 1?

Tr(ρ2)≤1d−1/2  ⟹  ρ∈STABn.\mathrm{Tr}(\rho^2) \leq \frac{1}{d-1/2} \implies \rho \in \mathrm{STAB}_n.

Background

Stabilizer states, Clifford gates and Pauli measurements can be simulated efficiently, i.e. in polynomial time, on a probabilistic classical computer. This is the content of the Gottesman-Knill theorem. States outside the stabilizer polytope STABn\mathrm{STAB}_n (also known as magic states) are the resource that lifts this to universal quantum computation. A basic question is how noisy a state can be while still being magic. Since purity is the simplest basis-independent measure of noise, the problem above asks for the largest Hilbert–Schmidt ball centred at the maximally mixed state I/dI/d that fits inside the polytope STABn\mathrm{STAB}_n, i.e. the inradius of the polytope.

For one qubit the answer is elementary and has been discussed in Ref. [2]: the stabilizer octahedron contains the Bloch ball of radius 1/31/\sqrt{3}, which is related to the purity 2/3=1/(d−1/2)2/3 = 1/(d-1/2).

The problem asks whether the same formula holds for every value nn of qubit systems.

What is known:

  • The statement was posed as Conjecture 1 by Liu et al. [1], who verified it for n=1,2n=1,2 and numerically up to n=4n=4. They prove the weaker threshold 1/(d−1/d)1/(d-1/d), and they show that 1/(d−1/2)1/(d-1/2) cannot be improved: there are magic states with purity arbitrarily close to it.
  • Zurel and Davis [2] obtain the same inradius conditionally on an equivalent conjecture, and resolve the analogous question unconditionally for odd prime local dimension, where the threshold is 1/(D−1/D)1/(D-1/D) for total dimension DD. There they also discuss other problems of interest, and constructions related to distinct polytopes, such as the Λ\Lambda-polytope.
  • By polarity, the statement is equivalent to a bound on the dual polytope
Λn={A:Tr[A]=1, ⟨s∣A∣s⟩≥0 for all stabilizer states ∣s⟩},\Lambda_n = \left\{A : \mathrm{Tr}[A]=1,\ \langle s|A|s\rangle \ge 0 \text{ for all stabilizer states } \vert s \rangle \right\},

namely

Tr(A2)≤2,∀A∈Λn.\mathrm{Tr}(A^2)\le 2, \quad \forall A\in\Lambda_n.

The bound is attained by a one-qubit phase-point operator tensored with a stabilizer state.

So only one direction is open: that every state below the threshold is a stabilizer mixture, for n≥3n\ge 3.

Relevance

The dual polytope Λn\Lambda_n is the state space of a hidden-variable description of quantum computation with magic states: its elements assign non-negative probabilities to every stabilizer measurement. The problem therefore asks how large such a "classical-looking" object can be, measured by Tr(A2)\mathrm{Tr}(A^2).

The link to contextuality is direct. Non-negativity on each stabilizer basis alone gives only the trivial bound Tr(A2)≤d\mathrm{Tr}(A^2)\le d, and that bound would be reached exactly by a deterministic, noncontextual ±1\pm1 value assignment to all Pauli observables. Such an assignment is forbidden by Mermin-square (Kochen–Specker) arguments. The conjectured value 22 is thus a quantitative statement of how strongly state-independent contextuality of the multiqubit Pauli group constrains these assignments.

This is also why qubits are the hard case. For odd prime dimension the stabilizer subtheory admits a noncontextual (Wigner-function) model and the corresponding inradius is already known [2]; for qubits the stabilizer subtheory is itself contextual, and no such model is available.

For the applications agenda, a proof would give a certified, basis-independent purity threshold: below it, no magic and hence no contextuality-based advantage can be present, whatever the state.

Significance

A proof would:

  • settle the exact Hilbert–Schmidt inradius of the multiqubit stabilizer polytope, and with it the minimal purity of a magic state, for all nn;
  • turn the conditional results of [2] on absolutely stabilizer states into theorems;
  • show that the largest-norm vertices of Λn\Lambda_n are of the simplest known (closed-noncontextual) type, which is structural information about a polytope whose vertices are unclassified for n≥3n\ge 3.

A counterexample would be equally informative: it would exhibit a new kind of vertex of Λn\Lambda_n and a magic state noisier than any currently known.

The scope is limited. The problem concerns one geometric constant of the stabilizer subtheory, and it bears on generalized noncontextuality only through the identification of magic with contextuality. It is best read as a sharp, well-posed test case rather than a step that would by itself advance the framework.

Feasibility

For each fixed nn the question is finite-dimensional convex geometry: maximise a convex quadratic over a polytope with known facets. It has been checked exactly for n=1,2n=1,2 and numerically for n=3,4n=3,4 [1,2]. The difficulty is uniformity in nn: the number of vertices of Λn\Lambda_n grows too fast to enumerate, and no classification exists.

Known obstructions to simple proofs (the last three items come from an AI-assisted exploration and have not been independently checked):

  • The naive 2-design argument gives only Tr(A2)≤d\mathrm{Tr}(A^2)\le d.
  • Induction on nn by measuring one Pauli and applying the n−1n-1 case gives Tr(A2)≤2+3d/(d2−2d−2)\mathrm{Tr}(A^2)\le 2+3d/(d^2-2d-2), which approaches but never reaches 22. Any argument that uses only the squares of the Pauli coefficients, and not their signs, is subject to the same limit.
  • For d≥4d\ge 4 there is no certificate of degree 2 in the stabilizer probabilities, even allowing sum-of-squares terms.
  • For n=2n=2 a degree-4 certificate does exist: 2−Tr(A2)2-\mathrm{Tr}(A^2) is a non-negative combination of products of four stabilizer probabilities.

Plausible routes are therefore (i) a family of positivity certificates whose degree grows with nn, generalising the n=2n=2 one; (ii) a quantitative Mermin-square inequality that supplies the missing sign information in the induction step; or (iii) a structural result on the vertices of Λn\Lambda_n. The tools are elementary, but the problem has resisted two independent groups, so it should be regarded as hard rather than routine.

Testing if edits work by adding a small line at the end

Permanent link:open-context.jan-bulling.com/contribution/5v7

References

  1. Zhenhuan Liu, Tobias Haug, Qi Ye, Zi-Wen Liu, and Ingo Roth, Triangle Criterion: a mixed-state magic criterion with applications in distillation and detection, arXiv:2512.16777 (2025)
  2. Michael Zurel and Jack Davis, Basis-independent stabilizerness and maximally noisy magic states, arXiv:2602.22336 (2026)
  3. Zhenhuan Liu and Zi-Wen Liu, On the geometry, typicality, and detectability of quantum magic, arXiv:2609.03944 (2026)
  4. Michael Zurel, Cihan Okay, and Robert Raussendorf, Hidden Variable Model for Universal Quantum Computation with Magic States on Qubits, Phys. Rev. Lett. 125, 260404 (2020)
  5. Ben W. Reichardt, Quantum universality by state distillation, arXiv:quant-ph/0608085 (2006)

Versions

  1. 20 Nov 2026

    Version 125v12Current

    Improvements on the references

    by Rafael Wagner

  2. 19 Nov 2026

    Version 115v11

    Improvements on the references

    by Rafael Wagner

  3. 19 Nov 2026

    Version 105v10

    Improvements on the references

    by Rafael Wagner

  4. 18 Nov 2026

    Version 95v9

    I think that the Relevance and Significance could be improved

    by Rafael Wagner · fully AI-generated

  5. 18 Nov 2026

    Version 85v8

    I've suggested improvements on the background of the problem

    by Rafael Wagner · fully AI-generated

  6. 18 Nov 2026

    Version 75v7Shown here

    Improved the problem's background

    by the editors

  7. 17 Nov 2026

    Version 65v6

    Tested if edits are now credited

    by Jan, Albert · partially AI-assisted

  8. 17 Nov 2026

    Version 55v5

    Included background and other things

    by Rafael Wagner

  9. 17 Nov 2026

    Version 45v4

    Improvements on the references

    by the editors

  10. 17 Nov 2026

    Version 35v3

    add the term magic state to the statement

    by Yìlè Yīng

  11. 17 Nov 2026

    Version 25v2

    Erased an earlier comment from the question posed, and added context to the question.

    by Rafael Wagner

  12. 17 Nov 2026

    Version 15v1

    First recorded version.