An improved computer-assisted bound at 0.4996 for all $n$, and a sharp 0.5 value for $n\leq 5$ (part I)
by Rafael Wagner · accepted 19 Nov 2026 · partially AI-assisted
Main result
After a couple of prompts, Claude Fable 5.2 found another advance:
Theorem (0.4996 bound): Let ρ∈D(n timesC2⊗⋯⊗C2) be an arbitrary n-qubit state, and denote STABn the convex polytope of n-qubit stabilizer states. For every integer n≥1, it holds that
Tr[ρ2]≤dn−a∗1⟹ρ∈STABn,
where dn=2n is the dimension of the underlying Hilbert space and a∗=0.4996. Furthermore, for 1≤n≤5 the conjecture is shown to hold, i.e., a∗=21.
How this contribution is organised. Because of its length, the argument is divided into two parts. This first part contains the preliminaries and two new results on the spectrum of the operators in the Λ-polytope: the theorem on the spectrum of a witness and the star inequality. Both are proved analytically. The second part combines them with the Liu–Liu inequality of Ref. [3] to prove the theorem above.
Preliminary mathematical ideas
Recall that a crucial ingredient in this discussion is the notion of the Λ-polytope from Ref. [4]. For more on Λ-polytopes we refer to Refs. [8, 9, 10, 11, 4]. It can be defined as follows:
Λn={A=A†:Tr[A]=1,⟨s∣A∣s⟩≥0for all stabilizer states ∣s⟩}.
Above the relevant operators are always defined relative to n-qubit Hilbert spaces C2⊗⋯⊗C2 of dimension dn=2n. Below, all sums taken over Paulis P run over the d2−1 Pauli operators which are different from the identity I. For such Pauli P, we also denote
Π±=(I±P)/2,
aP=Tr[PA] as the trace of that Pauli with an operator A, and B±=Π±AΠ±. Let A1=(I+X+Y+Z)/2, with eigenvalues λ±=(1±3)/2, and A⋆=A1⊗∣0…0⟩⟨0…0∣. Throughout this document we define
v:=λ+,c:=−λ−=v−1.
With these definitions, it is simple to show that the following equations all hold:
2v2=2v+1,vc=21,v2+c2=2,v3−c3=25.
Building on my earlier contribution, we recall that we are using ideas related to the stabilizer theory, which is tied to quantum error correction. Because of that, the language of "codes" is used below, without loss of generality.
Lemma (Block lemma). For an arbitrary Pauli P the range of Π± is an (n−1)-qubit code space whose stabilizer states are n-qubit stabilizer states. Hence B± is non-negative on them,
Tr[B±]=(1±aP)/2≥0,
with aP=Tr[PA], and
B±/Tr[B±]∈Λn−1.
As a specific case, if Tr[B±]=0 then B±=0.
This lemma is shown in Ref. [4] (their Lemma 1, part (2)) and discussed also in Ref. [3], Appendix A (see the "Pauli-compression recursion" subsection).
The following is another simple Lemma, which can be found, for example, in standard textbooks [7].
Lemma (a rule for Pauli sums). For arbitrary Hermitian operators X,Y, with the identity included in the sums, we have that
P∑PXP=dTr[X]I
and
P∑Tr[PX]Tr[PY]=dTr[XY].
The first rule in the above lemma says that conjugation by a uniformly random Pauli operator is the completely depolarizing channel, i.e. that the Pauli group is a unitary 1-design: Watrous, Eq. (4.109); Ref. [12]; for one qubit it is the fully depolarizing case of the quantum depolarizing channel written with the Kraus operators I,X,Y,Z.
The second rule is Parseval's identity for the Pauli operators, which form an orthogonal basis of the space of operators for the Hilbert–Schmidt inner product: see Pauli matrices ("Algebraic properties") for one qubit, and J. Watrous [7], Section 4.1.2, Eq. (4.78) (equation numbers as in the author's online version), where it is stated for the discrete Weyl operators (for a qubit these are the Pauli matrices up to phases, Example 4.12).
The spectrum of a witness
In order to show the main result, we need to first show a few theorems. The first one is the following:
Theorem (spectrum of a witness). Let A1=(I+X+Y+Z)/2, with eigenvalues λ±. For all n≥1 and A∈Λn it holds that λ−≤λmin(A) and λmax(A)≤λ+. If λmax(A)=λ+ or λmin(A)=λ−, then A has eigenvalues λ+,λ− and d−2 zeros.
Proof: The proof is an induction on n. For n=1, A=(I+r⋅σ)/2 with ∣ri∣≤1, so the eigenvalues (1±∣r∣)/2 lie in [λ−,λ+], and they are λ± when a bound is attained. Assume the theorem for n−1 and let A∈Λn, n≥2. The upper bound is proved in Section 2.1 and the lower bound in Section 2.2.
2.1 The largest eigenvalue
In this subsection n≥2 and A∈Λn are fixed, and the induction hypothesis is used in the form λmax(B)≤v for every B∈Λn−1. Let ℓ=λmax(A) with unit eigenvector φ, let q=Tr[A2] and let κ=max(0,−λmin(A)). For every Pauli P=I we define the real numbers
The operator R′ is positive semidefinite: A+κI≥0, and R′ is this operator with its eigenvalue ℓ+κ at φ removed. Therefore eP=αP+κ−(ℓ+κ)xP2≥0 for every P. We also note that ∣aP∣≤1, because by the block lemma aP=Tr[B+]−Tr[B−] is a difference of two non-negative numbers whose sum is Tr[A]=1.
Lemma (per-Pauli inequality). For every Pauli P=I,
0≤eP≤ω(1−xP2)−∣uP∣(1−σPxP).
Consequently, ω≥0 and ∣uP∣≤ω(1+σPxP) for every P=I.
Proof: By the block lemma and the induction hypothesis, B±≤vTr[B±]Π±. We take the expectation value in φ and use Aφ=ℓφ, Tr[B±]=(1±aP)/2 and ⟨φ∣Π±∣φ⟩=(1±xP)/2. This gives
ℓ+αP±2ℓxP≤v(1±aP)(1±xP).
Now insert αP=eP−κ+(ℓ+κ)xP2. The left-hand side becomes ℓ(1±xP)2−κ(1−xP2)+eP, and collecting terms we find
eP≤(1±xP)(ω±ζP),ζP:=vaP−(ℓ+κ)xP.
Since uP=ζP+ωxP, the two bounds are ω(1−xP2)+(1+xP)uP and ω(1−xP2)−(1−xP)uP. The smaller of the two is ω(1−xP2)−∣uP∣(1−σPxP), which is the claimed inequality.
For the consequences, note that there is a Pauli P with ∣xP∣<1 (because ∑PxP2=d−1<d2−1 by the rule for Pauli sums), and for this P the inequality gives 0≤ω(1−xP2), so ω≥0. If σPxP=1, we divide ∣uP∣(1−σPxP)≤ω(1−xP2) by 1−σPxP and obtain ∣uP∣≤ω(1+σPxP). If σPxP=1, the claim reads ∣uP∣≤2ω, and it holds because ∣aP∣≤1 gives ∣uP∣=σPvaP−(2ℓ−v)≤2(v−ℓ)≤2ω. □
Theorem (star inequality). Let n≥2 and A∈Λn, with largest eigenvalue ℓ, purity q and κ=max(0,−λmin(A)). Then
v2(dq−1)−2v(2ℓ−v)(dℓ−1)+(2ℓ−v)2(d−1)≤(v−ℓ+κ)G,
where
G=(v−ℓ)d(d−1)+d(ℓ−1)+2v(dℓ−1)−2(2ℓ−v)(d−1).
Equality holds for A=A⋆.
At this point of the argument the star inequality is proved under the induction hypothesis for n−1. Once the theorem on the spectrum of a witness is established, it holds for every n≥2 without any assumption, and this is how it is used in the second part.
Proof: The rule for Pauli sums gives the four identities (all sums run over P=I, as before)
Next we multiply ∣uP∣≤ω(1+σPxP) by ∣uP∣ and sum over P. Since ∣uP∣σP=uP and ω≥0, we get
P∑uP2≤ω(P∑∣uP∣(1−σPxP)+2P∑uPxP)≤ωG,
where we used ∑PuPxP=v(dℓ−1)−(2ℓ−v)(d−1). Finally, the four identities give
P∑uP2=v2(dq−1)−2v(2ℓ−v)(dℓ−1)+(2ℓ−v)2(d−1),
which is the left-hand side of the star inequality. For A⋆ one has ℓ=v, κ=c and q=2, and both sides are equal to d/2. □
Proof of the upper bound λmax(A)≤λ+: Suppose that ℓ=v+ε with ε≥0. Then ω=κ−ε≥0. A direct expansion, using 2v2=2v+1, gives
G=dv−ε(d(d+2−2v)−4)≤dv
and
P∑uP2=d[v2(q−ℓ2)+(21−(2−v)ε)2]−4ε2.
Since ω≥0 and G≤dv, the star inequality implies ∑PuP2≤(κ−ε)dv. Dividing by d and rearranging, this reads
v2(q−ℓ2−κ2)+(vκ−21)2+(3−1)ε+((2−v)2−d4)ε2≤0.
The first term is non-negative because q≥ℓ2+κ2, and the second term is a square. If ε>0, the last two terms are positive. Indeed, the coefficient of ε2 is positive for d≥16. For d=4 and d=8 it equals −0.60 and −0.10, but ε≤d−v (because ℓ2≤q≤d, the last inequality following from ∣aP∣≤1), that is, ε<0.64 and ε<1.47 respectively, and then (3−1)+((2−v)2−d4)ε>0. This contradiction shows that ε=0, i.e. ℓ≤λ+. If ℓ=λ+, the displayed inequality forces vκ=21, that is κ=c=−λ−, and q=ℓ2+κ2, so that all the other eigenvalues of A vanish. This proves the upper bound and its equality case.
2.2 The smallest eigenvalue
The argument is the mirror image of the previous one, and the induction hypothesis is now used in the form λmin(B)≥−c for every B∈Λn−1. If λmin(A)≥0 there is nothing to prove. Otherwise let −κ=λmin(A)<0 with unit eigenvector χ, and let ℓ=λmax(A). For every Pauli P=I we define
The operator R′′ is positive semidefinite, since ℓI−A≥0 and R′′ is this operator with its eigenvalue ℓ+κ at χ removed. Therefore fP=ℓ−αP′−(ℓ+κ)yP2≥0.
Lemma (mirror inequalities). For every Pauli P=I,
Proof: By the block lemma and the induction hypothesis, B±≥−cTr[B±]Π±. Taking the expectation value in χ and using Aχ=−κχ gives
−κ+αP′∓2κyP≥−c(1±aP)(1±yP).
Inserting αP′=ℓ−(ℓ+κ)yP2−fP and collecting terms, we find
fP≤(1±yP)(ω′±ζP′),ζP′:=caP−(κ+ℓ)yP.
Since uP′=ζP′+ω′yP, the smaller of the two bounds is ω′(1−yP2)−∣uP′∣(1−σP′yP), exactly as in the per-Pauli inequality. In the same way we obtain ω′≥0 and ∣uP′∣≤ω′(1+σP′yP) for every P (if σP′yP=1, then ∣uP′∣=σP′caP−(2κ−c)≤2(c−κ)≤2ω′).
The rule for Pauli sums now gives ∑PyP2=d−1, ∑PaPyP=−dκ−1, ∑PaP2=dq−1 and ∑PαP′=d+κ. Hence ∑PfP=ℓd(d−1)−d(1+κ), and summing the first inequality over P yields
P∑∣uP′∣(1−σP′yP)≤(c−κ)d(d−1)+d(1+κ).
Multiplying ∣uP′∣≤ω′(1+σP′yP) by ∣uP′∣, summing over P, and using ∑PuP′yP=−c(dκ+1)−(2κ−c)(d−1), we arrive at ∑PuP′2≤ω′G′. □
Proof of the lower bound λmin(A)≥λ−: Suppose that κ=c+ε with ε≥0. A direct expansion, using c2+c=vc=21, gives
G′=dc−ε(d(d+2+2c)−4)≤dc
and
P∑uP′2=d[c2(q−κ2)+(21+(2+c)ε)2]−4ε2.
Since ω′=ℓ−ε≥0 and G′≤dc, the mirror inequalities imply ∑PuP′2≤(ℓ−ε)dc. Dividing by d and rearranging, this reads
c2(q−ℓ2−κ2)+(cℓ−21)2+(1+3)ε+((2+c)2−d4)ε2≤0.
The first term is non-negative because q≥ℓ2+κ2, the second is a square, and the coefficients of ε and ε2 are positive. Hence ε=0, i.e. λmin(A)≥λ−. If λmin(A)=λ−, the displayed inequality forces cℓ=21, that is ℓ=v=λ+, and q=ℓ2+κ2, so that all the other eigenvalues of A vanish. This completes the induction and the proof of the theorem on the spectrum of a witness. □
The theorem has a direct translation into a statement about states.
Corollary (dual form of the theorem on the spectrum). For every n-qubit state ρ,
λ+d−1λ+I−ρ∈STABn
and
pρ+(1−p)dI∈STABnwheneverp≤1+(3−1)2n−11.
Both constants are optimal for every n.
Proof: A state σ belongs to STABn if and only if Tr[Aσ]≥0 for all A∈Λn[4]. By the theorem, λ−≤Tr[Aρ]≤λ+ for every state ρ and every A∈Λn. Hence Tr[A(λ+I−ρ)]=λ+−Tr[Aρ]≥0, and Tr[A(pρ+(1−p)I/d)]≥−pc+(1−p)/d, which is non-negative exactly when p≤1/(1+cd), and cd=(3−1)2n−1. For the optimality, take A=A⋆ and let ρ be its eigenvector with eigenvalue λ+ in the first statement and with eigenvalue λ− in the second. □
2.3 The star inequality near A⋆
For the application to purity in the second part, it is convenient to rewrite the star inequality in variables that measure the distance of a witness from A⋆. For A∈Λn with a negative eigenvalue we write
ℓ=λmax(A)=v−δ,κ=−λmin(A)=c−k,q=Tr[A2]=2+θ.
By the theorem on the spectrum of a witness, δ≥0 and k≥0, and for A⋆ we have δ=k=θ=0.
Lemma (the star inequality near A⋆). Let n≥2 and let A∈Λn have a negative eigenvalue. Then
dv2θ+dvk≤δ[(c−k)D−d(v+3)]+δ2[D+4d(v−1)+4],
where D:=d(d+2−2v)−4.
Proof: We insert ℓ=v−δ, κ=c−k and q=2+θ in the star inequality. Using 2v2=2v+1, vc=21 and v2+c2=2, one finds G=dv+δD and
Subtracting the two expressions gives the claim. □
The second part combines this lemma with the Liu–Liu inequality of Ref. [3] to bound the purity Tr[A2] of every witness, which is what the theorem stated at the beginning requires.
Remark. All the inequalities used in the proofs above were also tested numerically on elements of Λn for n=2,3,4. The argument is AI-generated and has not been peer reviewed.
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)
Michael Zurel and Jack Davis, Basis-independent stabilizerness and maximally noisy magic states, arXiv:2602.22336 (2026)
Zhenhuan Liu and Zi-Wen Liu, On the geometry, typicality, and detectability of quantum magic, arXiv:2609.03944 (2026)
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)
Ben W. Reichardt, Quantum universality by state distillation, arXiv:quant-ph/0608085 (2006)
Cihan Okay, Michael Zurel, Robert Raussendorf, On the extremal points of the $\Lambda$-polytopes and classical simulation of quantum computation with magic states, Quantum Information and Computation Vol.21 No.13&14, 1533-7146 (2021) doi:10.26421/QIC21.13-14-2
Michael Zurel, Cihan Okay, Robert Raussendorf, and Arne Heimendahl, Hidden variable model for quantum computation with magic states on qudits of any dimension, Quantum 8, 1323 (2024)
Michael Zurel, Cihan Okay, and Robert Raussendorf, Simulating Quantum Computation: How Many “Bits” for “It”?, PRX Quantum 5, 030343 (2024)