Introduction
Measurement incompatibility is a fundamental manifestation of quantum complementarity [1–3]. A collection of measurements is incompatible if there is no common parent measurement from which all of them can be obtained by classical post-processing; otherwise the measurements are compatible, or jointly measurable [4–6]. Incompatibility, which for projective measurements is equivalent to noncommutativity, is also a quantum resource: it underpins quantum steering [7, 8], is closely related to contextuality and Bell nonlocality [9, 10], and guarantees an advantage in suitable state discrimination tasks [11].
A related but operationally distinct form of complementarity is preparation uncertainty [12–14], which constrains the joint predictability of the outcomes of several observables in a single quantum state. For arbitrary finite Pauli families, we establish a direct connection between these two notions: the sharpness tradeoffs allowed by joint measurability are completely determined by the geometry of absolute Pauli expectation values attainable by quantum states.
Consider a finite family of projective (sharp) binary observables { A v } v ∈ V \{A_v\}_{v\in V} { A v } v ∈ V , represented by Hermitian unitaries with outcomes ± 1 \pm1 ± 1 . Assigning each observable an independent sharpness s v ∈ [ 0 , 1 ] s_v \in[0,1] s v ∈ [ 0 , 1 ] gives the noisy (unsharp) measurement with effects [ 1 ± s v A v ] / 2 [\mathbb{1} \pm s_v A_v]/2 [ 1 ± s v A v ] /2 . We say that the sharpness vector s = ( s v ) v ∈ V \boldsymbol{s}=(s_v)_{v\in V} s = ( s v ) v ∈ V is jointly measurable. The set of all such vectors forms the compatibility region, which describes the full tradeoff between the noise added to the different observables. Its upper boundary describes the optimal sharpness tradeoffs.
When all sharpnesses are equal, their largest compatible value is the optimal uniform sharpness. For Pauli observables, this coincides with the incompatibility robustness under depolarising noise [15]. Alongside characterising the full region, we seek explicit parent measurements realising its points. Of particular interest are optimal parents along the boundary, which are relevant in applications such as simultaneous observable estimation [16–18].
Despite its simple definition, joint measurability can be difficult to characterise for large families. For m m m binary measurements, the standard semidefinite formulation involves 2 m 2^m 2 m parent effects as optimisation variables [19, 20]. Exact criteria are known in several special settings, including pairs and triples of qubit measurements [21, 22], arbitrary finite families of unbiased binary qubit measurements [23], and certain highly symmetric families in higher dimensions, such as complete sets of mutually unbiased bases [24, 25].
Pauli observables—tensor products of single-qubit Pauli and identity operators—are ubiquitous across quantum information [26–31] and give the compatibility problem a useful discrete structure. Any two Pauli observables either commute or anti-commute, so their pairwise relations are encoded by an anti-commutativity graph , whose vertices represent observables and whose edges join anti-commuting pairs. On the preparation side, this graph has been used to derive uncertainty relations [32] and to study the joint numerical range [33] of Pauli families. On the measurement side, existing results have largely concerned incompatibility robustness, with exact or asymptotic values known for a few structured families [17, 34]. The robustness has been shown to depend only on the anti-commutativity graph, with graph invariants providing general bounds [35 ] . Here we seek a characterisation of the full compatibility region, including all nonuniform sharpness tradeoffs, together with explicit parent measurements realising them.
The present work gives an exact state-space characterisation of the full compatibility region for arbitrary finite Pauli families. A state ρ \rho ρ determines a predictability profile ( ∣ tr ( ρ A v ) ∣ ) v ∈ V (|\operatorname{tr}(\rho A_v)|)_{v\in V} ( ∣ tr ( ρ A v ) ∣ ) v ∈ V . We show that a sharpness vector s = ( s v ) v ∈ V s=(s_v)_{v\in V} s = ( s v ) v ∈ V is compatible if and only if it is componentwise bounded by a convex combination of these profiles. The state-space description also gives an explicit construction of joint measurements: the same states that determine the compatibility region generate parent measurements through their Pauli-conjugation orbits. By mixing these orbit POVMs and applying classical post-processing, we realise every compatible sharpness vector. In a canonical irreducible representation, the binary rank of the adjacency matrix determines the number of labelled outcomes in each orbit POVM, while its binary nullity bounds the number of seed orbits needed to realise any point in the compatibility region.
The full compatibility region depends only on the anti-commutativity graph, extending the previously known graph invariance of the incompatibility robustness [35 ] to all nonuniform sharpness tradeoffs. It also characterises how accurately arbitrary jointly measurable binary measurements can approximate the sharp Pauli measurements, as quantified by their worst-case total-variation errors. For the noise models considered in [36 ] , the same region determines the full nonuniform compatibility tradeoffs in all cases. At uniform sharpness, all of the resulting robustness thresholds are determined by the depolarising noise, with the same parent attaining each optimum.
We show that optimal sharpness tradeoffs along the boundary of the compatibility region can be determined from the ground-state energies of Hamiltonians that are linear combinations of the Pauli observables with suitable weights and signs. Ensembles of the corresponding ground states then generate joint measurements attaining these tradeoffs. For vertex-transitive graphs, we show that symmetry removes the optimisation over the relative weights of the Hamiltonian terms, reducing the uniform sharpness problem to a spectral optimisation over sign choices.
The state-space characterisation also reveals how magic [27] can enhance the sharpness attainable by joint measurements. Restricting the seed states in our construction to stabilizer states gives a corresponding class of stabilizer parents . We show that their attainable sharpness vectors form exactly the stable-set polytope of the anti-commutativity graph, which is equivalent to the region obtained by classically randomising over sharp joint measurements of commuting subsets. For every non-commuting Pauli family, the full compatibility region is strictly larger. We quantify this advantage and relate it to the reduced robustness of magic [37 , 38 ] . When no commuting subset of the family has product proportional to the identity, this robustness equals the smallest factor by which a seed’s sharpness vector must be reduced to become attainable by a stabilizer parent.
Finally, we apply the framework to structured graph families. For line graphs, quadratic Majorana realisations allow us to characterise the full compatibility region using Gaussian seed states. Their covariance matrices give the correlations that determine the sharpnesses attained by the corresponding orbit parents. For cycles and paths, we obtain exact compatibility characterisations and explicit optimal parents. In particular, removing one or two consecutive observables from an even cycle leaves the optimal uniform sharpness unchanged, and the same parent measurement remains optimal. For the complete quadratic Majorana family, skew-conference matrices provide Gaussian seeds whose single-orbit parents attain the optimal uniform sharpness. For the complete Pauli family, an optimal single-orbit parent at uniform sharpness exists if and only if a Pauli-covariant symmetric informationally complete measurement (SIC) exists.
The paper is organised as follows. Sec. II introduces the required preliminaries and notation. Sec. III gives the state-space characterisation and parent construction, together with their consequences for measurement uncertainty and different noise models. Sec. IV characterises optimal sharpness tradeoffs and constructs parent measurements that attain them. In Sec. V we treat stabilizer restrictions and magic, and Sec. VI presents exact results for several structured families. We conclude with a discussion of the main implications and open questions.
Preliminaries
Measurements and joint measurability
We work on a finite-dimensional Hilbert space H \mathcal{H} H of dimension d d d , with identity operator 1 \mathbb{1} 1 . A measurement with finite outcome set Ω \Omega Ω is a POVM E : = { E ( a ) } a ∈ Ω \mathrm{E}:=\{\mathrm{E}(a)\}_{a\in\Omega} E := { E ( a ) } a ∈ Ω , whose effects satisfy E ( a ) ≥ 0 \mathrm{E}(a)\geq0 E ( a ) ≥ 0 and ∑ a E ( a ) = 1 \sum_a\mathrm{E}(a)=\mathbb{1} ∑ a E ( a ) = 1 . For a quantum state ρ ≥ 0 \rho\geq0 ρ ≥ 0 with tr ( ρ ) = 1 \operatorname{tr}(\rho)=1 tr ( ρ ) = 1 , the probability of outcome a a a is tr ( ρ E ( a ) ) \operatorname{tr}(\rho\mathrm{E}(a)) tr ( ρ E ( a )) . We write ∥ T ∥ 1 : = tr ( T † T ) \lVert T\rVert_1:=\operatorname{tr}(\sqrt{T^\dagger T}) ∥ T ∥ 1 := tr ( T † T ) and ∥ T ∥ ∞ \lVert T\rVert_\infty ∥ T ∥ ∞ for the trace and operator norms, respectively.
Let A = { A v } v ∈ V \mathcal{A}=\{A_v\}_{v\in V} A = { A v } v ∈ V be a finite family of sharp binary observables satisfying A v = A v † A_v=A_v^\dagger A v = A v † and A v 2 = 1 A_v^2=\mathbb{1} A v 2 = 1 . We assign each observable a sharpness s v ∈ [ 0 , 1 ] s_v\in[0,1] s v ∈ [ 0 , 1 ] and write s = ( s v ) v ∈ V s=(s_v)_{v\in V} s = ( s v ) v ∈ V for the resulting sharpness vector of the family. The corresponding noisy (unsharp) binary POVMs are
M v s v ( b ) = 1 2 ( 1 + b s v A v ) , (1) \mathrm{M}^{s_v}_v(b)=\frac{1}{2}\left(\mathbb{1}+b\,s_v A_v\right), \tag*{(1)} M v s v ( b ) = 2 1 ( 1 + b s v A v ) , (1)
with outcomes b ∈ { + 1 } b\in\{+1\} b ∈ { + 1 } . Here s v = 1 s_v=1 s v = 1 gives the sharp measurement of A v A_v A v , while s v = 0 s_v=0 s v = 0 gives a uniformly random binary outcome. The noisy measurement can be obtained by flipping the sharp outcome with probability ( 1 − s v ) / 2 (1-s_v)/2 ( 1 − s v ) /2 .
A family of measurements is jointly measurable if its members can be obtained as marginals of a single measurement, described by a parent POVM. For the binary family { M v s v } v ∈ V \{\mathrm{M}^{s_v}_v\}_{v\in V} { M v s v } v ∈ V , this means that there exists a POVM { E ( a ) } a ∈ { ± 1 } V \{E(a)\}_{a\in\{\pm1\}^{V}} { E ( a ) } a ∈ { ± 1 } V satisfying
∑ a : a v = b E ( a ) = M v s v ( b ) , v ∈ V , \sum_{a:a_v=b} E(a)=M_v^{s_v}(b),\qquad v\in V, a : a v = b ∑ E ( a ) = M v s v ( b ) , v ∈ V ,
for outcome b ∈ { ± 1 } b\in\{\pm1\} b ∈ { ± 1 } . Each parent outcome a = ( a v ) v ∈ V a=(a_v)_{v\in V} a = ( a v ) v ∈ V records one binary result for each measurement. Measuring the parent and reporting the coordinate a v a_v a v therefore reproduces the statistics of M v s v M_v^{s_v} M v s v for every input state. This definition can equivalently be formulated in terms of classical post-processing [39 Proposition 8] , with each measurement obtained from a common parent POVM by a classical stochastic map. Since the two effects of each binary marginal sum to 1, the marginal conditions are equivalent to
∑ a a v E ( a ) = s v A v , v ∈ V . (2) \sum_a a_vE(a)=s_vA_v,\qquad v\in V. \tag*{(2)} a ∑ a v E ( a ) = s v A v , v ∈ V . (2)
The largest η ∈ [ 0 , 1 ] \eta\in[0,1] η ∈ [ 0 , 1 ] for which the family is jointly measurable with s v = η s_v=\eta s v = η for every v v v is its optimal uniform sharpness . For Pauli observables, this coincides with the incompatibility robustness under depolarising noise [15]. Sec. III 5 relates this threshold to other standard notions of incompatibility robustness.
Classical randomisation over measurements can itself be described by a single POVM. Choosing E j = { E j ( x ) } E_j=\{E_j(x)\} E j = { E j ( x )} with probability p j p_j p j and recording both j j j and x x x gives the POVM with effects p j E j ( x ) p_jE_j(x) p j E j ( x ) . We refer to this as mixing the POVMs .
Pauli families and conjugation symmetries
A Pauli observable on n n n qubits is a tensor product ± P 1 ⊗ ⋯ ⊗ P n \pm P_1\otimes\cdots\otimes P_n ± P 1 ⊗ ⋯ ⊗ P n , where P j ∈ { 1 , X , Y , Z } P_j\in\{1,X,Y,Z\} P j ∈ { 1 , X , Y , Z } . A finite collection of such observables is called a Pauli family . Any two Pauli observables either commute or anti-commute, so their pairwise relations are encoded by the anti-commutativity graph G = ( V , E ) G=(V,E) G = ( V , E ) , with
{ u , v } ∈ E ⟺ A u A v = − A v A u . \{u,v\}\in E\quad\Longleftrightarrow\quad A_uA_v=-A_vA_u. { u , v } ∈ E ⟺ A u A v = − A v A u .
Every finite simple graph admits a Pauli realisation [40 , 41 ] [33]. Writing B G B_G B G for the adjacency matrix of G G G over F 2 \mathbb{F}_2 F 2 , the commutation relations take the form
A u A v = ( − 1 ) ( B G ) u v A v A u . A_uA_v=(-1)^{(B_G)_{uv}}A_vA_u. A u A v = ( − 1 ) ( B G ) uv A v A u .
Together with A v = A v † A_v=A_v^\dagger A v = A v † and A v 2 = 1 A_v^2=1 A v 2 = 1 , these are the graph-Clifford relations associated with G G G . The binary rank and nullity of B G B_G B G are
r : = rank F 2 B G , r:=\operatorname{rank}_{\mathbb{F}_2}B_G, r := rank F 2 B G ,
ν 2 ( G ) : = dim F 2 ker B G = ∣ V ∣ − r . (3) \nu_2(G):=\dim_{\mathbb{F}_2}\ker B_G=|V|-r. \tag*{(3)} ν 2 ( G ) := dim F 2 ker B G = ∣ V ∣ − r . (3)
Since B G B_G B G is alternating over F 2 \mathbb{F}_2 F 2 , i.e., symmetric with zero diagonal, its rank r r r is even [41 ] . Every irreducible realisation of the graph-Clifford relations has dimension
d G = 2 r / 2 . d_G=2^{r/2}. d G = 2 r /2 .
We call any such irreducible realisation a canonical representation . The original physical representation need not be irreducible, and its dimension d d d need not equal d G d_G d G . Appendix A gives the algebraic details. Appendix § 4.1 explains how parent measurements can be mapped between canonical and physical representations without changing their sharpness vectors.
The matrix B G B_G B G also determines the sign changes induced by conjugation with products of the selected observables. Fix an ordering of V V V and, for z ∈ F 2 V z\in\mathbb{F}_2^V z ∈ F 2 V , define the ordered monomial
A z : = ∏ v ∈ V A v z v . A^z:=\prod_{v\in V}A_v^{z_v}. A z := v ∈ V ∏ A v z v .
The graph-Clifford relations give
A z A v ( A z ) † = ( − 1 ) ( B G z ) v A v . A^zA_v(A^z)^\dagger=(-1)^{(B_Gz)_v}A_v. A z A v ( A z ) † = ( − 1 ) ( B G z ) v A v .
Thus two labels z , z ′ z,z' z , z ′ induce the same sign changes on the family exactly when z − z ′ ∈ ker B G z-z'\in\ker B_G z − z ′ ∈ ker B G . These distinct actions form the finite abelian group
K G : = F 2 V / ker B G , ∣ K G ∣ = 2 r = d G 2 . \mathcal{K}_G:=\mathbb{F}_2^V/\ker B_G,\qquad|\mathcal{K}_G|=2^r=d_G^2. K G := F 2 V / ker B G , ∣ K G ∣ = 2 r = d G 2 .
Thus K G \mathcal{K}_G K G may be viewed as the group of sign patterns on the family generated by Pauli conjugation. For each class x ∈ K G x\in\mathcal{K}_G x ∈ K G , choose a representative x ~ ∈ F 2 V \tilde{x}\in\mathbb{F}_2^V x ~ ∈ F 2 V and set U x : = A x ~ U_x:=A^{\tilde{x}} U x := A x ~ . Define
χ v ( x ) : = ( − 1 ) ( B G x ~ ) v . (4) \chi_v(x):=(-1)^{(B_G\tilde{x})_v}. \tag*{(4)} χ v ( x ) := ( − 1 ) ( B G x ~ ) v . (4)
These functions are independent of the representative and are characters of K G \mathcal{K}_G K G , satisfying χ v ( x + y ) = χ v ( x ) χ v ( y ) \chi_v(x+y)=\chi_v(x)\chi_v(y) χ v ( x + y ) = χ v ( x ) χ v ( y ) . In particular,
U x A v U x † = χ v ( x ) A v . (5) U_xA_vU_x^\dagger=\chi_v(x)A_v. \tag*{(5)} U x A v U x † = χ v ( x ) A v . (5)
If k ∈ ker B G k\in\ker B_G k ∈ ker B G , the product A k A^k A k commutes with every observable A v A_v A v . In a canonical representation, irreducibility therefore forces A k = λ k 1 A^k=\lambda_k1 A k = λ k 1 , with ∣ λ k ∣ = 1 |\lambda_k|=1 ∣ λ k ∣ = 1 . Changing the representative of x ∈ K G x\in\mathcal{K}_G x ∈ K G consequently multiples U x U_x U x only by a phase, which cancels in U x X U x † U_xXU_x^\dagger U x X U x † for every operator X X X . The conjugation action is therefore independent of this choice. These symmetries underlie the orbit parent construction below; their algebraic properties are collected in Appendix A.
Majorana monomials (see e.g. § 3.2 ) fit the same framework through standard fermion-to-qubit mappings. Such monomials can be identified, up to phase, with Pauli strings that preserve their commutation relations [42 , 43 ] .
State-space characterisation and parent measurements
We now formulate joint measurability of Pauli observables in terms of the absolute expectation values attainable by quantum states. The same states generate explicit parent measurements through Pauli-conjugation orbits. We first develop this construction and bound the number of seeds needed, then derive its consequences for measurement uncertainty and compatibility under different noise models.
State-space characterisation
We first present the construction for a canonical Pauli family A = { A v } v ∈ V \mathcal{A} = \{A_v\}_{v\in V} A = { A v } v ∈ V on C d G \mathbb{C}^{d_G} C d G , and then extend the result to arbitrary physical Pauli families.
For a state ρ \rho ρ , define its absolute expectation-value vector c A ( ρ ) : = ( ∣ tr ( ρ A v ) ∣ ) v ∈ V c_{\mathcal{A}}(\rho) := \left(\lvert\operatorname{tr}(\rho A_v)\rvert\right)_{v\in V} c A ( ρ ) := ( ∣ tr ( ρ A v )∣ ) v ∈ V .
c A ( ρ ) : = ( ∣ tr ( ρ A v ) ∣ ) v ∈ V . (6) c_{\mathcal{A}}(\rho) := \left(\lvert\operatorname{tr}(\rho A_v)\rvert\right)_{v\in V}. \tag*{(6)} c A ( ρ ) := ( ∣ tr ( ρ A v )∣ ) v ∈ V . (6)
The correspondence below follows from two complementary constructions: normalising parent effects produces an ensemble of states, while Pauli conjugation turns suitable seed states into a parent measurement.
From parent measurements to states. For every nonzero effect E ( a ) E(a) E ( a ) of a parent satisfying Eq. (2) , set
p a = tr ( E ( a ) ) d G , ρ a = E ( a ) tr ( E ( a ) ) . (7) p_a = \frac{\operatorname{tr}(E(a))}{d_G}, \qquad\rho_a = \frac{E(a)}{\operatorname{tr}(E(a))}. \tag*{(7)} p a = d G tr ( E ( a )) , ρ a = tr ( E ( a )) E ( a ) . (7)
These define an ensemble with ∑ a p a = 1 \sum_a p_a = 1 ∑ a p a = 1 and ∑ a p a ρ a = 1 / d G \sum_a p_a\rho_a = \mathbb{1}/d_G ∑ a p a ρ a = 1/ d G . Multiplying Eq. (2) by A v A_v A v , taking the trace, and using A v 2 = 1 A_v^2=\mathbb{1} A v 2 = 1 gives
s v = ∑ a p a a v tr ( ρ a A v ) ≤ ∑ a p a ∣ tr ( ρ a A v ) ∣ . (8) s_v = \sum_a p_a a_v \operatorname{tr}(\rho_a A_v) \leq\sum_a p_a \lvert\operatorname{tr}(\rho_a A_v)\rvert. \tag*{(8)} s v = a ∑ p a a v tr ( ρ a A v ) ≤ a ∑ p a ∣ tr ( ρ a A v )∣ . (8)
Thus s s s lies componentwise below a convex combination of the vectors c A ( ρ a ) c_{\mathcal{A}}(\rho_a) c A ( ρ a ) . This necessary condition holds for any family of binary observables of the form Eq. (1) . The Pauli-specific result is that it is also sufficient.
From states to parent measurements. In the canonical representation, averaging over Pauli conjugations removes every operator component except the identity component. Weighting the same average by χ v \chi_v χ v (defined in Eq. (4) ) instead selects the component along A v A_v A v . Thus, for every operator X X X ,
1 ∣ K G ∣ ∑ x ∈ K G U x X U x † = tr ( X ) d G 1 , \frac{1}{\lvert K_G\rvert}\sum_{x\in K_G}U_x X U_x^\dagger= \frac{\operatorname{tr}(X)}{d_G}\mathbb{1}, ∣ K G ∣ 1 x ∈ K G ∑ U x X U x † = d G tr ( X ) 1 ,
1 ∣ K G ∣ ∑ x ∈ K G χ v ( x ) U x X U x † = tr ( A v X ) d G A v . (9) \frac{1}{\lvert K_G\rvert}\sum_{x\in K_G}\chi_v(x)U_x X U_x^\dagger= \frac{\operatorname{tr}(A_vX)}{d_G}A_v. \tag*{(9)} ∣ K G ∣ 1 x ∈ K G ∑ χ v ( x ) U x X U x † = d G tr ( A v X ) A v . (9)
Appendix A derives these identities from the conjugation action Eq. (5) .
Given a state ρ \rho ρ , define
E ρ ( x ) = 1 d G U x ρ U x † , x ∈ K G . (10) E_\rho(x)=\frac{1}{d_G}U_x\rho U_x^\dagger,\qquad x\in K_G. \tag*{(10)} E ρ ( x ) = d G 1 U x ρ U x † , x ∈ K G . (10)
The first identity in Eq. (9) , together with ∣ K G ∣ = d G 2 \lvert K_G\rvert=d_G^2 ∣ K G ∣ = d G 2 , shows that these effects sum to 1 \mathbb{1} 1 . We call ρ \rho ρ the seed state, the family { U x ρ U x † } x ∈ K G \{U_x\rho U_x^\dagger\}_{x\in K_G} { U x ρ U x † } x ∈ K G its Pauli orbit , and E ρ E_\rho E ρ the corresponding orbit POVM .
For each v v v , choose α v ∈ { ± 1 } \alpha_v\in\{\pm1\} α v ∈ { ± 1 } such that α v tr ( ρ A v ) = ∣ tr ( ρ A v ) ∣ \alpha_v\operatorname{tr}(\rho A_v)=\lvert\operatorname{tr}(\rho A_v)\rvert α v tr ( ρ A v ) = ∣ tr ( ρ A v )∣ , with either sign allowed when the expectation vanishes. We then assign the binary outcome α v χ v ( x ) \alpha_v\chi_v(x) α v χ v ( x ) to each orbit outcome x x x . The second character identity gives
∑ x ∈ K G α v χ v ( x ) E ρ ( x ) = ∣ tr ( ρ A v ) ∣ A v . (11) \sum_{x\in K_G}\alpha_v\chi_v(x)E_\rho(x)=\lvert\operatorname{tr}(\rho A_v)\rvert A_v. \tag*{(11)} x ∈ K G ∑ α v χ v ( x ) E ρ ( x ) = ∣ tr ( ρ A v )∣ A v . (11)
Since the binary marginal effects sum to 1 \mathbb{1} 1 , this is precisely the measurement M v ∣ tr ( ρ A v ) ∣ M_v^{\lvert\operatorname{tr}(\rho A_v)\rvert} M v ∣ tr ( ρ A v )∣ . Thus one seed state generates a parent with sharpness vector c A ( ρ ) c_{\mathcal{A}}(\rho) c A ( ρ ) .
Now consider a finite ensemble { p j , ρ j } \{p_j,\rho_j\} { p j , ρ j } . Choose j j j with probability p j p_j p j , perform the orbit POVM E ρ j E_{\rho_j} E ρ j on the input system, and record both j j j and the orbit outcome x x x . For each j j j and v v v , choose α j v ∈ { ± 1 } \alpha_{jv}\in\{\pm1\} α j v ∈ { ± 1 } such that α j v tr ( ρ j A v ) = ∣ tr ( ρ j A v ) ∣ \alpha_{jv}\operatorname{tr}(\rho_jA_v)=\lvert\operatorname{tr}(\rho_jA_v)\rvert α j v tr ( ρ j A v ) = ∣ tr ( ρ j A v )∣ , and assign the outcome α j v χ v ( x ) \alpha_{jv}\chi_v(x) α j v χ v ( x ) as the result for observable v v v . Averaging Eq. (11) over j j j gives sharpness
t v : = ∑ j p j ∣ tr ( ρ j A v ) ∣ . t_v:=\sum_j p_j\lvert\operatorname{tr}(\rho_jA_v)\rvert. t v := j ∑ p j ∣ tr ( ρ j A v )∣ .
Whenever s ≤ t s\leq t s ≤ t , independently flipping the reported result for v v v with probability $(1-s_v/t_v)/2 reduces its sharpness to s v s_v s v . If t v = 0 t_v=0 t v = 0 , then s v = 0 s_v=0 s v = 0 and no additional noise is needed.
Appendix B shows that the ensemble condition and parent construction extend beyond the canonical representation to arbitrary physical Pauli families. In the following definitions and theorem, A \mathcal{A} A may therefore act on its original Hilbert space H \mathcal{H} H , and the states in the ensemble are states on H \mathcal{H} H .
Define the state region and compatibility region by
R A : = { c A ( ρ ) : ρ a state } , (12) \mathcal{R}_{\mathcal{A}}:=\{c_{\mathcal{A}}(\rho):\rho\text{ a state}\}, \tag*{(12)} R A := { c A ( ρ ) : ρ a state } , (12)
C A : = { s ∈ [ 0 , 1 ] V : { M v s v } v ∈ V is jointly measurable } . (13) \mathcal{C}_{\mathcal{A}}:=\{s\in[0,1]^V:\{M_v^{s_v}\}_{v\in V}\text{ is jointly measurable}\}. \tag*{(13)} C A := { s ∈ [ 0 , 1 ] V : { M v s v } v ∈ V is jointly measurable } . (13)
The two constructions above establish the following characterisation.
Theorem 1. Let A = { A v } v ∈ V \mathcal{A}=\{A_v\}_{v\in V} A = { A v } v ∈ V be a finite Pauli family on H \mathcal{H} H , and let s ∈ [ 0 , 1 ] V s\in[0,1]^V s ∈ [ 0 , 1 ] V . The measurements { M v s v } v ∈ V \{M_v^{s_v}\}_{v\in V} { M v s v } v ∈ V are jointly measurable if and only if there is a finite ensemble { p j , ρ j } \{p_j,\rho_j\} { p j , ρ j } of states on H \mathcal{H} H , with p j ≥ 0 p_j\geq0 p j ≥ 0 and ∑ j p j = 1 \sum_jp_j=1 ∑ j p j = 1 , satisfying
s v ≤ ∑ j p j ∣ tr ( ρ j A v ) ∣ , v ∈ V . (14) s_v\leq\sum_jp_j\lvert\operatorname{tr}(\rho_jA_v)\rvert,\qquad v\in V. \tag*{(14)} s v ≤ j ∑ p j ∣ tr ( ρ j A v )∣ , v ∈ V . (14) In a canonical representation, every such ensemble gives the parent POVM
E ( j , x ) = p j E ρ j ( x ) = p j d G U x ρ j U x † , x ∈ K G . (15) E(j,x)=p_jE_{\rho_j}(x)=\frac{p_j}{d_G}U_x\rho_jU_x^\dagger,\qquad x\in K_G. \tag*{(15)} E ( j , x ) = p j E ρ j ( x ) = d G p j U x ρ j U x † , x ∈ K G . (15)
For an arbitrary physical representation, Appendix B supplies a corresponding parent with the same target sharpness vector s s s .
Proof. Necessity follows from Eq. (8) , with d G d_G d G replaced by dim H \dim\mathcal{H} dim H for an arbitrary physical representation. The preceding orbit construction, followed by classical output noise, proves sufficiency in a canonical representation and gives Eq. (15) . Lemmas B.2 and B.3 in Appendix B extend this construction to the original Hilbert space. □
Theorem 1 implies that the compatible sharpness vectors are those lying componentwise below a convex combination of state profiles:
C A = { s ∈ [ 0 , 1 ] V : s ≤ t for some t ∈ conv R A } . (16) \mathcal{C}_{\mathcal{A}}=\left\{s\in[0,1]^V:s\leq t\text{ for some }t\in\operatorname{conv}\mathcal{R}_{\mathcal{A}}\right\}. \tag*{(16)} C A = { s ∈ [ 0 , 1 ] V : s ≤ t for some t ∈ conv R A } . (16)
The seeds may always be chosen pure: decomposing each mixed seed and applying the triangle inequality can only increase the averaged absolute expectations. Any excess sharpness is removed by classical noise.
As mentioned above, the converse in Theorem 1 is Pauli-specific. For example, for A 1 = X A_1=X A 1 = X and A 2 = ( X + Z ) / 2 A_2=(X+Z)/\sqrt{2} A 2 = ( X + Z ) / 2 , an X X X eigenstate has absolute expectation-value vector ( 1 , 1 / 2 ) (1,1/\sqrt{2}) ( 1 , 1/ 2 ) . However, the measurements with sharpness vector s = ( 1 , 1 / 2 ) s=(1,1/\sqrt{2}) s = ( 1 , 1/ 2 ) are incompatible since any measurement jointly measurable with sharp X X X must commute with it.
Representation independence also implies that two Pauli families with the same anti-commutativity graph have the same compatibility region. This extends the graph invariance of the uniform threshold [35 ] to all nonuniform sharpness tradeoffs.
Corollary 1. Let A = { A v } v ∈ V \mathcal{A}=\{A_v\}_{v\in V} A = { A v } v ∈ V and A ′ = { A v ′ } v ∈ V \mathcal{A}'=\{A'_v\}_{v\in V} A ′ = { A v ′ } v ∈ V be finite-dimensional Pauli families with the same anti-commutativity graph G G G . Then
C A = C A ′ . \mathcal{C}_{\mathcal{A}}=\mathcal{C}_{\mathcal{A}'}. C A = C A ′ .
Hence the compatibility region depends only on G G G , and we denote it by C G \mathcal{C}_G C G .
Proof. Appendix B maps parent measurements between any realisation of G G G and a fixed canonical family A G c \mathcal{A}^c_G A G c without changing their sharpness vectors. Thus C A = C A G c = C A ′ \mathcal{C}_{\mathcal{A}}=\mathcal{C}_{\mathcal{A}^c_G}=\mathcal{C}_{\mathcal{A}'} C A = C A G c = C A ′ . □
The corresponding optimal uniform sharpness is
η ( G ) : = max { η ∈ [ 0 , 1 ] : η 1 ∈ C G } , (17) \eta(G):=\max\{\eta\in[0,1]:\eta\mathbf{1}\in\mathcal{C}_G\}, \tag*{(17)} η ( G ) := max { η ∈ [ 0 , 1 ] : η 1 ∈ C G } , (17)
where 1 ∈ R V \mathbf{1}\in\mathbb{R}^V 1 ∈ R V is the all-ones vector.
Example: the single-qubit Pauli family
We illustrate Theorem 1 for A = { X , Y , Z } \mathcal{A}=\{X,Y,Z\} A = { X , Y , Z } , whose anti-commutativity graph is K 3 K_3 K 3 . Here the Bloch ball determines the compatibility region and supplies a seed for every compatible sharpness vector.
For a qubit state ρ \rho ρ , the coordinates of c A ( ρ ) c_{\mathcal{A}}(\rho) c A ( ρ ) are the absolute values of its Bloch components. The state region is therefore the nonnegative octant of the Bloch ball,
R X Y Z = { ( x , y , z ) ∈ R + 3 : x 2 + y 2 + z 2 ≤ 1 } . (18) \mathcal{R}_{XYZ}=\left\{(x,y,z)\in\mathbb{R}_{+}^{3}:x^2+y^2+z^2\leq1\right\}. \tag*{(18)} R X Y Z = { ( x , y , z ) ∈ R + 3 : x 2 + y 2 + z 2 ≤ 1 } . (18)
This region is already convex and closed under coordinatewise decrease within the nonnegative orthant. Thus neither averaging profiles nor reducing their components enlarges it, and Theorem 1 gives C X Y Z = R X Y Z \mathcal{C}_{XYZ}=\mathcal{R}_{XYZ} C X Y Z = R X Y Z . Equivalently, s = ( s X , s Y , s Z ) ∈ [ 0 , 1 ] 3 s=(s_X,s_Y,s_Z)\in[0,1]^3 s = ( s X , s Y , s Z ) ∈ [ 0 , 1 ] 3 is compatible if and only if
s X 2 + s Y 2 + s Z 2 ≤ 1 , (19) s_X^2+s_Y^2+s_Z^2\leq1, \tag*{(19)} s X 2 + s Y 2 + s Z 2 ≤ 1 , (19)
recovering the known criterion [44 , 45 ] [23].
To construct a parent for such a vector, choose the seed whose Bloch vector is s s s , namely
ρ s = 1 2 ( 1 + s X X + s Y Y + s Z Z ) . (20) \rho_s=\frac{1}{2}(\mathbb{1}+s_XX+s_YY+s_ZZ). \tag*{(20)} ρ s = 2 1 ( 1 + s X X + s Y Y + s Z Z ) . (20)
Equation (19) ensures positivity, and c A ( ρ s ) = s c_{\mathcal{A}}(\rho_s)=s c A ( ρ s ) = s . The Pauli-orbit construction gives the four effects 1 2 U ρ s U † \frac{1}{2}U\rho_sU^\dagger 2 1 U ρ s U † , with U ∈ { 1 , X , Y , Z } U\in\{\mathbb{1},X,Y,Z\} U ∈ { 1 , X , Y , Z } . Each nonidentity Pauli conjugation flips the other two Bloch components, so the resulting sign triples satisfy a X a Y a Z = 1 a_Xa_Ya_Z=1 a X a Y a Z = 1 . Using these triples as outcome labels, the parent is
E ( a ) = 1 4 ( 1 + a X s X X + a Y s Y Y + a Z s Z Z ) , (21) \mathsf{E}(a)=\frac{1}{4}(\mathbb{1}+a_Xs_XX+a_Ys_YY+a_Zs_ZZ), \tag*{(21)} E ( a ) = 4 1 ( 1 + a X s X X + a Y s Y Y + a Z s Z Z ) , (21)
with a ∈ { ± 1 } 3 a\in\{\pm1\}^3 a ∈ { ± 1 } 3 and a X a Y a Z = 1 a_Xa_Ya_Z=1 a X a Y a Z = 1 .
The classical readout for observable A v A_v A v is simply a v a_v a v . For fixed v ∈ { X , Y , Z } v\in\{X,Y,Z\} v ∈ { X , Y , Z } and b ∈ { ± 1 } b\in\{\pm1\} b ∈ { ± 1 } , the two effects with a v = b a_v=b a v = b have opposite coefficients for the other two Paulis. Those terms cancel, giving
∑ a X a Y a Z = 1 a v = b E ( a ) = 1 2 ( 1 + b s v A v ) = M v s v ( b ) . (22) \sum_{\substack{a_Xa_Ya_Z=1\\a_v=b}}\mathsf{E}(a)=\frac{1}{2}(\mathbb{1}+bs_vA_v)=\mathsf{M}^{s_v}_v(b). \tag*{(22)} a X a Y a Z = 1 a v = b ∑ E ( a ) = 2 1 ( 1 + b s v A v ) = M v s v ( b ) . (22)
On the spherical boundary s X 2 + s Y 2 + s Z 2 = 1 s_X^2+s_Y^2+s_Z^2=1 s X 2 + s Y 2 + s Z 2 = 1 , the seed ρ s \rho_s ρ s is pure and is the ground state of − ( s X X + s Y Y + s Z Z ) -(s_XX+s_YY+s_ZZ) − ( s X X + s Y Y + s Z Z ) , anticipating the general construction in Sec. IV. At the uniform optimum s X = s Y = s Z = 1 / 3 s_X=s_Y=s_Z=1/\sqrt{3} s X = s Y = s Z = 1/ 3 , this parent is the tetrahedral qubit SIC [46 ] ; the higher-dimensional connection is developed in Sec. VI.
Thus every compatible vector is realised exactly by a single, possibly mixed, seed, without mixing orbit POVMs or adding further output noise. Whether one seed suffices for a general Pauli family is the subject of the next subsection.
Single seeds and mixtures
The qubit example above uses one seed for every compatible sharpness vector. For a general Pauli family, the ensemble in Theorem 1 need not be replaceable by a single state. We first characterise when one seed suffices, and then bound the number required in general.
Throughout this subsection, we fix a canonical irreducible representation of G G G . A parent obtained from one orbit POVM by classical post-processing is called a single-orbit parent .
Proposition 1. A sharpness vector s s s admits a single-orbit parent if and only if there exists a state ρ \rho ρ such that
s ≤ c A ( ρ ) , (23) s \le c_{\mathcal{A}}(\rho), \tag*{(23)} s ≤ c A ( ρ ) , (23) componentwise.
Proof. If s ≤ c A ( ρ ) s \le c_{\mathcal{A}}(\rho) s ≤ c A ( ρ ) , the orbit POVM generated by ρ \rho ρ has sharpness vector c A ( ρ ) c_{\mathcal{A}}(\rho) c A ( ρ ) , and classical output noise reduces it to s s s .
Conversely, let f v ( x ) ∈ [ − 1 , 1 ] f_v(x) \in[-1,1] f v ( x ) ∈ [ − 1 , 1 ] be the conditional mean of the binary result reported for observable v v v after obtaining orbit outcome x x x . Then s v A v = ∑ x ∈ K G f v ( x ) E ρ ( x ) s_v A_v = \sum_{x\in K_G} f_v(x)E_\rho(x) s v A v = ∑ x ∈ K G f v ( x ) E ρ ( x ) . Multiplying by A v A_v A v , taking the trace, and using Eq. (5) gives
s v = tr ( ρ A v ) 1 ∣ K G ∣ ∑ x ∈ K G f v ( x ) χ v ( x ) . s_v = \operatorname{tr}(\rho A_v)\frac{1}{\lvert K_G\rvert}\sum_{x\in K_G} f_v(x)\chi_v(x). s v = tr ( ρ A v ) ∣ K G ∣ 1 x ∈ K G ∑ f v ( x ) χ v ( x ) .
Since the absolute value of the average is at most one, s v ≤ ∣ tr ( ρ A v ) ∣ s_v \le\lvert\operatorname{tr}(\rho A_v)\rvert s v ≤ ∣ tr ( ρ A v )∣ for every v v v .
If the set of sharpness vectors admitting a single-orbit parent is convex, it already coincides with C G \mathcal{C}_G C G . Mixing orbit POVMs generated by different seeds then yields no additional sharpness vectors: every compatible vector admits a single-orbit parent.
The ensemble size also admits a general bound in terms of the nullity ν 2 ( G ) \nu_2(G) ν 2 ( G ) , defined in Eq. (3) .
Corollary 2. In a canonical irreducible representation, every s ∈ C G s \in\mathcal{C}_G s ∈ C G admits a parent obtained by mixing N o r b N_{\mathrm{orb}} N orb orbit POVMs with possibly mixed seeds, where
N o r b ≤ min { ∣ V ∣ + 1 , 2 ν 2 ( G ) } . (24) N_{\mathrm{orb}} \le\min\left\{\lvert V\rvert+1,2^{\nu_2(G)}\right\}. \tag*{(24)} N orb ≤ min { ∣ V ∣ + 1 , 2 ν 2 ( G ) } . (24) A single orbit suffices whenever B G B_G B G is nonsingular over F 2 \mathbb{F}_2 F 2 or G G G is an odd cycle.
The bound ∣ V ∣ + 1 \lvert V\rvert+1 ∣ V ∣ + 1 follows from Carathéodory’s theorem applied to R A ⊂ R ∣ V ∣ \mathcal{R}_{\mathcal{A}} \subset\mathbb{R}^{\lvert V\rvert} R A ⊂ R ∣ V ∣ [47 ] . Appendix C proves the nullity bound and gives the corresponding bound on parent outcomes. For odd cycles, an additional symmetry under complex conjugation reduces the bound from two orbits to one. This extends the single-seed construction for K 3 K_3 K 3 in Sec. III 2 to all odd cycles, despite their nonzero binary nullity.
Preparation and measurement uncertainty
The compatibility region also determines how accurately arbitrary jointly measurable binary measurements can approximate the sharp Pauli measurements. We show that noisy Pauli marginals already attain all optimal error tradeoffs, and relate these tradeoffs to preparation uncertainty in ensembles of seed states.
For binary distributions, the total-variation distance is
D T V ( p , q ) : = 1 2 ∑ a = ± 1 ∣ p ( a ) − q ( a ) ∣ = ∣ p ( + 1 ) − q ( + 1 ) ∣ . (25) D_{\mathrm{TV}}(p,q) := \frac{1}{2}\sum_{a=\pm1}\lvert p(a)-q(a)\rvert= \lvert p(+1)-q(+1)\rvert. \tag*{(25)} D TV ( p , q ) := 2 1 a = ± 1 ∑ ∣ p ( a ) − q ( a )∣ = ∣ p ( + 1 ) − q ( + 1 )∣ . (25)
We measure the error of a binary POVM F v F_v F v by the largest distance between its outcome distribution and that of the sharp measurement, over all input states [48 , 49 ] [14]:
e ( F v , A v ) : = sup ξ ∣ tr ( ξ ( F v ( + 1 ) − M v 1 ( + 1 ) ) ) ∣ = ∥ F v ( + 1 ) − M v 1 ( + 1 ) ∥ ∞ . (26) e(F_v,A_v) := \sup_{\xi}\left\lvert\operatorname{tr}\left(\xi(F_v(+1)-M_v^1(+1))\right)\right\rvert
= \left\lVert F_v(+1)-M_v^1(+1)\right\rVert_\infty. \tag*{(26)} e ( F v , A v ) := ξ sup tr ( ξ ( F v ( + 1 ) − M v 1 ( + 1 )) ) = F v ( + 1 ) − M v 1 ( + 1 ) ∞ . (26)
Here, M v 1 M_v^1 M v 1 is the POVM in Eq. (1) with s v = 1 s_v=1 s v = 1 . This compares outcome statistics, not the disturbance caused by performing a measurement. For the noisy Pauli marginals,
e ( M v s v , A v ) = 1 2 ( 1 − s v ) . (27) e(M_v^{s_v},A_v)=\frac{1}{2}(1-s_v). \tag*{(27)} e ( M v s v , A v ) = 2 1 ( 1 − s v ) . (27)
Preparation uncertainty concerns a different task: predicting an outcome when the state is known [50 ] [13]. For a state ρ \rho ρ , choosing the more probable sign minimises the probability of an incorrect prediction, giving
u v ( ρ ) : = 1 2 ( 1 − c v ( ρ ) ) , c v ( ρ ) = ∣ tr ( ρ A v ) ∣ . (28) u_v(\rho):=\frac{1}{2}(1-c_v(\rho)),\qquad c_v(\rho)=\lvert\operatorname{tr}(\rho A_v)\rvert. \tag*{(28)} u v ( ρ ) := 2 1 ( 1 − c v ( ρ )) , c v ( ρ ) = ∣ tr ( ρ A v )∣ . (28)
We write u ( ρ ) = ( u v ( ρ ) ) v ∈ V u(\rho)=(u_v(\rho))_{v\in V} u ( ρ ) = ( u v ( ρ ) ) v ∈ V . The following result expresses the attainable measurement-error bounds in terms of both C G \mathcal{C}_G C G and averages of these prediction errors.
Corollary 3. Let A = { A v } v ∈ V \mathcal{A}=\{A_v\}_{v\in V} A = { A v } v ∈ V be a finite Pauli family with anti-commutativity graph G G G , and let ϵ ∈ [ 0 , 1 / 2 ] V \epsilon\in[0,1/2]^V ϵ ∈ [ 0 , 1/2 ] V . There exist jointly measurable binary POVMs { F v } v ∈ V \{F_v\}_{v\in V} { F v } v ∈ V with e ( F v , A v ) ≤ ϵ v e(F_v,A_v)\le\epsilon_v e ( F v , A v ) ≤ ϵ v for every v v v if and only if ( 1 − 2 ϵ v ) v ∈ V ∈ C G (1-2\epsilon_v)_{v\in V}\in\mathcal{C}_G ( 1 − 2 ϵ v ) v ∈ V ∈ C G . Equivalently, there is a finite ensemble of states { ρ j , p j } \{\rho_j,p_j\} { ρ j , p j } such that
ϵ ≥ ∑ j p j u ( ρ j ) (29) \epsilon\ge\sum_j p_j u(\rho_j) \tag*{(29)} ϵ ≥ j ∑ p j u ( ρ j ) (29) componentwise. Whenever these conditions hold, the approximations can be chosen as F v = M v 1 − 2 ϵ v F_v=M_v^{1-2\epsilon_v} F v = M v 1 − 2 ϵ v .
Proof. Let E ( a ) E(a) E ( a ) , with a ∈ { + 1 } V a\in\{+1\}^V a ∈ { + 1 } V , be a joint POVM for the approximations. For its nonzero effects, set p a = tr ( E ( a ) ) / d p_a=\operatorname{tr}(E(a))/d p a = tr ( E ( a )) / d and ρ a = E ( a ) / tr ( E ( a ) ) \rho_a=E(a)/\operatorname{tr}(E(a)) ρ a = E ( a ) / tr ( E ( a )) , where d = dim H d=\dim\mathcal{H} d = dim H , and write B v : = F v ( + 1 ) − F v ( − 1 ) = ∑ a a v E ( a ) B_v:=F_v(+1)-F_v(-1)=\sum_a a_vE(a) B v := F v ( + 1 ) − F v ( − 1 ) = ∑ a a v E ( a ) . Then
∑ a p a u v ( ρ a ) ≤ 1 2 d tr ( A v ( A v − B v ) ) ≤ 1 2 ∥ A v − B v ∥ ∞ = e ( F v , A v ) ≤ ϵ v . (30) \begin{aligned}
\sum_a p_a u_v(\rho_a)\le\frac{1}{2d}\operatorname{tr}\left(A_v(A_v-B_v)\right) \\
&\le\frac{1}{2}\lVert A_v-B_v\rVert_\infty=e(F_v,A_v)\le\epsilon_v. \tag*{(30)}
\end{aligned} a ∑ p a u v ( ρ a ) ≤ 2 d 1 tr ( A v ( A v − B v ) ) ≤ 2 1 ∥ A v − B v ∥ ∞ = e ( F v , A v ) ≤ ϵ v . (30)
The first inequality uses a v tr ( ρ a A v ) ≤ ∣ tr ( ρ a A v ) ∣ a_v\operatorname{tr}(\rho_a A_v) \leq\lvert\operatorname{tr}(\rho_a A_v)\rvert a v tr ( ρ a A v ) ≤ ∣ tr ( ρ a A v )∣ and A v 2 = 1 A_v^2 = 1 A v 2 = 1 ; the second uses ∥ A v ∥ 1 = d \lVert A_v\rVert_1 = d ∥ A v ∥ 1 = d . Thus the ensemble condition is necessary.
Conversely, since c v ( ρ ) = 1 − 2 u v ( ρ ) c_v(\rho) = 1 - 2u_v(\rho) c v ( ρ ) = 1 − 2 u v ( ρ ) , the ensemble condition is equivalent to 1 − 2 ϵ v ≤ ∑ j p j c v ( ρ j ) 1 - 2\epsilon_v \leq\sum_j p_j c_v(\rho_j) 1 − 2 ϵ v ≤ ∑ j p j c v ( ρ j ) for every v v v . By Theorem 1, this is the condition ( 1 − 2 ϵ v ) v ∈ V ∈ C G (1 - 2\epsilon_v)_{v\in V} \in\mathcal{C}_{\mathcal{G}} ( 1 − 2 ϵ v ) v ∈ V ∈ C G . The noisy Pauli marginals M v 1 − 2 ϵ v M_v^{1-2\epsilon_v} M v 1 − 2 ϵ v then attain the prescribed errors by Eq. (27) .
Thus allowing biased or otherwise more general binary approximations does not improve the error tradeoffs. The connection to preparation uncertainty is also constructive: a seed ρ \rho ρ generates a parent with marginals satisfying
e ( M v c v ( ρ ) , A v ) = u v ( ρ ) , v ∈ V . (31) e(M_v^{c_v(\rho)}, A_v) = u_v(\rho), \qquad v \in V. \tag*{(31)} e ( M v c v ( ρ ) , A v ) = u v ( ρ ) , v ∈ V . (31)
Here ρ \rho ρ specifies the parent measurement; it is not the unknown input ξ \xi ξ over which the measurement error is maximised. Mixing the seed parents with probabilities p j p_j p j and retaining the seed label gives marginal errors ∑ j p j u v ( ρ j ) \sum_j p_j u_v(\rho_j) ∑ j p j u v ( ρ j ) . On the preparation side, this average assumes that the label j j j is known, so the best prediction is chosen separately for each ρ j \rho_j ρ j , rather than from the averaged state.
Related correspondences are known for covariant position–momentum and number–angle measurements [48 , 51 ] , and for finite Fourier-conjugate pairs [49 , 52 ] . Here the correspondence holds for arbitrary finite Pauli families with total-variation error, allowing ensembles when a single seed does not suffice.
Compatibility under different noise models
The preceding subsection compares approximate measurements through their worst-case statistical error. We now ask a different question: how much of each sharp Pauli measurement can be retained in a compatible mixture when the replacement measurements are restricted to a specified class? For a family A = { A v } v ∈ V \mathcal{A} = \{A_v\}_{v\in V} A = { A v } v ∈ V of nontrivial Pauli observables, consider
F v = t v M v 1 + ( 1 − t v ) N v , t = ( t v ) v ∈ V ∈ [ 0 , 1 ] V , F_v = t_v M_v^1 + (1-t_v)N_v, \qquad t = (t_v)_{v\in V} \in[0,1]^V, F v = t v M v 1 + ( 1 − t v ) N v , t = ( t v ) v ∈ V ∈ [ 0 , 1 ] V ,
where each N v N_v N v is a binary POVM describing the measurement noise. Write F : = { F v } v ∈ V \mathsf{F} := \{F_v\}_{v\in V} F := { F v } v ∈ V and N : = { N v } v ∈ V \mathsf{N} := \{N_v\}_{v\in V} N := { N v } v ∈ V for the resulting measurement family and the noise family, respectively. Different noise models restrict N \mathsf{N} N in different ways. We ask which vectors t t t admit an allowed noise family for which F \mathsf{F} F is jointly measurable.
Depolarising noise takes N v ( b ) = tr ( M v 1 ( b ) ) 1 / d N_v(b) = \operatorname{tr}(M_v^1(b))1/d N v ( b ) = tr ( M v 1 ( b )) 1/ d [52 ] [15], while random noise fixes N v ( b ) = 1 / 2 N_v(b) = 1/2 N v ( b ) = 1/2 [15]. These coincide here because tr ( M v 1 ( b ) ) = d / 2 \operatorname{tr}(M_v^1(b)) = d/2 tr ( M v 1 ( b )) = d /2 , recovering the noisy Pauli measurements considered throughout this work, with t v = s v t_v = s_v t v = s v . Probabilistic noise allows N v ( b ) = q v ( b ) 1 N_v(b) = q_v(b)1 N v ( b ) = q v ( b ) 1 for arbitrary binary probability distributions q v q_v q v [53 ] . Jointly measurable noise requires the noise family N \mathsf{N} N to be jointly measurable [54 ] , whereas generalised noise allows arbitrary binary noise POVMs [55 ] . These are the noise models considered in [36 ] .
The following proposition characterises all five cases in terms of the original compatibility region.
Proposition 2. Let A = { A v } v ∈ V \mathcal{A} = \{A_v\}_{v\in V} A = { A v } v ∈ V be a finite family of nontrivial Pauli observables with anti-commutativity graph G G G , and let t ∈ [ 0 , 1 ] V t \in[0,1]^V t ∈ [ 0 , 1 ] V . There exists a noise family N \mathsf{N} N of the specified type such that the measurements
F v = t v M v 1 + ( 1 − t v ) N v , v ∈ V , F_v = t_v M_v^1 + (1-t_v)N_v, \qquad v \in V, F v = t v M v 1 + ( 1 − t v ) N v , v ∈ V , are jointly measurable if and only if the corresponding condition holds:
For depolarising, random, or probabilistic noise, t ∈ C G t \in\mathcal{C}_{\mathcal{G}} t ∈ C G .
For jointly measurable noise, there exist s , γ ∈ C G s,\gamma\in\mathcal{C}_{\mathcal{G}} s , γ ∈ C G such that t v = s v + ( 1 − t v ) γ v t_v = s_v + (1-t_v)\gamma_v t v = s v + ( 1 − t v ) γ v for every v ∈ V v \in V v ∈ V .
For generalised noise, ( max { 0 , 2 t v − 1 } ) v ∈ V ∈ C G (\max\{0,2t_v-1\})_{v\in V} \in\mathcal{C}_{\mathcal{G}} ( max { 0 , 2 t v − 1 } ) v ∈ V ∈ C G .
In these three cases, the resulting compatible measurements can be chosen, respectively, as F v = M v t v F_v = M_v^{t_v} F v = M v t v , F v = M v s v F_v = M_v^{s_v} F v = M v s v , and F v = M v max { 0 , 2 t v − 1 } F_v = M_v^{\max\{0,2t_v-1\}} F v = M v m a x { 0 , 2 t v − 1 } .
Proof. For any binary measurement family F \mathsf{F} F , define x ( F ) = ( x v ( F ) ) v ∈ V x(\mathsf{F}) = (x_v(\mathsf{F}))_{v\in V} x ( F ) = ( x v ( F ) ) v ∈ V by
x v ( F ) : = 1 d tr ( A v ( F v ( + 1 ) − F v ( − 1 ) ) ) . x_v(\mathsf{F}) := \frac{1}{d}\operatorname{tr}\left(A_v\left(F_v(+1)-F_v(-1)\right)\right). x v ( F ) := d 1 tr ( A v ( F v ( + 1 ) − F v ( − 1 ) ) ) .
If F \mathsf{F} F is jointly measurable, normalising the nonzero effects of a parent gives an ensemble { p α , ρ α } \{p_\alpha,\rho_\alpha\} { p α , ρ α } with
∣ x v ( F ) ∣ ≤ ∑ α p α ∣ tr ( ρ α A v ) ∣ . \lvert x_v(\mathsf{F})\rvert\leq\sum_\alpha p_\alpha\lvert\operatorname{tr}(\rho_\alpha A_v)\rvert. ∣ x v ( F )∣ ≤ α ∑ p α ∣ tr ( ρ α A v )∣ .
The state-space characterisation therefore implies ∣ x ( F ) ∣ ∈ C G \lvert x(\mathsf{F})\rvert\in\mathcal{C}_{\mathcal{G}} ∣ x ( F )∣ ∈ C G , where the absolute value is taken componentwise.
For the mixture, x v ( F ) = t v + ( 1 − t v ) x v ( N ) x_v(\mathsf{F}) = t_v + (1-t_v)x_v(\mathsf{N}) x v ( F ) = t v + ( 1 − t v ) x v ( N ) . In the first three models, the noise effects are proportional to the identity and tr ( A v ) = 0 \operatorname{tr}(A_v)=0 tr ( A v ) = 0 , so x v ( N ) = 0 x_v(\mathsf{N})=0 x v ( N ) = 0 and hence t ∈ C G t\in\mathcal{C}_{\mathcal{G}} t ∈ C G . If N \mathsf{N} N is jointly measurable, then also ∣ x ( N ) ∣ ∈ C G \lvert x(\mathsf{N})\rvert\in\mathcal{C}_{\mathcal{G}} ∣ x ( N )∣ ∈ C G , while
t v ≤ ∣ x v ( F ) ∣ + ( 1 − t v ) ∣ x v ( N ) ∣ . t_v \leq\lvert x_v(\mathsf{F})\rvert+ (1-t_v)\lvert x_v(\mathsf{N})\rvert. t v ≤ ∣ x v ( F )∣ + ( 1 − t v ) ∣ x v ( N )∣ .
Reducing the two vectors componentwise until equality holds gives s , γ ∈ C G s,\gamma\in\mathcal{C}_{\mathcal{G}} s , γ ∈ C G satisfying the stated condition, since decreasing compatible sharpnesses preserves compatibility. For generalised noise, x v ( N ) ≥ − 1 x_v(\mathsf{N}) \geq-1 x v ( N ) ≥ − 1 , so max { 0 , 2 t v − 1 } ≤ ∣ x v ( F ) ∣ \max\{0,2t_v-1\} \leq\lvert x_v(\mathsf{F})\rvert max { 0 , 2 t v − 1 } ≤ ∣ x v ( F )∣ . The same componentwise-decrease property gives the generalised-noise condition.
Conversely, in the first case choose N v ( b ) = 1 / 2 N_v(b)=1/2 N v ( b ) = 1/2 , giving F v = M v t v F_v=M_v^{t_v} F v = M v t v . In the second, choose N v ( b ) = M v γ v ( − b ) N_v(b)=M_v^{\gamma_v}(-b) N v ( b ) = M v γ v ( − b ) . This noise family is jointly measurable, since swapping outcome labels preserves compatibility, and the mixture gives F v = M v s F_v=M_v^{s} F v = M v s . For generalised noise, choose
N v ( b ) = { M v 1 ( − b ) , t v ≥ 1 / 2 , M v t v / ( 1 − t v ) ( − b ) , t v < 1 / 2. N_v(b)=
\begin{cases}
M_v^{1}(-b), & t_v\ge1/2,\\
M_v^{t_v/(1-t_v)}(-b), & t_v<1/2.
\end{cases} N v ( b ) = { M v 1 ( − b ) , M v t v / ( 1 − t v ) ( − b ) , t v ≥ 1/2 , t v < 1/2.
Both choices are valid binary POVMs and give F v = M v max { 0 , 2 t v − 1 } F_v=M_v^{\max\{0,2t_v-1\}} F v = M v m a x { 0 , 2 t v − 1 } , completing the proof.
In the jointly measurable-noise case, s s s gives the sharpnesses of the resulting compatible measurements, while γ \gamma γ specifies the noise family N v ( b ) = M v γ v ( − b ) N_v(b)=M_v^{\gamma_v}(-b) N v ( b ) = M v γ v ( − b ) . These two compatible families need not have the same parent.
Thus the compatibility regions for all five models are determined entirely by C G \mathcal{C}_G C G and depend only on the anti-commutativity graph, not on the particular Pauli realisation.
The usual robustness thresholds are obtained by requiring t v = τ t_v=\tau t v = τ for every v v v and maximising τ ∈ [ 0 , 1 ] \tau\in[0,1] τ ∈ [ 0 , 1 ] . Following the notation of [36 ] , we denote them by η d ( A ) \eta^{\mathrm d}(\mathcal{A}) η d ( A ) , η r ( A ) \eta^{\mathrm r}(\mathcal{A}) η r ( A ) , η p ( A ) \eta^{\mathrm p}(\mathcal{A}) η p ( A ) , η j m ( A ) \eta^{\mathrm{jm}}(\mathcal{A}) η jm ( A ) , and η g ( A ) \eta^{\mathrm g}(\mathcal{A}) η g ( A ) for the five models listed above.
Corollary 4. For a finite family A \mathcal{A} A of nontrivial Pauli observables with anti-commutativity graph G G G ,
η d ( A ) = η r ( A ) = η p ( A ) = η ( G ) , \eta^{\mathrm d}(\mathcal{A})=\eta^{\mathrm r}(\mathcal{A})=\eta^{\mathrm p}(\mathcal{A})=\eta(G), η d ( A ) = η r ( A ) = η p ( A ) = η ( G ) ,
η j m ( A ) = 2 η ( G ) 1 + η ( G ) , η g ( A ) = 1 + η ( G ) 2 . \eta^{\mathrm{jm}}(\mathcal{A})=\frac{2\eta(G)}{1+\eta(G)},\qquad
\eta^{\mathrm g}(\mathcal{A})=\frac{1+\eta(G)}{2}. η jm ( A ) = 1 + η ( G ) 2 η ( G ) , η g ( A ) = 2 1 + η ( G ) .
Any parent realising { M v η ( G ) } v ∈ V \{M_v^{\eta(G)}\}_{v\in V} { M v η ( G ) } v ∈ V attains all five optima.
Proof. Write η = η ( G ) \eta=\eta(G) η = η ( G ) . The first three identities and the generalised-robustness formula follow directly from Proposition 2. For jointly measurable noise, its condition becomes τ 1 = s + ( 1 − τ ) γ \tau\mathbf{1}=s+(1-\tau)\gamma τ 1 = s + ( 1 − τ ) γ . Convexity gives
τ 2 − τ 1 = s 2 − τ + 1 − τ 2 − τ γ ∈ C G . \frac{\tau}{2-\tau}\mathbf{1}
=
\frac{s}{2-\tau}+\frac{1-\tau}{2-\tau}\gamma
\in\mathcal{C}_G. 2 − τ τ 1 = 2 − τ s + 2 − τ 1 − τ γ ∈ C G .
Thus τ / ( 2 − τ ) ≤ η \tau/(2-\tau)\le\eta τ / ( 2 − τ ) ≤ η , or τ ≤ 2 η / ( 1 + η ) \tau\le2\eta/(1+\eta) τ ≤ 2 η / ( 1 + η ) . Equality is attained by taking s = γ = η 1 s=\gamma=\eta\mathbf{1} s = γ = η 1 . At the respective optimal values of τ \tau τ , the constructions in the proposition all give the same compatible family { M v η } v ∈ V \{M_v^{\eta}\}_{v\in V} { M v η } v ∈ V .
All five thresholds therefore give the same ordering of sharp Pauli families by incompatibility. For the single-qubit Pauli family { X , Y , Z } \{X,Y,Z\} { X , Y , Z } , the tetrahedral parent of Sec. III 2 attains all five uniform robustness thresholds.
Optimal tradeoffs and parent measurements
Since C G \mathcal{C}_G C G also determines the tradeoffs for the noise models in Sec. III 5, we now focus on computing this sharpness region and constructing parents at its boundary. The key object is the support function, which records the largest attainable weighted sum of sharpnesses. For a compact convex region, these weighted optima determine the region itself. We show that, for Pauli families, they can be computed from the spectra of signed Pauli Hamiltonians, whose ground states provide seeds for optimal parent measurements. Finally, we use graph symmetry to obtain parents with optimal uniform sharpness.
Support functions and signed Pauli Hamiltonians
The support function records the best weighted sharpness attainable by a parent measurement. Assign nonnegative weights w v w_v w v to the observables, with ∑ v w v = 1 \sum_v w_v=1 ∑ v w v = 1 , and let Δ ( V ) \Delta(V) Δ ( V ) denote the simplex of these weight vectors. The support function of C G \mathcal{C}_G C G , restricted to weights w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) , is
h G ( w ) : = max s ∈ C G w ⋅ s . (32) h_G(w):=\max_{s\in\mathcal{C}_G}w\cdot s. \tag*{(32)} h G ( w ) := s ∈ C G max w ⋅ s . (32)
Different weights select different tradeoffs: increasing w v w_v w v gives more importance to the sharpness of observable A v A_v A v . Equivalently, since the marginal measurement error is ( 1 − s v ) / 2 (1-s_v)/2 ( 1 − s v ) /2 , the minimum weighted sum of these errors is ( 1 − h G ( w ) ) / 2 (1-h_G(w))/2 ( 1 − h G ( w )) /2 .
For each w w w , the hyperplane w ⋅ s = h G ( w ) w\cdot s=h_G(w) w ⋅ s = h G ( w ) supports C G \mathcal{C}_G C G , with normal direction w w w . The separating-hyperplane theorem implies that support bounds over all directions determine a compact convex region [56 ] . It is enough to consider nonnegative coefficients. When a coefficient is negative, setting the corresponding sharpness to zero cannot decrease the objective and preserves compatibility. Replacing the negative coefficients by zero therefore leaves the maximum unchanged. The resulting inequality is at least as restrictive for any nonnegative vector s s s . Normalising the coefficients then gives
C G = { s ∈ [ 0 , 1 ] V : w ⋅ s ≤ h G ( w ) ∀ w ∈ Δ ( V ) } . (33) \mathcal{C}_G=\left\{s\in[0,1]^V:w\cdot s\le h_G(w)\ \ \forall w\in\Delta(V)\right\}. \tag*{(33)} C G = { s ∈ [ 0 , 1 ] V : w ⋅ s ≤ h G ( w ) ∀ w ∈ Δ ( V ) } . (33)
Thus the support bounds give necessary and sufficient conditions for joint measurability, including nonuniform tradeoffs: a vector s s s is incompatible if and only if w ⋅ s > h G ( w ) w\cdot s>h_G(w) w ⋅ s > h G ( w ) for some w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) .
It remains to calculate these support values. For a Pauli family, this reduces to the spectra of the signed Pauli Hamiltonians
H w , a : = ∑ v ∈ V w v a v A v , a ∈ { ± 1 } V . (34) H_{w,a}:=\sum_{v\in V}w_va_vA_v,\qquad a\in\{\pm1\}^{V}. \tag*{(34)} H w , a := v ∈ V ∑ w v a v A v , a ∈ { ± 1 } V . (34)
The state-space characterisation expresses these support values in terms of the largest eigenvalues of signed Pauli Hamiltonians and identifies pure seed states that attain them.
Proposition 3. For every w ∈ Δ ( V ) w \in\Delta(V) w ∈ Δ ( V ) ,
h G ( w ) = max ρ ∑ v ∈ V w v ∣ tr ( ρ A v ) ∣ = max a ∈ { ± 1 } V λ max ( H w , a ) = − min a ∈ { ± 1 } V λ min ( H w , a ) . (35) \begin{aligned}
h_G(w) &= \max_{\rho} \sum_{v\in V} w_v \left|\operatorname{tr}(\rho A_v)\right| \\
&= \max_{a\in\{\pm1\}^V} \lambda_{\max}(H_{w,a}) \\
&= -\min_{a\in\{\pm1\}^V} \lambda_{\min}(H_{w,a}). \tag*{(35)}
\end{aligned} h G ( w ) = ρ max v ∈ V ∑ w v ∣ tr ( ρ A v ) ∣ = a ∈ { ± 1 } V max λ m a x ( H w , a ) = − a ∈ { ± 1 } V min λ m i n ( H w , a ) . (35) In a canonical representation, each support value is attained by a single orbit POVM with a pure seed.
Proof. By Theorem 1, every compatible vector is bounded componentwise by an average of seed profiles, and every seed profile is itself compatible. Since w ≥ 0 w \ge0 w ≥ 0 , averaging profiles and reducing their coordinates cannot increase the maximum of w ⋅ s w \cdot s w ⋅ s . Hence
h G ( w ) = max ρ ∑ v ∈ V w v ∣ tr ( ρ A v ) ∣ = max ρ max a ∈ { ± 1 } V tr ( ρ H w , a ) = max a ∈ { ± 1 } V λ max ( H w , a ) , \begin{aligned}
h_G(w) &= \max_{\rho} \sum_{v\in V} w_v \left|\operatorname{tr}(\rho A_v)\right| \\
&= \max_{\rho}\max_{a\in\{\pm1\}^V} \operatorname{tr}(\rho H_{w,a}) \\
&= \max_{a\in\{\pm1\}^V} \lambda_{\max}(H_{w,a}),
\end{aligned} h G ( w ) = ρ max v ∈ V ∑ w v ∣ tr ( ρ A v ) ∣ = ρ max a ∈ { ± 1 } V max tr ( ρ H w , a ) = a ∈ { ± 1 } V max λ m a x ( H w , a ) , where in the second line each sign a v a_v a v is chosen to agree with tr ( ρ A v ) \operatorname{tr}(\rho A_v) tr ( ρ A v ) . This proves Eqs. (35) and (35).
If a ⋆ a_\star a ⋆ attains the maximum, any pure eigenstate ρ ⋆ \rho_\star ρ ⋆ corresponding to the largest eigenvalue of H w , a ⋆ H_{w,a_\star} H w , a ⋆ satisfies
∑ v w v ∣ tr ( ρ ⋆ A v ) ∣ = h G ( w ) . \sum_v w_v\left|\operatorname{tr}(\rho_\star A_v)\right|=h_G(w). v ∑ w v ∣ tr ( ρ ⋆ A v ) ∣ = h G ( w ) . Thus its profile attains the support value and, in a canonical representation, its orbit POVM does so as well.
Finally, H w , − a = − H w , a H_{w,-a}=-H_{w,a} H w , − a = − H w , a and both signings are allowed, so max a λ max ( H w , a ) = − min a λ min ( H w , a ) \max_a\lambda_{\max}(H_{w,a})=-\min_a\lambda_{\min}(H_{w,a}) max a λ m a x ( H w , a ) = − min a λ m i n ( H w , a ) , proving Eq. (36).
For each choice of weights, one pure seed suffices to attain the maximum weighted sharpness. However, several sharpness vectors may attain the same maximum, and realising a specified one of them can require a mixture of seeds.
For example, consider A 1 = X A_1=X A 1 = X and A 2 = Z A_2=Z A 2 = Z . Anti-commutation gives
H w , a 2 = ( w 1 2 + w 2 2 ) 1 , h K 2 ( w ) = w 1 2 + w 2 2 . H_{w,a}^2=(w_1^2+w_2^2)\mathbb{1},\qquad h_{K_2}(w)=\sqrt{w_1^2+w_2^2}. H w , a 2 = ( w 1 2 + w 2 2 ) 1 , h K 2 ( w ) = w 1 2 + w 2 2 .
Writing q w = ∥ w ∥ 2 q_w=\lVert w\rVert_2 q w = ∥ w ∥ 2 , the pure seed
ρ w = 1 2 ( 1 + w 1 X + w 2 Z q w ) \rho_w=\frac{1}{2}\left(\mathbb{1}+\frac{w_1X+w_2Z}{q_w}\right) ρ w = 2 1 ( 1 + q w w 1 X + w 2 Z )
is a ground state of − ( w 1 X + w 2 Z ) -(w_1X+w_2Z) − ( w 1 X + w 2 Z ) and has profile s ( w ) = w / q w s(w)=w/q_w s ( w ) = w / q w . Its orbit POVM therefore attains the support bound w ⋅ s ≤ ∥ w ∥ 2 w\cdot s\le\lVert w\rVert_2 w ⋅ s ≤ ∥ w ∥ 2 . Taken over all nonnegative weights, these inequalities describe exactly the quarter unit disk s 1 2 + s 2 2 ≤ 1 s_1^2+s_2^2\le1 s 1 2 + s 2 2 ≤ 1 : one direction follows from Cauchy–Schwarz, and the converse follows by taking w w w proportional to a nonzero candidate s s s . Figure 1 illustrates
Figure 1. The support function describes the compatibility region through its tight linear bounds. For two anti-commuting Pauli observables, h K 2 ( w ) = ∥ w ∥ 2 h_{K_2}(w)=\lVert w\rVert_2 h K 2 ( w ) = ∥ w ∥ 2 , and the supporting line w ⋅ s = h K 2 ( w ) w\cdot s=h_{K_2}(w) w ⋅ s = h K 2 ( w ) touches the region at s ( w ) = w / ∥ w ∥ 2 s(w)=w/\lVert w\rVert_2 s ( w ) = w / ∥ w ∥ 2 . The weights w ( 1 ) = ( 2 / 3 , 1 / 3 ) w^{(1)}=(2/3,1/3) w ( 1 ) = ( 2/3 , 1/3 ) and w ( 2 ) = ( 1 / 3 , 2 / 3 ) w^{(2)}=(1/3,2/3) w ( 2 ) = ( 1/3 , 2/3 ) select the two illustrated tradeoffs, each attained by an orbit parent generated by a pure seed. The arrows show the normal directions. In the nonnegative quadrant, intersecting the half-spaces w ⋅ s ≤ h K 2 ( w ) w\cdot s\le h_{K_2}(w) w ⋅ s ≤ h K 2 ( w ) for all weights recovers exactly the shaded quarter disk.
how the supporting lines select individual tradeoffs while together determining the whole region.
Although Eq. (35) involves 2 ∣ V ∣ 2^{|V|} 2 ∣ V ∣ signings, Pauli conjugation makes many of them spectrally equivalent. Equation (5) gives
U x H w , a U x † = H w , a χ ( x ) , ( a χ ( x ) ) v = a v χ v ( x ) . U_xH_{w,a}U_x^\dagger=H_{w,a\chi(x)},\qquad(a\chi(x))_v=a_v\chi_v(x). U x H w , a U x † = H w , a χ ( x ) , ( a χ ( x ) ) v = a v χ v ( x ) .
The action partitions the signings into 2 ν 2 ( G ) 2^{\nu_2(G)} 2 ν 2 ( G ) equivalence classes, and only one representative from each class is needed; see Appendix C. When B G B_G B G is nonsingular, all signings have the same spectrum and the sign optimisation is unnecessary.
The state optimisation in Eq. (35) is the k = 1 k=1 k = 1 case of the generalised beta number β ( G , w , k ) \beta(G,w,k) β ( G , w , k ) introduced in [57 ] . Thus β ( G , w , 1 ) = h G ( w ) \beta(G,w,1)=h_G(w) β ( G , w , 1 ) = h G ( w ) has a joint measurement interpretation: it is the largest weighted sum of sharpnesses attainable by jointly measurable noisy Pauli observables. Equation (33) further shows that these values characterise the entire compatibility region.
Ground-state parent measurements
For fixed weights, several sharpness vectors may attain the same support value. These vectors form the exposed face
F G ( w ) : = { s ∈ C G : w ⋅ s = h G ( w ) } , F_G(w):=\{s\in\mathcal{C}_G:w\cdot s=h_G(w)\}, F G ( w ) := { s ∈ C G : w ⋅ s = h G ( w )} ,
namely the part of the compatibility region that touches the supporting hyperplane. In the two-observable example, each such face is a single point; in general it may contain a continuum of tradeoffs. Proposition 3 supplies a parent generated by a pure seed attaining one point of F G ( w ) F_G(w) F G ( w ) . We now show that every point of the face can be obtained by mixing ground-state orbit POVMs, with classical post-processing when necessary. The proof is a direct consequence of the state-space characterisation: if an averaged profile attains the support value, then every seed appearing with positive probability must attain it as well.
Theorem 2. Let w ∈ Δ ( V ) w \in\Delta(V) w ∈ Δ ( V ) and s ∈ F G ( w ) s \in F_G(w) s ∈ F G ( w ) . There exist a finite ensemble of pure states ρ j = ∣ ψ j ⟩ ⟨ ψ j ∣ \rho_j = |\psi_j\rangle\langle\psi_j| ρ j = ∣ ψ j ⟩ ⟨ ψ j ∣ , with probabilities p j p_j p j , and signings a ( j ) ∈ { ± 1 } V a^{(j)} \in\{\pm1\}^{V} a ( j ) ∈ { ± 1 } V such that
H w , a ( j ) ∣ ψ j ⟩ = − h G ( w ) ∣ ψ j ⟩ , s ≤ ∑ j p j c A ( ρ j ) . (36) H_{w,a^{(j)}}|\psi_j\rangle=-h_G(w)|\psi_j\rangle,
\qquad
s \le\sum_j p_j c_{\mathcal{A}}(\rho_j). \tag*{(36)} H w , a ( j ) ∣ ψ j ⟩ = − h G ( w ) ∣ ψ j ⟩ , s ≤ j ∑ p j c A ( ρ j ) . (36) Consequently, s s s admits a parent obtained from these pure ground-state seeds by the orbit construction, mixing, and classical output noise when necessary.
Proof. By Theorem 1, refining the seeds into pure states if necessary, choose an ensemble { p j , ρ j } \{p_j,\rho_j\} { p j , ρ j } with p j > 0 p_j>0 p j > 0 such that t : = ∑ j p j c A ( ρ j ) ≥ s t := \sum_j p_j c_{\mathcal{A}}(\rho_j) \ge s t := ∑ j p j c A ( ρ j ) ≥ s . Since s ∈ F G ( w ) s \in F_G(w) s ∈ F G ( w ) , Proposition 3 gives
h G ( w ) = w ⋅ s ≤ ∑ j p j w ⋅ c A ( ρ j ) ≤ ∑ j p j h G ( w ) = h G ( w ) . h_G(w)=w\cdot s\le\sum_j p_j w\cdot c_{\mathcal{A}}(\rho_j)
\le\sum_j p_j h_G(w)=h_G(w). h G ( w ) = w ⋅ s ≤ j ∑ p j w ⋅ c A ( ρ j ) ≤ j ∑ p j h G ( w ) = h G ( w ) .
Hence equality holds throughout. Since every p j > 0 p_j>0 p j > 0 , each seed satisfies w ⋅ c A ( ρ j ) = h G ( w ) w\cdot c_{\mathcal{A}}(\rho_j)=h_G(w) w ⋅ c A ( ρ j ) = h G ( w ) .
For each j j j , choose signs so that a v ( j ) tr ( ρ j A v ) = − ∣ tr ( ρ j A v ) ∣ a_v^{(j)}\operatorname{tr}(\rho_jA_v)=-|\operatorname{tr}(\rho_jA_v)| a v ( j ) tr ( ρ j A v ) = − ∣ tr ( ρ j A v ) ∣ for every v v v , with either sign allowed when the expectation vanishes. Then tr ( ρ j H w , a ( j ) ) = − h G ( w ) \operatorname{tr}(\rho_jH_{w,a^{(j)}})=-h_G(w) tr ( ρ j H w , a ( j ) ) = − h G ( w ) . By Eq. (36), λ min ( H w , a ) ≥ − h G ( w ) \lambda_{\min}(H_{w,a})\ge-h_G(w) λ m i n ( H w , a ) ≥ − h G ( w ) for every signing a a a . Thus each ρ j \rho_j ρ j is a ground state of its corresponding signed Hamiltonian, proving Eq. (36) . The orbit construction of Theorem 1, followed by classical output noise when necessary, gives the stated parent.
The same conclusion can also be seen directly at the parent level. If E ( a ) E(a) E ( a ) is any parent for s ∈ F G ( w ) s\in F_G(w) s ∈ F G ( w ) , then
0 = h G ( w ) − w ⋅ s = 1 d ∑ a tr ( E ( a ) ( h G ( w ) 1 − H w , a ) ) . 0=h_G(w)-w\cdot s=\frac{1}{d}\sum_a\operatorname{tr}\bigl(E(a)(h_G(w)\mathbb{1}-H_{w,a})\bigr). 0 = h G ( w ) − w ⋅ s = d 1 a ∑ tr ( E ( a ) ( h G ( w ) 1 − H w , a ) ) .
Each term is nonnegative, so every nonzero effect E ( a ) E(a) E ( a ) is supported on the h G ( w ) h_G(w) h G ( w ) -eigenspace of H w , a H_{w,a} H w , a . Equivalently, E ( a ) E(a) E ( a ) is supported on the ground-state space of − H w , a -H_{w,a} − H w , a .
In a canonical representation, the ensemble gives the parent in Eq. (15) . Upon observing ( j , x ) (j,x) ( j , x ) , report − a v ( j ) χ v ( x ) -a_v^{(j)}\chi_v(x) − a v ( j ) χ v ( x ) for observable A v A_v A v . Equation (11) then gives sharpness t v = ∑ j p j c v ( ρ j ) t_v=\sum_j p_j c_v(\rho_j) t v = ∑ j p j c v ( ρ j ) . The sign choice also includes observables with w v = 0 w_v=0 w v = 0 , since the parent must reproduce their marginals as well. Since t ≥ s t\ge s t ≥ s and w ⋅ ( t − s ) = 0 w\cdot(t-s)=0 w ⋅ ( t − s ) = 0 , we have t v = s v t_v=s_v t v = s v whenever w v > 0 w_v>0 w v > 0 . Additional output noise is needed only on zero-weight coordinates where t v > s v t_v>s_v t v > s v ; flipping the reported result with probability ( 1 − s v / t v ) / 2 (1-s_v/t_v)/2 ( 1 − s v / t v ) /2 then gives the target.
their marginals as well. Since t ≥ s t\ge s t ≥ s and w ⋅ ( t − s ) = 0 w\cdot(t-s)=0 w ⋅ ( t − s ) = 0 , we have t v = s v t_v=s_v t v = s v whenever w v > 0 w_v>0 w v > 0 . Additional output noise is needed only on zero-weight coordinates where t v > s v t_v>s_v t v > s v ; flipping the reported result with probability ( 1 − s v / t v ) / 2 (1-s_v/t_v)/2 ( 1 − s v / t v ) /2 then gives the target.
To relate this construction to optimal tradeoffs, call a compatible vector s s s maximal if there is no t ∈ C G t\in\mathcal{C}_G t ∈ C G with t ≥ s t\ge s t ≥ s and t ≠ s t\ne s t = s . Their set is the upper, or Pareto, boundary [47 ] ,
∂ C G : = { s ∈ C G : s is maximal } . \partial\mathcal{C}_G:=\{s\in\mathcal{C}_G:s\text{ is maximal}\}. ∂ C G := { s ∈ C G : s is maximal } .
At such a point, no sharpness can be increased without decreasing another or leaving the region. Every maximal point belongs to F G ( w ) F_G(w) F G ( w ) for some w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) , so the theorem covers every optimal tradeoff. Conversely, if all weights are positive, every point of F G ( w ) F_G(w) F G ( w ) is maximal; zero weights can also select nonmaximal points. If the desired sharpness vector s s s is maximal, then the compatible averaged profile t ≥ s t\ge s t ≥ s must equal s s s , so the ground-state construction requires no additional output noise.
Finally, all seed profiles in the proof belong to F G ( w ) F_G(w) F G ( w ) . Carathéodory’s theorem represents the same averaged profile t t t using at most dim F G ( w ) + 1 ≤ ∣ V ∣ \dim F_G(w)+1\le|V| dim F G ( w ) + 1 ≤ ∣ V ∣ pure ground-state seeds, since the face lies in the hyperplane w ⋅ t = h G ( w ) w\cdot t=h_G(w) w ⋅ t = h G ( w ) . If F G ( w ) F_G(w) F G ( w ) consists of a single point, one pure ground-state orbit POVM suffices.
The optimal sharpness tradeoffs also determine those for the other noise models of Sec. III.5. For depolarising, random, and probabilistic noise, the corresponding compatibility region in the variables t t t is exactly C G \mathcal{C}_G C G , while for generalised noise its Pareto boundary is obtained from that of C G \mathcal{C}_G C G by t v = ( 1 + s v ) / 2 t_v=(1+s_v)/2 t v = ( 1 + s v ) /2 . Hence, for w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) ,
h G d ( w ) = h G r ( w ) = h G p ( w ) = h G ( w ) , h_G^{\mathrm d}(w)=h_G^{\mathrm r}(w)=h_G^{\mathrm p}(w)=h_G(w), h G d ( w ) = h G r ( w ) = h G p ( w ) = h G ( w ) ,
and
h G g ( w ) = 1 + h G ( w ) 2 . h_G^{\mathrm g}(w)=\frac{1+h_G(w)}{2}. h G g ( w ) = 2 1 + h G ( w ) .
The same compatible measurements, and therefore the same parent, attain the corresponding optima. For jointly measurable noise one instead has
h G j m ( w ) = max s , γ ∈ C G ∑ v w v s v + γ v 1 + γ v , h_G^{\mathrm{jm}}(w)=\max_{s,\gamma\in\mathcal{C}_G}\sum_v w_v\frac{s_v+\gamma_v}{1+\gamma_v}, h G jm ( w ) = s , γ ∈ C G max v ∑ w v 1 + γ v s v + γ v ,
so an additional optimisation over the compatible noise profile γ \gamma γ is required.
We now determine the optimal uniform sharpness η ( G ) \eta(G) η ( G ) , defined in Eq. (17) . Setting s = η 1 s=\eta\mathbb{1} s = η 1 in a support inequality gives η ≤ h G ( w ) \eta\le h_G(w) η ≤ h G ( w ) , since the weights sum to one. Because these inequalities determine the entire region, the strongest such bound is the exact threshold. Uniform sharpness need not correspond to uniform weights: without vertex transitivity, nonuniform weights can give a tighter bound.
Corollary 5. For a Pauli family A = { A v } v ∈ V \mathcal{A}=\{A_v\}_{v\in V} A = { A v } v ∈ V with anti-commutativity graph G G G , the optimal uniform sharpness is
η ( G ) = min w ∈ Δ ( V ) h G ( w ) (37) \eta(G)=\min_{w\in\Delta(V)}h_G(w) \tag*{(37)} η ( G ) = w ∈ Δ ( V ) min h G ( w ) (37) = min w ∈ Δ ( V ) max a ∈ { ± 1 } V λ max ( H w , a ) . (38) =\min_{w\in\Delta(V)}\max_{a\in\{\pm1\}^{V}}\lambda_{\max}(H_{w,a}). \tag*{(38)} = w ∈ Δ ( V ) min a ∈ { ± 1 } V max λ m a x ( H w , a ) . (38) For every minimiser w ⋆ w_\star w ⋆ , an optimal parent is obtained from a suitable ensemble of pure ground states of signed Hamiltonians H w ⋆ , a H_{w_\star,a} H w ⋆ , a with energy − η ( G ) -\eta(G) − η ( G ) , using the orbit construction and classical output noise when necessary.
Proof. Since w ⋅ 1 = 1 w\cdot\mathbf{1}=1 w ⋅ 1 = 1 , Eq. (33) gives η 1 ∈ C G \eta\mathbf{1}\in\mathcal{C}_G η 1 ∈ C G if and only if η ≤ h G ( w ) \eta\le h_G(w) η ≤ h G ( w ) for every w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) . This proves Eq. (37) , and Proposition 3 gives Eq. (38) . The minimum exists because h G h_G h G is continuous and Δ ( V ) \Delta(V) Δ ( V ) is compact. For any minimiser w ⋆ w_\star w ⋆ , we have w ⋆ ⋅ ( η ( G ) 1 ) = η ( G ) = h G ( w ⋆ ) w_\star\cdot(\eta(G)\mathbf{1})=\eta(G)=h_G(w_\star) w ⋆ ⋅ ( η ( G ) 1 ) = η ( G ) = h G ( w ⋆ ) . Theorem 2 supplies the ground-state ensemble and parent.
For vertex-transitive graphs, symmetry allows us to use equal weights and construct a parent whose marginals all have the same sharpness. Let G = Aut ( G ) \mathfrak{G}=\operatorname{Aut}(G) G = Aut ( G ) be the group of vertex permutations preserving adjacency. In a fixed canonical representation, Appendix D shows that for every seed ρ \rho ρ and π ∈ G \pi\in\mathfrak{G} π ∈ G there is a transformed seed ρ π \rho^\pi ρ π with
c v ( ρ π ) = c π − 1 ( v ) ( ρ ) . c_v(\rho^\pi)=c_{\pi^{-1}(v)}(\rho). c v ( ρ π ) = c π − 1 ( v ) ( ρ ) .
If G G G is vertex-transitive, every vertex can be mapped to every other by an automorphism. Averaging these permuted profiles therefore gives the same value in every coordinate.
Theorem 3. If G G G is vertex-transitive, the uniform weight vector w ˉ = 1 / ∣ V ∣ \bar{w}=1/|V| w ˉ = 1/∣ V ∣ minimises h G h_G h G , and
η ( G ) = 1 ∣ V ∣ max a ∈ { ± 1 } V λ max ( ∑ v ∈ V a v A v ) (39) \eta(G)=\frac{1}{|V|}\max_{a\in\{\pm1\}^{V}}\lambda_{\max}\left(\sum_{v\in V}a_vA_v\right) \tag*{(39)} η ( G ) = ∣ V ∣ 1 a ∈ { ± 1 } V max λ m a x ( v ∈ V ∑ a v A v ) (39) = 1 ∣ V ∣ max ρ ∑ v ∈ V ∣ tr ( ρ A v ) ∣ . =\frac{1}{|V|}\max_{\rho}\sum_{v\in V}|\operatorname{tr}(\rho A_v)|. = ∣ V ∣ 1 ρ max v ∈ V ∑ ∣ tr ( ρ A v ) ∣. In a canonical representation, for any state ρ ⋆ \rho_\star ρ ⋆ attaining the state maximum, an optimal parent is
E ( π , x ) = 1 ∣ G ∣ d G U x ρ π U x † , ( π , x ) ∈ G × K G . (40) \mathsf{E}(\pi,x)=\frac{1}{|\mathfrak{G}|d_G}U_x\rho_\pi U_x^\dagger,\qquad(\pi,x)\in\mathfrak{G}\times K_G. \tag*{(40)} E ( π , x ) = ∣ G ∣ d G 1 U x ρ π U x † , ( π , x ) ∈ G × K G . (40) Proof. Let m = ∣ V ∣ m=|V| m = ∣ V ∣ , w ˉ = 1 / m \bar{w}=1/m w ˉ = 1/ m , and b = h G ( w ˉ ) b=h_G(\bar{w}) b = h G ( w ˉ ) . The support bound gives η ( G ) ≤ b \eta(G)\le b η ( G ) ≤ b . Choose a state ρ ⋆ \rho_\star ρ ⋆ attaining b = m − 1 ∑ v c v ( ρ ⋆ ) b=m^{-1}\sum_v c_v(\rho_\star) b = m − 1 ∑ v c v ( ρ ⋆ ) . Vertex transitivity implies
1 ∣ G ∣ ∑ π ∈ G c v ( ρ ⋆ π ) = 1 m ∑ u c u ( ρ ⋆ ) = b for every v . \frac{1}{|\mathfrak{G}|}\sum_{\pi\in\mathfrak{G}}c_v(\rho_\star^\pi)=\frac{1}{m}\sum_u c_u(\rho_\star)=b\qquad\text{for every }v. ∣ G ∣ 1 π ∈ G ∑ c v ( ρ ⋆ π ) = m 1 u ∑ c u ( ρ ⋆ ) = b for every v . Mixing the orbit POVMs of the transformed seeds uniformly over G \mathfrak{G} G gives Eq. (40) . For outcome ( π , x ) (\pi,x) ( π , x ) , report α π , v χ v ( x ) \alpha_{\pi,v}\chi_v(x) α π , v χ v ( x ) , where α π , v tr ( ρ ⋆ π A v ) = ∣ tr ( ρ ⋆ π A v ) ∣ \alpha_{\pi,v}\operatorname{tr}(\rho_\star^\pi A_v)=|\operatorname{tr}(\rho_\star^\pi A_v)| α π , v tr ( ρ ⋆ π A v ) = ∣ tr ( ρ ⋆ π A v ) ∣ , with either sign allowed at zero. The resulting marginals all have sharpness b b b , so η ( G ) ≥ b \eta(G)\ge b η ( G ) ≥ b . Thus η ( G ) = h G ( w ˉ ) \eta(G)=h_G(\bar{w}) η ( G ) = h G ( w ˉ ) ; Corollary 5 shows that uniform weights minimise h G h_G h G , and Proposition 3 gives Eq. (39) .
Mixing the orbit POVMs of the transformed seeds uniformly over G \mathfrak{G} G gives Eq. (40) . For outcome ( π , x ) (\pi,x) ( π , x ) , report α π , v χ v ( x ) \alpha_{\pi,v}\chi_v(x) α π , v χ v ( x ) , where α π , v tr ( ρ ⋆ π A v ) = ∣ tr ( ρ ⋆ π A v ) ∣ \alpha_{\pi,v}\operatorname{tr}(\rho_\star^\pi A_v)=|\operatorname{tr}(\rho_\star^\pi A_v)| α π , v tr ( ρ ⋆ π A v ) = ∣ tr ( ρ ⋆ π A v ) ∣ , with either sign allowed at zero. The resulting marginals all have sharpness b b b , so η ( G ) ≥ b \eta(G)\ge b η ( G ) ≥ b . Thus η ( G ) = h G ( w ˉ ) \eta(G)=h_G(\bar{w}) η ( G ) = h G ( w ˉ ) ; Corollary 5 shows that uniform weights minimise h G h_G h G , and Proposition 3 gives Eq. (39) .
The averaged profile has equal components, although the individual seed profiles need not. The permutation label must remain part of the measurement outcome because the binary outputs assigned to the observables can depend on it. Averaging the density operators before constructing the orbit POVM need not give the same sharpnesses: expectation values of opposite signs can cancel.
A seed is balanced when its absolute expectation values are equal for all selected observables. If a balanced seed attains the optimal uniform sharpness, its orbit POVM is already optimal, so averaging over graph automorphisms is unnecessary.
Corollary 6. For vertex-transitive G G G , an optimal single-orbit parent at uniform sharpness exists if and only if there is a state ρ ⋆ \rho_\star ρ ⋆ satisfying
∣ tr ( ρ ⋆ A v ) ∣ = η ( G ) , v ∈ V . (41) |\operatorname{tr}(\rho_\star A_v)|=\eta(G),\qquad v\in V. \tag*{(41)} ∣ tr ( ρ ⋆ A v ) ∣ = η ( G ) , v ∈ V . (41) Proof. Such a state generates an optimal parent by the orbit construction. Conversely, a seed whose orbit parent is optimal satisfies C A ( ρ ⋆ ) ≥ η ( G ) 1 \mathcal{C}_{\mathcal{A}}(\rho_\star)\ge\eta(G)\mathbf{1} C A ( ρ ⋆ ) ≥ η ( G ) 1 by Proposition 1, while Eq. (39) gives ∑ v ∈ V ∣ tr ( ρ ⋆ A v ) ∣ ≤ ∣ V ∣ η ( G ) \sum_{v\in V}|\operatorname{tr}(\rho_\star A_v)|\le|V|\eta(G) ∑ v ∈ V ∣ tr ( ρ ⋆ A v ) ∣ ≤ ∣ V ∣ η ( G ) . Every coordinate must therefore equal η ( G ) \eta(G) η ( G ) .
For example, consider a mutually anti-commuting family { A v } v = 1 m \{A_v\}_{v=1}^{m} { A v } v = 1 m , with m ≥ 2 m\ge2 m ≥ 2 , whose graph is K m K_m K m . For every signing a a a , H a = ∑ v = 1 m a v A v H_a=\sum_{v=1}^{m}a_vA_v H a = ∑ v = 1 m a v A v . Anti-commutation gives H a 2 = m 1 H_a^2=m\mathbb{1} H a 2 = m 1 and tr ( H a ) = 0 \operatorname{tr}(H_a)=0 tr ( H a ) = 0 , so its eigenvalues are ± m \pm\sqrt{m} ± m . Theorem 3 therefore yields
η ( K m ) = 1 m , (42) \eta(K_m)=\frac{1}{\sqrt{m}}, \tag*{(42)} η ( K m ) = m 1 , (42)
recovering the known threshold [34].
Every ground-state seed of H a H_a H a is balanced. Indeed, { H a , A v } = 2 a v 1 \{H_a,A_v\}=2a_v\mathbb{1} { H a , A v } = 2 a v 1 , so a state ρ \rho ρ supported on the ground eigenspace satisfies
tr ( ρ A v ) = − tr ( ρ { H a , A v } ) 2 m = − a v m . \operatorname{tr}(\rho A_v)=-\frac{\operatorname{tr}(\rho\{H_a,A_v\})}{2\sqrt{m}}=-\frac{a_v}{\sqrt{m}}. tr ( ρ A v ) = − 2 m tr ( ρ { H a , A v }) = − m a v .
Thus C A ( ρ ) = 1 / m \mathcal{C}_{\mathcal{A}}(\rho)=1/\sqrt{m} C A ( ρ ) = 1/ m , and its orbit POVM attains the optimal uniform sharpness without mixing seed orbits, even when the ground eigenspace is degenerate.
Magic as a resource for joint measurements
The stabilizer compatibility region
We now ask how restricting the seeds in Theorem 1 to stabilizer mixtures limits the attainable sharpnesses. We take convex mixtures of pure stabilizer states as the resource-free states; states outside this convex hull are nonstabilizer, or magic , states [26, 27]. We call a parent a stabilizer parent if every nonzero effect E ( a ) E(a) E ( a ) has E ( a ) / tr ( E ( a ) ) E(a)/\operatorname{tr}(E(a)) E ( a ) / tr ( E ( a )) in the convex hull of pure stabilizer states. We denote by C G s t a b \mathcal{C}^{\mathrm{stab}}_{G} C G stab the set of sharpness vectors s ∈ [ 0 , 1 ] V s \in[0,1]^{V} s ∈ [ 0 , 1 ] V for which { M v s v } v ∈ V \{M^{s_v}_v\}_{v\in V} { M v s v } v ∈ V admits such a parent.
For a pure stabilizer state σ \sigma σ , every Pauli expectation is 0 0 0 or ± 1 \pm1 ± 1 , and the observables with nonzero expectation mutually commute. Thus I σ : = { v ∈ V : ∣ tr ( σ A v ) ∣ = 1 } I_\sigma:= \{v \in V : |\operatorname{tr}(\sigma A_v)| = 1\} I σ := { v ∈ V : ∣ tr ( σ A v ) ∣ = 1 } is an independent set of G G G , and
c A ( σ ) = 1 I σ . (43) c_{\mathcal{A}}(\sigma)=\mathbf{1}_{I_\sigma}. \tag*{(43)} c A ( σ ) = 1 I σ . (43)
where 1 I \mathbf{1}_I 1 I denotes the incidence vector of I I I . The orbit POVM generated by σ \sigma σ is a stabilizer parent, since its normalised effects are Pauli conjugates of σ \sigma σ . Mixing these parents gives convex combinations of their profiles, which therefore lie in the stable-set polytope [58 ] ,
STAB ( G ) : = conv { 1 I : I ∈ I ( G ) } . (44) \operatorname{STAB}(G):=\operatorname{conv}\{\mathbf{1}_I:I\in\mathcal{I}(G)\}. \tag*{(44)} STAB ( G ) := conv { 1 I : I ∈ I ( G )} . (44)
where I ( G ) \mathcal{I}(G) I ( G ) is the family of independent sets of G G G . Here “stable set” is another name for “independent set”; STAB ( G ) \operatorname{STAB}(G) STAB ( G ) denotes a graph polytope, not a set of stabilizer states.
The following theorem shows that every point of STAB ( G ) \operatorname{STAB}(G) STAB ( G ) is attainable and that no stabilizer parent, whether or not it is constructed from seed orbits, can achieve sharpnesses outside this region.
Theorem 4. For every Pauli family with anti-commutativity graph G G G ,
C G s t a b = STAB ( G ) . (45) \mathcal{C}^{\mathrm{stab}}_{G}=\operatorname{STAB}(G). \tag*{(45)} C G stab = STAB ( G ) . (45) Moreover, if s ∈ C G ∖ STAB ( G ) s \in\mathcal{C}_{G}\setminus\operatorname{STAB}(G) s ∈ C G ∖ STAB ( G ) , then every parent realising s s s has a nonzero effect E ( a ) E(a) E ( a ) for which E ( a ) / tr ( E ( a ) ) E(a)/\operatorname{tr}(E(a)) E ( a ) / tr ( E ( a )) is a nonstabilizer state.
Proof. Suppose s s s is realised by a stabilizer parent. Normalising its effects as in Eq. (7) , the parent-to-state bound Eq. (8) , the triangle inequality, and Eq. (43) give
s ≤ ∑ α p α c A ( ρ α ) ≤ ∑ I q I 1 I s \leq\sum_{\alpha}p_\alpha c_{\mathcal{A}}(\rho_\alpha)\leq\sum_I q_I\mathbf{1}_I s ≤ α ∑ p α c A ( ρ α ) ≤ I ∑ q I 1 I
for some probability distribution { q I } \{q_I\} { q I } over independent sets, obtained by decomposing the ρ α \rho_\alpha ρ α into pure stabilizer states. Since STAB ( G ) \operatorname{STAB}(G) STAB ( G ) is closed under coordinatewise decrease in the nonnegative orthant, s ∈ STAB ( G ) s\in\operatorname{STAB}(G) s ∈ STAB ( G ) .
Conversely, for any independent set I I I , the commuting Pauli observables { A v : v ∈ I } \{A_v:v\in I\} { A v : v ∈ I } admit a common stabilizer eigenbasis. Every nonzero joint spectral projector, divided by its trace, is therefore a convex mixture of pure stabilizer states. This sharp joint measurement, with uniformly random outputs for v ∉ I v\notin I v ∈ / I , is a stabilizer parent with sharpness vector 1 I \mathbf{1}_I 1 I . Mixing these parents gives every point of STAB ( G ) \operatorname{STAB}(G) STAB ( G ) , proving the region equality. The final assertion follows immediately. □
The theorem has a direct operational interpretation. Every s ∈ STAB ( G ) s\in\operatorname{STAB}(G) s ∈ STAB ( G ) can be written as s = ∑ I p I 1 I s=\sum_I p_I\mathbf{1}_I s = ∑ I p I 1 I , where p I ≥ 0 p_I\geq0 p I ≥ 0 and ∑ I p I = 1 \sum_Ip_I=1 ∑ I p I = 1 . To realise s s s , choose the commuting subset I I I with probability p I p_I p I , jointly measure its observables sharply, and assign uniformly random outputs to the remaining observables. The sharpness of observable v v v is then ∑ I ∋ v p I = s v \sum_{I\ni v}p_I=s_v ∑ I ∋ v p I = s v . Thus classical randomisation over commuting-subset measurements attains every sharpness vector achievable by a stabilizer parent.
The optimal uniform sharpness for stabilizer parents is governed by the fractional chromatic number,
χ f ( G ) = min { w I } I ∈ I ( G ) { ∑ I ∈ I ( G ) w I : w I ≥ 0 , ∑ I ∋ v w I ≥ 1 ∀ v ∈ V } . (46) \chi_f(G)=\min_{\{w_I\}_{I\in\mathcal{I}(G)}}\left\{\sum_{I\in\mathcal{I}(G)}w_I:w_I\geq0,\ \sum_{I\ni v}w_I\geq1\ \ \forall v\in V\right\}. \tag*{(46)} χ f ( G ) = { w I } I ∈ I ( G ) min ⎩ ⎨ ⎧ I ∈ I ( G ) ∑ w I : w I ≥ 0 , I ∋ v ∑ w I ≥ 1 ∀ v ∈ V ⎭ ⎬ ⎫ . (46)
Define
η s t a b ( G ) : = max { η ∈ [ 0 , 1 ] : η 1 ∈ C G s t a b } . \eta_{\mathrm{stab}}(G):=\max\{\eta\in[0,1]:\eta\mathbf{1}\in\mathcal{C}^{\mathrm{stab}}_G\}. η stab ( G ) := max { η ∈ [ 0 , 1 ] : η 1 ∈ C G stab } .
Corollary 7. For every Pauli family with anti-commutativity graph G G G ,
η s t a b ( G ) = 1 χ f ( G ) . (47) \eta_{\mathrm{stab}}(G)=\frac{1}{\chi_f(G)}. \tag*{(47)} η stab ( G ) = χ f ( G ) 1 . (47)
Proof. By Theorem 4 and the possibility of reducing excess sharpness by classical noise, η 1 ∈ C G s t a b \eta\mathbf{1}\in\mathcal{C}^{\mathrm{stab}}_G η 1 ∈ C G stab if and only if there are probabilities p I p_I p I with ∑ I ∋ v p I ≥ η \sum_{I\ni v}p_I\geq\eta ∑ I ∋ v p I ≥ η for every v v v . For η > 0 \eta>0 η > 0 , the weights w I = p I / η w_I=p_I/\eta w I = p I / η form a fractional colouring of total weight 1 / η 1/\eta 1/ η . Hence η ≤ 1 / χ f ( G ) \eta\leq1/\chi_f(G) η ≤ 1/ χ f ( G ) .
Conversely, an optimal fractional colouring { w I } \{w_I\} { w I } gives probabilities p I = w I / χ f ( G ) p_I=w_I/\chi_f(G) p I = w I / χ f ( G ) satisfying ∑ I ∋ v p I ≥ 1 / χ f ( G ) \sum_{I\ni v}p_I\geq1/\chi_f(G) ∑ I ∋ v p I ≥ 1/ χ f ( G ) for every v v v . The same equivalence therefore proves achievability. □
An optimal fractional colouring therefore specifies the probabilities p I = w I / χ f ( G ) p_I=w_I/\chi_f(G) p I = w I / χ f ( G ) in the commuting-subset construction above. Each observable is measured sharply with total probability at least 1 / χ f ( G ) 1/\chi_f(G) 1/ χ f ( G ) ; classical noise removes any excess sharpness to give the optimal uniform value η s t a b ( G ) \eta_{\mathrm{stab}}(G) η stab ( G ) .
The cycle C 5 C_5 C 5 , for example, has five maximum independent sets, each corresponding to a commuting pair of observables; see Figure 2 (a). Choosing one pair uniformly, measuring its observables sharply, and reporting fair random outcomes for the remaining three gives each observable sharpness 2 / 5 2/5 2/5 , since each belongs to two pairs. The resulting sharpness vector is the average of the five incidence vectors in S T A B ( C 5 ) \mathrm{STAB}(C_5) STAB ( C 5 ) . This strategy corresponds to assigning fractional-colouring weight 1 / 2 1/2 1/2 to each pair: every vertex receives total weight one, and normalising the weights gives the sampling probability 1 / 5 1/5 1/5 . Theorem 4 guarantees optimality among all stabilizer parents, since every independent set has at most two vertices and hence ∑ v s v ≤ 2 \sum_v s_v \le2 ∑ v s v ≤ 2 throughout S T A B ( C 5 ) \mathrm{STAB}(C_5) STAB ( C 5 ) . Thus
Figure 2. Stabilizer-restricted and unrestricted joint measurements. (a) Each colour identifies one of the five maximum independent sets of C 5 C_5 C 5 , corresponding to a commuting pair of observables. Every vertex receives two colours of weight 1 / 2 1/2 1/2 , giving total coverage 1 and an optimal fractional colouring of weight χ f ( C 5 ) = 5 / 2 \chi_f(C_5)=5/2 χ f ( C 5 ) = 5/2 . Normalising these weights gives probability 1 / 5 1/5 1/5 for each commuting-pair measurement and uniform sharpness η s t a b ( C 5 ) = 2 / 5 = 1 / χ f ( C 5 ) \eta_{\mathrm{stab}}(C_5)=2/5=1/\chi_f(C_5) η stab ( C 5 ) = 2/5 = 1/ χ f ( C 5 ) . (b) For two anti-commuting Paulis X X X and Z Z Z , stabilizer parents fill the triangle S T A B ( K 2 ) \mathrm{STAB}(K_2) STAB ( K 2 ) , whereas arbitrary parents fill the quarter-disc C K 2 \mathcal{C}_{K_2} C K 2 . Along the uniform sharpness direction, allowing nonstabilizer effects increases the optimal sharpness from η s t a b = 1 / 2 \eta_{\mathrm{stab}}=1/2 η stab = 1/2 to η = 1 / 2 \eta=1/\sqrt{2} η = 1/ 2 , a factor of 2 \sqrt{2} 2 equal to the reduced robustness of magic of the corresponding optimal seed state.
η s t a b ( C 5 ) = 2 5 , χ f ( C 5 ) = 5 2 . (48) \eta_{\mathrm{stab}}(C_5)=\frac{2}{5},\qquad\chi_f(C_5)=\frac{5}{2}. \tag*{(48)} η stab ( C 5 ) = 5 2 , χ f ( C 5 ) = 2 5 . (48)
By contrast, sampling the three colour classes of a fixed proper 3-colouring uniformly gives sharpness only 1 / 3 1/3 1/3 : randomising over overlapping commuting pairs improves on using a fixed partition into colour classes. The simplest strict separation of arbitrary and stabilizer parents occurs for two anti-commuting observables, such as X X X and Z Z Z :
S T A B ( K 2 ) = { ( s X , s Z ) ≥ 0 : s X + s Z ≤ 1 } , C K 2 = { ( s X , s Z ) ≥ 0 : s X 2 + s Z 2 ≤ 1 } . (49) \mathrm{STAB}(K_2)=\{(s_X,s_Z)\ge0:s_X+s_Z\le1\},\qquad
\mathcal{C}_{K_2}=\{(s_X,s_Z)\ge0:s_X^2+s_Z^2\le1\}. \tag*{(49)} STAB ( K 2 ) = {( s X , s Z ) ≥ 0 : s X + s Z ≤ 1 } , C K 2 = {( s X , s Z ) ≥ 0 : s X 2 + s Z 2 ≤ 1 } . (49)
The stabilizer triangle is strictly contained in the compatibility quarter-disc, as shown in Figure 2 (b), with
η s t a b ( K 2 ) = 1 2 , η ( K 2 ) = 1 2 . \eta_{\mathrm{stab}}(K_2)=\frac{1}{2},\qquad\eta(K_2)=\frac{1}{\sqrt{2}}. η stab ( K 2 ) = 2 1 , η ( K 2 ) = 2 1 .
More generally, if ( u , v ) ∈ E ( G ) (u,v)\in E(G) ( u , v ) ∈ E ( G ) , an optimal parent for this anti-commuting pair, with uniformly random outputs for all other observables, realises s u = s v = 1 / 2 s_u=s_v=1/\sqrt{2} s u = s v = 1/ 2 and s w = 0 s_w=0 s w = 0 for w ≠ u , v w\ne u,v w = u , v . This violates the stable-set inequality s u + s v ≤ 1 s_u+s_v\le1 s u + s v ≤ 1 . Consequently,
C G s t a b = C G ⟺ G is edgeless . \mathcal{C}^{\mathrm{stab}}_G=\mathcal{C}_G\quad\Longleftrightarrow\quad G\text{ is edgeless}. C G stab = C G ⟺ G is edgeless .
We next quantify this separation and determine its correspondence to the reduced robustness of magic.
Maximal sharpness advantage
We now quantify how much unrestricted parents can improve on the stabilizer benchmark. For a fixed choice of weights w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) , Sec. IV gives the unrestricted optimum h G ( w ) h_G(w) h G ( w ) . Since C G s t a b = S T A B ( G ) \mathcal{C}^{\mathrm{stab}}_G=\mathrm{STAB}(G) C G stab = STAB ( G ) , the corresponding stabilizer optimum is
h G s t a b ( w ) : = max s ∈ C G s t a b w ⋅ s = max I ∈ I ( G ) ∑ v ∈ I w v = α ( G , w ) , (50) \begin{aligned}
h^{\mathrm{stab}}_G(w):=\max_{s\in\mathcal{C}^{\mathrm{stab}}_G}w\cdot s \\
&=\max_{I\in\mathcal{I}(G)}\sum_{v\in I}w_v=\alpha(G,w), \tag*{(50)}
\end{aligned} h G stab ( w ) := s ∈ C G stab max w ⋅ s = I ∈ I ( G ) max v ∈ I ∑ w v = α ( G , w ) , (50)
where α ( G , w ) \alpha(G,w) α ( G , w ) is the weighted independence number. A commuting subset of maximum total weight already attains this value; randomising between subsets cannot improve a fixed linear objective. Thus h G ( w ) / h G s t a b ( w ) h_G(w)/h^{\mathrm{stab}}_G(w) h G ( w ) / h G stab ( w ) measures the multiplicative advantage for the same weighted sharpness objective.
There is also a geometric way to compare all tradeoffs at once. Define
Adv ( G ) : = inf { λ ≥ 1 : C G ⊆ λ S T A B ( G ) } . (51) \operatorname{Adv}(G):=\inf\{\lambda\ge1:\mathcal{C}_G\subseteq\lambda\mathrm{STAB}(G)\}. \tag*{(51)} Adv ( G ) := inf { λ ≥ 1 : C G ⊆ λ STAB ( G )} . (51)
This is the smallest factor by which every compatible sharpness vector can be divided to make it attainable by a stabilizer parent. For the profile generated by a particular seed ρ \rho ρ , define similarly
R G ( ρ ) : = min { λ ≥ 1 : c A ( ρ ) λ ∈ STAB ( G ) } . (52) R_G(\rho):=\min\left\{\lambda\geq1:\frac{c_{\mathcal{A}}(\rho)}{\lambda}\in\operatorname{STAB}(G)\right\}. \tag*{(52)} R G ( ρ ) := min { λ ≥ 1 : λ c A ( ρ ) ∈ STAB ( G ) } . (52)
Here R G ( ρ ) = 1 R_G(\rho)=1 R G ( ρ ) = 1 means that the seed’s sharpness profile is already attainable by a stabilizer parent, not necessarily that ρ \rho ρ is a stabilizer mixture.
Proposition 4. For every Pauli family with anti-commutativity graph G G G ,
Adv ( G ) = max ρ R G ( ρ ) = max w ∈ Δ ( V ) h G ( w ) h G s t a b ( w ) . (53) \operatorname{Adv}(G)=\max_{\rho}R_G(\rho)=\max_{w\in\Delta(V)}\frac{h_G(w)}{h_G^{\mathrm{stab}}(w)}. \tag*{(53)} Adv ( G ) = ρ max R G ( ρ ) = w ∈ Δ ( V ) max h G stab ( w ) h G ( w ) . (53)
Proof. By Theorem 1, C G \mathcal{C}_G C G is the downward closure of the convex hull of the profiles c A ( ρ ) c_{\mathcal{A}}(\rho) c A ( ρ ) . Since λ STAB ( G ) \lambda\operatorname{STAB}(G) λ STAB ( G ) is convex and downward closed, it contains C G \mathcal{C}_G C G precisely when it contains every such profile. This proves the first equality. By the support-function characterisation of § 2 , the same containment holds precisely when h G ( w ) ≤ λ h G s t a b ( w ) h_G(w)\leq\lambda h_G^{\mathrm{stab}}(w) h G ( w ) ≤ λ h G stab ( w ) for every w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) . The smallest such λ \lambda λ is the largest support-function ratio.
Thus maximising the sharpness advantage over the weights gives the same result as maximising R G ( ρ ) R_G(\rho) R G ( ρ ) over seed states. In a canonical representation, the orbit POVM of one pure seed attains this maximum, although realising a prescribed compatible sharpness vector may require several seeds. To construct such a seed, choose weights maximising the ratio and a pure ground state of an optimal signed Hamiltonian from Proposition 3. Its orbit parent attains h G ( w ) h_G(w) h G ( w ) for those weights.
The X X X , Z Z Z example in Figure 2 (b) illustrates both comparisons. The seed
ρ ⋆ = 1 2 ( 1 + X + Z 2 ) (54) \rho_\star=\frac{1}{2}\left(\mathbb{1}+\frac{X+Z}{\sqrt{2}}\right) \tag*{(54)} ρ ⋆ = 2 1 ( 1 + 2 X + Z ) (54)
has profile ( 1 , 1 ) / 2 (1,1)/\sqrt{2} ( 1 , 1 ) / 2 , which must be divided by 2 \sqrt{2} 2 to reach the stabilizer triangle s X + s Z ≤ 1 s_X+s_Z\leq1 s X + s Z ≤ 1 . Thus R K 2 ( ρ ⋆ ) = 2 R_{K_2}(\rho_\star)=\sqrt{2} R K 2 ( ρ ⋆ ) = 2 . For equal weights, the unrestricted and stabilizer optima are 1 / 2 1/\sqrt{2} 1/ 2 and 1 / 2 1/2 1/2 , respectively, giving the same ratio.
For general families, the gain at uniform sharpness need not attain Adv ( G ) \operatorname{Adv}(G) Adv ( G ) . Since η ( G ) 1 ∈ C G \eta(G)\mathbf{1}\in\mathcal{C}_G η ( G ) 1 ∈ C G , the definition gives η ( G ) / η s t a b ( G ) ≤ Adv ( G ) \eta(G)/\eta_{\mathrm{stab}}(G)\leq\operatorname{Adv}(G) η ( G ) / η stab ( G ) ≤ Adv ( G ) . The weights may be zero on some observables, so the maximal weighted advantage can be determined by a proper subfamily.
For perfect graphs, the maximal gain is determined by a largest mutually anti-commuting subfamily. Recall that a graph is perfect when every induced subgraph has chromatic number equal to its clique number.
Corollary 8. For a perfect graph G G G with clique number ω ( G ) \omega(G) ω ( G ) ,
Adv ( G ) = ω ( G ) . (55) \operatorname{Adv}(G)=\sqrt{\omega(G)}. \tag*{(55)} Adv ( G ) = ω ( G ) . (55)
Proof. For a perfect graph, STAB ( G ) \operatorname{STAB}(G) STAB ( G ) is described by s ≥ 0 s\geq0 s ≥ 0 together with the clique inequalities ∑ v ∈ Q s v ≤ 1 \sum_{v\in Q}s_v\leq1 ∑ v ∈ Q s v ≤ 1 for every clique Q Q Q of $G [58 ] . Since the observables indexed by Q Q Q mutually anti-commute, ∑ v ∈ Q c v ( ρ ) 2 ≤ 1 \sum_{v\in Q}c_v(\rho)^2\leq1 ∑ v ∈ Q c v ( ρ ) 2 ≤ 1 , and Cauchy–Schwarz gives ∑ v ∈ Q c v ( ρ ) ≤ ∣ Q ∣ ≤ ω ( G ) \sum_{v\in Q}c_v(\rho)\leq\sqrt{|Q|}\leq\sqrt{\omega(G)} ∑ v ∈ Q c v ( ρ ) ≤ ∣ Q ∣ ≤ ω ( G ) . Thus c A ( ρ ) / ω ( G ) c_{\mathcal{A}}(\rho)/\sqrt{\omega(G)} c A ( ρ ) / ω ( G ) satisfies every clique inequality and therefore lies in STAB ( G ) \operatorname{STAB}(G) STAB ( G ) . Hence R G ( ρ ) ≤ ω ( G ) R_G(\rho)\leq\sqrt{\omega(G)} R G ( ρ ) ≤ ω ( G ) for every ρ \rho ρ .
For the reverse inequality, let Q ⋆ Q_\star Q ⋆ be a maximum clique, so ∣ Q ⋆ ∣ = ω ( G ) |Q_\star|=\omega(G) ∣ Q ⋆ ∣ = ω ( G ) . The balanced-seed construction for a mutually anti-commuting family gives a state ρ ⋆ \rho_\star ρ ⋆ with c v ( ρ ⋆ ) = 1 / ω ( G ) c_v(\rho_\star)=1/\sqrt{\omega(G)} c v ( ρ ⋆ ) = 1/ ω ( G ) for every v ∈ Q ⋆ v\in Q_\star v ∈ Q ⋆ (for ω ( G ) = 1 \omega(G)=1 ω ( G ) = 1 , choose an eigenstate of the selected observable). If c A ( ρ ⋆ ) / λ ∈ STAB ( G ) c_{\mathcal{A}}(\rho_\star)/\lambda\in\operatorname{STAB}(G) c A ( ρ ⋆ ) / λ ∈ STAB ( G ) , then the clique inequality for Q ⋆ Q_\star Q ⋆ gives λ ≥ ∑ v ∈ Q ⋆ c v ( ρ ⋆ ) = ω ( G ) \lambda\geq\sum_{v\in Q_\star}c_v(\rho_\star)=\sqrt{\omega(G)} λ ≥ ∑ v ∈ Q ⋆ c v ( ρ ⋆ ) = ω ( G ) . Therefore R G ( ρ ⋆ ) = ω ( G ) R_G(\rho_\star)=\sqrt{\omega(G)} R G ( ρ ⋆ ) = ω ( G ) , and Proposition 4 completes the proof. □ \square □
The four-vertex path P 4 P_4 P 4 , with edges { 1 , 2 } \{1,2\} { 1 , 2 } , { 2 , 3 } \{2,3\} { 2 , 3 } and { 3 , 4 } \{3,4\} { 3 , 4 } , shows that the uniform-sharpness ratio can be strictly smaller than the maximal weighted advantage. Mixing sharp joint measurements of the commuting pairs { A 1 , A 3 } \{A_1,A_3\} { A 1 , A 3 } and { A 2 , A 4 } \{A_2,A_4\} { A 2 , A 4 } with equal probabilities attains uniform sharpness 1 / 2 1/2 1/2 . The stabilizer constraint s 1 + s 2 ≤ 1 s_1+s_2\leq1 s 1 + s 2 ≤ 1 shows that this is optimal, so η s t a b ( P 4 ) = 1 / 2 \eta_{\mathrm{stab}}(P_4)=1/2 η stab ( P 4 ) = 1/2 . We will prove in Proposition 7 that unrestricted parents attain η ( P 4 ) = 2 / 3 \eta(P_4)=2/3 η ( P 4 ) = 2/3 . Since P 4 P_4 P 4 is perfect with clique number two, Corollary 8 gives
η ( P 4 ) η s t a b ( P 4 ) = 4 3 < 2 = Adv ( P 4 ) . \frac{\eta(P_4)}{\eta_{\mathrm{stab}}(P_4)}=\frac{4}{3}<\sqrt{2}=\operatorname{Adv}(P_4). η stab ( P 4 ) η ( P 4 ) = 3 4 < 2 = Adv ( P 4 ) .
The maximal weighted advantage is attained by assigning weight 1 / 2 1/2 1/2 to each endpoint of any one edge and zero weight to the remaining vertices.
Connection to reduced magic
Robustness of magic is the minimum sum of the absolute values of the coefficients in a decomposition of a state into pure stabilizer states, with real coefficients that sum to one and may be negative [59 ] . The reduced robustness applies the same construction to selected Pauli expectations, allowing magic to be certified without full state tomography [37 ] .
Unlike the sharpness advantage R G ( ρ ) R_G(\rho) R G ( ρ ) , reduced robustness retains the signs of the expectation values. Writing b A ( ρ ) = ( tr ( ρ A v ) ) v ∈ V b_{\mathcal{A}}(\rho)=(\operatorname{tr}(\rho A_v))_{v\in V} b A ( ρ ) = ( tr ( ρ A v ) ) v ∈ V , define
RoM A ( ρ ) : = min { ∑ j ∣ q j ∣ : ∑ j q j = 1 , b A ( ρ ) = ∑ j q j b A ( σ j ) } , \operatorname{RoM}_{\mathcal{A}}(\rho):=\min\left\{\sum_j|q_j|:\sum_jq_j=1,\quad b_{\mathcal{A}}(\rho)=\sum_jq_jb_{\mathcal{A}}(\sigma_j)\right\}, RoM A ( ρ ) := min { j ∑ ∣ q j ∣ : j ∑ q j = 1 , b A ( ρ ) = j ∑ q j b A ( σ j ) } ,
where the σ j \sigma_j σ j are pure stabilizer states and q j ∈ R q_j\in\mathbb{R} q j ∈ R . A value of one means that a stabilizer mixture reproduces these expectations. A larger value certifies magic from the selected observables, because negative coefficients are then unavoidable.
Signed expectations can obey constraints absent from the graph. For example, ( Z ⊗ 1 ) ( 1 ⊗ Z ) ( Z ⊗ Z ) = 1 (Z \otimes1)(1 \otimes Z)(Z \otimes Z)=1 ( Z ⊗ 1 ) ( 1 ⊗ Z ) ( Z ⊗ Z ) = 1 constrains the simultaneous eigenvalues of these commuting observables. Following [38 ] , we say that A \mathcal{A} A has no active dependencies if no nonempty mutually commuting subset has product proportional to the identity.
Proposition 5. Let A \mathcal{A} A be a Pauli family with anti-commutativity graph G G G . For every state ρ \rho ρ ,
R G ( ρ ) ≤ RoM A ( ρ ) (56) R_G(\rho) \leq\operatorname{RoM}_{\mathcal{A}}(\rho) \tag*{(56)} R G ( ρ ) ≤ RoM A ( ρ ) (56) Adv ( G ) ≤ max ρ RoM A ( ρ ) (57) \operatorname{Adv}(G) \leq\max_{\rho} \operatorname{RoM}_{\mathcal{A}}(\rho) \tag*{(57)} Adv ( G ) ≤ ρ max RoM A ( ρ ) (57) Both bounds are equalities if A \mathcal{A} A has no active dependencies.
Proof. Any feasible decomposition has total absolute weight t = ∑ j ∣ q j ∣ ≥ 1 t=\sum_j |q_j|\geq1 t = ∑ j ∣ q j ∣ ≥ 1 and satisfies c A ( ρ ) ≤ ∑ j ∣ q j ∣ c A ( σ j ) c_{\mathcal{A}}(\rho)\leq\sum_j |q_j|c_{\mathcal{A}}(\sigma_j) c A ( ρ ) ≤ ∑ j ∣ q j ∣ c A ( σ j ) . Thus c A ( ρ ) / t c_{\mathcal{A}}(\rho)/t c A ( ρ ) / t lies componentwise below a convex combination of stabilizer profiles. This combination belongs to STAB ( G ) \operatorname{STAB}(G) STAB ( G ) , as does c A ( ρ ) / t c_{\mathcal{A}}(\rho)/t c A ( ρ ) / t , since reducing nonnegative coordinates preserves membership. Hence R G ( ρ ) ≤ t R_G(\rho)\leq t R G ( ρ ) ≤ t , and minimising over decompositions proves the first bound. Appendix E proves pointwise equality when A \mathcal{A} A has no active dependencies. The bound and equality for Adv ( G ) \operatorname{Adv}(G) Adv ( G ) then follow from Adv ( G ) = max ρ R G ( ρ ) \operatorname{Adv}(G)=\max_\rho R_G(\rho) Adv ( G ) = max ρ R G ( ρ ) in Proposition 4. □
Thus, in the absence of active dependencies, the reduced robustness of magic equals the smallest factor by which a seed’s sharpness vector must be divided to become attainable by a stabilizer parent. Its maximum, the witness capacity of the selected family [38 ] , then equals the maximal joint measurement advantage. For perfect graphs, Corollary 8 therefore recovers the witness-capacity formula ω ( G ) \sqrt{\omega(G)} ω ( G ) of that reference. The corollary’s measurement-advantage formula itself holds even when active dependencies are present.
Exact results for structured graph families
We now apply the general framework to structured graph families, obtaining exact compatibility characterisations and explicit parent measurements. A quadratic Majorana realisation provides a common description of line graphs, including paths and cycles. We then treat the complete quadratic Majorana and complete Pauli families, for which symmetry gives parents attaining the optimal uniform sharpness and balanced seeds sometimes make a single orbit sufficient.
Line graphs and Gaussian parents
We begin with line graphs, which admit a natural quadratic Majorana realisation. In this representation, the relevant expectation values are encoded directly in a covariance matrix, making Gaussian states particularly convenient seed states. We show that Gaussian seeds are in fact sufficient to generate the entire compatibility region. This provides a common framework for the cycle and path families discussed later.
Let R = ( V , E ) R=(V,E) R = ( V , E ) be a finite simple graph with V = [ N ] : = { 1 , … , N } V=[N]:=\{1,\ldots,N\} V = [ N ] := { 1 , … , N } and E ≠ ∅ E\ne\varnothing E = ∅ . Its vertices will label Majorana operators, while its edges will label the observables to be measured. Let M = 2 ⌊ N / 2 ⌋ M=2\lfloor N/2\rfloor M = 2 ⌊ N /2 ⌋ and choose Hermitian Majorana operators Γ 1 , … , Γ M \Gamma_1,\ldots,\Gamma_M Γ 1 , … , Γ M satisfying { Γ u , Γ v } = 2 δ u v 1 \{\Gamma_u,\Gamma_v\}=2\delta_{uv}1 { Γ u , Γ v } = 2 δ uv 1 [60 ] . We work on the full Fock space of M / 2 M/2 M /2 fermionic modes, including both parity sectors. When N N N is odd, Γ N + 1 \Gamma_{N+1} Γ N + 1 is an auxiliary Majorana unused by the observables.
For each edge e = { u , v } ∈ E e=\{u,v\}\in E e = { u , v } ∈ E , with u < v u<v u < v , define A e = i Γ u Γ v A_e=\mathrm{i}\Gamma_u\Gamma_v A e = i Γ u Γ v , and let
A : = { A e : e ∈ E } . \mathcal{A}:=\{A_e:e\in E\}. A := { A e : e ∈ E } .
Thus the edges of R R R index the observables in A \mathcal{A} A . Each A e A_e A e is a Hermitian unitary and is represented by a Pauli string under the Jordan–Wigner transformation.
Recall that the line graph L ( R ) L(R) L ( R ) has vertex set E E E , with two vertices e , f ∈ E e,f\in E e , f ∈ E adjacent exactly when the corresponding edges of R R R share an endpoint. The quadratic Majorana construction then gives the following correspondence [61 , 62 ] .
Lemma VI.1. The anti-commutativity graph of A \mathcal{A} A is L ( R ) L(R) L ( R ) .
Proof. For distinct e , f ∈ E e,f\in E e , f ∈ E , the Majorana relations give
A e A f = ( − 1 ) ∣ e ∩ f ∣ A f A e . A_eA_f=(-1)^{|e\cap f|}A_fA_e. A e A f = ( − 1 ) ∣ e ∩ f ∣ A f A e .
Since R R R is simple, ∣ e ∩ f ∣ = 1 |e\cap f|=1 ∣ e ∩ f ∣ = 1 exactly when e e e and f f f share an endpoint. Hence A e A_e A e and A f A_f A f anti-commute exactly when e e e and f f f are adjacent in L ( R ) L(R) L ( R ) . □
The graph R R R therefore specifies the quadratic observables, whereas L ( R ) L(R) L ( R ) records their anti-commutation relations. Sharpnesses and weights are indexed by E E E , so s ∈ [ 0 , 1 ] E s\in[0,1]^E s ∈ [ 0 , 1 ] E and w ∈ Δ ( E ) w\in\Delta(E) w ∈ Δ ( E ) . By representation independence, the resulting compatibility region applies to every Pauli realisation of L ( R ) L(R) L ( R ) .
The covariance matrix
Q u v : = i 2 tr ( ρ [ Γ u , Γ v ] ) Q_{uv}:=\frac{\mathrm{i}}{2}\operatorname{tr}\bigl(\rho[\Gamma_u,\Gamma_v]\bigr) Q uv := 2 i tr ( ρ [ Γ u , Γ v ] )
records the expectation values relevant to the quadratic Majorana observables. In particular, for u ≠ v u\ne v u = v , the Majorana anti-commutation relations give Q u v = tr ( ρ i Γ u Γ v ) Q_{uv}=\operatorname{tr}(\rho\,\mathrm{i}\Gamma_u\Gamma_v) Q uv = tr ( ρ i Γ u Γ v ) . For any state, Q Q Q is real and skew-symmetric with ∥ Q ∥ ∞ ≤ 1 \lVert Q\rVert_\infty\leq1 ∥ Q ∥ ∞ ≤ 1 . For a pure Gaussian state, moreover, Q Q Q determines the state completely and satisfies Q 2 = − 1 Q^2=-1 Q 2 = − 1 . Conversely, every real skew-symmetric matrix satisfying this condition specifies a unique pure Gaussian state ρ Q \rho_Q ρ Q [63 ] .
For an edge e = { u , v } e=\{u,v\} e = { u , v } with u < v u<v u < v , tr ( ρ Q A e ) = Q u v \operatorname{tr}(\rho_Q A_e)=Q_{uv} tr ( ρ Q A e ) = Q uv , so the corresponding Pauli-orbit parent has sharpness vector
c A ( ρ Q ) = ( ∣ Q u v ∣ ) { u , v } ∈ E . c_{\mathcal{A}}(\rho_Q)=\left(\lvert Q_{uv}\rvert\right)_{\{u,v\}\in E}. c A ( ρ Q ) = ( ∣ Q uv ∣ ) { u , v } ∈ E .
Thus the covariance matrix specifies the Gaussian seed, while its edge entries determine the sharpnesses. We can construct the corresponding parent directly on the full Fock space, without first passing to a canonical irreducible representation.
For this purpose, use all Majorana monomials Γ x = Γ 1 x 1 ⋯ Γ M x M \Gamma^x=\Gamma_1^{x_1}\cdots\Gamma_M^{x_M} Γ x = Γ 1 x 1 ⋯ Γ M x M , with x ∈ F 2 M x\in\mathbb{F}_2^M x ∈ F 2 M , and write D = 2 M / 2 D=2^{M/2} D = 2 M /2 . Up to phases, these D 2 D^2 D 2 operators form the full Pauli basis, so the conjugation averages of Appendix A give the orbit POVM
E ρ ( x ) = 1 D Γ x ρ ( Γ x ) † , x ∈ F 2 M , (58) E_\rho(x)=\frac{1}{D}\Gamma^x\rho(\Gamma^x)^\dagger,\qquad x\in\mathbb{F}_2^M, \tag*{(58)} E ρ ( x ) = D 1 Γ x ρ ( Γ x ) † , x ∈ F 2 M , (58)
for any seed state ρ \rho ρ . For an edge e = { u , v } e=\{u,v\} e = { u , v } , conjugation gives Γ x A e ( Γ x ) † = ( − 1 ) x u + x v A e \Gamma^x A_e(\Gamma^x)^\dagger=(-1)^{x_u+x_v}A_e Γ x A e ( Γ x ) † = ( − 1 ) x u + x v A e . Reporting f e ( x ) = α e ( − 1 ) x u + x v f_e(x)=\alpha_e(-1)^{x_u+x_v} f e ( x ) = α e ( − 1 ) x u + x v , with α e tr ( ρ A e ) = ∣ tr ( ρ A e ) ∣ \alpha_e\operatorname{tr}(\rho A_e)=\lvert\operatorname{tr}(\rho A_e)\rvert α e tr ( ρ A e ) = ∣ tr ( ρ A e )∣ and α e ∈ { ± 1 } \alpha_e\in\{\pm1\} α e ∈ { ± 1 } , therefore gives sharpness ∣ tr ( ρ A e ) ∣ \lvert\operatorname{tr}(\rho A_e)\rvert ∣ tr ( ρ A e )∣ by Eq. (11) . For the Gaussian seed ρ Q \rho_Q ρ Q , this is ∣ Q u v ∣ \lvert Q_{uv}\rvert ∣ Q uv ∣ . The orbit includes odd-degree monomials, which exchange parity sectors and ensure normalisation on the full space even when the seed has definite parity.
It remains to choose a seed that maximises a prescribed weighted sum of sharpnesses. By Proposition 3, this reduces to the spectral optimisation of signed Hamiltonians. For a fixed signing a ∈ { ± 1 } E a\in\{\pm1\}^E a ∈ { ± 1 } E , let S w , a S_{w,a} S w , a be the real skew-symmetric N × N N\times N N × N matrix with upper-triangular entries w e a e w_ea_e w e a e on edges e = { u , v } e=\{u,v\} e = { u , v } and zero on nonedges. The corresponding signed Hamiltonian is
H w , a = i 2 ∑ u , v = 1 N ( S w , a ) u v Γ u Γ v . (59) H_{w,a}=\frac{\mathrm{i}}{2}\sum_{u,v=1}^{N}(S_{w,a})_{uv}\Gamma_u\Gamma_v. \tag*{(59)} H w , a = 2 i u , v = 1 ∑ N ( S w , a ) uv Γ u Γ v . (59)
Writing S = S w , a S=S_{w,a} S = S w , a , a state with covariance Q Q Q satisfies
tr ( ρ H w , a ) = 1 2 tr ( Q T S ) ≤ 1 2 ∥ Q ∥ ∞ ∥ S ∥ 1 ≤ 1 2 ∥ S ∥ 1 , \operatorname{tr}(\rho H_{w,a})=\frac{1}{2}\operatorname{tr}(Q^{T}S)\leq\frac{1}{2}\lVert Q\rVert_{\infty}\lVert S\rVert_1\leq\frac{1}{2}\lVert S\rVert_1, tr ( ρ H w , a ) = 2 1 tr ( Q T S ) ≤ 2 1 ∥ Q ∥ ∞ ∥ S ∥ 1 ≤ 2 1 ∥ S ∥ 1 ,
where we used ∥ Q ∥ ∞ ≤ 1 \lVert Q\rVert_\infty\leq1 ∥ Q ∥ ∞ ≤ 1 and trace-norm/operator-norm duality (padding S S S by a zero row and column when N N N is odd).
When S S S is nonsingular, the bound is attained by the pure Gaussian covariance
Q = S ( − S 2 ) − 1 / 2 , (60) Q=S(-S^2)^{-1/2}, \tag*{(60)} Q = S ( − S 2 ) − 1/2 , (60)
as shown in Appendix § 4.5 . This is the orthogonal factor in the polar decomposition of S S S : it satisfies Q 2 = − 1 Q^2=-1 Q 2 = − 1 and Q T S = ( − S 2 ) 1 / 2 Q^TS=(-S^2)^{1/2} Q T S = ( − S 2 ) 1/2 , and hence gives λ max ( H w , a ) = 1 2 ∥ S ∥ 1 \lambda_{\max}(H_{w,a})=\frac{1}{2}\lVert S\rVert_1 λ m a x ( H w , a ) = 2 1 ∥ S ∥ 1 .
For singular S S S , the polar factor on ( ker S ) ⊥ (\ker S)^\perp ( ker S ) ⊥ can be extended over ker S \ker S ker S to a pure Gaussian covariance Q Q Q satisfying Q 2 = − 1 Q^2=-1 Q 2 = − 1 . When N N N is odd, we first adjoin the unused auxiliary Majorana. Appendix § 4.5 gives the construction. Thus, for every signing, the spectral optimum is attained by a pure Gaussian state.
Proposition 6. Let A = { A e : e ∈ E } \mathcal{A}=\{A_e:e\in E\} A = { A e : e ∈ E } be the quadratic Majorana family associated with R R R , so that its anti-commutativity graph is L ( R ) L(R) L ( R ) . Then
h L ( R ) ( w ) = 1 2 max a ∈ { ± 1 } E ∥ S w , a ∥ 1 , w ∈ Δ ( E ) . (61) h_{L(R)}(w)=\frac{1}{2}\max_{a\in\{\pm1\}^E}\lVert S_{w,a}\rVert_1,\qquad w\in\Delta(E). \tag*{(61)} h L ( R ) ( w ) = 2 1 a ∈ { ± 1 } E max ∥ S w , a ∥ 1 , w ∈ Δ ( E ) . (61) For any maximising signing a ⋆ a_\star a ⋆ , the corresponding pure Gaussian covariance Q Q Q gives a seed with profile s { u , v } = ∣ Q u v ∣ s_{\{u,v\}}=\lvert Q_{uv}\rvert s { u , v } = ∣ Q uv ∣ satisfying w ⋅ s = h L ( R ) ( w ) w\cdot s=h_{L(R)}(w) w ⋅ s = h L ( R ) ( w ) . Its orbit POVM is therefore an optimal joint measurement for w w w .
Proof. For each signing a a a , the construction above gives λ max ( H w , a ) = 1 2 ∥ S w , a ∥ 1 \lambda_{\max}(H_{w,a})=\frac{1}{2}\lVert S_{w,a}\rVert_1 λ m a x ( H w , a ) = 2 1 ∥ S w , a ∥ 1 , attained by a pure Gaussian state. Maximising over a a a and applying Proposition 3 gives the support formula; the Gaussian seed for a maximising signing generates the stated parent. □
Equation (61) extends the skew-energy approach of [35 ] . Recall that the skew energy of an orientation is the trace norm of its skew-adjacency matrix, so for uniform edge weights Eq. (61) recovers the maximum skew-energy bound used there. Here the edge weights can also vary, and minimising over them gives the exact threshold η ( L ( R ) ) \eta(L(R)) η ( L ( R )) . Thus uniform edge weights suffice when L ( R ) L(R) L ( R ) is vertex-transitive, whereas optimising the weights can give a stronger bound for other root graphs.
For a Δ \Delta Δ -regular root graph R R R , the Δ \Delta Δ edges incident to any vertex form a clique in L ( R ) L(R) L ( R ) , so η ( L ( R ) ) ≤ 1 / Δ \eta(L(R))\leq1/\sqrt{\Delta} η ( L ( R )) ≤ 1/ Δ . It was shown in [35 ] that equality can hold only if R R R has an orientation whose skew-adjacency matrix S S S satisfies S S T = Δ I SS^T=\Delta I S S T = Δ I . Proposition 6 shows that this condition is also sufficient, and gives an explicit optimal Gaussian seed. The details are given in Appendix § 4.5 .
Corollary 9. Let R R R be Δ \Delta Δ -regular. Then η ( L ( R ) ) = 1 / Δ \eta(L(R))=1/\sqrt{\Delta} η ( L ( R )) = 1/ Δ if and only if R R R admits an orientation whose skew-adjacency matrix S S S satisfies S S T = Δ I SS^T=\Delta I S S T = Δ I . In this case Q = S / Δ Q=S/\sqrt{\Delta} Q = S / Δ is the covariance of a balanced pure Gaussian seed, and its orbit POVM attains the optimal uniform sharpness.
More generally, the weighted support values determine the full compatibility region. Since every support value is attained by a pure Gaussian seed, Gaussian seeds suffice to generate every compatible sharpness vector, not just the uniform optimum.
Corollary 10. A vector s ∈ [ 0 , 1 ] E s\in[0,1]^E s ∈ [ 0 , 1 ] E belongs to C L ( R ) \mathcal{C}_{L(R)} C L ( R ) if and only if there are finitely many real skew-symmetric
matrices Q ( j ) ∈ R M × M Q^{(j)} \in\mathbb{R}^{M \times M} Q ( j ) ∈ R M × M satisfying ( Q ( j ) ) 2 = − 1 (Q^{(j)})^2=-\mathbb{1} ( Q ( j ) ) 2 = − 1 , and probabilities p j ≥ 0 p_j \ge0 p j ≥ 0 , ∑ j p j = 1 \sum_j p_j=1 ∑ j p j = 1 , such that
s { u , v } ≤ ∑ j p j ∣ Q u v ( j ) ∣ , { u , v } ∈ E . (62) s_{\{u,v\}} \le\sum_j p_j \lvert Q^{(j)}_{uv}\rvert,\qquad\{u,v\}\in E. \tag*{(62)} s { u , v } ≤ j ∑ p j ∣ Q uv ( j ) ∣ , { u , v } ∈ E . (62)
A parent is obtained by mixing the orbit POVMs of the Gaussian seeds ρ Q ( j ) \rho_{Q^{(j)}} ρ Q ( j ) and applying classical output noise when necessary.
Proof. By Theorem 1, the vectors satisfying Eq. (62) form a compact, convex subset of C L ( R ) \mathcal{C}_L(R) C L ( R ) that is closed under coordinatewise decrease. Proposition 6 shows that this subset has the same nonnegative support values. The support characterisation (33) therefore makes the two regions equal.
For a pure Gaussian seed, Q 2 = − 1 Q^2=-\mathbb{1} Q 2 = − 1 implies
∑ u < v ≤ M ∣ Q u v ∣ 2 = M 2 . \sum_{u<v\le M}\lvert Q_{uv}\rvert^2=\frac{M}{2}. u < v ≤ M ∑ ∣ Q uv ∣ 2 = 2 M .
When N N N is odd, the correlations with the auxiliary Majorana have total squared magnitude one, so in both cases
∑ u < v ≤ N ∣ Q u v ∣ 2 = ⌊ N 2 ⌋ . \sum_{u<v\le N}\lvert Q_{uv}\rvert^2=\left\lfloor\frac{N}{2}\right\rfloor. u < v ≤ N ∑ ∣ Q uv ∣ 2 = ⌊ 2 N ⌋ .
Restricting the sum to edges can only decrease it. The squared Euclidean norm is convex and cannot increase under coordinatewise decrease of a nonnegative vector, so Corollary 10 gives the necessary compatibility condition
∑ e ∈ E s e 2 ≤ ⌊ N 2 ⌋ . (63) \sum_{e\in E}s_e^2\le\left\lfloor\frac{N}{2}\right\rfloor. \tag*{(63)} e ∈ E ∑ s e 2 ≤ ⌊ 2 N ⌋ . (63)
For a pure Gaussian seed with covariance Q Q Q , its profile saturates Eq. (63) if and only if Q u v = 0 Q_{uv}=0 Q uv = 0 on every nonedge of R R R among the first N N N Majoranas. In particular, when R R R is complete there are no nonedges, so every pure Gaussian profile saturates the bound. We use this observation later for the complete quadratic Majorana family (cf. § 3.2 4). In general, the bound is only necessary for compatibility.
Cycles
We now consider families whose anti-commutativity graph is the cycle C n C_n C n , with n ≥ 3 n\ge3 n ≥ 3 . Since L ( C n ) ≅ C n L(C_n)\cong C_n L ( C n ) ≅ C n , such a family is obtained from the line graph construction by taking R = C n R=C_n R = C n . Explicitly, A = { A 1 , … , A n } \mathcal{A}=\{A_1,\ldots,A_n\} A = { A 1 , … , A n } , where A j = i Γ j Γ j + 1 A_j=i\Gamma_j\Gamma_{j+1} A j = i Γ j Γ j + 1 for 1 ≤ j < n 1\le j<n 1 ≤ j < n and A n = i Γ n Γ 1 A_n=i\Gamma_n\Gamma_1 A n = i Γ n Γ 1 .
For this family, the weighted support function reduces to two sign choices, and the optimal uniform sharpness is attained by a single pure Gaussian seed. We retain the full Fock space convention of Sec. VII 1, including an unused auxiliary Majorana when n n n is odd.
The signing optimisation in Eq. (61) simplifies because changes of sign of the individual Majoranas can move all edge signs to the closing edge. Explicitly, for a ∈ { ± 1 } n a\in\{\pm1\}^n a ∈ { ± 1 } n , conjugating the signed skew-adjacency matrix by the diagonal orthogonal matrix
D a = diag ( 1 , a 1 , a 1 a 2 , … , a 1 ⋯ a n − 1 ) D_a=\operatorname{diag}(1,a_1,a_1a_2,\ldots,a_1\cdots a_{n-1}) D a = diag ( 1 , a 1 , a 1 a 2 , … , a 1 ⋯ a n − 1 )
changes the edge signs to ( 1 , … , 1 , τ ) (1,\ldots,1,\tau) ( 1 , … , 1 , τ ) , where τ = ∏ j = 1 n a j \tau=\prod_{j=1}^n a_j τ = ∏ j = 1 n a j . The trace norm is unchanged, so only the two choices τ = ± 1 \tau=\pm1 τ = ± 1 need be considered.
For w ∈ Δ ( [ n ] ) w\in\Delta([n]) w ∈ Δ ([ n ]) , let S w ( τ ) S_w^{(\tau)} S w ( τ ) be the skew-symmetric matrix defined by
( S w ( τ ) ) j , j + 1 = w j ( 1 ≤ j < n ) , ( S w ( τ ) ) n , 1 = τ w n , \left(S_w^{(\tau)}\right)_{j,j+1}=w_j\quad(1\le j<n),\qquad\left(S_w^{(\tau)}\right)_{n,1}=\tau w_n, ( S w ( τ ) ) j , j + 1 = w j ( 1 ≤ j < n ) , ( S w ( τ ) ) n , 1 = τ w n ,
with opposite entries fixed by skew symmetry and all remaining entries zero. Proposition 6 gives
h C n ( w ) = 1 2 max τ = ± 1 ∥ S w ( τ ) ∥ 1 . (64) h_{C_n}(w)=\frac{1}{2}\max_{\tau=\pm1}\left\|S_w^{(\tau)}\right\|_1. \tag*{(64)} h C n ( w ) = 2 1 τ = ± 1 max S w ( τ ) 1 . (64)
Together with Eq. (33) , this determines the full nonuniform compatibility region. Each support value is attained by a parent generated by a pure Gaussian state obtained from an optimal signed matrix by the covariance construction above.
For uniform sharpness, vertex transitivity and Theorem 3 give η ( C n ) = h C n ( w ˉ ) \eta(C_n)=h_{C_n}(\bar{w}) η ( C n ) = h C n ( w ˉ ) , where w ˉ = 1 / n \bar{w}=1/n w ˉ = 1/ n . Evaluating the trace norms at these weights recovers the known threshold [35 ] ,
η ( C n ) = { 1 n cot ( π 2 n ) , n odd , 2 n csc ( π n ) , n even . (65) \eta(C_n)=
\begin{cases}
\frac{1}{n}\cot\left(\frac{\pi}{2n}\right), & n\ \text{odd},\\
\frac{2}{n}\csc\left(\frac{\pi}{n}\right), & n\ \text{even}.
\end{cases} \tag*{(65)} η ( C n ) = { n 1 cot ( 2 n π ) , n 2 csc ( n π ) , n odd , n even . (65)
The same support value gives the tight inequality ∑ j s j ≤ n η ( C n ) \sum_j s_j\le n\eta(C_n) ∑ j s j ≤ n η ( C n ) for every compatible vector.
For even n n n , a parent attaining the optimal uniform sharpness can be specified explicitly by the covariance matrix of a single pure Gaussian seed. For even n n n , the maximising choice is τ = − 1 \tau=-1 τ = − 1 , so we set S = S w ˉ ( − 1 ) S=S_{\bar{w}}^{(-1)} S = S w ˉ ( − 1 ) . This matrix is nonsingular, and the seed covariance is Q ⋆ = S ( − S 2 ) − 1 / 2 Q_\star=S(-S^2)^{-1/2} Q ⋆ = S ( − S 2 ) − 1/2 .
For odd n n n , both choices of τ \tau τ are optimal; we take τ = + 1 \tau=+1 τ = + 1 and set S = S w ˉ ( + 1 ) S=S_{\bar{w}}^{(+1)} S = S w ˉ ( + 1 ) . Its kernel is spanned by u = 1 / n u=\mathbf{1}/\sqrt{n} u = 1 / n . Let Q 0 Q_0 Q 0 be the polar factor obtained from the same formula on the nonzero modes, with Q 0 u = 0 Q_0u=0 Q 0 u = 0 . Including the auxiliary Majorana, the full seed covariance is
Q ⋆ = ( Q 0 u − u T 0 ) . Q_\star=
\begin{pmatrix}
Q_0 & u\\
-u^{\mathsf{T}} & 0
\end{pmatrix}. Q ⋆ = ( Q 0 − u T u 0 ) .
This completion satisfies Q ⋆ 2 = − 1 Q_\star^2=-\mathbb{1} Q ⋆ 2 = − 1 and leaves the correlations among the original n n n Majoranas unchanged.
In both cases, Q ⋆ Q_\star Q ⋆ specifies a pure Gaussian state ρ ⋆ \rho_\star ρ ⋆ attaining the support value h C n ( w ˉ ) = η ( C n ) h_{C_n}(\bar{w})=\eta(C_n) h C n ( w ˉ ) = η ( C n ) . The cyclic symmetry of the chosen signed matrix makes the cycle entries of its covariance equal in magnitude. Their average magnitude is therefore also their common value, giving
∣ tr ( ρ ⋆ A j ) ∣ = η ( C n ) , j = 1 , … , n . (66) \left|\operatorname{tr}(\rho_\star A_j)\right|=\eta(C_n),\qquad j=1,\ldots,n. \tag*{(66)} ∣ tr ( ρ ⋆ A j ) ∣ = η ( C n ) , j = 1 , … , n . (66)
Thus the seed’s orbit POVM gives every observable the optimal common sharpness, without mixing different seed orbits or adding output noise.
Appendix G verifies these covariance and symmetry statements and shows that the construction also gives a single-orbit optimal parent in a canonical irreducible representation.
Opening cycles: paths
We now consider families whose anti-commutativity graph is the path P n P_n P n , with n ≥ 2 n \ge2 n ≥ 2 . Since L ( P n + 1 ) ≅ P n L(P_{n+1}) \cong P_n L ( P n + 1 ) ≅ P n , such a family is obtained from the line graph construction by taking R = P n + 1 R = P_{n+1} R = P n + 1 . Explicitly, A = { A 1 , … , A n } \mathcal{A} = \{A_1,\ldots,A_n\} A = { A 1 , … , A n } , where A j = i Γ j Γ j + 1 A_j = \mathrm{i}\Gamma_j\Gamma_{j+1} A j = i Γ j Γ j + 1 for j = 1 , … , n j = 1,\ldots,n j = 1 , … , n .
This family can also be obtained from the cycle family for C n + 1 C_{n+1} C n + 1 by removing its closing observable. At the level of the parent measurement, this requires only omitting the corresponding classical readout, so the seed state and parent POVM can remain unchanged. This relation allows the path support function to be obtained directly from that of the cycle. Setting that observable’s weight to zero makes the two signed cycle matrices coincide with the ( n + 1 ) × ( n + 1 ) (n+1) \times(n+1) ( n + 1 ) × ( n + 1 ) skew-symmetric matrix Ω w \Omega_w Ω w , defined by ( Ω w ) j , j + 1 = w j (\Omega_w)_{j,j+1} = w_j ( Ω w ) j , j + 1 = w j , ( Ω w ) j + 1 , j = − w j (\Omega_w)_{j+1,j} = -w_j ( Ω w ) j + 1 , j = − w j , and zero entries elsewhere. Hence, for n ≥ 2 n \ge2 n ≥ 2 and w ∈ Δ ( [ n ] ) w \in\Delta([n]) w ∈ Δ ([ n ]) ,
h P n ( w ) = h C n + 1 ( w 1 , … , w n , 0 ) = 1 2 ∥ Ω w ∥ 1 . (67) h_{P_n}(w) = h_{C_{n+1}}(w_1,\ldots,w_n,0)
= \frac{1}{2}\lVert\Omega_w\rVert_1. \tag*{(67)} h P n ( w ) = h C n + 1 ( w 1 , … , w n , 0 ) = 2 1 ∥ Ω w ∥ 1 . (67)
Thus paths require no optimisation over signings. For each choice of weights, Proposition 6 supplies a pure Gaussian seed that attains the corresponding maximum. Varying the weights determines the full compatibility region through Eq. (33) .
For uniform sharpness, the question is whether opening a cycle allows a larger common value. Paths with at least three vertices are not vertex-transitive, so the uniform-weight argument used for cycles no longer applies. Nevertheless, removing one or two consecutive observables from an even cycle leaves its optimal uniform sharpness unchanged. The following resolves Conjecture 1 of [35 ] and also shows that an optimal parent can be obtained simply by restricting an optimal parent for the even cycle.
Proposition 7. For every m ≥ 1 m \ge1 m ≥ 1 , the cycles and paths C 2 m + 2 C_{2m+2} C 2 m + 2 , P 2 m + 1 P_{2m+1} P 2 m + 1 , and P 2 m P_{2m} P 2 m have the same optimal uniform sharpness:
η ( C 2 m + 2 ) = η ( P 2 m + 1 ) = η ( P 2 m ) = 1 m + 1 csc ( π 2 m + 2 ) . (68) \eta(C_{2m+2}) = \eta(P_{2m+1}) = \eta(P_{2m})
= \frac{1}{m+1}\csc\left(\frac{\pi}{2m+2}\right). \tag*{(68)} η ( C 2 m + 2 ) = η ( P 2 m + 1 ) = η ( P 2 m ) = m + 1 1 csc ( 2 m + 2 π ) . (68) Every parent that attains this common sharpness for C 2 m + 2 C_{2m+2} C 2 m + 2 also attains it for P 2 m + 1 P_{2m+1} P 2 m + 1 and P 2 m P_{2m} P 2 m .
Proof. Deleting one or two consecutive observables preserves the sharpness of every retained marginal, so η ( C 2 m + 2 ) ≤ η ( P 2 m + 1 ) ≤ η ( P 2 m ) \eta(C_{2m+2}) \le\eta(P_{2m+1}) \le\eta(P_{2m}) η ( C 2 m + 2 ) ≤ η ( P 2 m + 1 ) ≤ η ( P 2 m ) . It therefore suffices to prove a matching upper bound for the shorter path.
Set θ = π / ( 2 m + 2 ) \theta= \pi/(2m+2) θ = π / ( 2 m + 2 ) . The path trace-norm calculation in Appendix H gives, for every s ∈ C P 2 m s \in\mathcal{C}_{P_{2m}} s ∈ C P 2 m ,
∑ j = 1 2 m sin ( j θ ) sin ( ( j + 1 ) θ ) s j ≤ cot θ . (69) \sum_{j=1}^{2m} \sin(j\theta)\sin((j+1)\theta)s_j \le\cot\theta. \tag*{(69)} j = 1 ∑ 2 m sin ( j θ ) sin (( j + 1 ) θ ) s j ≤ cot θ . (69)
The coefficients sum to ( m + 1 ) cos θ (m+1)\cos\theta ( m + 1 ) cos θ , so setting s j = η s_j = \eta s j = η gives η ( P 2 m ) ≤ 1 / ( ( m + 1 ) sin θ ) = η ( C 2 m + 2 ) \eta(P_{2m}) \le1/((m+1)\sin\theta) = \eta(C_{2m+2}) η ( P 2 m ) ≤ 1/ (( m + 1 ) sin θ ) = η ( C 2 m + 2 ) , where the last equality is Eq. (65) . All three thresholds therefore coincide. Since restriction preserves the retained sharpness, it also preserves optimality for these two paths.
The proof also identifies weights whose supporting inequality is saturated at the common optimal sharpness in Proposition 7. Normalising the coefficients in Eq. (69) gives an optimal weight vector w ⋆ w^\star w ⋆ for P 2 m P_{2m} P 2 m . These weights are symmetric under reversal of the path, but are nonuniform for m ≥ 2 m \ge2 m ≥ 2 .
The same inequality also applies to P 2 m + 1 P_{2m+1} P 2 m + 1 and C 2 m + 2 C_{2m+2} C 2 m + 2 : one simply adds zero weight to the additional observables, giving ( w ⋆ , 0 ) (w^\star,0) ( w ⋆ , 0 ) and ( w ⋆ , 0 , 0 ) (w^\star,0,0) ( w ⋆ , 0 , 0 ) , respectively. The upper bound obtained from P 2 m P_{2m} P 2 m is therefore sufficient to prove optimality for all three families.
In particular, the covariance Q ⋆ Q_\star Q ⋆ constructed for C 2 m + 2 C_{2m+2} C 2 m + 2 in Sec. VI 2 already specifies an optimal seed for both paths. The same state and orbit POVM remain unchanged; only the first 2 m + 1 2m+1 2 m + 1 or 2 m 2m 2 m readouts are retained.
For a two-qubit example, take
A 1 = X ⊗ 1 , A 2 = Z ⊗ 1 , A_1 = X \otimes\mathbb{1},\qquad A_2 = Z \otimes\mathbb{1}, A 1 = X ⊗ 1 , A 2 = Z ⊗ 1 ,
A 3 = X ⊗ X , A 4 = 1 ⊗ Z , A_3 = X \otimes X,\qquad A_4 = \mathbb{1} \otimes Z, A 3 = X ⊗ X , A 4 = 1 ⊗ Z ,
A 5 = 1 ⊗ X , A 6 = Z ⊗ Z . A_5 = \mathbb{1} \otimes X,\qquad A_6 = Z \otimes Z. A 5 = 1 ⊗ X , A 6 = Z ⊗ Z .
Their anti-commutativity graph is C 6 C_6 C 6 , and the state
∣ ψ ⋆ ⟩ = 3 ∣ 00 ⟩ + ∣ 01 ⟩ + ∣ 10 ⟩ + ∣ 11 ⟩ 2 3 (70) |\psi_\star\rangle= \frac{3|00\rangle+ |01\rangle+ |10\rangle+ |11\rangle}{2\sqrt{3}} \tag*{(70)} ∣ ψ ⋆ ⟩ = 2 3 3∣00 ⟩ + ∣01 ⟩ + ∣10 ⟩ + ∣11 ⟩ (70)
satisfies ⟨ ψ ⋆ ∣ A j ∣ ψ ⋆ ⟩ = 2 / 3 \langle\psi_\star|A_j|\psi_\star\rangle= 2/3 ⟨ ψ ⋆ ∣ A j ∣ ψ ⋆ ⟩ = 2/3 for every j j j . Its Pauli orbit therefore gives parents attaining the optimal uniform sharpness for C 6 C_6 C 6 , P 5 P_5 P 5 and P 4 P_4 P 4 .
The weighted description also reveals the tradeoffs away from uniform sharpness. For P 4 P_4 P 4 , consider the reflection-symmetric slice s = ( x , y , y , x ) s = (x,y,y,x) s = ( x , y , y , x ) . By reflection symmetry, it is enough to consider reflection-symmetric weights. Optimising the resulting support inequalities gives the exact compatibility condition
( max { 2 x − 1 , 0 } ) 2 + 2 y 2 ≤ 1. (\max\{2x-1,0\})^2 + 2y^2 \le1. ( max { 2 x − 1 , 0 } ) 2 + 2 y 2 ≤ 1.
Its coordinatewise maximal points form the arc
( 2 x − 1 ) 2 + 2 y 2 = 1 , 1 2 ≤ x ≤ 1 , y ≥ 0. (71) (2x-1)^2 + 2y^2 = 1,\qquad\frac{1}{2} \le x \le1,\quad y \ge0. \tag*{(71)} ( 2 x − 1 ) 2 + 2 y 2 = 1 , 2 1 ≤ x ≤ 1 , y ≥ 0. (71)
The rest of the compatible region (see Figure 3 ) is obtained by decreasing one or both sharpnesses from a point on the arc; see Appendix H 2.
Figure 3. Sharpness tradeoffs for P 4 P_4 P 4 with s = ( x , y , y , x ) s=(x,y,y,x) s = ( x , y , y , x ) . The two endpoints have sharpness x x x and the two internal vertices have sharpness y y y . The shaded region is the compatible region in this reflection-symmetric slice. The arc, ( 2 x − 1 ) 2 + 2 y 2 = 1 (2x-1)^2+2y^2=1 ( 2 x − 1 ) 2 + 2 y 2 = 1 for 1 / 2 ≤ x ≤ 1 1/2\le x\le1 1/2 ≤ x ≤ 1 and y ≥ 0 y\ge0 y ≥ 0 , shows the optimal tradeoffs: increasing one sharpness requires decreasing the other. The dashed line x + 2 y = 2 x+2y=2 x + 2 y = 2 , corresponding to w ⋆ = ( 1 , 2 , 2 , 1 ) / 6 w^\star=(1,2,2,1)/6 w ⋆ = ( 1 , 2 , 2 , 1 ) /6 , is tangent to the arc at the optimal common sharpness x = y = 2 / 3 x=y=2/3 x = y = 2/3 .
The uniform optimum is x = y = 2 / 3 x=y=2/3 x = y = 2/3 . The weights w ⋆ = ( 1 , 2 , 2 , 1 ) / 6 w^\star=(1,2,2,1)/6 w ⋆ = ( 1 , 2 , 2 , 1 ) /6 give the bound x + 2 y ≤ 2 x+2y\le2 x + 2 y ≤ 2 , whose boundary line is tangent to the arc at this point. Setting x = y = η x=y=\eta x = y = η gives 3 η ≤ 2 3\eta\le2 3 η ≤ 2 , directly recovering the optimal common sharpness. Other weight choices select the remaining points on the arc.
Opening an odd cycle behaves differently. Removing one observable from C 2 m + 1 C_{2m+1} C 2 m + 1 gives P 2 m P_{2m} P 2 m , but Eqs. (65) and (68) imply η ( C 2 m + 1 ) < η ( P 2 m ) \eta(C_{2m+1})<\eta(P_{2m}) η ( C 2 m + 1 ) < η ( P 2 m ) . A parent attaining the optimal uniform sharpness for the odd cycle remains a valid parent for the path, but its marginals do not attain the path optimum.
This also explains why every observable must receive positive weight in a bound that establishes the odd-cycle optimum. Setting any weight to zero leaves a path problem, whose optimal common sharpness is strictly larger; such a bound cannot give the smaller cycle threshold. Appendix H gives the details.
An interesting phenomenon arises when an even path is closed without changing the number of observables. The graphs P 2 m P_{2m} P 2 m and C 2 m C_{2m} C 2 m differ by one additional edge, yet η ( P 2 m ) < η ( C 2 m ) \eta(P_{2m})<\eta(C_{2m}) η ( P 2 m ) < η ( C 2 m ) for m ≥ 2 m\ge2 m ≥ 2 . Thus adding an anti-commutation relation can increase, rather than decrease, the optimal uniform sharpness [35 ] .
Complete quadratic Majorana families
We now consider the line graph of R = K N R=K_N R = K N . Thus, for N N N Majorana operators, we have one quadratic observable for every unordered pair { u , v } \{u,v\} { u , v } . This gives the complete quadratic family of ( N 2 ) \binom{N}{2} ( 2 N ) observables,
A N , 2 = { A u v = i Γ u Γ v : 1 ≤ u < v ≤ N } . \mathcal{A}_{N,2}=\{A_{uv}=i\Gamma_u\Gamma_v:1\le u<v\le N\}. A N , 2 = { A uv = i Γ u Γ v : 1 ≤ u < v ≤ N } .
Its anti-commutativity graph is L ( K N ) = J ( N , 2 ) L(K_N)=J(N,2) L ( K N ) = J ( N , 2 ) , the Johnson graph.
For this family, the edge sum in Eq. (63) is the full sum ∑ 1 ≤ u < v ≤ N ∣ Q u v ∣ 2 \sum_{1\le u<v\le N}|Q_{uv}|^2 ∑ 1 ≤ u < v ≤ N ∣ Q uv ∣ 2 . Every pure Gaussian profile therefore saturates the bound, ∑ 1 ≤ u < v ≤ N ∣ Q u v ∣ 2 = ⌊ N 2 ⌋ \sum_{1\le u<v\le N}|Q_{uv}|^2=\left\lfloor\frac{N}{2}\right\rfloor ∑ 1 ≤ u < v ≤ N ∣ Q uv ∣ 2 = ⌊ 2 N ⌋ . By Proposition 6, h J ( N , 2 ) ( w ) h_{J(N,2)}(w) h J ( N , 2 ) ( w ) is the maximum of ∑ u < v w u v ∣ Q u v ∣ \sum_{u<v}w_{uv}|Q_{uv}| ∑ u < v w uv ∣ Q uv ∣ over pure Gaussian covariances Q Q Q . Cauchy–Schwarz therefore gives, for w ∈ Δ ( E ( K N ) ) w\in\Delta(E(K_N)) w ∈ Δ ( E ( K N )) ,
h J ( N , 2 ) ( w ) ≤ ⌊ N 2 ⌋ ∥ w ∥ 2 , (72) h_{J(N,2)}(w)\le\sqrt{\left\lfloor\frac{N}{2}\right\rfloor}\,\lVert w\rVert_2, \tag*{(72)} h J ( N , 2 ) ( w ) ≤ ⌊ 2 N ⌋ ∥ w ∥ 2 , (72)
with equality if and only if there exists a pure Gaussian covariance Q Q Q satisfying
∣ Q u v ∣ = ⌊ N 2 ⌋ w u v ∥ w ∥ 2 2 , 1 ≤ u < v ≤ N . (73) |Q_{uv}|=\sqrt{\left\lfloor\frac{N}{2}\right\rfloor}\frac{w_{uv}}{\lVert w\rVert_2^2},\qquad1\le u<v\le N. \tag*{(73)} ∣ Q uv ∣ = ⌊ 2 N ⌋ ∥ w ∥ 2 2 w uv , 1 ≤ u < v ≤ N . (73)
Thus every pure Gaussian seed is optimal for some weighted sharpness objective: choosing the weights proportional to its absolute quadratic correlations makes its profile saturate Eq. (72) .
We now turn to uniform sharpness. Since J ( N , 2 ) J(N,2) J ( N , 2 ) is vertex-transitive, Theorem 3 gives η ( J ( N , 2 ) ) = h J ( N , 2 ) ( w ˉ ) \eta(J(N,2))=h_{J(N,2)}(\bar{w}) η ( J ( N , 2 )) = h J ( N , 2 ) ( w ˉ ) , where w ˉ = 1 / ( N 2 ) \bar{w}=1/\binom{N}{2} w ˉ = 1/ ( 2 N ) . Combining this with the line graph support formula (61) gives
η ( J ( N , 2 ) ) = 1 N ( N − 1 ) max S ∈ T N ∥ S ∥ 1 , (74) \eta(J(N,2))=\frac{1}{N(N-1)}\max_{S\in\mathcal{T}_N}\lVert S\rVert_1, \tag*{(74)} η ( J ( N , 2 )) = N ( N − 1 ) 1 S ∈ T N max ∥ S ∥ 1 , (74)
where T N \mathcal{T}_N T N is the set of real skew-symmetric N × N N\times N N × N matrices with off-diagonal entries in { ± 1 } \{\pm1\} { ± 1 } . These are the skew-adjacency matrices of tournaments [64 ] .
By Proposition 6, a maximising matrix gives a pure Gaussian seed ρ Q \rho_Q ρ Q whose sharpness vector c A ( ρ Q ) c_{\mathcal{A}}(\rho_Q) c A ( ρ Q ) attains the maximum in Eq. (39) . Hence
1 ( N 2 ) ∑ u < v ∣ tr ( ρ Q A u v ) ∣ = η ( J ( N , 2 ) ) . \frac{1}{\binom{N}{2}}\sum_{u<v}|\operatorname{tr}(\rho_Q A_{uv})|=\eta(J(N,2)). ( 2 N ) 1 u < v ∑ ∣ tr ( ρ Q A uv ) ∣ = η ( J ( N , 2 )) .
The individual sharpnesses need not, however, be equal. Averaging the parents obtained by permuting the Majorana labels, as in Theorem 3, makes them all equal to this average and therefore gives a parent attaining the optimal uniform sharpness.
Equation (74) gives the exact uniform optimum, whereas Eq. (72) gives a simpler upper bound. Set M = 2 ⌈ N / 2 ⌉ M=2\lceil N/2\rceil M = 2 ⌈ N /2 ⌉ , so that M = N M=N M = N for even N N N and $M=N+1 for odd N N N . At uniform weights, the latter bound gives η ( J ( N , 2 ) ) ≤ 1 / M − 1 \eta(J(N,2)) \le1/\sqrt{M-1} η ( J ( N , 2 )) ≤ 1/ M − 1 . Equality requires all absolute quadratic correlations of an attaining Gaussian seed to be equal, by Eq. (73) . The seed is then already balanced, so its orbit parent has uniform sharpness without symmetry averaging.
Saturation is characterised by skew-conference matrices : matrices S ∈ T M S \in\mathcal{T}_M S ∈ T M satisfying S S T = ( M − 1 ) 1 SS^{\mathsf{T}}=(M-1)\mathbf{1} S S T = ( M − 1 ) 1 [65 ] . The existence of such a matrix is equivalent to the existence of a skew-Hadamard matrix of the same order, via H S H = 1 + S H_{\mathrm{SH}}=\mathbf{1}+S H SH = 1 + S . For even N N N , the following recovers the known saturation criterion [35 ] (see also [17, Theorem 2(i)]); it also gives the corresponding criterion for odd N N N and, in both cases, an optimal parent measurement from a Gaussian seed.
Proposition 8. Let N ≥ 2 N \ge2 N ≥ 2 and M = 2 ⌈ N / 2 ⌉ M=2\lceil N/2\rceil M = 2 ⌈ N /2 ⌉ , i.e., M = N M=N M = N for even N N N and M = N + 1 M=N+1 M = N + 1 for odd N N N . Then η ( J ( N , 2 ) ) ≤ 1 / M − 1 \eta(J(N,2)) \le1/\sqrt{M-1} η ( J ( N , 2 )) ≤ 1/ M − 1 , with equality if and only if a skew-conference matrix of order M M M exists. For every such matrix S S S , the covariance Q S = S / M − 1 Q_S=S/\sqrt{M-1} Q S = S / M − 1 specifies a pure Gaussian seed ρ S \rho_S ρ S whose orbit parent for A N , 2 \mathcal{A}_{N,2} A N , 2 has uniform sharpness
s u v = η ( J ( N , 2 ) ) = 1 M − 1 , 1 ≤ u < v ≤ N . (75) s_{uv}=\eta(J(N,2))=\frac{1}{\sqrt{M-1}},\qquad1\le u<v\le N. \tag*{(75)} s uv = η ( J ( N , 2 )) = M − 1 1 , 1 ≤ u < v ≤ N . (75)
Proof. The bound follows from Eq. (72) at uniform weights. If equality holds, Eq. (73) supplies a pure Gaussian covariance Q Q Q with ∣ Q u v ∣ = 1 / M − 1 \lvert Q_{uv}\rvert=1/\sqrt{M-1} ∣ Q uv ∣ = 1/ M − 1 for every 1 ≤ u < v ≤ N 1\le u<v\le N 1 ≤ u < v ≤ N .
For even N N N , M = N M=N M = N , and S = N − 1 Q S=\sqrt{N-1}Q S = N − 1 Q has off-diagonal entries in { ± 1 } \{\pm1\} { ± 1 } and satisfies S S T = ( N − 1 ) 1 SS^{\mathsf{T}}=(N-1)\mathbf{1} S S T = ( N − 1 ) 1 . Hence S S S is a skew-conference matrix.
For odd N N N , M = N + 1 M=N+1 M = N + 1 . Since Q T Q = 1 Q^{\mathsf{T}}Q=\mathbf{1} Q T Q = 1 , the N − 1 N-1 N − 1 measured entries in each of the first N N N rows contribute ( N − 1 ) / N (N-1)/N ( N − 1 ) / N to its squared norm. The remaining entry, involving the auxiliary Majorana, therefore has magnitude 1 / N 1/\sqrt{N} 1/ N . Thus every off-diagonal entry of the full covariance has magnitude 1 / N 1/\sqrt{N} 1/ N , and S = N Q S=\sqrt{N}Q S = N Q is a skew-conference matrix of order N + 1 N+1 N + 1 .
Conversely, any skew-conference matrix S S S of order M M M gives a pure Gaussian covariance Q S = S / M − 1 Q_S=S/\sqrt{M-1} Q S = S / M − 1 . Its state satisfies ∣ tr ( ρ S A u v ) ∣ = 1 / M − 1 \lvert\operatorname{tr}(\rho_S A_{uv})\rvert=1/\sqrt{M-1} ∣ tr ( ρ S A uv )∣ = 1/ M − 1 for every measured pair. For odd N N N , the final Majorana is simply unused. Hence the orbit parent has uniform sharpness 1 / M − 1 1/\sqrt{M-1} 1/ M − 1 and saturates the bound.
The skew-conference seed also has a simple reduced-magic value. Since the independent sets of J ( N , 2 ) J(N,2) J ( N , 2 ) are matchings of K N K_N K N , and a maximum matching has ⌊ N / 2 ⌋ \lfloor N/2\rfloor ⌊ N /2 ⌋ edges, vertex transitivity gives
η s t a b ( J ( N , 2 ) ) = ⌊ N / 2 ⌋ ( N 2 ) = 1 M − 1 . \eta_{\mathrm{stab}}(J(N,2))=\frac{\lfloor N/2\rfloor}{\binom{N}{2}}=\frac{1}{M-1}. η stab ( J ( N , 2 )) = ( 2 N ) ⌊ N /2 ⌋ = M − 1 1 .
On the full Fock space, every nonempty commuting subset of the quadratic family is a matching whose product is a nontrivial Majorana monomial, and is therefore not scalar. Thus the family has no active dependencies.
The seed’s uniform sharpness 1 / M − 1 1/\sqrt{M-1} 1/ M − 1 , the definition of R G R_G R G , and Proposition 5 give
RoM A N , 2 ( ρ S ) = R J ( N , 2 ) ( ρ S ) = η ( J ( N , 2 ) ) η s t a b ( J ( N , 2 ) ) = M − 1 . \operatorname{RoM}_{\mathcal{A}_{N,2}}(\rho_S)=R_{J(N,2)}(\rho_S)
=\frac{\eta(J(N,2))}{\eta_{\mathrm{stab}}(J(N,2))}
=\sqrt{M-1}. RoM A N , 2 ( ρ S ) = R J ( N , 2 ) ( ρ S ) = η stab ( J ( N , 2 )) η ( J ( N , 2 )) = M − 1 .
This statement concerns the full Fock-space realisation; restriction to a fixed parity sector can introduce active dependencies.
Complete Pauli families and SIC parents
We finally consider all nonidentity Pauli observables on n n n qubits. Let d = 2 n d=2^n d = 2 n and choose Hermitian representatives { P x : x ∈ F 2 2 n } \{P_x:x\in\mathbb{F}_2^{2n}\} { P x : x ∈ F 2 2 n } of the Pauli group modulo phase, with P 0 = 1 P_0=\mathbb{1} P 0 = 1 . The complete family is
A n : = { P x : x ∈ F 2 2 n ∖ { 0 } } , (76) \mathcal{A}_n:=\{P_x:x\in\mathbb{F}_2^{2n}\setminus\{0\}\}, \tag*{(76)} A n := { P x : x ∈ F 2 2 n ∖ { 0 }} , (76)
containing d 2 − 1 d^2-1 d 2 − 1 observables.
For x = ( p , q ) x=(p,q) x = ( p , q ) and y = ( p ′ , q ′ ) y=(p',q') y = ( p ′ , q ′ ) , the binary symplectic form ω ( x , y ) = p ⋅ q ′ + q ⋅ p ′ \omega(x,y)=p\cdot q'+q\cdot p' ω ( x , y ) = p ⋅ q ′ + q ⋅ p ′ determines commutation: P x P y = ( − 1 ) ω ( x , y ) P y P x P_xP_y=(-1)^{\omega(x,y)}P_yP_x P x P y = ( − 1 ) ω ( x , y ) P y P x [66 ] . Thus the anticommutativity graph is the symplectic graph G n : = Sp ( 2 n , 2 ) G_n:=\operatorname{Sp}(2n,2) G n := Sp ( 2 n , 2 ) , with nonzero Pauli labels as vertices and adjacency given by ω ( x , y ) = 1 \omega(x,y)=1 ω ( x , y ) = 1 .
The Pauli operators form an orthogonal operator basis, tr ( P x P y ) = d δ x y \operatorname{tr}(P_xP_y)=d\delta_{xy} tr ( P x P y ) = d δ x y . Expanding ρ \rho ρ in this basis therefore gives tr ( ρ 2 ) = 1 d ∑ x ∣ tr ( ρ P x ) ∣ 2 \operatorname{tr}(\rho^2)=\frac{1}{d}\sum_x\lvert\operatorname{tr}(\rho P_x)\rvert^2 tr ( ρ 2 ) = d 1 ∑ x ∣ tr ( ρ P x ) ∣ 2 . Since P 0 = 1 P_0=\mathbb{1} P 0 = 1 and tr ( ρ ) = 1 \operatorname{tr}(\rho)=1 tr ( ρ ) = 1 ,
∑ x ≠ 0 ∣ tr ( ρ P x ) ∣ 2 = d tr ( ρ 2 ) − 1 ≤ d − 1. \sum_{x\ne0}\lvert\operatorname{tr}(\rho P_x)\rvert^2=d\operatorname{tr}(\rho^2)-1\le d-1. x = 0 ∑ ∣ tr ( ρ P x ) ∣ 2 = d tr ( ρ 2 ) − 1 ≤ d − 1.
As in the Majorana case, averaging profiles and reducing their coordinates preserves this bound. Hence every s ∈ G G n s\in\mathcal{G}_{G_n} s ∈ G G n satisfies
∑ x ≠ 0 s x 2 ≤ d − 1. (77) \sum_{x\ne0}s_x^2\le d-1. \tag*{(77)} x = 0 ∑ s x 2 ≤ d − 1. (77)
Every pure state profile saturates this bound and therefore lies on the Pareto boundary of G G n \mathcal{G}_{G_n} G G n . Cauchy–Schwarz gives
h G n ( w ) ≤ d − 1 ∥ w ∥ 2 , (78) h_{G_n}(w)\le\sqrt{d-1}\lVert w\rVert_2, \tag*{(78)} h G n ( w ) ≤ d − 1 ∥ w ∥ 2 , (78)
with equality if and only if there exists a pure state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ whose absolute Pauli expectations are proportional to w w w . Thus every pure state is optimal for a suitable weighted sharpness objective, attained by its Pauli-orbit parent.
We now turn to uniform sharpness. Clifford conjugations act transitively on the nonidentity Paulis, so G n G_n G n is vertex-transitive and
η ( G n ) = 1 d 2 − 1 max ρ ∑ x ≠ 0 ∣ tr ( ρ P x ) ∣ . (79) \eta(G_n)=\frac{1}{d^2-1}\max_{\rho}\sum_{x\ne0}\lvert\operatorname{tr}(\rho P_x)\rvert. \tag*{(79)} η ( G n ) = d 2 − 1 1 ρ max x = 0 ∑ ∣ tr ( ρ P x )∣ . (79)
Setting s x = η s_x=\eta s x = η in Eq. (77) gives η ( G n ) ≤ 1 / d + 1 \eta(G_n)\leq1/\sqrt{d+1} η ( G n ) ≤ 1/ d + 1 . Saturating this bound requires a pure state whose nonidentity Pauli expectations all have magnitude 1 / d + 1 1/\sqrt{d+1} 1/ d + 1 . This is exactly the condition for its Pauli orbit to form a SIC.
Proposition 9. For the complete n n n -qubit Pauli family,
η ( G n ) ≤ 1 d + 1 . (80) \eta(G_n)\leq\frac{1}{\sqrt{d+1}}. \tag*{(80)} η ( G n ) ≤ d + 1 1 . (80) Equality holds if and only if a Pauli-covariant SIC exists; equivalently, if and only if a parent attaining the optimal uniform sharpness can be chosen as a single Pauli orbit. If ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ is a SIC fiducial, then
E ψ ( x ) = 1 d P x ∣ ψ ⟩ ⟨ ψ ∣ P x † , x ∈ F 2 2 n , (81) E_\psi(x)=\frac{1}{d}P_x|\psi\rangle\langle\psi|P_x^\dagger,\qquad x\in\mathbb{F}_2^{2n}, \tag*{(81)} E ψ ( x ) = d 1 P x ∣ ψ ⟩ ⟨ ψ ∣ P x † , x ∈ F 2 2 n , (81) is an optimal parent with uniform sharpness 1 / d + 1 1/\sqrt{d+1} 1/ d + 1 .
Proof. By Eq. (79) , Cauchy–Schwarz and Pauli orthogonality give
η ( G n ) ≤ 1 d 2 − 1 ( d 2 − 1 ) ( d − 1 ) = 1 d + 1 . \eta(G_n)\leq\frac{1}{d^2-1}\sqrt{(d^2-1)(d-1)}=\frac{1}{\sqrt{d+1}}. η ( G n ) ≤ d 2 − 1 1 ( d 2 − 1 ) ( d − 1 ) = d + 1 1 .
Equality holds if and only if a maximising state can be chosen pure with ∣ ⟨ ψ ∣ P x ∣ ψ ⟩ ∣ 2 = 1 d + 1 |\langle\psi|P_x|\psi\rangle|^2=\frac{1}{d+1} ∣ ⟨ ψ ∣ P x ∣ ψ ⟩ ∣ 2 = d + 1 1 for x ≠ 0 x\ne0 x = 0 . Since P x † P y P_x^\dagger P_y P x † P y is proportional to P x + y P_{x+y} P x + y , this is exactly the condition that the Pauli orbit of ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ form a SIC [46 ] . The orbit construction of Theorem 1 then gives Eq. (81) .
Finally, if a parent attaining the optimal uniform sharpness is generated by a single Pauli orbit, Corollary 6 gives a seed ρ \rho ρ with ∣ tr ( ρ P x ) ∣ = η ( G n ) |\operatorname{tr}(\rho P_x)|=\eta(G_n) ∣ tr ( ρ P x ) ∣ = η ( G n ) for every x ≠ 0 x\ne0 x = 0 . Hence ρ \rho ρ maximises Eq. (79) and is pure by Appendix § 0.1 . Pauli orthogonality then gives ( d 2 − 1 ) η ( G n ) 2 = d − 1 (d^2-1)\eta(G_n)^2=d-1 ( d 2 − 1 ) η ( G n ) 2 = d − 1 , so the bound is saturated and the seed obeys the SIC condition above. □
Pauli-covariant SICs of this type exist exactly for n = 1 n=1 n = 1 and n = 3 n=3 n = 3 [67 ] , giving the tetrahedral and Hoggar SICs [46 , 68 ] . In particular, the Hoggar SIC gives an optimal 64-outcome parent for all 63 nonidentity three-qubit Paulis, with sharpness 1 / 3 1/3 1/3 .
When no Pauli-covariant SIC exists, no single Pauli orbit attains the optimal uniform sharpness. Nevertheless, take any state maximising Eq. (79) and form the orbit POVMs generated by its Clifford conjugates. Mixing these POVMs as in Theorem 3 gives every marginal the sharpness η ( G n ) \eta(G_n) η ( G n ) .
Discussion
Joint measurability is generally formulated as a search over the effects of a parent POVM, where the number of effects grows exponentially with the number of measurements. For Pauli observables, the present results replace this by a state-space problem: absolute Pauli expectation values determine the full compatibility region, and the same states generate explicit parent measurements through Pauli conjugations and classical post-processing. This region also determines the optimal worst-case total-variation error tradeoffs for jointly measurable binary approximations, and the full nonuniform tradeoffs under standard noise models.
This correspondence has several consequences. The full compatibility problem depends only on the anticommutativity graph, rather than on the particular Pauli realisation. The parent effects need not be treated as independent optimisation variables, but can be organised into symmetry-related orbits generated by a bounded number of seed states. Optimal sharpness tradeoffs are determined by spectral problems for signed Pauli Hamiltonians, whose ground states provide seeds for attaining parents.
The framework also reveals the role of magic in accessing the full compatibility region. Stabilizer seeds generate exactly the stable-set polytope of the anti-commutativity graph, so nonstabilizer resources are necessary to attain the full region. We quantified the maximal sharpness advantage and related it to the reduced robustness of magic. For several structured families, including highly symmetric ones, the framework yields explicit descriptions of the compatibility region and corresponding optimal joint measurements.
Our results also make it clear where the remaining difficulty lies when constructing optimal joint measurements. To construct a parent at a specified point on the Pareto boundary, one must find ground states of the relevant signed Pauli Hamiltonians and choose an ensemble whose averaged profile equals the desired sharpness vector. This suggests several natural questions, including how many seed orbits are genuinely required for a general graph, when a single orbit suffices, and which graph families admit tractable spectral descriptions of their compatibility regions. For estimation tasks, a further question is how to choose the seed ensemble, and hence the parent measurement, to balance implementation costs against statistical errors.
Finally, it is useful to distinguish what properties of Pauli observables are determined purely by their anticommutativity graph. The full joint numerical range can depend on algebraic relations among commuting observables that the graph does not capture [33]. These relations also play an essential role in Pauli contextuality [69 , 70 , 71 ] and in the reduced robustness of magic [38 ] , where they constrain the allowed signed Pauli expectation values. By contrast, quantities built from absolute or squared expectation values can exhibit stronger graph invariance [57 ] [32]. Our results establish this invariance for the full compatibility region and the tradeoff regions under the noise models considered here.
Acknowledgements
We acknowledge support from INFN through the project “QUANTUM” and from the Italian funding within the “Budget MUR - Dipartimenti di Eccellenza 2023–2027” - Quantum Sensing and Modelling for One-Health (QuaSi-ModO). We acknowledge support from Projects PN-RIC Q-SUD (Q-SUD B99H26000380007) and PN-RIC QUAN-TAS (SYNERGIA B99H26000410007). PF acknowledges support from the Italian National Group of Mathematical Physics (GNFM-INdAM). This work was supported in part by a grant of access to OpenAI models through the ChatGPT for Academic Researchers program. AI assistance was used in preparing figures, checking and developing proofs, and copyediting.
References
Appendix A: Graph-Clifford representations and Pauli conjugation symmetries
We describe the irreducible representations of the graph-Clifford relations and derive the Pauli-conjugation identities used in the orbit construction of Sec. III. We begin by recalling the decomposition of the graph-Clifford algebra into a direct sum of full matrix algebras [41 ] , which determines these irreducible representations; see also [72 ] . Appendix B uses this representation structure to show that the state-space condition in Eq. (14) is independent of the realisation and to transfer parent measurements between realisations.
Canonical representation and sign-change group
Let G = ( V , E ) G=(V,E) G = ( V , E ) be an anti-commutativity graph with adjacency matrix B G B_G B G over F 2 \mathbb{F}_2 F 2 . We use the binary rank r r r and nullity ν 2 ( G ) = ∣ V ∣ − r \nu_2(G)=|V|-r ν 2 ( G ) = ∣ V ∣ − r defined in Eq. (3) . Consider the universal complex graph-Clifford algebra C ( G ) \mathcal{C}(G) C ( G ) , generated by abstract self-adjoint unitaries A v A_v A v subject only to the graph-Clifford relations of Sec. II 2. Here “universal” means that we impose no additional algebraic relations that might hold in a particular physical realisation. The ordered monomials A z A^z A z therefore satisfy
A z A z ′ = ( − 1 ) z T B G z ′ A z ′ A z , z , z ′ ∈ F 2 V . A^z A^{z'} = (-1)^{z^{\mathsf T}B_Gz'} A^{z'}A^z,\qquad z,z'\in\mathbb{F}_2^V. A z A z ′ = ( − 1 ) z T B G z ′ A z ′ A z , z , z ′ ∈ F 2 V .
Thus the binary form z T B G z ′ z^{\mathsf T}B_Gz' z T B G z ′ records whether two monomials commute or anticommute.
Since B G B_G B G is alternating over F 2 \mathbb{F}_2 F 2 , i.e., symmetric with zero diagonal, its rank r r r is even. The normal form for an alternating bilinear form gives an invertible binary matrix T T T such that
T T B G T = ( ⨁ j = 1 r / 2 ( 0 1 1 0 ) ) ⊕ 0 ν 2 ( G ) . T^{\mathsf T}B_GT=\left(\bigoplus_{j=1}^{r/2}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right)\oplus0_{\nu_2(G)}. T T B G T = j = 1 ⨁ r /2 ( 0 1 1 0 ) ⊕ 0 ν 2 ( G ) .
Each column of T T T labels a monomial, which we take as a new generator. Each 2 × 2 2\times2 2 × 2 block corresponds to an anticommuting pair, while generators belonging to different blocks commute. The ν 2 ( G ) \nu_2(G) ν 2 ( G ) columns corresponding to the zero block lie in ker B G \ker B_G ker B G , so their monomials commute with every generator and are central.
Every monomial squares to ± 1 \pm1 ± 1 , so multiplying it by a suitable phase makes it a self-adjoint involution. Denote the resulting anticommuting pairs by P j , Q j P_j,Q_j P j , Q j , j = 1 , … , r / 2 j=1,\ldots,r/2 j = 1 , … , r /2 , and the central involutions by C ℓ C_\ell C ℓ , ℓ = 1 , … , ν 2 ( G ) \ell=1,\ldots,\nu_2(G) ℓ = 1 , … , ν 2 ( G ) . Because the columns of T T T form a basis of F 2 V \mathbb{F}_2^V F 2 V , every original generator A v A_v A v can be recovered, up to a fixed phase, as a product of the new generators. The change of generators is therefore invertible and gives an equivalent set of generators for C ( G ) \mathcal{C}(G) C ( G ) .
Each pair P j , Q j P_j,Q_j P j , Q j satisfies the same relations as the single-qubit Pauli operators X , Z X,Z X , Z and generates M 2 ( C ) M_2(\mathbb{C}) M 2 ( C ) . Since different pairs commute, together they generate a tensor product of r / 2 r/2 r /2 copies of M 2 ( C ) M_2(\mathbb{C}) M 2 ( C ) . In an irreducible representation, each central involution must be scalar, so C ℓ = λ ℓ 1 C_\ell=\lambda_\ell\mathbf{1} C ℓ = λ ℓ 1 with λ ℓ ∈ { ± 1 } \lambda_\ell\in\{\pm1\} λ ℓ ∈ { ± 1 } . To see that every choice of these signs occurs, represent P j , Q j P_j,Q_j P j , Q j by X , Z X,Z X , Z on the j j j th of r / 2 r/2 r /2 qubits and set C ℓ = λ ℓ 1 C_\ell=\lambda_\ell\mathbf{1} C ℓ = λ ℓ 1 . These operators satisfy the relations among the new generators, and reversing the change of generators gives a representation of the original graph-Clifford relations. Thus no constraint links the choices of the signs λ ℓ \lambda_\ell λ ℓ .
For each sign vector λ ∈ { ± 1 } ν 2 ( G ) \lambda\in\{\pm1\}^{\nu_2(G)} λ ∈ { ± 1 } ν 2 ( G ) , fixing these central values leaves the full matrix algebra on r / 2 r/2 r /2 qubits. Consequently,
C ( G ) ≅ ⨁ λ ∈ { ± 1 } ν 2 ( G ) M 2 r / 2 ( C ) . \mathcal{C}(G)\cong\bigoplus_{\lambda\in\{\pm1\}^{\nu_2(G)}}M_{2^{r/2}}(\mathbb{C}). C ( G ) ≅ λ ∈ { ± 1 } ν 2 ( G ) ⨁ M 2 r /2 ( C ) .
In particular, every irreducible realisation has dimension d G = 2 r / 2 d_G=2^{r/2} d G = 2 r /2 . Two irreducible realisations are unitarily equivalent if and only if their central signs agree, or equivalently if all central monomials have the same scalar values in both realisations. The inverse change of generators also realises the original generators as signed Pauli strings on r / 2 r/2 r /2 qubits.
For the remainder of this appendix, we fix a canonical irreducible representation and use the operators U x U_x U x defined in Sec. II 2 and the characters χ v \chi_v χ v of Eq. (4) . If k ∈ ker B G k\in\ker B_G k ∈ ker B G , then A k A^k A k commutes with every generator and is therefore scalar by irreducibility. Changing the representative of x ∈ K G x\in K_G x ∈ K G consequently multiplies U x U_x U x only by a phase. Moreover, U x U y = μ ( x , y ) U x + y U_xU_y=\mu(x,y)U_{x+y} U x U y = μ ( x , y ) U x + y with μ ( x , y ) ∈ { ± 1 } \mu(x,y)\in\{\pm1\} μ ( x , y ) ∈ { ± 1 } , so multiplication follows the group law of K G K_G K G up to a phase. Thus the U x U_x U x form a projective representation of K G K_G K G . Since these phases cancel under conjugation, the maps X ↦ U x X U x † X\mapsto U_xXU_x^\dagger X ↦ U x X U x † define a group action on the full operator space, independent of the chosen representatives. Their action on the generators follows from the monomial commutation rule and is given in Eq. (5) .
Monomial basis and conjugation averages
Lemma A.1. The monomials { U x : x ∈ K G } \{U_x:x\in K_G\} { U x : x ∈ K G } form an orthogonal unitary basis of the operator space of the canonical irreducible representation:
tr ( U x † U y ) = d G δ x , y . (82) \operatorname{tr}(U_x^\dagger U_y)=d_G\delta_{x,y}. \tag*{(82)} tr ( U x † U y ) = d G δ x , y . (82) Their conjugation action is
U x U y U x † = ( − 1 ) x ~ T B G y ~ U y . (83) U_xU_yU_x^\dagger=(-1)^{\widetilde{x}^{\mathsf T}B_G\widetilde{y}}U_y. \tag*{(83)} U x U y U x † = ( − 1 ) x T B G y U y . (83) where x ~ , y ~ ∈ F 2 V \widetilde{x},\widetilde{y}\in\mathbb{F}_2^V x , y ∈ F 2 V represent x , y ∈ K G x,y\in K_G x , y ∈ K G . The exponent is independent of these choices.
Proof. For z ∈ F 2 V ∖ ker B G z\in\mathbb{F}_2^V\setminus\ker B_G z ∈ F 2 V ∖ ker B G , choose v ∈ V v\in V v ∈ V such that ( B G z ) v = 1 (B_Gz)_v=1 ( B G z ) v = 1 . Then A z A^z A z anticommutes with A v A_v A v , so tr ( A z ) = tr ( A v A z A v ) = − tr ( A z ) \operatorname{tr}(A^z)=\operatorname{tr}(A_vA^zA_v)=-\operatorname{tr}(A^z) tr ( A z ) = tr ( A v A z A v ) = − tr ( A z ) . Hence tr ( A z ) = 0 \operatorname{tr}(A^z)=0 tr ( A z ) = 0 .
If x ≠ y x\ne y x = y in K G K_G K G , then x ~ + y ~ ∉ ker B G \widetilde{x}+\widetilde{y}\notin\ker B_G x + y ∈ / ker B G , and U x † U y U_x^\dagger U_y U x † U y is, up to phase, the monomial A x ~ + y ~ A^{\widetilde{x}+\widetilde{y}} A x + y . Its trace therefore vanishes. For x = y x=y x = y , unitarity gives tr ( U x † U x ) = d G \operatorname{tr}(U_x^\dagger U_x)=d_G tr ( U x † U x ) = d G . This proves Eq. (82) . Since ∣ K G ∣ = d G 2 |K_G|=d_G^2 ∣ K G ∣ = d G 2 , these orthogonal monomials form a basis of the operator space.
Equation Eq. (83) follows from the monomial commutation rule in Appendix A1. Adding an element of ker B G \ker B_G ker B G to either representative leaves the exponent unchanged. □ \square □
The vertex characters χ v \chi_v χ v need not be distinct. If χ u = χ v \chi_u=\chi_v χ u = χ v , then A u A v A_uA_v A u A v is unchanged by every conjugation U x U_x U x and hence commutes with every generator. It is therefore scalar by irreducibility, and self-adjointness and unitarity give A u = ± A v A_u=\pm A_v A u = ± A v . An isolated vertex similarly satisfies A v = ± 1 A_v=\pm\mathbb{1} A v = ± 1 , since it commutes with every generator.
Lemma A.2. The character identities in Eq. (9) hold for every operator X X X on the canonical irreducible space:
1 ∣ K G ∣ ∑ x ∈ K G U x X U x † = tr ( X ) d G 1 , \frac{1}{|\mathcal{K}_G|}\sum_{x\in\mathcal{K}_G}U_x X U_x^\dagger=\frac{\operatorname{tr}(X)}{d_G}\mathbb{1}, ∣ K G ∣ 1 x ∈ K G ∑ U x X U x † = d G tr ( X ) 1 , 1 ∣ K G ∣ ∑ x ∈ K G χ v ( x ) U x X U x † = tr ( A v X ) d G A v . \frac{1}{|\mathcal{K}_G|}\sum_{x\in\mathcal{K}_G}\chi_v(x)U_x X U_x^\dagger=\frac{\operatorname{tr}(A_vX)}{d_G}A_v. ∣ K G ∣ 1 x ∈ K G ∑ χ v ( x ) U x X U x † = d G tr ( A v X ) A v .
Proof. Conjugation by any U y U_y U y permutes the summands of the first average, since U y U x U_yU_x U y U x differs from U x + y U_{x+y} U x + y only by a phase. The average therefore commutes with every U y U_y U y . Each generator A v A_v A v is a phase multiple of one of these monomials, so the average commutes with every generator and is scalar by irreducibility. Taking its trace gives the first identity.
For the second identity, Eq. (5) gives U x A v = χ v ( x ) A v U x U_xA_v=\chi_v(x)A_vU_x U x A v = χ v ( x ) A v U x . Together with A v 2 = 1 A_v^2=\mathbb{1} A v 2 = 1 , this yields
1 ∣ K G ∣ ∑ x ∈ K G χ v ( x ) U x X U x † = A v ( 1 ∣ K G ∣ ∑ x ∈ K G U x ( A v X ) U x † ) = tr ( A v X ) d G A v , \frac{1}{|\mathcal{K}_G|}\sum_{x\in\mathcal{K}_G}\chi_v(x)U_x X U_x^\dagger
=A_v\left(\frac{1}{|\mathcal{K}_G|}\sum_{x\in\mathcal{K}_G}U_x(A_vX)U_x^\dagger\right)
=\frac{\operatorname{tr}(A_vX)}{d_G}A_v, ∣ K G ∣ 1 x ∈ K G ∑ χ v ( x ) U x X U x † = A v ( ∣ K G ∣ 1 x ∈ K G ∑ U x ( A v X ) U x † ) = d G tr ( A v X ) A v ,
where the last equality applies the first identity to A v X A_vX A v X .
Appendix B: Independence of the physical representation
We show that the state-space condition in Eq. (14) and the compatibility region defined in Eq. (13) are independent of the chosen finite-dimensional realisation of the graph-Clifford relations. The key fact, stated in Lemma B.1, is that every such realisation decomposes, up to a unitary change of basis, into copies of a fixed canonical irreducible family with some generator signs changed. We use this decomposition to compare ensembles of states in different representations and to construct parent measurements with the same sharpnesses.
Lemma B.1. Fix a canonical irreducible realisation { A v } v ∈ V \{A_v\}_{v\in V} { A v } v ∈ V of G G G on C d G \mathbb{C}^{d_G} C d G . For any finite-dimensional realisation { A v ′ } v ∈ V \{A'_v\}_{v\in V} { A v ′ } v ∈ V of the same graph-Clifford relations on H ′ \mathcal{H}' H ′ , there exist a finite-dimensional Hilbert space K \mathcal{K} K , commuting self-adjoint unitaries { D v } v ∈ V \{D_v\}_{v\in V} { D v } v ∈ V on K \mathcal{K} K , and a unitary W : H ′ ⟶ C d G ⊗ K W:\mathcal{H}'\longrightarrow\mathbb{C}^{d_G}\otimes\mathcal{K} W : H ′ ⟶ C d G ⊗ K such that
W A v ′ W † = A v ⊗ D v , v ∈ V . (84) WA'_vW^\dagger=A_v\otimes D_v,\qquad v\in V. \tag*{(84)} W A v ′ W † = A v ⊗ D v , v ∈ V . (84)
Proof. Theorem 2 of [33] states that, after a unitary change of basis, every realisation is a fixed standard irreducible family tensored with commuting self-adjoint unitaries. Applying this decomposition to the fixed canonical irreducible family leaves a one-dimensional multiplicity space, so the additional factors are scalar signs. Multiplying the corresponding factors for the physical realisation by these signs gives Eq. (84) relative to the chosen family { A v } \{A_v\} { A v } .
In this decomposition, the physical realisation is a direct sum of canonical copies, with possibly different generator signs in different sectors. The operators D v D_v D v record these signs; they are commuting self-adjoint unitaries because they act as ± 1 \pm\mathbb{1} ± 1 on each sector.
The factor K \mathcal{K} K records the sector labels and their multiplicities within the original physical Hilbert space. We take { P z } \{P_z\} { P z } to be the nonzero joint spectral projections of the commuting operators { D v } v ∈ V \{D_v\}_{v\in V} { D v } v ∈ V , so that
∑ z P z = 1 K , D v P z = d v ( z ) P z , d v ( z ) ∈ { ± 1 } . (85) \sum_z P_z=\mathbb{1}_{\mathcal{K}},\qquad D_vP_z=d_v(z)P_z,\qquad d_v(z)\in\{\pm1\}. \tag*{(85)} z ∑ P z = 1 K , D v P z = d v ( z ) P z , d v ( z ) ∈ { ± 1 } . (85)
Thus, in sector z z z , the observables act as d v ( z ) A v d_v(z)A_v d v ( z ) A v on the canonical factor and as the identity on the multiplicity factor.
The next lemma adapts the state-decomposition argument of [33, Appendix C] to absolute expectation-value profiles.
Lemma B.2. For every state ρ ′ \rho' ρ ′ on H ′ \mathcal{H}' H ′ , there is an ensemble { q z , ρ z } \{q_z,\rho_z\} { q z , ρ z } of states on the canonical irreducible space such that
∣ tr ( ρ ′ A v ′ ) ∣ ≤ ∑ z q z ∣ tr ( ρ z A v ) ∣ , v ∈ V . (86) \left|\operatorname{tr}(\rho'A'_v)\right|\leq\sum_z q_z\left|\operatorname{tr}(\rho_zA_v)\right|,\qquad v\in V. \tag*{(86)} ∣ tr ( ρ ′ A v ′ ) ∣ ≤ z ∑ q z ∣ tr ( ρ z A v ) ∣ , v ∈ V . (86)
Conversely, every absolute expectation-value profile in the canonical representation is attained by a state on H ′ \mathcal{H}' H ′ .
Proof. Set ρ : = W ρ ′ W † \rho:=W\rho'W^\dagger ρ := W ρ ′ W † , a state on C d G ⊗ K \mathbb{C}^{d_G}\otimes\mathcal{K} C d G ⊗ K , and define q z : = tr ( ρ ( 1 ⊗ P z ) ) q_z:=\operatorname{tr}(\rho(\mathbb{1}\otimes P_z)) q z := tr ( ρ ( 1 ⊗ P z )) . For each z z z with q z > 0 q_z>0 q z > 0 , let
ρ z : = 1 q z tr 2 ( ( 1 ⊗ P z ) ρ ( 1 ⊗ P z ) ) . (87) \rho_z:=\frac{1}{q_z}\operatorname{tr}_2\left((\mathbb{1}\otimes P_z)\rho(\mathbb{1}\otimes P_z)\right). \tag*{(87)} ρ z := q z 1 tr 2 ( ( 1 ⊗ P z ) ρ ( 1 ⊗ P z ) ) . (87)
where tr 2 \operatorname{tr}_2 tr 2 denotes the partial trace over K \mathcal{K} K . Each ρ z \rho_z ρ z is a state, and ∑ z q z = 1 \sum_zq_z=1 ∑ z q z = 1 ; labels with q z = 0 q_z=0 q z = 0 may be omitted.
The observables A v ⊗ D v A_v\otimes D_v A v ⊗ D v are block diagonal with respect to the projections 1 ⊗ P z \mathbb{1}\otimes P_z 1 ⊗ P z , so coherences between different sectors do not contribute to their expectations. Using Eqs. (84) and (85) , we therefore obtain
tr ( ρ ′ A v ′ ) = ∑ z q z d v ( z ) tr ( ρ z A v ) . (88) \operatorname{tr}(\rho'A'_v)=\sum_zq_zd_v(z)\operatorname{tr}(\rho_zA_v). \tag*{(88)} tr ( ρ ′ A v ′ ) = z ∑ q z d v ( z ) tr ( ρ z A v ) . (88)
The triangle inequality gives Eq. (86) .
For the converse, let σ \sigma σ be any canonical state. Choose a state τ z \tau_z τ z supported in the range of a nonzero P z P_z P z and set σ ′ : = W † ( σ ⊗ τ z ) W \sigma':=W^\dagger(\sigma\otimes\tau_z)W σ ′ := W † ( σ ⊗ τ z ) W . Then
tr ( σ ′ A v ′ ) = tr ( σ A v ) tr ( τ z D v ) = d v ( z ) tr ( σ A v ) . (89) \operatorname{tr}(\sigma'A'_v)=\operatorname{tr}(\sigma A_v)\operatorname{tr}(\tau_zD_v)=d_v(z)\operatorname{tr}(\sigma A_v). \tag*{(89)} tr ( σ ′ A v ′ ) = tr ( σ A v ) tr ( τ z D v ) = d v ( z ) tr ( σ A v ) . (89)
Taking absolute values shows that σ ′ \sigma' σ ′ has the same absolute expectation-value profile as σ \sigma σ .
Applying the first part of Lemma B.2 to each state of an ensemble, and multiplying its original weight by the corresponding q z q_z q z , gives a canonical ensemble whose averaged absolute expectations are at least as large. For each canonical state, the converse construction gives a state on H ′ \mathcal{H}' H ′ with the same absolute expectation values. Thus the inequalities in Eq. (14) are feasible for the same sharpness vectors in every realisation. Equivalently, averaging profiles and then reducing individual coordinates gives the same set, although the profiles attainable by individual states may differ.
The next lemma extends the representation-independence argument of [35 Proposition 2] from the uniform threshold to arbitrary sharpness vectors, with explicit maps between parent measurements.
Lemma B.3. Let { A v ′ } v ∈ V \{A'_v\}_{v\in V} { A v ′ } v ∈ V be any finite-dimensional realisation of the same graph-Clifford relations as the canonical family { A v } v ∈ V \{A_v\}_{v\in V} { A v } v ∈ V . A sharpness vector s ∈ [ 0 , 1 ] V s\in[0,1]^V s ∈ [ 0 , 1 ] V admits a parent measurement for { A v } v ∈ V \{A_v\}_{v\in V} { A v } v ∈ V if and only if it admits a parent measurement for { A v ′ } v ∈ V \{A'_v\}_{v\in V} { A v ′ } v ∈ V .
Proof. Suppose first that { E ( a ) } a ∈ { ± 1 } V \{E(a)\}_{a\in\{\pm1\}^V} { E ( a ) } a ∈ { ± 1 } V is a parent in the canonical representation satisfying Eq. (2) . In sector z z z , the generator signs d v ( z ) d_v(z) d v ( z ) can be implemented by reversing the corresponding outcome labels. Define d ( z ) a : = ( d v ( z ) a v ) v ∈ V d(z)a := (d_v(z)a_v)_{v\in V} d ( z ) a := ( d v ( z ) a v ) v ∈ V and set
E ~ ( a ) : = ∑ z E ( d ( z ) a ) ⊗ P z . (90) \widetilde{E}(a) := \sum_z E(d(z)a) \otimes P_z. \tag*{(90)} E ( a ) := z ∑ E ( d ( z ) a ) ⊗ P z . (90)
These effects are positive. For each z z z , the map a ↦ d ( z ) a a\mapsto d(z)a a ↦ d ( z ) a is a permutation of { ± 1 } V \{\pm1\}^V { ± 1 } V , so the effects sum to 1 ⊗ 1 K \mathbb{1}\otimes\mathbb{1}_{\mathcal{K}} 1 ⊗ 1 K . Relabelling b = d ( z ) a b=d(z)a b = d ( z ) a gives
∑ a a v E ~ ( a ) = ∑ z d v ( z ) ( ∑ b b v E ( b ) ) ⊗ P z = s v A v ⊗ D v . (91) \sum_a a_v\widetilde{E}(a) = \sum_z d_v(z)\left(\sum_b b_vE(b)\right)\otimes P_z
= s_vA_v\otimes D_v. \tag*{(91)} a ∑ a v E ( a ) = z ∑ d v ( z ) ( b ∑ b v E ( b ) ) ⊗ P z = s v A v ⊗ D v . (91)
Conjugating these effects by W † W^\dagger W † gives a parent in the physical realisation.
Conversely, after conjugating a physical parent by W W W , let { E ′ ( a ) } a ∈ { ± 1 } V \{E'(a)\}_{a\in\{\pm1\}^V} { E ′ ( a ) } a ∈ { ± 1 } V denote its effects on C d G ⊗ K \mathbb{C}^{d_G}\otimes\mathcal{K} C d G ⊗ K . They satisfy
∑ a a v E ′ ( a ) = s v A v ⊗ D v . (92) \sum_a a_vE'(a)=s_vA_v\otimes D_v. \tag*{(92)} a ∑ a v E ′ ( a ) = s v A v ⊗ D v . (92)
We compress this parent to one canonical copy in any nonzero sector and reverse the same outcome signs. Choose a unit vector ζ z \zeta_z ζ z in the range of a nonzero P z P_z P z and define the isometry V z ψ : = ψ ⊗ ζ z V_z\psi:=\psi\otimes\zeta_z V z ψ := ψ ⊗ ζ z . Set
E z ( a ) : = V z † E ′ ( d ( z ) a ) V z . (93) E_z(a):=V_z^\dagger E'(d(z)a)V_z. \tag*{(93)} E z ( a ) := V z † E ′ ( d ( z ) a ) V z . (93)
These effects are positive and sum to V z † V z = 1 V_z^\dagger V_z=\mathbb{1} V z † V z = 1 . Relabelling a ↦ d ( z ) a a\mapsto d(z)a a ↦ d ( z ) a and using D v ζ z = d v ( z ) ζ z D_v\zeta_z=d_v(z)\zeta_z D v ζ z = d v ( z ) ζ z gives
∑ a a v E z ( a ) = s v d v ( z ) V z † ( A v ⊗ D v ) V z = s v A v . (94) \sum_a a_vE_z(a)=s_vd_v(z)V_z^\dagger(A_v\otimes D_v)V_z
=s_vA_v. \tag*{(94)} a ∑ a v E z ( a ) = s v d v ( z ) V z † ( A v ⊗ D v ) V z = s v A v . (94)
Thus { E z ( a ) } \{E_z(a)\} { E z ( a )} is a parent in the canonical representation.
Comparing every realisation with the fixed canonical family shows that the compatibility region depends only on the anti-commutativity graph G G G , as stated in Corollary 1.
Appendix C: Orbit bounds and binary nullity
The Carathéodory bound N o r b ≤ ∣ V ∣ + 1 N_{\mathrm{orb}}\leq|V|+1 N orb ≤ ∣ V ∣ + 1 in Corollary 2 follows from Theorem 1, as explained in the main text. Here we prove the nullity bound by combining seed states whose expectation signs can be aligned by Pauli conjugation. Once the signs agree, mixing the states preserves their averaged absolute expectation values.
The nullity bound
Fix a canonical irreducible realisation A = { A v } v ∈ V \mathcal{A}=\{A_v\}_{v\in V} A = { A v } v ∈ V on C d G \mathbb{C}^{d_G} C d G . For s ∈ G G s\in\mathcal{G}_G s ∈ G G , Theorem 1 supplies a finite ensemble { p j , ρ j } \{p_j,\rho_j\} { p j , ρ j } satisfying s ≤ ∑ j p j C A ( ρ j ) s\leq\sum_jp_j\mathcal{C}_{\mathcal{A}}(\rho_j) s ≤ ∑ j p j C A ( ρ j ) . For each seed, choose z j ∈ F 2 V z_j\in\mathbb{F}_2^V z j ∈ F 2 V such that
tr ( ρ j A v ) = ( − 1 ) ( z j ) v C A ( ρ j ) v , v ∈ V , \operatorname{tr}(\rho_jA_v)=(-1)^{(z_j)_v}\mathcal{C}_{\mathcal{A}}(\rho_j)_v,\qquad v\in V, tr ( ρ j A v ) = ( − 1 ) ( z j ) v C A ( ρ j ) v , v ∈ V ,
with either sign allowed when the expectation vanishes.
By Eq. (5) , conjugating a seed by U x U_x U x changes its sign vector from z j z_j z j to z j + B G x z_j+B_Gx z j + B G x , without changing its absolute profile. The available sign changes form S G : = im B G S_G:=\operatorname{im}B_G S G := im B G . There are ∣ F 2 V / S G ∣ = 2 ν 2 ( G ) |\mathbb{F}_2^V/S_G|=2^{\nu_2(G)} ∣ F 2 V / S G ∣ = 2 ν 2 ( G ) cosets, and signs within each coset can therefore be aligned.
For each coset C C C containing some z j z_j z j with p j > 0 p_j>0 p j > 0 , choose a representative z C z_C z C . Whenever z j ∈ C z_j\in C z j ∈ C , choose x j ∈ K G x_j\in\mathcal{K}_G x j ∈ K G such that B G x ~ j = z j + z C B_G\widetilde{x}_j=z_j+z_C B G x j = z j + z C and set ρ ~ j : = U x j ρ j U x j † \widetilde{\rho}_j:=U_{x_j}\rho_jU_{x_j}^{\dagger} ρ j := U x j ρ j U x j † . Then
tr ( ρ ~ j A v ) = ( − 1 ) ( z C ) v C A ( ρ j ) v . \operatorname{tr}(\widetilde{\rho}_jA_v)=(-1)^{(z_C)_v}\mathcal{C}_{\mathcal{A}}(\rho_j)_v. tr ( ρ j A v ) = ( − 1 ) ( z C ) v C A ( ρ j ) v .
Define
q C : = ∑ j : z j ∈ C p j , σ C : = 1 q C ∑ j : z j ∈ C p j ρ ~ j . q_C:=\sum_{j:z_j\in C}p_j,\qquad
\sigma_C:=\frac{1}{q_C}\sum_{j:z_j\in C}p_j\widetilde{\rho}_j. q C := j : z j ∈ C ∑ p j , σ C := q C 1 j : z j ∈ C ∑ p j ρ j .
All expectations being averaged have the same sign in each coordinate. Hence
q C C A ( σ C ) = ∑ j : z j ∈ C p j C A ( ρ j ) . q_C\mathcal{C}_{\mathcal{A}}(\sigma_C)=\sum_{j:z_j\in C}p_j\mathcal{C}_{\mathcal{A}}(\rho_j). q C C A ( σ C ) = j : z j ∈ C ∑ p j C A ( ρ j ) .
Summing over the occupied cosets gives
∑ C q C C A ( σ C ) = ∑ j p j C A ( ρ j ) ≥ s . \sum_Cq_C\mathcal{C}_{\mathcal{A}}(\sigma_C)=\sum_jp_j\mathcal{C}_{\mathcal{A}}(\rho_j)\geq s. C ∑ q C C A ( σ C ) = j ∑ p j C A ( ρ j ) ≥ s .
Thus one mixed seed per occupied coset suffices. Applying the parent construction in Eq. (15) , together with the Carathéodory bound, proves
N o r b ≤ min { ∣ V ∣ + 1 , 2 ν 2 ( G ) } . (95) N_{\mathrm{orb}} \le\min\left\{|V|+1,2^{\nu_2(G)}\right\}. \tag*{(95)} N orb ≤ min { ∣ V ∣ + 1 , 2 ν 2 ( G ) } . (95)
If B G B_G B G is nonsingular over F 2 \mathbb{F}_2 F 2 , all sign vectors lie in one coset and a single orbit suffices.
Each orbit POVM has ∣ K G ∣ = d G 2 |K_G|=d_G^2 ∣ K G ∣ = d G 2 labelled outcomes. Consequently, every compatible sharpness vector admits a parent in the canonical representation with
∣ Ω ∣ ≤ d G 2 min { ∣ V ∣ + 1 , 2 ν 2 ( G ) } . (96) |\Omega| \le d_G^2 \min\left\{|V|+1,2^{\nu_2(G)}\right\}. \tag*{(96)} ∣Ω∣ ≤ d G 2 min { ∣ V ∣ + 1 , 2 ν 2 ( G ) } . (96)
Here Ω \Omega Ω records the seed and orbit labels. Classical post-processing, including output noise when needed, gives the required binary marginals without increasing the number of POVM outcomes.
The same cosets reduce the spectral optimisation in Eq. (35). Writing a v ( z ) = ( − 1 ) z v a_v(z)=(-1)^{z_v} a v ( z ) = ( − 1 ) z v , we have
U x H w , a ( z ) U x † = H w , a ( z + B G x ~ ) . U_x H_{w,a}(z)U_x^\dagger=H_{w,a}(z+B_G\widetilde{x}). U x H w , a ( z ) U x † = H w , a ( z + B G x ) .
It therefore suffices to check one signing per coset.
Refinement by complex conjugation
Choose a basis in which the canonical generators are Pauli strings, and let ∗ * ∗ denote entrywise complex conjugation. Then A v ∗ = ( − 1 ) κ v A v A_v^*=(-1)^{\kappa_v}A_v A v ∗ = ( − 1 ) κ v A v for some κ ∈ F 2 V \kappa\in\mathbb{F}_2^V κ ∈ F 2 V , and
tr ( ρ ∗ A v ) = ( − 1 ) κ v tr ( ρ A v ) . \operatorname{tr}(\rho^* A_v)=(-1)^{\kappa_v}\operatorname{tr}(\rho A_v). tr ( ρ ∗ A v ) = ( − 1 ) κ v tr ( ρ A v ) .
Thus complex conjugation changes a seed’s sign vector from z z z to z + κ z+\kappa z + κ while preserving its absolute profile.
If κ ∉ S G \kappa\notin S_G κ ∈ / S G , this transformation pairs distinct cosets C C C and C + κ C+\kappa C + κ . Conjugating the seeds in one coset of each pair places their sign vectors in the other coset. Pauli conjugation then makes the expectation values have the same sign for each observable. Mixing these states gives one seed for each pair of cosets. Consequently,
N o r b ≤ min { ∣ V ∣ + 1 , 2 ν 2 ( G ) − 1 } . (97) N_{\mathrm{orb}} \le\min\left\{|V|+1,2^{\nu_2(G)-1}\right\}. \tag*{(97)} N orb ≤ min { ∣ V ∣ + 1 , 2 ν 2 ( G ) − 1 } . (97)
The factor 2 ν 2 ( G ) 2^{\nu_2(G)} 2 ν 2 ( G ) in Eq. (96) can likewise be replaced by 2 ν 2 ( G ) − 1 2^{\nu_2(G)-1} 2 ν 2 ( G ) − 1 .
A sufficient graph condition for this improvement is the existence of k ∈ ker B G k\in\ker B_G k ∈ ker B G whose support induces an odd number of edges. Indeed, A k A^k A k is scalar by irreducibility, so ( A k ) ∗ = ( A k ) † (A^k)^*=(A^k)^\dagger ( A k ) ∗ = ( A k ) † . Reversing its factors contributes one minus sign per induced edge, whereas conjugating the factors individually contributes ( − 1 ) κ ⋅ k (-1)^{\kappa\cdot k} ( − 1 ) κ ⋅ k . Hence
( − 1 ) κ ⋅ k A k = ( A k ) ∗ = ( A k ) † = − A k . (-1)^{\kappa\cdot k}A^k=(A^k)^*=(A^k)^\dagger=-A^k. ( − 1 ) κ ⋅ k A k = ( A k ) ∗ = ( A k ) † = − A k .
Thus κ ⋅ k = 1 \kappa\cdot k=1 κ ⋅ k = 1 , and S G = ( ker B G ) ⊥ S_G=(\ker B_G)^\perp S G = ( ker B G ) ⊥ implies κ ∉ S G \kappa\notin S_G κ ∈ / S G .
For an odd cycle C 2 m + 1 C_{2m+1} C 2 m + 1 , m ≥ 1 m\ge1 m ≥ 1 , the kernel equation B G k = 0 B_Gk=0 B G k = 0 gives k j + 2 = k j k_{j+2}=k_j k j + 2 = k j , with indices taken cyclically. The odd cycle length forces all coordinates to be equal, so the kernel is spanned by the all-ones vector. Its support induces 2 m + 1 2m+1 2 m + 1 edges. Thus ν 2 ( C 2 m + 1 ) = 1 \nu_2(C_{2m+1})=1 ν 2 ( C 2 m + 1 ) = 1 , and Eq. (97) gives N o r b ≤ 1 N_{\mathrm{orb}}\le1 N orb ≤ 1 , proving the odd-cycle assertion in Corollary 2.
The paired signing classes also have identical spectra, since
H w , a ( z + κ ) = H w , a ∗ ( z ) . H_{w,a}(z+\kappa)=H_{w,a}^*(z). H w , a ( z + κ ) = H w , a ∗ ( z ) .
Under the same graph condition, at most 2 ν 2 ( G ) − 1 2^{\nu_2(G)-1} 2 ν 2 ( G ) − 1 representatives therefore suffice in the spectral optimisation.
The combined seeds may be mixed; decomposing them into pure states need not preserve these bounds on the number of orbit POVMs. Complex conjugation is used only to specify a new seed, not as an operation on the unknown input state.
Appendix D: Automorphisms and symmetry reduction
Fix a canonical irreducible family A = { A v } v ∈ V \mathcal{A}=\{A_v\}_{v\in V} A = { A v } v ∈ V on C d G \mathbb{C}^{d_G} C d G , with ∣ V ∣ ≥ 1 |V|\ge1 ∣ V ∣ ≥ 1 , and let G = Aut ( G ) \mathfrak{G}=\operatorname{Aut}(G) G = Aut ( G ) . We first show that graph automorphisms permute the attainable absolute expectation-value profiles. We then use this symmetry to reduce the weight minimisation in Eq. (37) .
Lemma D.1. For every π ∈ G \pi\in\mathfrak{G} π ∈ G , there exists a unitary W π W_\pi W π such that, for every state ρ \rho ρ , the state ρ π : = W π ρ W π † \rho^\pi:=W_\pi\rho W_\pi^\dagger ρ π := W π ρ W π † satisfies
c A ( ρ π ) v = c A ( ρ ) π − 1 ( v ) , v ∈ V . (98) c_{\mathcal{A}}(\rho^\pi)_v=c_{\mathcal{A}}(\rho)_{\pi^{-1}(v)},\qquad v\in V. \tag*{(98)} c A ( ρ π ) v = c A ( ρ ) π − 1 ( v ) , v ∈ V . (98)
Proof. The permuted family { A π ( v ) } v ∈ V \{A_{\pi(v)}\}_{v\in V} { A π ( v ) } v ∈ V is an irreducible realisation of the same graph-Clifford relations. Since both families act on C d G \mathbb{C}^{d_G} C d G , the multiplicity space in Lemma B.1 is one-dimensional. Hence there exist a unitary W π W_\pi W π and signs σ π , v ∈ { ± 1 } \sigma_{\pi,v}\in\{\pm1\} σ π , v ∈ { ± 1 } such that
W π A v W π † = σ π , v A π ( v ) . (99) W_\pi A_v W_\pi^\dagger=\sigma_{\pi,v}A_{\pi(v)}. \tag*{(99)} W π A v W π † = σ π , v A π ( v ) . (99)
It follows that tr ( ρ π A π ( v ) ) = σ π , v tr ( ρ A v ) \operatorname{tr}(\rho^\pi A_{\pi(v)})=\sigma_{\pi,v}\operatorname{tr}(\rho A_v) tr ( ρ π A π ( v ) ) = σ π , v tr ( ρ A v ) . Taking absolute values and relabelling v v v gives Eq. (98) .
The unitaries may be chosen separately for each π \pi π ; no group representation property of π ↦ W π \pi\mapsto W_\pi π ↦ W π is required. □
For w ∈ Δ ( V ) w\in\Delta(V) w ∈ Δ ( V ) , define ( π w ) v : = w π − 1 ( v ) (\pi w)_v:=w_{\pi^{-1}(v)} ( π w ) v := w π − 1 ( v ) . Equation (D1) gives ( π w ) ⋅ c A ( ρ π ) = w ⋅ c A ( ρ ) (\pi w)\cdot c_{\mathcal{A}}(\rho^\pi)=w\cdot c_{\mathcal{A}}(\rho) ( π w ) ⋅ c A ( ρ π ) = w ⋅ c A ( ρ ) . As ρ \rho ρ ranges over all states, so does ρ π \rho^\pi ρ π . Maximising over ρ \rho ρ and using Eq. (35) therefore yields
h G ( π w ) = h G ( w ) . (100) h_G(\pi w)=h_G(w). \tag*{(100)} h G ( π w ) = h G ( w ) . (100)
We now apply the standard averaging argument for convex optimisation [25, Appendix B.1]. For a subgroup Λ ≤ G \Lambda\le\mathfrak{G} Λ ≤ G , define w ˉ : = 1 ∣ Λ ∣ ∑ π ∈ Λ π w \bar{w}:=\frac{1}{|\Lambda|}\sum_{\pi\in\Lambda}\pi w w ˉ := ∣Λ∣ 1 ∑ π ∈ Λ π w . This vector belongs to Δ ( V ) \Delta(V) Δ ( V ) and is fixed by every element of Λ \Lambda Λ , so it is constant on each vertex orbit of Λ \Lambda Λ . Convexity of the support function and Eq. (100) give
h G ( w ˉ ) ≤ 1 ∣ Λ ∣ ∑ π ∈ Λ h G ( π w ) = h G ( w ) . (101) h_G(\bar{w})\le\frac{1}{|\Lambda|}\sum_{\pi\in\Lambda}h_G(\pi w)=h_G(w). \tag*{(101)} h G ( w ˉ ) ≤ ∣Λ∣ 1 π ∈ Λ ∑ h G ( π w ) = h G ( w ) . (101)
Averaging a minimiser therefore gives another minimiser. Thus the minimisation in Eq. (37) may be restricted to weights that are constant on each vertex orbit of Λ \Lambda Λ .
If G G G is vertex-transitive, taking Λ = G \Lambda= G Λ = G gives w ˉ = 1 / ∣ V ∣ \bar{w} = 1/|V| w ˉ = 1/∣ V ∣ , so uniform weights are optimal. The corresponding parent construction is given in Theorem 3.
Reduced magic and sharpness advantage
We use the characterisation of the reduced stabilizer polytope in [37 Theorem 3] and [38 ] to prove the equality in Proposition 5. The distinction is that joint measurability depends on absolute Pauli expectation values, whereas reduced magic retains their signs.
For the signed correlation vector b A ( ρ ) = ( tr ( ρ A v ) ) v ∈ V \boldsymbol{b}_{\mathcal{A}}(\rho) = (\operatorname{tr}(\rho A_v))_{v\in V} b A ( ρ ) = ( tr ( ρ A v ) ) v ∈ V , define the reduced stabilizer polytope
P s t a b ( A ) : = conv { b A ( σ ) : σ a pure stabilizer state } . (102) \mathcal{P}_{\mathrm{stab}}(\mathcal{A}) := \operatorname{conv}\{\boldsymbol{b}_{\mathcal{A}}(\sigma): \sigma\ \text{a pure stabilizer state}\}. \tag*{(102)} P stab ( A ) := conv { b A ( σ ) : σ a pure stabilizer state } . (102)
In the decomposition defining RoM A \operatorname{RoM}_{\mathcal{A}} RoM A in Sec. V 3, the coefficients are real and sum to one, but may be negative. One may equivalently use points of P s t a b ( A ) \mathcal{P}_{\mathrm{stab}}(\mathcal{A}) P stab ( A ) : expanding each point into pure stabilizer correlations does not increase the total absolute weight.
For a pure stabilizer state, the support of b A ( σ ) \boldsymbol{b}_{\mathcal{A}}(\sigma) b A ( σ ) is an independent set of G G G , but Pauli product relations can constrain its signs. Discarding these sign constraints gives the symmetric graph relaxation [38 ]
P ^ G : = { b ∈ [ − 1 , 1 ] V : ∣ b ∣ ∈ STAB ( G ) } , (103) \widehat{\mathcal{P}}_G := \{\boldsymbol{b}\in[-1,1]^V: |\boldsymbol{b}|\in\operatorname{STAB}(G)\}, \tag*{(103)} P G := { b ∈ [ − 1 , 1 ] V : ∣ b ∣ ∈ STAB ( G )} , (103)
where ∣ b ∣ |\boldsymbol{b}| ∣ b ∣ is taken componentwise. When A \mathcal{A} A has no active dependencies, meaning that no nonempty mutually commuting subset has product proportional to 1 \mathbb{1} 1 , the relaxation is exact (see [37 Theorem 3] and [38 ] ):
P s t a b ( A ) = P ^ G . (104) \mathcal{P}_{\mathrm{stab}}(\mathcal{A}) = \widehat{\mathcal{P}}_G. \tag*{(104)} P stab ( A ) = P G . (104)
Under this assumption, set t = R G ( ρ ) ≥ 1 t = R_G(\rho) \ge1 t = R G ( ρ ) ≥ 1 and p = b A ( ρ ) / t p = \boldsymbol{b}_{\mathcal{A}}(\rho)/t p = b A ( ρ ) / t . By Eq. (52) , ∣ p ∣ = c A ( ρ ) / t ∈ STAB ( G ) |p| = \boldsymbol{c}_{\mathcal{A}}(\rho)/t \in\operatorname{STAB}(G) ∣ p ∣ = c A ( ρ ) / t ∈ STAB ( G ) , so Eq. (104) gives p , − p ∈ P s t a b ( A ) p,-p \in\mathcal{P}_{\mathrm{stab}}(\mathcal{A}) p , − p ∈ P stab ( A ) . The identity
b A ( ρ ) = t + 1 2 p + 1 − t 2 ( − p ) (105) \boldsymbol{b}_{\mathcal{A}}(\rho) = \frac{t+1}{2}p + \frac{1-t}{2}(-p) \tag*{(105)} b A ( ρ ) = 2 t + 1 p + 2 1 − t ( − p ) (105)
has coefficients whose sum is one and whose absolute values sum to t t t . Expanding p p p and − p -p − p into pure stabilizer mixtures therefore gives RoM A ( ρ ) ≤ t = R G ( ρ ) \operatorname{RoM}_{\mathcal{A}}(\rho) \le t = R_G(\rho) RoM A ( ρ ) ≤ t = R G ( ρ ) . The reverse inequality is Eq. (56) , so if A \mathcal{A} A has no active dependencies,
RoM A ( ρ ) = R G ( ρ ) . (106) \operatorname{RoM}_{\mathcal{A}}(\rho) = R_G(\rho). \tag*{(106)} RoM A ( ρ ) = R G ( ρ ) . (106)
Replacing P s t a b ( A ) \mathcal{P}_{\mathrm{stab}}(\mathcal{A}) P stab ( A ) by P ^ G \widehat{\mathcal{P}}_G P G in this optimisation gives minimum total absolute weight R G ( ρ ) R_G(\rho) R G ( ρ ) , even when active dependencies are present.
Quadratic Majorana Hamiltonians and Gaussian seeds
We collect the standard facts about quadratic Majorana Hamiltonians and fermionic Gaussian states needed in Sec. VI. Further details can be found, for example, in [63 , 73 ] [17]. We first bound the energy using the covariance matrix, then diagonalise the Hamiltonian and construct a pure Gaussian state attaining the bound. We also apply this construction to the saturation criterion for regular root graphs in Corollary 9.
Spectral optima and Gaussian seeds
Let M = 2 ⌈ N / 2 ⌉ M = 2\lceil N/2\rceil M = 2 ⌈ N /2 ⌉ and choose Hermitian Majorana operators Γ 1 , … , Γ M \Gamma_1,\ldots,\Gamma_M Γ 1 , … , Γ M satisfying { Γ j , Γ k } = 2 δ j k 1 \{\Gamma_j,\Gamma_k\} = 2\delta_{jk}\mathbb{1} { Γ j , Γ k } = 2 δ j k 1 . We work on the full Fock space of M / 2 M/2 M /2 fermionic modes, of dimension 2 M / 2 2^{M/2} 2 M /2 , without restricting to a fixed fermion-parity sector. When N N N is odd, Γ N + 1 \Gamma_{N+1} Γ N + 1 is an unused auxiliary Majorana. For a real skew-symmetric N × N N\times N N × N matrix S S S , consider
H ( S ) = i 2 ∑ j , k = 1 N S j k Γ j Γ k . (107) H(S) = \frac{\mathrm{i}}{2}\sum_{j,k=1}^{N} S_{jk}\Gamma_j\Gamma_k. \tag*{(107)} H ( S ) = 2 i j , k = 1 ∑ N S j k Γ j Γ k . (107)
Set S ^ = S ⊕ 0 M − N \widehat{S} = S\oplus0_{M-N} S = S ⊕ 0 M − N . The added zero row and column, when present, change neither the Hamiltonian nor the trace norm: H ( S ^ ) = H ( S ) H(\widehat{S}) = H(S) H ( S ) = H ( S ) and ∥ S ^ ∥ 1 = ∥ S ∥ 1 \|\widehat{S}\|_1 = \|S\|_1 ∥ S ∥ 1 = ∥ S ∥ 1 .
For any state ρ \rho ρ , define its covariance matrix on all M M M Majoranas by
( Q ρ ) j k = i 2 tr ( ρ [ Γ j , Γ k ] ) . (108) (Q_\rho)_{jk} = \frac{\mathrm{i}}{2}\operatorname{tr}\bigl(\rho[\Gamma_j,\Gamma_k]\bigr). \tag*{(108)} ( Q ρ ) j k = 2 i tr ( ρ [ Γ j , Γ k ] ) . (108)
This matrix is real and skew-symmetric, with zero diagonal and ( Q ρ ) j k = i tr ( ρ Γ j Γ k ) (Q_\rho)_{jk} = \mathrm{i}\operatorname{tr}(\rho\Gamma_j\Gamma_k) ( Q ρ ) j k = i tr ( ρ Γ j Γ k ) for j ≠ k j\ne k j = k . It satisfies ∥ Q ρ ∥ ∞ ≤ 1 \|Q_\rho\|_\infty\le1 ∥ Q ρ ∥ ∞ ≤ 1 . Indeed, for x , y ∈ R M x,y\in\mathbb{R}^M x , y ∈ R M , let the operator Γ ( x ) : = ∑ j x j Γ j \Gamma(x):=\sum_j x_j\Gamma_j Γ ( x ) := ∑ j x j Γ j obeys Γ ( x ) 2 = ∥ x ∥ 2 2 1 \Gamma(x)^2=\|x\|_2^2\mathbb{1} Γ ( x ) 2 = ∥ x ∥ 2 2 1 , so ∥ Γ ( x ) ∥ ∞ = ∥ x ∥ 2 \|\Gamma(x)\|_\infty=\|x\|_2 ∥Γ ( x ) ∥ ∞ = ∥ x ∥ 2 . The commutator norm bound therefore gives
∣ x T Q ρ y ∣ = 1 2 ∣ tr ( ρ [ Γ ( x ) , Γ ( y ) ] ) ∣ ≤ ∥ Γ ( x ) ∥ ∞ ∥ Γ ( y ) ∥ ∞ = ∥ x ∥ 2 ∥ y ∥ 2 . (109) \begin{aligned}
|x^{\mathsf{T}}Q_\rho y| = \frac{1}{2}\left|\operatorname{tr}\bigl(\rho[\Gamma(x),\Gamma(y)]\bigr)\right| \\
&\le\|\Gamma(x)\|_\infty\|\Gamma(y)\|_\infty= \|x\|_2\|y\|_2. \tag*{(109)}
\end{aligned} ∣ x T Q ρ y ∣ = 2 1 tr ( ρ [ Γ ( x ) , Γ ( y )] ) ≤ ∥Γ ( x ) ∥ ∞ ∥Γ ( y ) ∥ ∞ = ∥ x ∥ 2 ∥ y ∥ 2 . (109)
Using the covariance representation of the quadratic Hamiltonian and the inequality ∣ tr ( X T Y ) ∣ ≤ ∥ X ∥ ∞ ∥ Y ∥ 1 |\operatorname{tr}(X^{\mathsf{T}}Y)|\le\|X\|_\infty\|Y\|_1 ∣ tr ( X T Y ) ∣ ≤ ∥ X ∥ ∞ ∥ Y ∥ 1 , we obtain
tr ( ρ H ( S ) ) = 1 2 tr ( Q ρ T S ^ ) ≤ 1 2 ∥ Q ρ ∥ ∞ ∥ S ^ ∥ 1 ≤ 1 2 ∥ S ∥ 1 . (110) \begin{aligned}
\operatorname{tr}(\rho H(S)) = \frac{1}{2}\operatorname{tr}(Q_\rho^{\mathsf{T}}\widehat{S}) \\
&\le\frac{1}{2}\|Q_\rho\|_\infty\|\widehat{S}\|_1 \le\frac{1}{2}\|S\|_1. \tag*{(110)}
\end{aligned} tr ( ρ H ( S )) = 2 1 tr ( Q ρ T S ) ≤ 2 1 ∥ Q ρ ∥ ∞ ∥ S ∥ 1 ≤ 2 1 ∥ S ∥ 1 . (110)
To construct a state saturating the bound, we use the real skew-symmetric normal form. There is a real orthogonal matrix O ∈ O ( M ) O\in O(M) O ∈ O ( M ) , satisfying O T O = 1 M O^{\mathsf{T}}O = \mathbb{1}_M O T O = 1 M , such that
S ^ = O [ ⨁ k = 1 M / 2 σ k J 2 ] O T , J 2 = ( 0 1 − 1 0 ) , σ k ≥ 0. (111) \widehat{S} = O\left[\bigoplus_{k=1}^{M/2}\sigma_k J_2\right]O^{\mathsf{T}},\qquad J_2=\begin{pmatrix}0&1\\-1&0\end{pmatrix},\qquad\sigma_k\ge0. \tag*{(111)} S = O k = 1 ⨁ M /2 σ k J 2 O T , J 2 = ( 0 − 1 1 0 ) , σ k ≥ 0. (111)
Define the transformed Majorana operators by
Γ ~ j : = ∑ ℓ = 1 M O ℓ j Γ ℓ . \widetilde{\Gamma}_j := \sum_{\ell=1}^{M} O_{\ell j}\Gamma_\ell. Γ j := ℓ = 1 ∑ M O ℓ j Γ ℓ .
They remain Hermitian and satisfy { Γ ~ j , Γ ~ k } = 2 ( O T O ) j k 1 = 2 δ j k 1 \{\widetilde{\Gamma}_j,\widetilde{\Gamma}_k\}=2(O^{\mathsf T}O)_{jk}\mathbb{1}=2\delta_{jk}\mathbb{1} { Γ j , Γ k } = 2 ( O T O ) j k 1 = 2 δ j k 1 . Substituting Γ ℓ = ∑ j O ℓ j Γ ~ j \Gamma_\ell=\sum_j O_{\ell j}\widetilde{\Gamma}_j Γ ℓ = ∑ j O ℓ j Γ j into the Hamiltonian gives
H ( S ) = i 2 ∑ j , k = 1 M ( O T S ^ O ) j k Γ ~ j Γ ~ k = ∑ k = 1 M / 2 σ k i Γ ~ 2 k − 1 Γ ~ 2 k . (112) \begin{aligned}
H(S)=\frac{i}{2}\sum_{j,k=1}^{M}(O^{\mathsf T}\widehat{S}O)_{jk}\widetilde{\Gamma}_j\widetilde{\Gamma}_k \\
&=\sum_{k=1}^{M/2}\sigma_k\,i\widetilde{\Gamma}_{2k-1}\widetilde{\Gamma}_{2k}. \tag*{(112)}
\end{aligned} H ( S ) = 2 i j , k = 1 ∑ M ( O T S O ) j k Γ j Γ k = k = 1 ∑ M /2 σ k i Γ 2 k − 1 Γ 2 k . (112)
These quadratic terms commute because they involve disjoint Majorana pairs.
Their eigenvalues have the usual occupation-number interpretation. The fermionic annihilation operators f k : = ( Γ ~ 2 k − 1 + i Γ ~ 2 k ) / 2 f_k:=(\widetilde{\Gamma}_{2k-1}+i\widetilde{\Gamma}_{2k})/2 f k := ( Γ 2 k − 1 + i Γ 2 k ) /2 have occupation operators n k = f k † f k n_k=f_k^\dagger f_k n k = f k † f k , with i Γ ~ 2 k − 1 Γ ~ 2 k = 2 n k − 1 i\widetilde{\Gamma}_{2k-1}\widetilde{\Gamma}_{2k}=2n_k-1 i Γ 2 k − 1 Γ 2 k = 2 n k − 1 . Thus Eq. (112) is a sum of independent terms σ k ( 2 n k − 1 ) \sigma_k(2n_k-1) σ k ( 2 n k − 1 ) . On the full Fock space, the occupations can be chosen independently from { 0 , 1 } \{0,1\} { 0 , 1 } . Choosing every occupation to be one, including those with σ k = 0 \sigma_k=0 σ k = 0 , gives the rank-one projector
ρ ⋆ = ∏ k = 1 M / 2 1 + i Γ ~ 2 k − 1 Γ ~ 2 k 2 . (113) \rho_\star=\prod_{k=1}^{M/2}\frac{\mathbb{1}+i\widetilde{\Gamma}_{2k-1}\widetilde{\Gamma}_{2k}}{2}. \tag*{(113)} ρ ⋆ = k = 1 ∏ M /2 2 1 + i Γ 2 k − 1 Γ 2 k . (113)
This occupation-number state is a pure Gaussian state [73 ] . In the transformed basis, its covariance is ⨁ k J 2 \bigoplus_k J_2 ⨁ k J 2 . Returning to the original basis gives
Q ⋆ = O [ ⨁ k = 1 M / 2 J 2 ] O T . (114) Q_\star=O\left[\bigoplus_{k=1}^{M/2}J_2\right]O^{\mathsf T}. \tag*{(114)} Q ⋆ = O k = 1 ⨁ M /2 J 2 O T . (114)
Writing ∣ S ^ ∣ = ( S ^ T S ^ ) 1 / 2 |\widehat{S}|=(\widehat{S}^{\mathsf T}\widehat{S})^{1/2} ∣ S ∣ = ( S T S ) 1/2 , the block forms in Eqs. (111) and (F8) give Q ⋆ 2 = − 1 M Q_\star^2=-\mathbb{1}_M Q ⋆ 2 = − 1 M and Q ⋆ T S ^ = ∣ S ^ ∣ Q_\star^{\mathsf T}\widehat{S}=|\widehat{S}| Q ⋆ T S = ∣ S ∣ . Thus ρ ⋆ \rho_\star ρ ⋆ attains the bound in Eq. (110) . Each σ k \sigma_k σ k occurs twice among the singular values of S ^ \widehat{S} S , so
tr ( ρ ⋆ H ( S ) ) = λ max ( H ( S ) ) = ∑ k = 1 M / 2 σ k = 1 2 ∥ S ∥ 1 . (115) \operatorname{tr}(\rho_\star H(S))=\lambda_{\max}(H(S))=\sum_{k=1}^{M/2}\sigma_k=\frac{1}{2}\|S\|_1. \tag*{(115)} tr ( ρ ⋆ H ( S )) = λ m a x ( H ( S )) = k = 1 ∑ M /2 σ k = 2 1 ∥ S ∥ 1 . (115)
In particular, ρ ⋆ \rho_\star ρ ⋆ is a ground state of H ( − S ) = − H ( S ) H(-S)=-H(S) H ( − S ) = − H ( S ) . Replacing every occupation by its complement reverses the energy, so the spectrum is symmetric about zero and ∥ H ( S ) ∥ ∞ = λ max ( H ( S ) ) \|H(S)\|_\infty=\lambda_{\max}(H(S)) ∥ H ( S ) ∥ ∞ = λ m a x ( H ( S )) . When S S S is nonsingular, N = M N=M N = M and all σ k > 0 \sigma_k>0 σ k > 0 . Maximal energy then requires every occupation to be one, making ρ ⋆ \rho_\star ρ ⋆ unique.
The covariance can also be expressed through the polar decomposition. For nonsingular S S S , its block form gives
Q ⋆ = S ∣ S ∣ − 1 = S ( − S 2 ) − 1 / 2 , (116) Q_\star=S|S|^{-1}=S(-S^2)^{-1/2}, \tag*{(116)} Q ⋆ = S ∣ S ∣ − 1 = S ( − S 2 ) − 1/2 , (116)
so S = Q ⋆ ∣ S ∣ S=Q_\star|S| S = Q ⋆ ∣ S ∣ . For singular S ^ \widehat{S} S , this formula determines the covariance only on the orthogonal complement of the kernel. Let Z : = ker S ^ ⊆ R M \mathcal{Z}:=\ker\widehat{S}\subseteq\mathbb{R}^M Z := ker S ⊆ R M and let P Z P_{\mathcal{Z}} P Z be the orthogonal projector onto Z \mathcal{Z} Z . Define Q ^ 0 \widehat{Q}_0 Q 0 to equal S ^ ( − S ^ 2 ) − 1 / 2 \widehat{S}(-\widehat{S}^2)^{-1/2} S ( − S 2 ) − 1/2 on Z ⊥ \mathcal{Z}^{\perp} Z ⊥ and to vanish on Z \mathcal{Z} Z . Then
Q ^ 0 2 = − ( 1 M − P Z ) , Q ^ 0 T S ^ = ∣ S ^ ∣ . (117) \widehat{Q}_0^2=-(\mathbb{1}_M-P_{\mathcal{Z}}),\qquad\widehat{Q}_0^{\mathsf T}\widehat{S}=|\widehat{S}|. \tag*{(117)} Q 0 2 = − ( 1 M − P Z ) , Q 0 T S = ∣ S ∣. (117)
The kernel has even dimension, since S ^ \widehat{S} S has even size and even rank. Choose a real skew-symmetric operator Q Z Q_{\mathcal{Z}} Q Z on Z \mathcal{Z} Z satisfying Q Z 2 = − 1 Z Q_{\mathcal{Z}}^2=-\mathbb{1}_{\mathcal{Z}} Q Z 2 = − 1 Z , and extend it by zero on Z ⊥ \mathcal{Z}^{\perp} Z ⊥ . The completion Q ⋆ = Q ^ 0 + Q Z Q_\star=\widehat{Q}_0+Q_{\mathcal{Z}} Q ⋆ = Q 0 + Q Z satisfies Q ⋆ 2 = − 1 M Q_\star^2=-\mathbb{1}_M Q ⋆ 2 = − 1 M and Q ⋆ T S ^ = ∣ S ^ ∣ Q_\star^{\mathsf T}\widehat{S}=|\widehat{S}| Q ⋆ T S = ∣ S ∣ . Every real skew-symmetric covariance with square − 1 -\mathbb{1} − 1 specifies a unique pure Gaussian state [73 ] , so this again gives a state saturating the bound in Eq. (110) . The freedom in Q Z Q_{\mathcal{Z}} Q Z corresponds to choosing a pure Gaussian state for the zero-energy fermionic modes. It leaves the energy unchanged but can change individual quadratic correlations.
For odd N N N with ker S \ker S ker S one-dimensional, the completion can preserve the entire covariance block on the original Majoranas. This is the case used for uniformly weighted odd cycles in Appendix G. Let u u u be a unit vector spanning ker S \ker S ker S , and let Q 0 Q_0 Q 0 equal S ( − S 2 ) − 1 / 2 S(-S^2)^{-1/2} S ( − S 2 ) − 1/2 on u ⊥ u^\perp u ⊥ and vanish on u u u . The kernel of S ^ = S ⊕ 0 \widehat{S}=S\oplus0 S = S ⊕ 0 is then spanned by ( u , 0 ) (u,0) ( u , 0 ) and the auxiliary coordinate. Pairing these two directions gives
Q ^ = ( Q 0 u − u T 0 ) . (118) \widehat{Q}=
\begin{pmatrix}
Q_0 & u\\
-u^{\mathsf T} & 0
\end{pmatrix}. \tag*{(118)} Q = ( Q 0 − u T u 0 ) . (118)
Since Q 0 u = 0 Q_0u=0 Q 0 u = 0 and Q 0 2 = − ( 1 N − u u T ) Q_0^2=-(\mathbb{1}_N-uu^{\mathsf T}) Q 0 2 = − ( 1 N − u u T ) , direct multiplication gives Q ^ 2 = − 1 N + 1 \widehat{Q}^2=-\mathbb{1}_{N+1} Q 2 = − 1 N + 1 and Q ^ T S ^ = ∣ S ∣ ⊕ 0 \widehat{Q}^{\mathsf T}\widehat{S}=|S|\oplus0 Q T S = ∣ S ∣ ⊕ 0 . It therefore specifies a pure Gaussian state ρ ⋆ \rho_\star ρ ⋆ attaining the largest eigenvalue of H ( S ) H(S) H ( S ) . Its upper-left block is Q 0 Q_0 Q 0 , so the original quadratic correlations are preserved, namely, i tr ( ρ ⋆ Γ j Γ k ) = ( Q 0 ) j k i\operatorname{tr}(\rho_\star\Gamma_j\Gamma_k)=(Q_0)_{jk} i tr ( ρ ⋆ Γ j Γ k ) = ( Q 0 ) j k , 1 ≤ j ≠ k ≤ N 1\leq j\ne k\leq N 1 ≤ j = k ≤ N .
Saturation for regular root graphs
We now prove Corollary 9. Recall that, for a finite simple Δ \Delta Δ -regular graph R = ( [ N ] , E ) R=([N],E) R = ([ N ] , E ) with Δ ≥ 1 \Delta\geq1 Δ ≥ 1 , the corollary states that η ( L ( R ) ) = 1 / Δ \eta(L(R))=1/\sqrt{\Delta} η ( L ( R )) = 1/ Δ if and only if R R R admits an orientation whose skew-adjacency matrix satisfies
S S T = Δ 1. SS^{\mathsf T}=\Delta\mathbb{1}. S S T = Δ1.
In this case, Q = S / Δ Q=S/\sqrt{\Delta} Q = S / Δ is the covariance of a balanced pure Gaussian seed whose orbit parent attains the optimal uniform sharpness. We also show that the construction gives a single-orbit parent in a canonical irreducible representation.
Proof. The Δ \Delta Δ edges incident at any vertex correspond to mutually anti-commuting observables, giving η ( L ( R ) ) ≤ 1 / Δ \eta(L(R))\leq1/\sqrt{\Delta} η ( L ( R )) ≤ 1/ Δ . The necessity of S S T = Δ 1 SS^{\mathsf T}=\Delta\mathbb{1} S S T = Δ1 for equality follows from [35 ] .
Conversely, suppose an orientation has a skew-adjacency matrix S S S satisfying this condition. Then S S S is nonsingular, so N N N is even, and ∣ S ∣ = Δ 1 |S|=\sqrt{\Delta}\mathbb{1} ∣ S ∣ = Δ 1 . Thus
Q = S Δ = S ∣ S ∣ − 1 Q=\frac{S}{\sqrt{\Delta}}=S|S|^{-1} Q = Δ S = S ∣ S ∣ − 1
e n d s m i d = 1 {ends_mid=1} e n d s m i d = 1
is the polar covariance in Eq. (116) . It specifies a pure Gaussian state ρ \rho ρ attaining the largest eigenvalue of H ( S ) H(S) H ( S ) . Since S u v ∈ { ± 1 } S_{uv} \in\{\pm1\} S uv ∈ { ± 1 } on every edge,
∣ tr ( ρ A e ) ∣ = 1 Δ , e ∈ E . \left|\operatorname{tr}(\rho A_e)\right| = \frac{1}{\sqrt{\Delta}}, \qquad e \in E. ∣ tr ( ρ A e ) ∣ = Δ 1 , e ∈ E .
The orbit POVM in Eq. (58) therefore attains the upper bound.
It remains to obtain a single orbit in a canonical representation. Since S S S is nonsingular, all coefficients σ k \sigma_k σ k in Eq. (112) are positive, so the maximal-energy state ρ \rho ρ is unique. Decompose the full space representation of the selected observables into irreducible summands. The Hamiltonian, being a linear combination of these observables, is block diagonal in this decomposition. Its unique maximal-energy eigenvector must lie in one summand: otherwise its nonzero components in different summands would give linearly independent eigenvectors with the same maximal energy. Restricting the observables to this summand preserves the balanced profile. The orbit construction of Theorem 1 then gives an optimal single-orbit parent in this canonical representation.
For the seed constructed above, the full Fock space parent in Eq. (58) is already optimal. The final part of the proof establishes the additional conclusion that a single canonical orbit attains the same sharpnesses. We restrict the seed and observables to an irreducible invariant subspace and then construct a new parent using Theorem 1. The single-orbit form is therefore established by this construction, rather than by simply restricting the original full-space POVM.
For cycles, a suitable subspace can instead be identified using fermion parity . The full Fock space splits into two parity sectors, spanned by occupation-number states with even and odd total occupation, respectively. Quadratic Majorana observables preserve both sectors, and each pure Gaussian seed is supported in one of them. A parity sector need not itself be irreducible. In Appendix G, we verify that the sector containing the constructed seed is irreducible.
Appendix G: Cycles
We verify that the Gaussian seeds specified in § 3.2 2 are balanced, so a single orbit attains the optimal uniform sharpness η ( C n ) \eta(C_n) η ( C n ) . We then show that the balanced seed may be taken in a canonical irreducible representation.
Let w ˉ = n − 1 ( 1 , … , 1 ) \bar{w}=n^{-1}(1,\ldots,1) w ˉ = n − 1 ( 1 , … , 1 ) and S n ( τ ) = n S ( τ ) S_n^{(\tau)}=nS^{(\tau)} S n ( τ ) = n S ( τ ) . At these weights, the maximum in Eq. (64) is attained by τ = − 1 \tau=-1 τ = − 1 for even n n n and by either sign for odd n n n [35 ] . We use τ = + 1 \tau=+1 τ = + 1 in the latter case.
Suppose first that n n n is even and set S = S n ( − 1 ) S=S_n^{(-1)} S = S n ( − 1 ) . This matrix is nonsingular, so the covariance Q Q Q in Eq. (60) defines a pure Gaussian state ρ ⋆ \rho_\star ρ ⋆ attaining the largest eigenvalue of H ( S ) H(S) H ( S ) .
To show that the absolute expectations are equal, let T T T be the signed cyclic shift with T j , j + 1 = 1 T_{j,j+1}=1 T j , j + 1 = 1 for j < n j<n j < n and T n , 1 = − 1 T_{n,1}=-1 T n , 1 = − 1 . Then S = T − T T S=T-T^{\mathsf{T}} S = T − T T and T S T T = S TST^{\mathsf{T}}=S T S T T = S . The formula for Q Q Q preserves this symmetry, giving T Q T T = Q TQT^{\mathsf{T}}=Q T Q T T = Q . Comparing entries gives Q j , j + 1 = Q j + 1 , j + 2 Q_{j,j+1}=Q_{j+1,j+2} Q j , j + 1 = Q j + 1 , j + 2 for j < n − 1 j<n-1 j < n − 1 and Q n − 1 , n = − Q n , 1 Q_{n-1,n}=-Q_{n,1} Q n − 1 , n = − Q n , 1 . Thus Q j , j + 1 = q Q_{j,j+1}=q Q j , j + 1 = q for all j < n j<n j < n and Q n , 1 = − q Q_{n,1}=-q Q n , 1 = − q , for some real q q q . Each term in H ( S ) H(S) H ( S ) therefore has expectation q q q , giving
n q = tr ( ρ ⋆ H ( S ) ) = 1 2 tr ( Q T S ) = 1 2 ∥ S ∥ 1 = n η ( C n ) . (119) \begin{aligned}
nq=\operatorname{tr}(\rho_\star H(S))=\frac{1}{2}\operatorname{tr}(Q^{\mathsf{T}}S) \\
&=\frac{1}{2}\lVert S\rVert_1=n\eta(C_n). \tag*{(119)}
\end{aligned} n q = tr ( ρ ⋆ H ( S )) = 2 1 tr ( Q T S ) = 2 1 ∥ S ∥ 1 = n η ( C n ) . (119)
Hence q = η ( C n ) > 0 q=\eta(C_n)>0 q = η ( C n ) > 0 .
For odd n n n , take S = S n ( + 1 ) S=S_n^{(+1)} S = S n ( + 1 ) . Its kernel is spanned by u = n − 1 / 2 ( 1 , … , 1 ) T u=n^{-1/2}(1,\ldots,1)^{\mathsf{T}} u = n − 1/2 ( 1 , … , 1 ) T . Let Q 0 Q_0 Q 0 equal S ( − S 2 ) − 1 / 2 S(-S^2)^{-1/2} S ( − S 2 ) − 1/2 on ( ker S ) ⊥ (\ker S)^\perp ( ker S ) ⊥ and vanish on the kernel. The cyclic shift with T n , 1 = 1 T_{n,1}=1 T n , 1 = 1 preserves S S S and hence Q 0 Q_0 Q 0 . The same entrywise comparison gives ( Q 0 ) j , j + 1 = ( Q 0 ) n , 1 = q (Q_0)_{j,j+1}=(Q_0)_{n,1}=q ( Q 0 ) j , j + 1 = ( Q 0 ) n , 1 = q for all j < n j<n j < n . Since Q 0 T S = ∣ S ∣ Q_0^{\mathsf{T}}S=|S| Q 0 T S = ∣ S ∣ , repeating the calculation in Eq. (119) gives q = η ( C n ) q=\eta(C_n) q = η ( C n ) .
The completion in Eq. (118) pairs the kernel direction u u u with the auxiliary Majorana. It gives a pure Gaussian covariance without changing the block on the original n n n Majoranas. Thus, for both even and odd n n n , the constructed state satisfies the balanced expectations in Eq. (66) .
To obtain a single canonical orbit, it remains to show that the parity sector containing the seed is irreducible. Including the auxiliary Majorana when n n n is odd, each parity sector has dimension 2 ⌈ n / 2 ⌉ − 1 2^{\lceil n/2\rceil-1} 2 ⌈ n /2 ⌉ − 1 . The kernel equation B C n k = 0 B C_n k=0 B C n k = 0 over F 2 \mathbb{F}_2 F 2 gives k j + 2 = k j k_{j+2}=k_j k j + 2 = k j , with indices taken cyclically, so ν 2 ( C n ) = 2 \nu_2(C_n)=2 ν 2 ( C n ) = 2 for even n n n and ν 2 ( C n ) = 1 \nu_2(C_n)=1 ν 2 ( C n ) = 1 for odd n n n . Thus each parity sector has dimension d C n = 2 ( n − ν 2 ( C n ) ) / 2 d_{C_n}=2^{(n-\nu_2(C_n))/2} d C n = 2 ( n − ν 2 ( C n )) /2 . Since every irreducible summand has this dimension by Appendix A, each parity sector is itself irreducible. Restricting the observables to the sector containing the seed preserves its expectation values, so Theorem 1 gives an optimal single-orbit parent in this canonical representation.
Appendix H: Paths
We prove Proposition 7, which establishes Conjecture 1 of [35 ] , and then derive the reflection-symmetric P 4 P_4 P 4 boundary slice. We use the path realisation of § 3.2 3 and the weighted support formula in Eq. (67) . The remaining step is to exhibit weights giving a matching upper bound. Throughout, we use the full Fock space convention of Appendix F.
Proof of the path threshold
We show that deleting one or two consecutive observables from an even cycle leaves the optimal uniform sharpness unchanged. Write
ℓ = m + 1 ≥ 2 , θ = π 2 ℓ , η 0 = 1 ℓ sin θ . (120) \ell= m+1 \ge2,\qquad\theta= \frac{\pi}{2\ell},\qquad\eta_0 = \frac{1}{\ell\sin\theta}. \tag*{(120)} ℓ = m + 1 ≥ 2 , θ = 2 ℓ π , η 0 = ℓ sin θ 1 . (120)
By Eq. (65) , η ( C 2 ℓ ) = η 0 \eta(C_{2\ell})=\eta_0 η ( C 2 ℓ ) = η 0 .
A parent for the cycle also measures any subfamily. Deleting one observable gives P 2 ℓ − 1 P_{2\ell-1} P 2 ℓ − 1 , and deleting an endpoint of this path gives P 2 ℓ − 2 P_{2\ell-2} P 2 ℓ − 2 . At each step, any uniform sharpness achievable before the deletion remains achievable afterwards. Hence
η 0 = η ( C 2 ℓ ) ≤ η ( P 2 ℓ − 1 ) ≤ η ( P 2 ℓ − 2 ) . (121) \eta_0=\eta(C_{2\ell})\le\eta(P_{2\ell-1})\le\eta(P_{2\ell-2}). \tag*{(121)} η 0 = η ( C 2 ℓ ) ≤ η ( P 2 ℓ − 1 ) ≤ η ( P 2 ℓ − 2 ) . (121)
Thus both paths can attain η 0 \eta_0 η 0 ; the question is whether removing observables allows a larger uniform sharpness. To show that it does not, it suffices to bound the threshold of the shorter path by η 0 \eta_0 η 0 . We will choose weights for P 2 ℓ − 2 P_{2\ell-2} P 2 ℓ − 2 whose support value is at most η 0 \eta_0 η 0 . Since the weights sum to one, the corresponding support inequality bounds every achievable uniform sharpness by η 0 \eta_0 η 0 , forcing equality throughout Eq. (121) .
Let β j : = sin ( j θ ) \beta_j:=\sin(j\theta) β j := sin ( j θ ) and choose
w j ⋆ = β j β j + 1 ℓ cos θ , j = 1 , … , 2 ℓ − 2. (122) w_j^\star=\frac{\beta_j\beta_{j+1}}{\ell\cos\theta},\qquad j=1,\ldots,2\ell-2. \tag*{(122)} w j ⋆ = ℓ cos θ β j β j + 1 , j = 1 , … , 2 ℓ − 2. (122)
Using the recurrence β r − 1 + β r + 1 = 2 cos θ β r \beta_{r-1}+\beta_{r+1}=2\cos\theta\,\beta_r β r − 1 + β r + 1 = 2 cos θ β r and the identity ∑ k = 1 ℓ − 1 β 2 k 2 = ℓ / 2 \sum_{k=1}^{\ell-1}\beta_{2k}^2=\ell/2 ∑ k = 1 ℓ − 1 β 2 k 2 = ℓ /2 , we obtain
∑ j = 1 2 ℓ − 2 β j β j + 1 = ∑ k = 1 ℓ − 1 β 2 k ( β 2 k − 1 + β 2 k + 1 ) = 2 cos θ ∑ k = 1 ℓ − 1 β 2 k 2 = ℓ cos θ . (123) \begin{aligned}
\sum_{j=1}^{2\ell-2}\beta_j\beta_{j+1}
&=\sum_{k=1}^{\ell-1}\beta_{2k}(\beta_{2k-1}+\beta_{2k+1})\\
&=2\cos\theta\sum_{k=1}^{\ell-1}\beta_{2k}^2=\ell\cos\theta. \tag*{(123)}
\end{aligned} j = 1 ∑ 2 ℓ − 2 β j β j + 1 = k = 1 ∑ ℓ − 1 β 2 k ( β 2 k − 1 + β 2 k + 1 ) = 2 cos θ k = 1 ∑ ℓ − 1 β 2 k 2 = ℓ cos θ . (123)
Thus w ⋆ ∈ Δ ( [ 2 ℓ − 2 ] ) w^\star\in\Delta([2\ell-2]) w ⋆ ∈ Δ ([ 2 ℓ − 2 ]) . These weights are positive, symmetric about the centre of the path, and nonuniform for ℓ ≥ 3 \ell\ge3 ℓ ≥ 3 .
Reorder the Majorana indices into odd and even sites, and multiply the k k k th basis vector within each block by ( − 1 ) k − 1 (-1)^{k-1} ( − 1 ) k − 1 . This orthogonal change of basis gives
Ω w ≃ ( 0 X w − X w T 0 ) , (124) \Omega_w\simeq
\begin{pmatrix}
0 & X_w\\
-X_w^{\mathsf T} & 0
\end{pmatrix}, \tag*{(124)} Ω w ≃ ( 0 − X w T X w 0 ) , (124)
where X w ∈ R ℓ × ( ℓ − 1 ) X_w\in\mathbb{R}^{\ell\times(\ell-1)} X w ∈ R ℓ × ( ℓ − 1 ) is bidiagonal, with
( X w ) k , k = w 2 k − 1 , ( X w ) k + 1 , k = w 2 k , (125) (X_w)_{k,k}=w_{2k-1},\qquad(X_w)_{k+1,k}=w_{2k}, \tag*{(125)} ( X w ) k , k = w 2 k − 1 , ( X w ) k + 1 , k = w 2 k , (125)
for k = 1 , … , ℓ − 1 k=1,\ldots,\ell-1 k = 1 , … , ℓ − 1 . Each singular value of X w X_w X w occurs twice in the skew block matrix, so Eq. (67) becomes h P 2 ℓ − 2 ( w ) = ∥ X w ∥ 1 h_{P_{2\ell-2}}(w)=\lVert X_w\rVert_1 h P 2 ℓ − 2 ( w ) = ∥ X w ∥ 1 .
For the weights in Eq. (122) , X w ⋆ = 1 ℓ cos θ X ℓ X_{w^\star}=\frac{1}{\ell\cos\theta}X_\ell X w ⋆ = ℓ c o s θ 1 X ℓ , where the only nonzero entries of X ℓ X_\ell X ℓ are
( X ℓ ) k , k = β 2 k − 1 β 2 k , ( X ℓ ) k + 1 , k = β 2 k β 2 k + 1 . (126) (X_\ell)_{k,k}=\beta_{2k-1}\beta_{2k},\qquad(X_\ell)_{k+1,k}=\beta_{2k}\beta_{2k+1}. \tag*{(126)} ( X ℓ ) k , k = β 2 k − 1 β 2 k , ( X ℓ ) k + 1 , k = β 2 k β 2 k + 1 . (126)
Let M ℓ M_\ell M ℓ be the ℓ × ( ℓ − 1 ) \ell\times(\ell-1) ℓ × ( ℓ − 1 ) matrix with ones on the diagonal and subdiagonal and zeros elsewhere. Then X ℓ = M ℓ ⊙ ( u v T ) X_\ell=M_\ell\odot(uv^{\mathsf T}) X ℓ = M ℓ ⊙ ( u v T ) , where ⊙ \odot ⊙ denotes entrywise multiplication, u j = sin ( ( 2 j − 1 ) θ ) u_j=\sin((2j-1)\theta) u j = sin (( 2 j − 1 ) θ ) for j = 1 , … , ℓ j=1,\ldots,\ell j = 1 , … , ℓ , and v k = sin ( 2 k θ ) v_k=\sin(2k\theta) v k = sin ( 2 k θ ) for k = 1 , … , ℓ − 1 k=1,\ldots,\ell-1 k = 1 , … , ℓ − 1 . Both squared Euclidean norms equal ℓ / 2 \ell/2 ℓ /2 .
Entrywise multiplication by M ℓ M_\ell M ℓ retains the diagonal and subdiagonal entries of a matrix and sets all other entries to zero. Applying [74 Theorem 4.2] to M ℓ T M_\ell^{\mathsf T} M ℓ T with n = ℓ − 1 n=\ell-1 n = ℓ − 1 , and using that transposition preserves the operator norm, gives
∥ M ℓ ⊙ Y ∥ ∞ ≤ 2 ℓ cot θ ∥ Y ∥ ∞ . \lVert M_\ell\odot Y\rVert_\infty\le\frac{2}{\ell}\cot\theta\,\lVert Y\rVert_\infty. ∥ M ℓ ⊙ Y ∥ ∞ ≤ ℓ 2 cot θ ∥ Y ∥ ∞ .
To obtain a bound on ∥ X ℓ ∥ 1 \lVert X_\ell\rVert_1 ∥ X ℓ ∥ 1 , we use the variational formula for the trace norm: for a real matrix X X X , this is the maximum of ∣ tr ( Y T X ) ∣ \lvert\operatorname{tr}(Y^{\mathsf T}X)\rvert ∣ tr ( Y T X )∣ over real matrices Y Y Y of the same size with ∥ Y ∥ ∞ ≤ 1 \lVert Y\rVert_\infty\le1 ∥ Y ∥ ∞ ≤ 1 . Since X ℓ = M ℓ ⊙ ( u v T ) X_\ell=M_\ell\odot(uv^{\mathsf T}) X ℓ = M ℓ ⊙ ( u v T ) , expanding the trace entrywise gives
∥ X ℓ ∥ 1 = max ∥ Y ∥ ∞ ≤ 1 ∣ tr ( Y T X ℓ ) ∣ = max ∥ Y ∥ ∞ ≤ 1 ∣ u T ( M ℓ ⊙ Y ) v ∣ ≤ 2 ℓ cot θ ∥ u ∥ 2 ∥ v ∥ 2 = cot θ , \begin{aligned}
\lVert X_\ell\rVert_1
&=\max_{\lVert Y\rVert_\infty\le1}\left|\operatorname{tr}(Y^{\mathsf T}X_\ell)\right|\\
&=\max_{\lVert Y\rVert_\infty\le1}\left|u^{\mathsf T}(M_\ell\odot Y)v\right|\\
&\le\frac{2}{\ell}\cot\theta\,\lVert u\rVert_2\lVert v\rVert_2=\cot\theta,
\end{aligned} ∥ X ℓ ∥ 1 = ∥ Y ∥ ∞ ≤ 1 max tr ( Y T X ℓ ) = ∥ Y ∥ ∞ ≤ 1 max u T ( M ℓ ⊙ Y ) v ≤ ℓ 2 cot θ ∥ u ∥ 2 ∥ v ∥ 2 = cot θ ,
where the last equality uses ∥ u ∥ 2 2 = ∥ v ∥ 2 2 = ℓ / 2 \lVert u\rVert_2^2=\lVert v\rVert_2^2=\ell/2 ∥ u ∥ 2 2 = ∥ v ∥ 2 2 = ℓ /2 .
By Eq. (37) , this estimate gives
η ( P 2 ℓ − 2 ) ≤ h P 2 ℓ − 2 ( w ⋆ ) ≤ cot θ ℓ cos θ = η 0 . (127) \eta(P_{2\ell-2})\le h_{P_{2\ell-2}}(w^\star)
\le\frac{\cot\theta}{\ell\cos\theta}=\eta_0. \tag*{(127)} η ( P 2 ℓ − 2 ) ≤ h P 2 ℓ − 2 ( w ⋆ ) ≤ ℓ cos θ cot θ = η 0 . (127)
Combining this with Eq. (121) forces equality throughout:
η ( P 2 ℓ − 2 ) = η ( P 2 ℓ − 1 ) = η ( C 2 ℓ ) = 1 ℓ sin θ . (128) \eta(P_{2\ell-2})=\eta(P_{2\ell-1})=\eta(C_{2\ell})=\frac{1}{\ell\sin\theta}. \tag*{(128)} η ( P 2 ℓ − 2 ) = η ( P 2 ℓ − 1 ) = η ( C 2 ℓ ) = ℓ sin θ 1 . (128)
The inequalities also imply ∥ X ℓ ∥ 1 = cot θ \lVert X_\ell\rVert_1=\cot\theta ∥ X ℓ ∥ 1 = cot θ . Substituting ℓ = m + 1 \ell=m+1 ℓ = m + 1 proves Eq. (68) . Multiplying the supporting inequality w ⋆ ⋅ s ≤ η 0 w^\star\cdot s\le\eta_0 w ⋆ ⋅ s ≤ η 0 by ℓ cos θ \ell\cos\theta ℓ cos θ gives Eq. (69) , with the optimal normalised weights in Eq. (122) .
Restricting the cycle parents to either path attains this common threshold, completing the proof of Proposition 7.
For m ≥ 1 m\ge1 m ≥ 1 , let x = π / [ 2 ( 2 m + 1 ) ] x=\pi/[2(2m+1)] x = π / [ 2 ( 2 m + 1 )] and y = π / [ 2 ( m + 1 ) ] y=\pi/[2(m+1)] y = π / [ 2 ( m + 1 )] . Equations (65) and (H9) give
η ( C 2 m + 1 ) = 2 π x cot x < 2 π < 2 π y sin y = η ( P 2 m ) , \eta(C_{2m+1})=\frac{2}{\pi}x\cot x<\frac{2}{\pi}<\frac{2}{\pi}\frac{y}{\sin y}=\eta(P_{2m}), η ( C 2 m + 1 ) = π 2 x cot x < π 2 < π 2 sin y y = η ( P 2 m ) ,
using tan x > x \tan x>x tan x > x and sin y < y \sin y<y sin y < y . Since setting any cycle weight to zero leaves the path support problem in Eq. (67) , every optimal odd-cycle weighting has strictly positive entries.
A boundary slice of P 4 P_4 P 4
We derive the compatibility condition for s = ( x , y , y , x ) s=(x,y,y,x) s = ( x , y , y , x ) , where the two endpoints have sharpness x x x and the two internal vertices have sharpness y y y , with 0 ≤ x , y ≤ 1 0\le x,y\le1 0 ≤ x , y ≤ 1 . By Eq. (33) , such a vector is compatible if and only if w ⋅ s ≤ h P 4 ( w ) w\cdot s\le h_{P_4}(w) w ⋅ s ≤ h P 4 ( w ) for every w ∈ Δ ( [ 4 ] ) w\in\Delta([4]) w ∈ Δ ([ 4 ]) . We first reduce the weights by reflection symmetry, then evaluate the resulting bounds.
Let R R R reverse the vertex order. For any w ∈ Δ ( [ 4 ] ) w\in\Delta([4]) w ∈ Δ ([ 4 ]) , the average w ˉ = ( w + R w ) / 2 \bar w=(w+Rw)/2 w ˉ = ( w + R w ) /2 satisfies w ˉ ⋅ s = w ⋅ s \bar w\cdot s=w\cdot s w ˉ ⋅ s = w ⋅ s . Equation (D3) gives h P 4 ( R w ) = h P 4 ( w ) h_{P_4}(Rw)=h_{P_4}(w) h P 4 ( R w ) = h P 4 ( w ) , so convexity implies h P 4 ( w ‾ ) ≤ h P 4 ( w ) h_{P_4}(\overline{w}) \le h_{P_4}(w) h P 4 ( w ) ≤ h P 4 ( w ) . Thus averaging the weights leaves the left-hand side of the inequality unchanged and can only decrease the right-hand side. Any violated bound therefore remains violated after averaging. It follows that we need only consider weights of the form
w = ( a , b , b , a ) 2 ( a + b ) , a , b ≥ 0 , a + b > 0. (129) w = \frac{(a,b,b,a)}{2(a+b)}, \qquad a,b \ge0,\quad a+b>0. \tag*{(129)} w = 2 ( a + b ) ( a , b , b , a ) , a , b ≥ 0 , a + b > 0. (129)
To evaluate Eq. (67) for these weights, reorder the five Majorana indices as ( 1 , 3 , 5 ; 2 , 4 ) (1,3,5;2,4) ( 1 , 3 , 5 ; 2 , 4 ) . In this order, the matrix 2 ( a + b ) Ω w 2(a+b)\Omega_w 2 ( a + b ) Ω w is
\begin{pmatrix} 0 & B \\ -B^{\mathsf T} & 0 \end{pmatrix}, \qquad B = \begin{pmatrix} a & 0 \\ -b & b \\ 0 & -a \end{pmatrix}. \tag*{(130)}\end{pmatrix}
The eigenvalues of B T B B^{\mathsf T}B B T B are a 2 a^2 a 2 and a 2 + 2 b 2 a^2+2b^2 a 2 + 2 b 2 , so ∥ B ∥ 1 = a + a 2 + 2 b 2 \lVert B\rVert_1=a+\sqrt{a^2+2b^2} ∥ B ∥ 1 = a + a 2 + 2 b 2 . The skew-symmetric block matrix has each singular value of B B B twice, together with one zero. Its trace norm is therefore 2 ∥ B ∥ 1 2\lVert B\rVert_1 2 ∥ B ∥ 1 . Dividing by the normalisation factor 2 ( a + b ) 2(a+b) 2 ( a + b ) and using h P 4 ( w ) = 1 2 ∥ Ω w ∥ 1 h_{P_4}(w)=\frac{1}{2}\lVert\Omega_w\rVert_1 h P 4 ( w ) = 2 1 ∥ Ω w ∥ 1 gives
h P 4 ( ( a , b , b , a ) 2 ( a + b ) ) = a + a 2 + 2 b 2 2 ( a + b ) . (131) h_{P_4}\left(\frac{(a,b,b,a)}{2(a+b)}\right)=\frac{a+\sqrt{a^2+2b^2}}{2(a+b)}. \tag*{(131)} h P 4 ( 2 ( a + b ) ( a , b , b , a ) ) = 2 ( a + b ) a + a 2 + 2 b 2 . (131)
Substituting this expression and w ⋅ s = ( a x + b y ) / ( a + b ) w\cdot s=(ax+by)/(a+b) w ⋅ s = ( a x + b y ) / ( a + b ) into Eq. (33) shows that s s s is compatible exactly when
a ( 2 x − 1 ) + 2 b y ≤ a 2 + 2 b 2 for all a , b ≥ 0. (132) a(2x-1)+2by\le\sqrt{a^2+2b^2}\qquad\text{for all }a,b\ge0. \tag*{(132)} a ( 2 x − 1 ) + 2 b y ≤ a 2 + 2 b 2 for all a , b ≥ 0. (132)
Both sides scale by the same factor when ( a , b ) (a,b) ( a , b ) is rescaled, so it suffices to consider a 2 + 2 b 2 = 1 a^2+2b^2=1 a 2 + 2 b 2 = 1 . If 2 x − 1 < 0 2x-1<0 2 x − 1 < 0 , the left-hand side is maximised by taking a = 0 a=0 a = 0 and b = 1 / 2 b=1/\sqrt{2} b = 1/ 2 , giving 2 y \sqrt{2}y 2 y . If 2 x − 1 ≥ 0 2x-1\ge0 2 x − 1 ≥ 0 , Cauchy–Schwarz applied to ( a , 2 b ) (a,\sqrt{2}b) ( a , 2 b ) and ( 2 x − 1 , 2 y ) (2x-1,\sqrt{2}y) ( 2 x − 1 , 2 y ) gives the maximum ( 2 x − 1 ) 2 + 2 y 2 \sqrt{(2x-1)^2+2y^2} ( 2 x − 1 ) 2 + 2 y 2 . This value is attained by choosing the two vectors proportional; when the second vector is zero, the maximum is zero for every choice of weights. Thus compatibility is equivalent to
( max { 2 x − 1 , 0 } ) 2 + 2 y 2 ≤ 1 , x , y ≥ 0. (133) \left(\max\{2x-1,0\}\right)^2+2y^2\le1,\qquad x,y\ge0. \tag*{(133)} ( max { 2 x − 1 , 0 } ) 2 + 2 y 2 ≤ 1 , x , y ≥ 0. (133)
For 0 ≤ x ≤ 1 / 2 0\le x\le1/2 0 ≤ x ≤ 1/2 , this condition requires only y ≤ 1 / 2 y\le1/\sqrt{2} y ≤ 1/ 2 ; for x ≥ 1 / 2 x\ge1/2 x ≥ 1/2 , it becomes ( 2 x − 1 ) 2 + 2 y 2 ≤ 1 (2x-1)^2+2y^2\le1 ( 2 x − 1 ) 2 + 2 y 2 ≤ 1 . Points with x < 1 / 2 x<1/2 x < 1/2 cannot be coordinatewise maximal, since x x x can be increased to 1 / 2 1/2 1/2 without reducing y y y . The coordinatewise maximal points therefore form the arc in Eq. (71) .
Appendix I: The complete Pauli family
We now prove that every state maximising
L ( ρ ) : = ∑ x ≠ 0 ∣ tr ( ρ P x ) ∣ , (134) \mathcal{L}(\rho):=\sum_{x\ne0}\left|\operatorname{tr}(\rho P_x)\right|, \tag*{(134)} L ( ρ ) := x = 0 ∑ ∣ tr ( ρ P x ) ∣ , (134)
is pure. Together with Corollary 6, which characterises optimal single-orbit parents by seeds having equal absolute Pauli expectations, this gives the SIC characterisation in Proposition 9 of Sec. VI 5.
Lemma I.1. Every maximiser of L \mathcal{L} L is pure.
Proof. Let L ⋆ : = max σ L ( σ ) \mathcal{L}_\star:=\max_\sigma\mathcal{L}(\sigma) L ⋆ := max σ L ( σ ) , and let ρ = ∑ j = 1 k p j ρ j \rho=\sum_{j=1}^{k}p_j\rho_j ρ = ∑ j = 1 k p j ρ j be the spectral decomposition of a maximiser, where p j > 0 p_j>0 p j > 0 and the ρ j \rho_j ρ j are mutually orthogonal rank-one projectors. Convexity gives
L ⋆ = L ( ρ ) ≤ ∑ j p j L ( ρ j ) ≤ L ⋆ . \mathcal{L}_\star=\mathcal{L}(\rho)\le\sum_j p_j\mathcal{L}(\rho_j)\le\mathcal{L}_\star. L ⋆ = L ( ρ ) ≤ j ∑ p j L ( ρ j ) ≤ L ⋆ . Equality holds throughout. The first inequality is a sum of triangle inequalities, one for each Pauli expectation, so each must be saturated. Since every p j > 0 p_j>0 p j > 0 , for each x ≠ 0 x\ne0 x = 0 the nonzero expectations tr ( ρ j P x ) \operatorname{tr}(\rho_jP_x) tr ( ρ j P x ) have the same sign.
Suppose now that k ≥ 2 k\ge2 k ≥ 2 . Since the d 2 d^2 d 2 Pauli operators form an orthogonal basis on the d d d -dimensional Hilbert space, Pauli expansion gives
d tr ( ρ 1 ρ 2 ) = 1 + ∑ x ≠ 0 tr ( ρ 1 P x ) tr ( ρ 2 P x ) . d\operatorname{tr}(\rho_1\rho_2)=1+\sum_{x\ne0}\operatorname{tr}(\rho_1P_x)\operatorname{tr}(\rho_2P_x). d tr ( ρ 1 ρ 2 ) = 1 + x = 0 ∑ tr ( ρ 1 P x ) tr ( ρ 2 P x ) . Every term in the sum is nonnegative by the sign property above, so d tr ( ρ 1 ρ 2 ) ≥ 1 d\operatorname{tr}(\rho_1\rho_2)\ge1 d tr ( ρ 1 ρ 2 ) ≥ 1 . But ρ 1 \rho_1 ρ 1 and ρ 2 \rho_2 ρ 2 are orthogonal, and hence tr ( ρ 1 ρ 2 ) = 0 \operatorname{tr}(\rho_1\rho_2)=0 tr ( ρ 1 ρ 2 ) = 0 , giving a contradiction. Therefore k = 1 k=1 k = 1 , so ρ \rho ρ is pure. □ \square □