Certifying nonstabilizerness in quantum processors
Rafael Wagner Filipa C. R. Peres Emmanuel Zambrini Cruzeiro Ernesto F. Galvão























[These authors contributed equally. 
 Corresponding author: ]rafael.wagner@inl.int






[These authors contributed equally. 
 Corresponding author: ]rafael.wagner@inl.int


















     Nonstabilizerness, also known as magic, is a crucial resource for quantum computation. The growth in complexity of quantum processing units (QPUs) demands robust and scalable techniques for characterizing this resource. We introduce the notion of set magic: a set of states has this property if at least one state in the set is a non-stabilizer state. We show that certain two-state overlap inequalities, recently introduced as witnesses of basis-independent coherence, are also witnesses of multi-qubit set magic. We also show it is possible to certify the presence of magic across multiple QPUs without the need for entanglement between them and reducing the demands on each individual QPU. 


Certifying nonstabilizerness in quantum  processors
    Ernesto F. Galvão
    April 29, 2024
===================================================




Introduction.– The certification of quantum devices is a crucial task <cit.>. One fundamental characteristic of quantum computing hardware is the ability to generate non-classical resources: quantum coherence <cit.>, quantum entanglement <cit.>, nonstabilizerness <cit.>, Hilbert space dimension <cit.>, quantum contextuality <cit.>  are all necessary resources for quantum information processing. The growth in complexity of near-term noisy devices <cit.> demands scalable and robust methods for witnessing non-classical properties.

In this Letter, we propose a technique for certifying the presence of nonstabilizerness in a network of quantum processing units (QPUs), without the need to entangle resources between separate units. Our protocol is efficient, robust, and based on estimating two-state overlaps r_i,j = Tr(ρ_i ρ_j) (also known as fidelity, if one of the states is pure), as sketched in Fig. <ref>. Interestingly, despite not entangling different units, we can use this scheme to certify nonstabilizerness among various QPUs. We envision many use cases. First, certifying the presence of nonstabilizer resources in a single QPU. Secondly, certifying the presence of nonstabilizerness generated by multiple QPUs in a network; for example, a referee collects overlap statistics from different QPUs and, after processing these values (i.e., calculating linear functionals of overlaps), can infer that at least some QPUs generated nonstabilizer resources. Finally, certifying nonstabilizerness present in n-qubit systems and not realizable by systems with fewer qubits.



Many tools for certifying nonstabilizerness exist. However, as the 
majority is aimed at the task of  resource quantification – in the formal resource theoretic sense <cit.> – rather than the simpler one of witnessing, most protocols have strict requirements. Most commonly, there is a need for: (i) full tomographic information of quantum states <cit.>, (ii) purity of states (or specific subclasses of states) <cit.>, (iii) additional entanglement generation <cit.>, or (iv) vertex characterization of the stabilizer polytope <cit.>. We avoid all these requirements. Our certification scheme depends on two promises of the device-generated statistics: (a) the data is described by two-state overlaps and (b) the device consists of a multi-qubit system. For certain witnesses, it will be possible to relax the last requirement. 

Our method is based on showing that some inequalities, initially introduced as coherence witnesses <cit.>, can also be used as witnesses of nonstabilizerness. The basis-independent nature of such inequalities implies the existence of a relational notion of nonstabilizerness defined for an ensemble of states, that we term set magic. The idea of viewing ensemble-based resources has recently been widely studied within quantum resource theories <cit.>. This novel foundational understanding is at the core of the application we envision, allowing us to distribute a quantum certification protocol among various parties in a network of QPUs. 


Background: Stabilizer subtheory.– In this work, we will focus on the stabilizer subtheory of n-qubit systems. We say that a pure quantum state |ψ⟩ is a stabilizer state when it is the eigenvector with eigenvalue +1 for all elements of a maximal abelian subgroup of the Pauli group 𝒫_n. The Pauli group is formed by all possible n-qubit Pauli operators, multiplied by phases ± 1 and ± i. The dynamics of this subtheory is described in terms of Clifford operations, defined to be those that preserve the Pauli group under conjugation, i.e., C 𝒫_n C^† = 𝒫_n. 

For many different architectures, it is relatively easy to perform Clifford operations and prepare stabilizer states. This subtheory is crucial to applications in fault-tolerant magic-state injection schemes and quantum error correction, and much work has been done to understand its geometrical properties. Ref. <cit.> showed that stabilizer states have a fixed overlap structure. Recall that any two pure states |ψ⟩, |ϕ⟩∈ℋ can be orthogonal (|⟨ψ | ϕ⟩| = 0), parallel (|⟨ψ | ϕ⟩| = 1) or oblique (0<|⟨ψ|ϕ⟩| < 1). When two pure stabilizer states are oblique, their two-state overlap obeys the following result.

    Given two oblique n-qubit pure stabilizer states |ψ⟩ and |ϕ⟩ their overlap is given by |⟨ϕ|ψ⟩|^2 = 2^-k for some k ∈{1,2,…,n}.


The convex hull of all n-qubit pure stabilizer states, for each fixed value of n≥ 1, forms a polytope that we will refer to as STAB. Any state outside of STAB is termed in the literature magic or nonstabilizer. Note that Theorem <ref> presents a simple method for witnessing magic of pure states using overlaps. Any deviation from the values 1/2^k witnesses the presence of such a resource. Beyond that, purity allows efficient schemes to quantify nonstabilizerness. Refs. <cit.> provide quantifying protocols that are close to being optimally efficient. However, without the assumption of purity (which is never perfectly attained experimentally), any overlap is possible by states inside of STAB, and the task of witnessing magic becomes non-trivial. The test we propose, although based on two-state overlaps, does not require purity of states. 


Background: Coherence witnesses based on two-state overlaps.– Initially motivated by benchmarking various resources in linear optical devices – Hilbert space dimension <cit.>, quantum coherence <cit.>, indistinguishability <cit.> – Refs. <cit.> proposed an 
inequality formalism based solely on linear functionals of two-state overlaps, defined by r_i,j = Tr(ρ_iρ_j) for any two states ρ_i and ρ_j over the same Hilbert space. 

Consider edge-weighted graphs (𝒢,r) where 𝒢 = (V(𝒢),E(𝒢)) is a graph [A graph is an ordered pair (V(𝒢),E(𝒢)) where V(𝒢), E(𝒢) are sets. The first set V(𝒢) is interpreted as a set of nodes (or vertices) for the graph, hence a simple set of labels. The second set E(G) corresponds to elements of the form e = {i,j} such that i,j ∈ V(𝒢), i.e., the edges of 𝒢. ], and r: E(𝒢) → [0,1] is a function. We refer to fully connected finite simple graphs 𝒢 as event graphs [A finite graph is one in which |V(𝒢)|<∞. A simple graph is undirected, no pair of nodes can have more than one edge, and there exist no edges of the form {v,v} for v ∈ V(𝒢). Finally, a fully connected graph is one in which for any two vertices v,w there exists a family of edges connecting the two.], as introduced in Ref. <cit.>. Any  (r_e)_e ∈ E(G) is merely a tuple of numbers. We will be interested in the problem of deciding when the numbers r_i,j in these tuples are realizable by quantum states, thus equating to Tr(ρ_i ρ_j); this is an instance of a quantum realization problem <cit.>. More formally, let 𝒟(ℋ) represent the set of all quantum states with respect to a system ℋ and consider a finite state ensemble ρ≡{ρ_i}_i ⊂𝒟(ℋ). Denote r(ρ) ≡ r({ρ_i}_i) := (Tr(ρ_iρ_j))_{i,j}∈ E(𝒢); we will refer to r(ρ) as a quantum realization for a given edge-weight r. Tuples r ∈ [0,1]^|E(𝒢)| can have any number of quantum realizations, including none at all <cit.>.

We proceed to discuss the notion of coherence for a state ensemble <cit.>, that differs from the commonly described basis-dependent view on coherence <cit.> and its witnesses <cit.>. It also differs from the basis-independent coherence discussed in  Refs. <cit.> defined with respect to a single state ρ instead of sets ρ. When there exists some unitary U such that a set of states ρ  satisfy U ρU^† = σ with σ some set of diagonal density matrices, we say that the state ensemble  ρ is set-incoherent [Equivalently, a set of states is incoherent iff all its elements pairwise commute.]. Otherwise, we say that it is set-coherent <cit.>. Set coherence is a basis-independent property of a set of states. Importantly, for any event graph 𝒢, it is possible to bound two-state overlaps r realized by incoherent ensembles: in such cases, incoherent states in the ensemble satisfy σ∋σ = ∑_λ∈Λσ_λλ|λ⟩⟨λ|, for some ℋ with d=(ℋ) and some basis Λ = {|λ⟩}_λ = 1^d.


For any fixed event graph 𝒢, the set of all possible edge-weights r realizable by some set-incoherent ensemble σ forms a full-dimensional convex polytope, denoted by ℭ(𝒢) <cit.>. Some convex polytopes ℭ(𝒢) have been completely characterized for certain event graphs 𝒢. The facet-defining inequalities for ℭ(𝒞_m), with 𝒞_m the cycle graph of m-nodes, were presented in Ref. <cit.> and are the so-called m-cycle inequalities


    c_m(r) := -r_e +∑_e'≠e r_e'≤ m-2,  for each e ∈ E(𝒞_m).

For any convex-linear functional h(r), we denote h(r(ρ)) its value attained by some quantum realization r(ρ). Violations c_m(r(ρ))>m-2 witness the impossibility of the overlaps to be realized by incoherent ensembles of states, i.e., they witness set coherence of any such ensemble ρ. We resolve two open questions from Ref. <cit.>. First, in Appendix <ref>, using semidefinite programming (SDP) relaxation tools <cit.>, we obtain tight maximal violations of such inequalities up to m=7, and lower bounds up to m=20. Secondly, in Appendix <ref>, we provide a proof of the following theorem.

    The maximal quantum values of c_m(r), for any m≥ 3 are attainable with sets ψ⊆𝒟(ℂ^2) of pure single-qubit states.

We also show that all facet-defining overlap inequalities for ℭ(𝒢), for any event graph 𝒢, are maximally violated by sets of pure states, meaning that, in particular, pure states maximally violate c_m(r)≤ m-2. 

Another relevant family of inequalities, defined recursively, is the following:

    h_m(r) = h_m-1(r)+r_1m-∑_i=2^m-1r_im≤ 1 .

The sequence above starts with h_3(r) = r_12+r_13-r_23≡ c_3(r) and   defines novel inequalities for any integer m>3. Each h_m inequality was shown in Ref. <cit.> to be facet-defining for the polytope ℭ(𝒦_m), where 𝒦_m is the complete graph with m nodes. It has been shown for up to 12-qubit systems that h_m(r)≤ 1 cannot be violated by sets ρ⊆𝒟(ℂ^d) where d≤ m-2 <cit.>. Numerically, we can see maximal quantum violations for m states ρ with dimension d≥ m-1. 

Generalizing magic to state ensembles.– We start the presentation of our main results by introducing the notion of set magic. 

Let ρ⊆𝒟(ℋ) be a finite set of states and d=(ℋ)<∞. We say ρ is set-magic when there exists no unitary U: ℋ→ℋ such that UρU^† = ρ^' is a set of states within the stabilizer polytope. 

Set magic implies magic of some element in the set. Notably, the converse is not true, as we will see in a moment. The definition above is a straightforward translation of set coherence <cit.> to the context of magic as a quantum resource. Later, we will show that, under certain conditions, it is possible to bound the number of states ρ∈ρ that are outside of STAB, instead of merely witnessing that some are.

Set magic and set coherence are different notions. A simple way to see this is that various sets of stabilizer states ρ_STAB (e.g., {| 0⟩, | +⟩,|+_i⟩}) are set coherent, without being set magic. We can present another (more subtle) difference between the two notions. Given any basis-dependent coherent pure state |ψ⟩, with respect to some basis of reference {| i⟩}_i, we have that {|ψ⟩, | i⟩} must be set-coherent. In general, given a magic state |ϕ⟩ and a stabilizer state | s ⟩∈ STAB, we have that {|ϕ⟩, | s ⟩} will not necessarily be set-magic. For example, the set {| 0⟩, | T ⟩}, with | T ⟩ := 1/√(2)(| 0⟩ + e^iπ/4| 1 ⟩), can be taken to a set of states inside STAB:

    T^†{| 0⟩⟨ 0 | , | T ⟩⟨ T |}T ↦{| 0 ⟩⟨ 0 |, | + ⟩⟨ + |}⊂STAB ,

where T diag(1,e^iπ/4). Hence, this pair is not set-magic, although it clearly has nonstabilizerness in the usual sense. 


Nonstabilizerness in QPUs.– In any certification protocol, the assumptions behind the test play a central role. In our case, we assume: (a) multi-qubit systems and (b) the ability to estimate two-state overlaps. The exact way in which this estimation is obtained may be unknown. Common techniques involve performing SWAP tests, Bell measurements, or generating specific prepare-and-measure statistics. Minimizing sample and measurement complexity is desired for scalability, although not essential for the certification per se. Commonly, a minimal requirement is using a number of samples and measurements smaller than the one needed to make (ideal) quantum state tomography <cit.>, which is of order O(d_T^2/ε^2), where ε is a fixed precision with respect to distance functions and d_T is the dimension of the whole Hilbert space considered. For single QPUs with n qubits and associated Hilbert space ℋ=(ℂ^2)^⊗ n, a network of s ∈ℕ units has space ℋ^⊗ s, implying d_T=(ℋ^⊗ s)=2^sn. 

As shown in Appendix <ref>, event-graph inequalities cannot witness nonstabilizerness in general. This is somewhat unsurprising, as they were not proposed for such a task. However, we show that some event-graph inequalities are witnesses of both nonstabilizerness and coherence, starting with the cycle inequalities.

    Every cycle inequality violation c_m(r)> m-2 is a robust witness of nonstabilizerness for any set ρ of multi-qubit states such that r=r(ρ).


We defer the proof of this result to Appendix <ref> but its underlying idea is extremely simple: After showing that pure states maximize any facet-defining inequality functional, we can use Theorem <ref> to look only at some specific overlaps that, in principle, could violate the inequalities. We then show that any stabilizer realization satisfies c_3(r(ψ_STAB)) ≤ 1 and use induction to show that the same must hold for all integers m≥ 3. Importantly, Theorem <ref> holds for any set of multi-qubit states and not only for pure states.

Here, it is important to pause and clarify precisely the nature of the certifications allowed by Theorem <ref>. Suppose we have a network with s distinct units. Then, one possible task is to certify that each individual QPU can produce or has produced magic. This is illustrated in Fig. <ref>(a). Alternatively, we might be interested only in certifying that the network as a whole can generate magic somewhere across its parties. In this case, we can distribute the state preparation and overlap estimation across different units (see Fig. <ref>(b)), reducing the number of overlaps that need to be evaluated in each QPU. Compared to other protocols <cit.> ours has the advantage that it foregoes the need to entangle the different parties in the network to carry out this certification.


To make things even clearer, suppose that the certification of each unit in Fig. <ref>(a) requires the evaluation of m overlaps. In total, the individual certification of all units will require a total of sm overlaps to be estimated. If we instead consider the distributed certification depicted in Fig. <ref>(b), the evaluation of m overlaps suffices to certify the entire network for the presence of set magic. 

We take this opportunity to highlight two notable features of our work. First, suppose a single QPU in the network is capable of generating non-stabilizer resources. The argute reader will note that, rather than taking the distributed approach, by simply evaluating the overlaps on the proper QPU, one not only certifies the entire network for the presence “somewhere”, but further certifies the special unit. However, doing so requires prior knowledge of which QPU is capable of generating nonstabilizerness. If that is not the case, running the overlaps on a single (randomly chosen) QPU has a probability of success of 1/s whilst the distributed certification always succeeds. Secondly, we will see below that, in some cases, this same procedure can enable an even stronger certification, allowing us to guarantee that  all but one QPU have produced non-stabilizer results. 


We explained how to certify the production of magic (somewhere) in a given quantum hardware.  Alternatively, Theorem <ref> can also be used for a second (subtly different) task. Suppose we are supplied with an ensemble of m unknown states provided by third parties and are asked the question: Is the set magic? Then, we can use our network to answer this question by distributing the estimation of the overlaps among any number of the available QPUs. We inevitably need to evaluate m overlaps to accomplish this task, regardless of how we choose to distribute this evaluation. Again, unlike previous protocols <cit.>, this has the added advantage of avoiding additional entanglement when certifying the presence of magic.

Note the two tasks are fundamentally different. Crucially, in the first, we want to certify that magic can be produced within our hardware. In contrast, in the second, we aim to witness the presence of magic in a set of states supplied by (any number of) third parties. In Appendix <ref>, we make a comprehensive comparison between our scheme and other protocols. 


From the known connection of event-graph inequalities to contextuality <cit.>, the astute reader may question if such a result is in tension with or trivially follows from known results <cit.>. In Appendix <ref>, we discuss how our work connects with contextuality theory and resolve these two points arguing that neither do our results trivially follow from known connections between contextuality and magic <cit.>, nor are they in tension with them.

Witnessing nonstabilizerness in higher-dimensional systems.– Cycle inequalities certify the presence of nonstabilizerness but, as stated above, they are always maximally violated by sets ρ⊆𝒟(ℂ^2) of single-qubit states. This feature implies that such a certification scheme is not capable of capturing genuine properties of multi-qubit nonstabilizer resources, i.e., magic states in 𝒟(ℂ^2^n). 

To address the possibility of witnessing nonstabilizerness that necessitates having access to higher Hilbert space dimensions, we study inequalities that witness both of these properties. The simplest example of such inequalities is h_4(r)≤ 1 which requires two-qubit systems (or single qutrits) to have a violation, as shown in Ref. <cit.>. We complement this result by showing that violations of h_4(r)≤ 1 also witness nonstabilizerness. 

    The inequality h_4(r) ≤ 1 cannot be violated by quantum realizations r=r(ρ_STAB) of sets of stabilizer states ρ_STAB.


We defer the proof of this result to  Appendix <ref>.

Robustness and scalability.– These inequalities, c_m(r)≤ m-2 and h_4(r)≤ 1, are our main nonstabilizerness witnesses. By default, they are both robust to incoherent noise and scalable. Robustness follows from the fact that they remain valid witnesses if, rather than pure states, we consider any set of states. Specifically, any state inside STAB  cannot violate these inequalities. On the other hand, scalability follows from the fact that (i) two-state overlaps are well-defined independently of any Hilbert space dimension, and (ii) quantum computers can efficiently estimate overlaps <cit.>. We refer to a protocol as scalable, or efficient, if one does not require exponentially increasing computational time, number of measurements, or samples.  Additionally, in our case, it is clear that scalability will also depend on the trade-off between dimension and number of overlaps estimated in a given inequality, for instance estimating h_2^n(r) is certainly not efficient. 

Full set magic.– We have seen that our inequality witnesses certify the presence of set magic for  ρ. This indicates that some state(s) in the set must lie outside of the STAB polytope. It is therefore natural to ask if it is possible to certify a lower bound on the number of states that must always lie outside of STAB. Clearly, for any set ρ, at least one state ρ_𝗋𝖾𝖿 can always be unitarily mapped inside the STAB. With this in mind, we introduce the following notion.
 Let ρ⊆𝒟(ℋ) be a finite set of states, d=(ℋ)<∞. We say that the set ρ is fully set magic if, for every unitary U:ℋ→ℋ, all states (but one) lie outside of the stabilizer polytope. 




There exist sets of states with full set magic. Let ℋ = ℂ^2 and consider any triplet {ρ_1,ρ_2,ρ_3} of  states. It can be shown numerically that c_3(r(ρ))≤ 1.21 if at most one state in ρ is outside of STAB. Recall that the maximal value of c_3  achieved with generic quantum states is 1.25. Note that, for analyzing full set magic, we fix the dimension. Therefore, there may be multi-qubit systems realizing values larger than c_3(r) = 1.21 while having only one magic state. In Appendix <ref>, we present numerical bounds for witnessing full set magic using other cycle inequalities and show numerical evidence that only odd cycle inequalities can witness full set magic. We also discuss concrete implementations of our certification scheme.


Discussion and further directions.– We have introduced novel witnesses of nonstabilizerness applicable to a single QPU and networks of QPUs. Our witnesses are robust in the sense of applying to pure and mixed states of any kind. They are also scalable, meaning they are independent of the system's dimension. This scalability, however, depends on the number of overlaps required to estimate a certain inequality. 

Various of the tools put forward either have their own technical interest or present novel theoretical opportunities. For instance, set magic and full set magic can be further investigated within the resource-theory framework. In this Letter, set magic arises naturally from using unitary invariants as our witnesses. There are several open questions on the possible operational importance of these results for quantum computation. Is it possible to connect set magic to the hardness of classically simulating a stabilizer circuit given a specific set of input states? Does a suitable quantifier for set magic exist? Framing simulation within a unitary-invariant framework could better pinpoint the resources responsible for the exponential overhead of classical simulation and even lead to a unified view of different simulation schemes <cit.>.

In another direction, exploring if a similar effect to full set magic exists when considering the notion of set coherence could be of interest <cit.>. Moreover, for composite systems, large violations of the inequality h_4(r) ≤ 1 may also require the presence of entanglement. We believe this is an intriguing aspect that merits further investigation.  Finally, we showed certain classes of inequalities that witness magic, but we do not claim that these are the best ones. It is certainly possible that finding other overlap inequalities (or even going beyond two-state overlap to higher-order multivariate trace invariants) can result in better witnesses, simplifying experimental implementations.


We would like to thank Raman Choudhary for useful discussions. FCRP and RW acknowledge support from FCT – Fundação para a Ciência e a Tecnologia (Portugal) through PhD Research Scholarship 2020.07245.BD, and PhD Grant SFRH/BD/151199/2021,  respectively. EZC acknowledges funding by FCT/MCTES through national funds and, when applicable, co-funding by EU funds under the project UIDB/50008/2020. EZC also acknowledges funding by FCT through project 2021.03707.CEECIND/CP1653/CT0002. EFG acknowledges support from FCT via project CEECINST/00062/2018. This work was supported by the ERC Advanced Grant QU-BOSS, GA no. 884676.


 




Supplementary Material for: Certifying nonstabilizerness in quantum processors







§ QUANTUM BOUNDS FOR NON-STABILIZER WITNESSES




 §.§ Lower bounds


Let f:𝒟(ℋ)^|V(𝒢)|→ℝ be a convex-multilinear functional defined with respect to some facet-defining inequality of ℭ(𝒢), for some 𝒢, i.e., f(·) ≡ h(r(·)). In its generic form, f is given by,

    f(ρ) = ∑_u,v ∈ V(𝒢)α_uvTr(ρ_uρ_v),

where α_uv∈ℤ for all u,v. We are interested in evaluating the quantum bound of this functional, i.e., max_{ρ_x}_x=1^N f , over all possible quantum realizations, where N = |V(𝒢)|.

To determine lower bounds for the quantum bound, we employ a seesaw of SDP. Indeed, by fixing all the states except one, the problem of maximizing the bound over the remaining state is an SDP.



 §.§ Upper bounds: hierarchy of semidefinite programming relaxations


A way to evaluate upper bounds for this quantity is to adapt the Navascues-Vértesi (NV) hierarchy <cit.>  to this particular problem. In a similar spirit, we make a list of operators 𝒮 = {1, {ρ_x}} and choose a degree of relaxation k. A relaxation of degree k consists of keeping all products of at most k operators from the list. The moment matrix is then constructed,

    Γ_ij = Tr[S_i S_j],

where S_i∈𝒮. For a good introduction and review of SDP techniques in quantum information science see Ref. <cit.>.

One samples a linearly independent basis of such moment matrices {Γ^(1),…, Γ^(m)}. The relaxation then consists of finding an affine combination Γ = ∑_j=1^mc_jΓ^(j)∈ f, with Γ≥ 0, as follows,

    max_c⃗∈ℝ^m      f(Γ)
    s.t.     Γ≥ 0,
       ∑_j=1^m c_j = 1.




 §.§ Maximal quantum violation of m-cycle inequalities




  §.§.§ Qubit model


The optimal solution of the maximization problem for c_m(r) is a set of states {|ψ_x⟩}_x=1^m of the form

    |ψ_x⟩ = cos (θ_x^(m)) |0⟩ + sin (θ_x^(m))|1⟩.

where 

    θ_x^(m) =
        π/2 - (x-1)π/2m   if m is odd,
    π/2 + (x-1)π/2m   if m is even.


This family of optimal states is found explicitly using the SDP seesaw. Using the hierarchy, we could prove that the quantum bound is tight (to 10^-5 precision) for this family of states up to m = 8. For larger values of m, m ≤ 20, we have checked the lower bounds match the analytical formula up to the same precision. For  m > 20, we conjecture that this is the optimal quantum solution.



  §.§.§ Asymptotic behaviour


Let us denote the set of optimal quantum states as ψ^max. The maximum quantum violation is then given by

    c_m(r(ψ^max)) = (m-1)cos^2(π/2m)-cos^2((1-1/m)π/2).

On the other hand, the optimal incoherent quantum realization is c_m(r(ψ^inc)) = m-2. The fraction between these two quantities goes to 1 as m grows.

    The limit of the ratio c_m(r(ψ^inc))/c_m(r(ψ^max)) when m→∞ is 1.



To see this, write

    c_m(r(ψ^inc))/c_m(r(ψ^max)) = m-2/(m-1)cos^2(π/2m)-cos^2(1/2(1-1/m)π)


The term cos^2(1/2(1-1/m)π) is bounded, therefore the limit reduces to

    lim_m→∞c_m(r(ψ^inc))/c_m(r(ψ^max)) = lim_m→∞m-2/(m-1)cos^2(π/2m) = 
       lim_m→∞m-2/m-1 = 1.



Fig. <ref> shows the ratio as a function of m, denoted, for simplicity, as C/Q. The numerics above suggest that pure single-qubit states always provide the optimal violation. In the following, we prove this to be true.



  §.§.§ Qubit optimality



    Let 𝒞_m be the m-cycle event graph and r an edge-weight. We show later (see Lemma <ref> of Appendix <ref>) that, for any quantum realization r=r(ρ), there exists some pure state quantum realization r=r(ψ) for which c_m(r(ρ)) ≤ c_m(r(ψ)). Therefore, for optimal violations, we can focus on pure state realizations. Let r=r(ψ) be any pure state quantum realization for an edge-weight r of the event graph 𝒞_m. Then, consider the unitary sending ψ= {|ψ_1⟩, |ψ_2⟩ , …, |ψ_m⟩} to ψ̃ = {| 0⟩, |ψ_2⟩, …, |ψ_m⟩}. In this case, any overlap r_i,i+1 with respect to elements in ψ̃ in the cycle will be equal to cos^2(θ_i+1-θ_i). The angle θ_i is the angle between the vectors |ψ̃_i⟩ with the reference state | 0⟩, and can have any value θ_i ∈ [0,π), for all i=1,…,m. The above implies that we can write any c_m(r(ψ)) as
    
    c_m(r(ψ))=   -r_1,2+r_2,3+… +r_m-1,m + r_m,1
    
            =    -cos^2(θ_2)+cos^2(θ_3-θ_2)
    +   …+cos^2(θ_m-θ_m-1)+cos^2(θ_m).

    Note that this is independent of any dimensionality constraint. Nevertheless, each overlap in the tuple (r_e)_e ∈𝒞_m attaining the values above can also be obtained by the set of states
    
    | q_1⟩   = | 0⟩, 
    | q_2⟩   = cos(θ_2)| 0⟩ + sin(θ_2)| 1⟩ , 
    | q_3⟩   = cos(θ_3)| 0⟩ + sin(θ_3)| 1⟩ , 
       ⋮
    | q_m⟩   = cos(θ_m)| 0⟩ + sin(θ_m)| 1⟩ ,

    that is, within the space ℂ^2. Hence, using just the single-qubit states q= {| q_x⟩}_x=1^m, we have that c_m(r(ψ)) = c_m(r(q)). In other words, any value attained by c_m(r) with pure quantum states of any dimension is also attained by using just single-qubit states. In particular, this will also be valid for the maximal values of c_m(r). This concludes the proof.




 §.§ Maximum quantum violation of h_4(r) ≤ 1
 

Again, using the methods described in this Appendix, we can show tight bounds for the maximal quantum realizations violating h_4(r)≤ 1, for sets ρ⊆𝒟(ℂ^d) with d = 3, 4. 

Note that h_4 (as any event-graph functional) satisfies h_4(r(ρ)) = h_4(r(U ρ U^†)) for any unitary U and U ρ U^†≡{U ρ_i U^†}_i=1^m. This implies that any maximal quantum violation can be attained using Hilbert spaces of at most dimension d=4. We find a tight bound of 1+1/3, up to 10^-5 precision, for both d = 3, 4, proving that qutrits are sufficient to achieve the maximum quantum violation of h_4.




§ PROOF OF THEOREM <REF>


Before proving  Theorem <ref>, we present some novel technical results that are of general interest to the event-graph formalism introduced in Ref. <cit.>. 

Following the same notation used in the main text, for any given event graph 𝒢, with edges E(𝒢) and vertices V(𝒢), we denote the polytope of all edge-weights r: E(𝒢) → [0,1] realizable by set-incoherent tuples as ℭ(𝒢). The Hamming weight of a string (or, equivalently, a tuple) s of 0/1-assignments equals the number of 1 assignments in the string (or tuple) and is denoted |s|_H.

    Let 𝒢=𝒞_m be the m-cycle graph. Fix m≥ 3 and some ẽ∈ E(𝒞_m). If we denote 
    ℭ_ẽ := {r ∈ℭ(𝒞_m) :  r_ẽ=1},
 we have that ℭ_ẽ = {1}×ℭ(𝒞_m-1). 


This lemma shows that if we define the cross-section ℭ_ẽ of the polytope ℭ(𝒞_m) along the direction r_ẽ=1, the resulting polytope is isomorphic to ℭ(𝒞_m-1). This implies that given any facet-defining inequality of ℭ(𝒞_m), if we force an edge to be equal to one, the resulting inequality will be a facet-defining inequality of ℭ(𝒞_m-1), or a trivial inequality. 


    Because ℭ(𝒞_m) is a convex polytope, the same is true for ℭ_ẽ. Let ext(P) denote the set of extremal points of any convex polytope P, and hence P = ConvHull[ext(P)]. Let us assume, wlog, an ordering r=(r_e)_e ∈ E(𝒞_m) = (r_ẽ,r_e_1,…,r_e_m-1). We have, 
    
    ext(ℭ_ẽ) = {(1,s)∈ℝ^m: s ∈ext(ℭ(𝒞_m-1))}.

    
    (⊆) Let r̃∈ext(ℭ_ẽ). By construction, we must have that r̃≡ (1,s̃) ∈ext(ℭ(𝒞_m)), with s̃ a deterministic assignment for which |s̃|_H≠ m-2. Therefore, s̃∈ext(ℭ(𝒞_m-1)).
    
    (⊇) This direction follows trivially.

    Hence, we have that
    
    ℭ_ẽ = {1}×ℭ(𝒞_m-1),

    where {1} is the singleton polytope, as we wanted. 


This simple result will be instrumental for constructing the inductive step used in the proof of Theorem <ref>.

We now make the notion of a quantum realization within the context of the event graph formalism precise. We can associate nodes of the graph to quantum states V(𝒢) ∋ v ℓ↦ρ_v ∈ρ via some vertex ρ-labeling ℓ: V(𝒢) →ρ. Once such labeling ℓ is fixed, we associate edge-weights r_e ≡ r_u,v to two-state overlaps E(𝒢) ∋ e ={u,v}ℓ↦{ρ_u,ρ_v}⟨· , ·⟩_HS↦Tr(ρ_uρ_v) [Sometimes the inner-product ⟨ϕ_i | ϕ_j ⟩ is called an overlap. We will not use this terminology here and simply refer to the overlap as the absolute value square of inner-product between states, or more generally, to the trace between the product of two density matrices.], with ⟨ X, Y ⟩_HS = Tr(X^† Y) the Hilbert-Schmidt inner product. 

The cardinality of ρ is not necessarily equal to that of V(𝒢), e.g., the same state can be associated to all vertices by the labeling ℓ(v) = ρ, ∀ v ∈ V(𝒢). Each vertex labeling ℓ is isomorphic to a tuple (ℓ(v))_v ∈ V(𝒢)∈𝒟(ℋ)^|V(𝒢)|. Given some ρ-labeling ℓ, we can see r as a function that outputs a tuple of two-state overlaps r_ℓ(ρ) for an input set ρ. For instance, take ρ= {|ψ⟩⟨ψ|}∪{σ_1,σ_2} and ℓ(v)=|ψ⟩⟨ψ| for all v ∈ V(𝒢), as above. Since all vertices of V(𝒢) have been assigned the same state, the associated r_ℓ(ρ) is  r_ℓ(ρ) = (1,1,…,1). When it is clear from the context which labeling ℓ is being used, we simply write r(ρ).

Recall that, any edge-weight r: E(𝒢) → [0,1] for an event graph 𝒢, is said to have a quantum realization <cit.> if there exists ρ= {ρ_i}_i ∈ V(𝒢) such that r=r(ρ) ≡ (Tr(ρ_iρ_j))_{i,j}∈ E(𝒢). We denote |X| the cardinality of a set X. We say that a quantum state ρ∈𝒟(ℋ) is pure when Tr(ρ^2) = 1, in which case we denote it as a rank-1 projector ρ=|ψ⟩⟨ψ|≡ψ.

    Let h:ℝ^|E(𝒢)|→ℝ be any convex-linear functional, acting over elements r ∈ [0,1]^|E(𝒢)|, for any event graph 𝒢. Then, for any quantum realization r=r(ρ) with states {ρ_i}_i, there exists a pure state quantum realization r=r(ψ) with states {|ψ_i ⟩}_i, such that 
    h(r(ρ)) ≤ h(r(ψ)).

    Moreover, ψ⊆ConvHull(ρ).



    Each ρ_i ∈ρ is a convex combination of pure states {ψ^(i)_ω_i}_ω_i ∈Ω_i for some ensemble of pure states Ω_i. Noticing that h(r) are, by construction, linear functionals over the overlaps,
    
    ∀ i,ρ_i = ∑_ωλ_ω^(i)|ψ_ω^(i)⟩⟨ψ_ω^(i)|⇒
    
            h(r({ρ_i}_i)) = ∑_ω_1,…,ω_mλ_ω_1^(1)…λ_ω_m^(m)h(r({ψ_ω_i^(i)}_i)).

    To conclude the above, one needs to introduce some redundant values of 1 = ∑_ω_iλ_ω_i^(i). The equation then follows from linearity with respect to r, and hence multilinearity with respect to the states. 
    
    We can collectively write s = (ω_1,…,ω_m) and define q_s = λ_ω_1^(1)…λ_ω_m^(m). Because each set of weights {λ_ω_i^(i)}_ω_i ∈Ω_i correspond to convex weights, i.e., ∑_ω_iλ_ω_i^(i) =1 with 0≤λ_ω_i≤ 1, we get that {q_s}_s is also a set of convex weights. With this simplified notation we have that 
    h(r({ρ_i}_i)) = ∑_sq_s h(r({ψ^(i)_s}_i)) with ∑_sq_s=1 and 0≤ q_s≤ 1. In other words, the linear functional h realized by overlaps between general quantum states can be written as the convex combination of the same functional realized by overlaps between pure states. Choosing now a particular s^⋆ such that ∀ s, h(r({ψ_s^⋆^(i)}_i)) ≥ h(r({ψ_s^(i)}_i)) we see that 
    h(r({ρ_i}_i)) = ∑_sq_s h(r({ψ^(i)_s}_i))≤∑_sq_s h(r({ψ_s^⋆^(i)}_i)).

    Since ∑_sq_s=1 we have that h(r({ρ_i}_i)) ≤ h(r({ψ_s^⋆^(i)}_i)).



    Let h(r) be any linear-functional over r=(r_e)_e ∈ E(𝒢) for any event graph 𝒢 and 𝔔(𝒢), defined by 
    𝔔(𝒢):= {r:E(𝒢) → [0,1] : ∃ρ, r=r(ρ)},
 be the set of quantum realizable edge-weights. Then, there always exists a pure state quantum realization r=r(ψ) such that  
    
    h(r(ψ)) = max_r ∈𝔔(𝒢)h(r).

    The same holds if we restrict realizations to some convex and compact subset 𝔖⊆𝒟(ℋ) of all states, so that the quantum realizations are such that r=r(ρ_𝔖), with ρ_𝔖⊆𝔖. 



    For any such h, Lemma <ref> shows that to every quantum realization r=r(ρ), there exists a larger pure state realization within the convex hull of ρ. Therefore, the maximum attainable value, among all quantum realizations r ∈𝔔(𝒢), must be pure-state realizable, otherwise this would contradict Lemma <ref>. The argument is the same if 𝔖 is used instead.


This Theorem implies the immediate corollary.

    The maximal quantum violation of any facet-defining inequality of ℭ(𝒢), for any event graph 𝒢, is attained by pure states.



    Since ℭ(𝒢) is a convex polytope, any facet-defining inequality from ℭ(𝒢) is described by convex-linear functionals h(r), together with some b ∈ℝ satisfying h(r) ≤ b.


This Corollary proves (and generalizes) a conjecture from Ref. <cit.>, that the maximal bounds violating the c_3(r)≤ 1 inequality using pure states were also valid for mixed states in general, and for any dimension. While here we will use these results to prove Theorem <ref>, they are important by themselves for the event-graph approach and the theory of coherence witnesses. 

Finally, we prove Theorem <ref> of the main text.


    Due to Theorem <ref>, we can restrict ourselves to pure stabilizer states. Consider first the 3-cycle inequality. We have
    
    r_1,2+r_1,3-r_2,3≤ 1.

    From Theorem <ref>, we see that if all states in the graph are oblique to their neighbors there can be no violation since r_1,2+r_1,3-r_2,3≤ r_1,2+r_1,3≤1/2^k+1/2^k'≤ 1 for all k,k'=1,…,n. The same holds if we allow some edge-weights to be zero. If we allow any edge-weight in the inequality to be equal to one, it is simple to see that we cannot have a violation, as we would have two nodes corresponding to the same stabilizer state, implying that the remaining pair of overlaps is equal. This shows the result for c_3(r). 

    To show that the same is true for any m-cycle inequality we proceed by induction. Assume that an m-cycle inequality cannot be violated by quantum realizations r=r(ρ_STAB), with ρ_STAB⊆STAB. For any (m+1)-cycle inequality we have that,  ∀ e ∈ E(𝒞_m+1), 
    
    -r_e + ∑_[ e' ∈ E(𝒞_m+1);         e'≠ e ]r_e'≤∑_[ e' ∈ E(𝒞_m+1);         e'≠ e ]r_e'≤m/2

    for any set of pure stabilizer states oblique or orthogonal to their neighbors in the graph. Since m/2 ≤ m-2 for all m≥ 4 it remains to show that if two (or more) neighboring stabilizer states are equal we still cannot have a violation. 
    
    From Lemma <ref>, if any edge-weight is equal to one, this implies that the cycle inequality from ℭ(𝒞_m+1) becomes an inequality from ℭ(𝒞_m), which, by hypothesis, cannot be violated with the stabilizer subtheory, i.e., by any quantum realization r=r(ρ_STAB). We conclude that if the stabilizer subtheory cannot violate inequalities from ℭ(𝒞_m) it will also not violate the inequalities from ℭ(𝒞_m+1). As we know this is true for the cycle inequalities ℭ(𝒞_3), by induction, this property must be satisfied by all facet-defining inequalities for the event graph polytopes ℭ(𝒞_m) for any m.




§ KNOWN FACTS REGARDING THE RELATION BETWEEN CONTEXTUALITY AND MAGIC


In this Appendix, we will prove the existence of an event-graph inequality that is both facet-defining and violated by sets of stabilizer states. To do so, we use some results within the field of Kochen-Specker noncontextuality <cit.>. We then extend these considerations to generalized noncontextuality <cit.>.

To provide some context, recall that magic-state injection is the leading model for experimentally realizing fault-tolerant quantum computation. While it involves only stabilizer operations at every step of the computation, the injection of magic states elevates the model to quantum universality.  Ref. <cit.> showed that contextuality is a necessary resource for universal quantum computation via magic-state injection. The scope of this result depends on whether the model involves even-prime dimensional qudits (i.e. qubits) or odd-prime qudits. For the latter case, a state is non-contextual if and only if it belongs to the set of states unable to unlock any computational speed-up. This set forms a polytope, denoted as 𝒫_SIM, meaning that the subtheory within this polytope is efficiently simulable with classical computation. This polytope strictly contains the set of stabilizer states but is not equivalent to it. 

Therefore, for odd-prime dimensions, Kochen-Specker noncontextuality inequalities serve as witnesses of nonstabilizerness. However, for even-dimensional systems, the same does not hold, as we now show. We start by constructing the relevant event graph. First, we construct the so-called exclusivity graph 𝒢_exc <cit.>. We take this graph to be the complement graph [The complement of a graph 𝒢 is a new graph 𝒢^c such that V(𝒢) = V(𝒢^c) and, e ∈𝒢^c iff e ∉𝒢.] of the Shrikhande graph <cit.>. See Ref. <cit.> for a representation of  𝒢_exc. We follow closely the discussion of the proof of KS-contextuality discussed in Ref. <cit.>.  Secondly, we take the suspension graph <cit.> ∇𝒢_exc by a new node ⋆. This new graph will be our event graph 𝒢 = ∇𝒢_exc. It was shown in Ref. <cit.> that any inequality from an exclusivity graph 𝒢_ext is mapped to some facet defining inequality of the event graph 𝒢= ∇𝒢_exc. Therefore, the inequality 

    ∑_v ∈ V(𝒢_exc)r_⋆,v≤ 3

is both a noncontextuality inequality (within the Cabello-Severini-Winter  framework <cit.>) and a facet-defining event-graph inequality, when a specific mapping takes place (see Ref. <cit.> for details). This inequality corresponds to Mermin's Bell inequality <cit.> and can be violated by letting the vertices v∈ V(𝒢_exc) be given by the stabilizer (separable) states

    | 0,+,+⟩,  | 1,-,+⟩, | 1,+,-⟩, | 0,-,-⟩
       | +,0,+⟩, | -,1,+⟩, | -,0,-⟩, | +,1,-⟩
       | +,+,0⟩, | -,-,0⟩, | -,+,1⟩, | +,-,1⟩
       | 1,1,1⟩,     | 0,0,1⟩,    | 0,1,0⟩,     | 1,0,0⟩.

and ⋆ by the Greenberger–Horne–Zeilinger (GHZ) state |GHZ⟩ = 1/√(2)(| 0,0,0⟩ + | 1,1,1⟩). In this way, 

    ∑_v ∈ V(𝒢_exc)r_⋆,v = ∑_v ∈ V(𝒢_exc) |⟨GHZ| v⟩ |^2 = 4 > 3.


The above shows that there are event-graph inequalities that can be violated by stabilizer states. 

Let us now discuss the relationship between generalized noncontextuality <cit.> and magic. It was shown in Refs. <cit.> that odd-dimensional stabilizer subtheory allows for a generalized noncontextual model. In this case, any violation of a noncontextuality inequality attesting to the failure of generalized contextuality will also be a witness of having states (transformations, measurement effects) outside the stabilizer subtheory. However, similarly to the case of KS-noncontextuality, for even-dimensional systems, no such noncontextual model for the stabilizer subtheory exists. Therefore, in general, even dimensional stabilizer subtheory can violate generalized noncontextuality inequalities. Finding which inequalities are not violated by such stabilizer subtheory becomes a case-by-case study. 


In summary, the connection between event graph inequalities and noncontextuality inequalities does not imply that any event graph inequality will immediately be a nonstabilizerness witness and therefore does not render our results trivial. On the other hand, it also does not make our results immediately incorrect. The fact that our inequality witnesses (which can also be interpreted as noncontextuality inequalities) cannot be violated by stabilizer states does not imply that they do not violate some noncontextuality inequality. As it is in general, for a given KS-measurement scenario (or equivalently, a generalized prepare-and-measure noncontextuality scenario), it is only if one satisfies all the noncontextuality inequalities that a noncontextual model exists.



§ COMPARISON WITH OTHER SCHEMES


In this Appendix, we make a comprehensive review of existing methods for witnessing the nonstabilizerness of quantum states. Clearly, any quantification scheme also constitutes a witness, thus, for a broader comparison, we were careful to include such methods as well. 



 §.§ Methods that require additional entanglement generation


We start by presenting two witnessing schemes that require additional entanglement; they use multifractal flatness <cit.> and spectral flatness <cit.>. First, define the inverse participation ratio,

    I_q(|ψ⟩) := ∑_b ∈𝔽_2^n|⟨ b|ψ⟩|^2q = ∑_b ∈𝔽_2^nr_b,ψ^q .

We note that, to calculate I_q(|ψ⟩) for any fixed q, one needs to evaluate d=2^n overlaps. The multifractal flatness is defined as

    ℱ_multi(|ψ⟩) := I_3(|ψ⟩)-(I_2(|ψ⟩))^2 .

This quantity witnesses nonstabilizerness whenever we obtain ℱ_multi(C|ψ⟩) > 0, where C is an n-qubit Clifford operation. Since both calculating and measuring this quantity require O(d=2^n) overlaps, this witnessing process is inefficient. We remark that, when averaged over the Clifford orbit of the state |ψ⟩, this witness provides information about the stabilizer Rényi entropy M_2 which we will discuss in more detail later on. 

Three key aspects of this witness stand in stark contrast to our scheme. First, it is device-dependent. Secondly, it is only applicable to pure states. Finally, it requires additional entangling gates to be applied over the state |ψ⟩, stemming from the Clifford unitary, C, needed for ℱ_multi(C|ψ⟩) > 0 to properly witness nonstabilizerness of |ψ⟩.

Another function that can be used to witness nonstabilizerness is the entanglement spectrum flatness ℱ_A(|ψ⟩). We consider a pure state |ψ⟩ [Ref. <cit.> exemplifies the task using an n-qubit fully separable state, but, to the best of our understanding, their protocol works for any state.] and some n-qubit Clifford operation C such that C |ψ⟩ is sufficiently entangled. In some cases, shallow Clifford evolutions are enough. We then choose an arbitrary bipartition ℋ_A ⊗ℋ_B ≃ℂ^⊗ n of the n-qubit system and calculate ρ_A := Tr_B(C|ψ⟩⟨ψ| C^†). The entanglement spectrum flatness of this bipartition is given by 

    ℱ_A(C|ψ⟩) Tr(ρ_A^3)-(Tr(ρ_A^2))^2.
 
If we obtain that ℱ_A(C|ψ⟩)>0, |ψ⟩ must be a magic state, and therefore ℱ_A(C|ψ⟩)>0 acts as a witness of nonstabilizerness. This witness can be efficiently measured (in terms of the number of measurements and samples of ρ_A required) using simple quantum circuits <cit.>. 

Let us discuss more explicitly the advantages and drawbacks of these techniques when compared to the scheme we propose in the main text. Entanglement spectrum flatness has the advantage that it can witness almost any magic state (in the sense of Haar random states). In contrast, in our inequality-based witness, certifications should target certain overlap values that become increasingly rare for large systems to randomly access. This happens since the two-state overlap between Haar random n-qubit states behaves as r_i,j∼ 1/2^n. Moreover, both flatness results from above can approximate values of nonstabilizer monotones; thus, they can ultimately be used for quantification (a task strictly more powerful than witnessing). At the moment, our protocol has no known link with quantification tools, although we believe this to be an interesting direction for future research.

On the other hand, unlike our scheme, both of these methods are device-dependent and applicable only to pure states. Additionally, let us assume that we would like to certify the generation of magic in some QPU of a network. Fig. <ref>(b) in the main text illustrates how to handle this task within our protocol. Notably, as explained therein, the certification can be distributed requiring fewer resources than if we were to certify each QPU individually [Fig. <ref>(a)]. Contrastingly, with either of the two witnesses presented here, distributing the certification requires us to entangle the degrees of freedom of the multiple QPUs in the network we are interested in certifying, due to the Clifford operations that must be applied. 



 §.§ Methods that require full information of the STAB polytope, or full information of the quantum state


The vast majority of quantification schemes require full information on the stabilizer polytope. Beyond that, they often also require full (tomographic) information of the quantum state. The following monotones require complete knowledge of the underlying state and of the STAB polytope: stabilizer fidelity <cit.>, stabilizer extent <cit.>, stabilizer rank <cit.>, stabilizer nullity <cit.>. Some that are also well-defined for generic mixed states, having the same drawbacks, are mana <cit.>, all variations of the robustness of magic <cit.>, relative entropy <cit.>, min- and max-relative entropies <cit.>, and the dyadic negativity <cit.>.

It is interesting to remark that the stabilizer extent ξ(|Ψ⟩) has the extremely useful property of being multiplicative,

    ξ(|Ψ⟩) ξ(|ψ_1⟩⊗…⊗|ψ_m ⟩) = ∏_j=1^m ξ(|ψ_j ⟩) ,

provided that all states |ψ_j ⟩ are 1-, 2- or 3-qubit states, i.e., that ψ⊆𝒟(ℂ^2^s) with s ∈{1,2,3} <cit.>.

This implies that an alternative strategy to witnessing magic is to make 1-, 2-, or 3-qubit state tomography of all states |ψ_j⟩, use that information to calculate their stabilizer extent, and then multiply the results. Compared to our scheme, beyond being significantly device-dependent and demanding great control of the system (since one must perform full tomography), our scheme requires a smaller number of measurements and samples (since overlap estimation is experimentally less demanding than performing full tomography, even for single-qubit systems). It has been shown that the stabilizer extent is not multiplicative in general <cit.>. It is also clear that, for larger systems, our witnessing technique will outperform any strategy that demands full-state tomography.

The stabilizer nullity can be extended to treat unitaries <cit.>. In this form, it gives a lower bound to the number of T gates required to apply a certain unitary. A similar property holds for other magic monotones. Bounding the number of T gates is not possible with our formalism, as this is a profoundly basis-dependent characterization.

It is noteworthy that several of the quantifiers mentioned above have been associated with the perspective of witnessing as can be seen in Ref. <cit.>. Therein some witnesses for single-qubit magic states were proposed. Additionally, the authors also show curious lower and upper bounds on the scaling of magic monotones as the number of qubits n grows. 



 §.§ Methods that are not valid for generic mixed states


To the best of our knowledge, various quantifiers have not been generalized beyond pure states; examples of these include stabilizer fidelity, stabilizer rank, and stabilizer nullity. On the other hand, the stabilizer extent has a mixed state version <cit.>.

Recall that if one assumes purity of states and multi-qubit systems, a trivial witness is to measure a single overlap of the state with respect to the | 0^n⟩ state, in which case deviations from 1/2^n will witness nonstabilizerness. Because of that, it is only quantification that proves to be a non-trivial task in the case of multi-qubit pure states. Therefore, in this section, we focus on quantification methods that are in some way efficient to calculate, or measure, at the cost of being defined only for pure states (or specific classes of mixed states). The stabilizer entropies are the most relevant monotones in this category. The first such entropy introduced was the stabilizer Rényi entropy <cit.>. While this quantity cannot be efficiently measured in general, it can be efficiently computed. Ref. <cit.> investigated when such functions can be considered monotones and provided an explicit case study where stabilizer entropies could be computed efficiently. Ref. <cit.> introduced novel stabilizer entropies that can also be efficiently measured, but are still defined only for pure states.

It is simple to see for the case of stabilizer Rényi entropies why the quantifiers do not hold for generic mixed states. Let us consider, for instance, the stabilizer 2-Rényi entropy defined for mixed states ρ∈𝒟(ℂ^2) as

    M̃_2(ρ)  -log_2 (∑_P(Tr(Pρ))^4/2 Tr (ρ^2))

where and the sum is taken over the +1 elements of the single-qubit Pauli group {1, X, Y, Z}. Crucially, M is not a monotone to any mixed state ρ, but only those with a specific form, given by ρ = 1/2+ 1/2∑_P ∈ Gϕ_P P where G is a subset of the single-qubit Pauli group, and ϕ_P ∈{-1,1} <cit.>. For instance, considering the magic state

    | F ⟩⟨ F | = 1/2(1+1/√(3)(X+Y+Z))

and mixed states ρ_ν = ℰ_ν(| F ⟩⟨ F | ) = (1-ν) | F⟩⟨ F | + ν1/2,
the monotone as a function of ν becomes

    M_2(ρ_ν) = -log_2 {1+3[(1-ν)/√(3)]^4/1+3[(1-ν)/√(3)]^2}.

Since M_2(ρ_ν)>0 for any ν>0, it is not a faithful monotone (or witness), since it would signal the presence of nonstabilizerness for states arbitrarily close to the maximally mixed state. 

Despite not being defined for mixed states, these monotones are extremely promising ways of efficiently estimating nonstabilizerness. For instance, Ref. <cit.> estimated magic in a cloud-available quantum computer. Ref. <cit.> showed that there are stabilizer entropies that can be efficiently measured, with the required number of measurements (or post-processing) being independent of system size. Finally, Ref. <cit.> introduced a novel monotone, which the authors termed “Bell magic”, that besides efficiently estimated on a quantum computer via Bell measurements also generalizes to certain sets of mixed states. Bell magic was recently measured in Ref. <cit.>.



 §.§ Methods that are semi-device independent


Due to the connection between magic, the negativity of quasiprobability distributions and noncontextuality (both Kochen–Specker and generalized), under certain considerations, any test of such notions of classicality will also be a test capable of witnessing nonstabilizerness. This was already discussed in Appendix <ref>. Here, we comment on the device- or semi-device-independence of these tests.

Our witnesses are inequality-based and semi-device independent in the sense that (i) the test is made based only on statistics arising from two-state overlaps and (ii) we assume (in most cases) that the underlying system is a multi-qubit system. These restrictions are the “semi” for our approach. Inequalities that can be used to witness noncontextuality are significantly more device-independent, in the sense that they are not necessarily overlap-based (or correlation-based), while they will necessarily require some prior information about the Hilbert space considered: even, odd,  odd-prime, or composite system dimensionality structures.

One subtle point needs to be made:  Violations of noncontextuality inequalities per se do not suffice to experimentally witness the failure of noncontextual explanations of the data. One must also test that the experimental requirements relative to the notions of KS-noncontextuality or generalized noncontextuality are operationally met. Similarly to Bell inequality violations, merely violating them does not attest to the failure of a local explanation of the data; some minimal requirements need to be met (such as space-like separation between parties, no-signaling, etc.). In our case, the requirement is that the data is described by two-state overlaps, while in noncontextuality inequalities other requirements are needed, and should be taken into consideration, even if one is only interested in witnessing nonstabilizerness due to contextuality.  




§ PROOF OF THEOREM <REF>


In this Appendix, we start by building a series of results that are used to facilitate the proof of Theorem <ref>.

The inequality h_4(r)≤ 1 is facet-defining for ℭ(𝒦_4), where 𝒦_4 is the complete graph of four vertices. This inequality is given by

    h_4(r) = r_1,2+r_1,3+r_1,4-r_2,3-r_2,4-r_3,4≤ 1.


We now demonstrate the following lemma.

    Let 𝒢 = 𝒦_m. If r=r(ψ) such that the ψ-labeling ℓ: V(𝒢) →ψ assigns the same pure state to adjacent vertices (any pair of vertices sharing an edge), then h_m(r(ψ)) ≤ 1.
    



    Without loss of generality, we may consider r_1,k^⋆=1 for some k^⋆≠ 1. Let r=r(ψ) be any pure state realization satisfying this constraint. In this case, we must have that |ψ_1⟩ = |ψ_k^⋆⟩. Therefore, r_1,k=r_k^⋆, k for all k={2,…,m}\{k^⋆}. The inequality h_m(r) ≤ 1 is then written as 
    
    h_m(r)    = ∑_k=2^m r_1,k-∑_i=2^m-1∑_j>i^mr_i,j
       = 1+∑_[    k=2; k≠ k^⋆ ]^m r_k^⋆, k-∑_i=2^m-1∑_j>i^mr_i,j
       = 1-∑_[    i=2; i≠ k^⋆ ]^m-1( ∑_[    j>i; j≠ k^⋆ ]^m r_i,j) ≤ 1

    where we have used the fact that every element r_k^⋆, k is present in the sum ∑_i=2^m-1∑_j>i^mr_i,j.



Recall that 𝔔(𝒢) is the set of all quantum realizable edge-weights given an event graph 𝒢. Any stabilizer realization is (evidently) a quantum realization. In the remainder of this Appendix, we will focus on situations concerning stabilizer realizations.

Let us now show that, assuming an edge-weight is non-zero then its stabilizer realization has a lower bound.

    Take three (arbitrary) n-qubit stabilizer states |ψ_1⟩, |ψ_2 ⟩, and |ψ_3 ⟩ such that r_1,2 = 1/2^N_2, r_1,3 = 1/2^N_3 and r_2,3≠ 0. Then, r_2,3≥ 1/2^N_2+N_3 where N_2,N_3∈{0,…,n}.



    Without loss of generality, we can take |ψ_1⟩ = |0^n⟩. Let us start by considering the case where both N_2,N_3 ≠ 0 or, equivalently, where r_1,2,r_1,3≠ 1. Since r_1,2 = 1/2^N_2, we have that |ψ_2 ⟩ is of the form 
    
    |ψ_2 ⟩ = 1/2^N_2/2( | 0^n⟩ + ∑_j=1^2^N_2-1 i^α_j|a_j⟩)

    where α_j ∈ℤ_4 and a_j ∈𝔽_2^n\{0^n}.
    Similarly, r_1,3 = 1/2^N_3 implies that the state |ψ_3 ⟩ is of the form 
    
    |ψ_3 ⟩ = 1/2^N_3/2( | 0^n⟩ + ∑_j=1^2^N_3-1 i^β_j|b_j⟩),

    where β_j ∈ℤ_4 and b_j ∈𝔽_2^n\{0^n}. From this, we see that
    
    r_2,3 = 1/2^N_2+N_3| 1 + ∑_j,j^' i^α_j - β_j^'⟨b_j^'|a_j|⟩|^2.

   If r_2,3≠ 0, it is clear from the expression above that r_2,3≥ 1/(2^N_2+N_3).

   Finally, we note that, if either N_i= 0, we have the corresponding state |ψ_i⟩ = |0^n⟩. In that case, it is clear that r_2,3 = 1/2^N_j, with j≠ i, which complies with the lower bound established above. 


Next, we demonstrate a result concerning realizations containing orthogonal states. This is the most important stepping stone to the proof of Theorem <ref> because realizations involving null edge-weights are significantly harder to analyze with respect to inequality violations. 

    Let 𝒢 = 𝒦_4 and consider a quantum realization r=r(ρ_STAB) ∈𝔔(𝒦_4), where STAB denotes the set of n-qubit stabilizer states. If such a realization assigns to any two vertices two orthogonal states, then h_4(r) ≤ 1.
    


    Consider the set of four (pure) n-qubit stabilizer states: {|ψ_1⟩, |ψ_2⟩, |ψ_3⟩, |ψ_4⟩}, where |ψ_i⟩ is the stabilizer state associated with the ith vertex.
    The following observations follow trivially from Lemma <ref> when considering realizations with stabilizer states: (i) If four or more overlaps are zero, Eq. (<ref>) cannot be violated; (ii) If |ψ_1⟩ is orthogonal to any of the other states, again no violation of Eq. (<ref>) is possible; (iii) To achieve a violation, at least two of the overlaps r_1,j must equal 1/2 and the remaining overlap with positive contribution must obey r_1,k>r_2,3 + r_2,4 + r_3,4 with k≠ j. 

    Throughout, we take r_1,2 = 1/2 and |ψ_2⟩ = |0^n⟩ which imposes that |ψ_1⟩ = (|0^n⟩ + i^α|s⟩)/√(2), where α∈ℤ_4, s∈𝔽_2^n\{0^n}, and |s⟩ denotes the corresponding computational-basis state. Moreover, we can set α = 0 because there is always a Clifford unitary that transforms (|0^n⟩ + i^α|s⟩)/√(2) into (|0^n⟩ + |s⟩)/√(2) while leaving the state |0^n⟩ unchanged. Thus, for simplicity, we take |ψ_1⟩ = (|0^n⟩ + |s⟩)/√(2). All of this is done wlog.
    
    If we have three overlaps equal to zero, the only way for a violation to occur is that: (i) r_2,3 = r_2,4 = r_3,4 = 0, (ii) r_1,3 = 1/2, and (iii) r_1,4>0. Note that the roles of r_1,3 and r_1,4 could be switched, leading exactly to the same conclusion. We will now show that these three conditions are incompatible. A generic stabilizer state takes the form:
    
    |ψ_j⟩ = 1/√(|𝒲_j|)∑_w∈𝒲_j i^α_w|w⟩

    where 𝒲_j ⊆𝔽_2^n and |𝒲_j| = 2^N_j, for some N_j∈{0,n}. For the state to be a stabilizer state, 𝒲_j and α_w must possess specific properties; these are irrelevant for the purposes of our proof and we will therefore omit them, but the interested reader is pointed to Appendix A of Ref. <cit.> or Theorem 9 of Ref. <cit.> for details.
    
    Since, r_2,3 = 0, for the state |ψ_3⟩, 0^n cannot belong to 𝒲_3. Combining this observation with condition (ii), and given that |ψ_1⟩ = (|0^n⟩ + |s⟩)/√(2), it clear that |ψ_3⟩ = |s⟩. Because r_2,4 = r_3,4 = 0, the remaining state |ψ_4⟩ must be a linear combination of computational-basis states so that 0^n,s ∉𝒲_4. This necessarily means that r_1,4 = 0, violating condition (iii). 
    
    If exactly two of the overlaps {r_2,3, r_2,4,r_3,4} are zero, Fig. <ref>(a) illustrates the nine possible combinations of edge-weight assignments that could potentially lead to violations. Fortunately, symmetry constraints illustrated therein mean that we can restrict ourselves to only two different sub-cases.
    

    Subcase1.–We consider the case depicted in the second row of the second column of Fig. <ref>(a): r_1,2 = r_1,3 = 1/2 and r_2,3 = r_2,4 = 0. Every scenario in the top two rows is equivalent to this one.
    
    For a violation to occur r_1,4 > r_3,4. The fact that r_1,3 = 1/2 and r_2,3 = 0 implies that |ψ_3⟩ = |s⟩. The state placed at the fourth vertex can admit the form in Eq. (<ref>). Because r_2,4=0 then 0^n∉𝒲_4; contrarily, since r_3,4≠ 0, s∈𝒲_4. Immediately, this means that r_1,4 = 1/2^N_4+1 while r_3,4 = 1/2^N_4, which means that r_3,4 > r_1,4, and therefore no violation can occur. 

    Subcase2.– We now consider the cases in the bottom row of Fig. <ref>(a) which are all equivalent between themselves, but non-equivalent to the six cases in the top two rows. We take the edge-weight assignment on the first column: r_1,2 = r_1,4 = 1/2 and r_2,3 = r_3,4 = 0. This means that, for a violation to occur r_1,3 > r_2,4. The condition that r_1,4 = 1/2 enforces one of the following three forms for |ψ_4⟩:
    
    |ψ_4⟩ = 
            |0^n⟩
    |s⟩
    |0^n⟩ + i^β|s⟩/√(2), β∈{1,3} .

    Lemma <ref> informs us that the first option will lead to no violation; moreover, the second option leads to r_2,4 = 0 taking us back to the three-null-overlaps situation which we already proved leads to no violation. This leaves us with the last option, that is: |ψ_4⟩ = (|0^n⟩ + i^β|s⟩)√(2), with β∈{1,3}. Immediately, we see that r_2,4 = 1/2, and therefore it is impossible to meet that condition that r_1,3 > r_2,4, so that no violation is possible in this case either.

    Finally, it remains to assess the case where only a single null overlap exists. Fig. <ref>(b) illustrates the three possible edge-weight assignments that may lead to violations. We note that the top two cases are equivalent, meaning that, again, we have to focus only on two subcases.

    Subcase1.–We consider r_1,2 = r_1,4 = 1/2 and r_2,3 = 0 (second row of Fig. <ref>(b)). For a violation to occur, the following must hold r_1,3 > r_2,4 + r_3,4. We note that r_1,4 = 1/2 and r_2,4≠ 0 implies that |ψ_4⟩ = (|0⟩ + i^β|s⟩)/√(2), with β= {1,3}. This fixes r_2,4 = 1/2 which immediately means that the condition r_1,3 > r_2,4 + r_3,4 can never be met, and therefore no violation can occur.
    
    Subcase2.–We consider r_1,2 = r_1,3 = 1/2 and r_2,3 = 0. This means that for a violation to hold, we must have r_1,4 > r_2,4 + r_3,4. The fact that r_1,3 = 1/2 and r_2,3 = 0 implies that |ψ_3⟩ = |s⟩. The state in the fourth vertex can assume the general form given by Eq. (<ref>) where both 0^n and s must belong to the set 𝒲_4 (otherwise, we fall back into the cases with two or three null overlaps). Automatically this means that r_2,4 = r_3,4 = 1/2^N_4. On the other hand, r_1,4 can be (at most) r_1,4 = 1/2^N_4-1, which means that the condition r_1,4 > r_2,4 + r_3,4 cannot be met, and therefore no violation can occur.

    This concludes the assessment of all possible cases. Therefore, if any overlap r_i,j is zero, no violation of the inequality (<ref>) is possible.


Finally, we have all the tools needed to prove Theorem <ref> of the main text.


    Consider a set of four (pure) n-qubit stabilizer states: {|ψ_1⟩, |ψ_2⟩, |ψ_3⟩, |ψ_4⟩}. Recall that, if we want to find a violation of Eq. (<ref>), no two states can be the same (Lemma <ref>) so that: |ψ_i⟩≠|ψ_j⟩ for i≠ j. Therefore, to obtain h_4 > 1 the following conditions must hold: (i) there are at least two r_1,j = 1/2, (ii) the remaining overlap r_1,k with k≠ j must obey: r_1,k > r_2,3 + r_2,4 + r_3,4 .

    Without loss of generality, take |ψ_1⟩ = |0^n⟩ and assume that r_1,2 = r_1,4 = 1/2 . Under these assumptions, for a violation to occur we must have r_1,3 > r_2,3 + r_2,4 + r_3,4 .
    
    Because r_1,2 = 1/2 this means that |ψ_2⟩ = (|0^n⟩ + |s⟩)/√(2) where s∈𝔽_2^n\{0^n}. Evidently, something similar can be said for |ψ_4⟩: |ψ_4⟩ = (|0^n⟩ + i^α|w⟩)/√(2), with w∈𝔽_2^n\{0^n} and α∈ℤ_4. This will impose a constraint on the overlap r_2,4:
    
    r_2,4 = 
            
            1,     if  w=s α = 0 
    
            0,     if  w=s α = 2 
    
            1/2,   if  w=s α = {1,3}
    
            1/4,   if  w≠ s
             .

    Lemmas <ref> and <ref> guarantee, respectively, that the first and second options give no violation and we can thus focus on the other two.

    Taking r_2,4 = 1/2 we have: r_1,3 > 1/2 + r_2,3 + r_3,4, which is impossible to verify since at most r_1,3 can be 1/2.

    Taking r_2,4 = 1/4 we get the condition r_1,3 > 1/4 + r_2,3 + r_3,4. In order for this to hold, r_1,3 must be equal to 1/2 which implies that the corresponding state must take the form |ψ_3⟩ = (|0^n⟩ + i^β|t⟩)/√(2). Immediately, this will imply that the values for r_2,3 and r_3,4 are bounded as r_2,4 in Eq. (<ref>). Since we know realizations with null overlaps to yield no violation (Lemma <ref>), it is clear that the condition r_1,3 > 1/4 + r_2,3 + r_3,4 can never be met, because r_1,3 can be at most 1/2.

    Theorem <ref> guarantees that this holds also for mixed stabilizer states. This concludes the proof.


We conclude this Appendix by generalizing Thereom <ref> for d-dimensional qudits.


    There exists no quantum realization r=r(ρ_STAB(d)) ∈𝔔(𝒦_4), where STAB(d) denotes the set of stabilizer states of n d-dimensional qudits, such that h_4(r) >1, for any integer value n≥ 1.
    


    The overlap | ⟨ψ|ϕ⟩|^2 of any two non-orthogonal stabilizer states, |ψ⟩ and |ϕ⟩, of n qudits of dimension d can assume value 1/d^N with 0 ≤ N ≤ n, see Lemma 2 of Ref. <cit.> on the overlap between pure stabilizer states. 

    Again, Lemma <ref> guarantees that, if any state is repeated, there is no violation of the inequality, so we assume all states to be different. The positive terms in h_4(r) lead to r_1,2 + r_1,3 + r_1,4 = 3/d , in the best case. For d = 3 this leads to a value of at most 1 and for d>3 the value will be smaller than one. As a consequence, it is immediately realized that no violation of the inequality is possible.






§ FULL SET MAGIC AND OVERLAP ESTIMATION


In this Appendix, we present numerical evidence for the ability of odd cycle inequalities to witness full set magic. As can bee seen from Table <ref>, letting ρ= {ρ_i}_i=1^m ⊆𝒟(ℂ^2) be the set of states such that c_m(r(ρ))>m-2, we have that at least m-2 states of ρ must be magic states. Depending on how large the violation is, we have that, other than one reference state that can always be unitarily sent inside STAB, all other states must be magic. The second column from Table <ref> is obtained as follows. We assume that there are at least two states in a set {|ψ_i ⟩}_i=1^m that are single-qubit stabilizer states. Without loss of generality, we can take {| 0⟩, | +⟩}. All the remaining m-2 states are generic single-qubit states of the form |ψ_i⟩ = cos(θ_i)| 0⟩ + e^i ϕ_isin(θ_i)| 1 ⟩. For all possible combinations of m-2 generic states with the two chosen stabilizer states (or, equivalently, all possible edge ψ-labelings of the graph  𝒞_m permuting the two STAB states), we maximize c_m with respect to the variables θ= {θ_i}_i and ϕ= {ϕ_i}_i.

Let us take c_4 as an example. The set of quantum states is {| 0⟩, | +⟩, |ψ_1⟩, |ψ_2⟩} and two possible maximizations are c_m(r(ℓ_1(ψ))) = -r_0,++r_+,1+r_1,2+r_2,0
and c_m(r(ℓ_2(ψ))) = -r_0,1+r_1,++r_+,2+r_2,0.
The tool used for the maximization was  of Wolfram Mathematica and all available solvers were tested, with the final result presented as the one that found the largest value. Note that, as before, even though we are maximizing for pure states, the results presented in Table <ref> hold for generic mixed states. The last column corresponds to the situation wherein the set is allowed to be full set magic, i.e., all states but one are magic.

Interestingly, for even cycle inequalities, we cannot witness full set magic since m-2 magic states are sufficient to maximally violate the inequality. Moreover, we can see that the gap between set magic and full set magic decreases as m increases.


We take this opportunity to discuss different strategies for evaluating two-state overlaps. One option is to consider prepare-and-measure estimation. In this case, a preparation stage prepares states |ψ_i⟩ = U_i | 0⟩, while a measurement stage acts as a projection onto ⟨ψ_j | = ⟨ 0 |  U_j^†. Assuming we are in the regime of full set magic, each overlap inequality will certify the nonstabilizerness of all the preparations U_i and all measurements U_j.

Another possibility is to use the SWAP-test <cit.> which, despite using a nonstabilizer gate (the Fredkin gate), can unambiguously witness nonstabilizerness of the quantum states that are sent by a third party (sender). If we want to avoid the use of auxiliary qubits and nonstabilizer operations to estimate the overlaps, we can instead use Bell measurements <cit.>.

Finally, in the context of linear-optical implementations, we can use the Hong-Ou-Mandel effect <cit.>. Any linear-optical interferometer that is insensitive to internal degrees of freedom of the photons (e.g. polarization, frequency, time of arrival) has outcomes determined only by unitary-invariant properties of the spectral functions describing them <cit.>. This means the Hong-Ou-Mandel effect, or interferometry in more complex multimode interferometers, can be used to directly estimate those invariant properties. Such a test could be used to certify the nonstabilizerness of these states.

