Source-linked AI summary
Robustness of Magic and Symmetries of the Stabiliser Polytope
Markus Heinrich, David Gross
TL;DR
Computing the robustness of many-copy magic states is difficult because direct optimisation grows exponentially with the number of qubits. The paper exploits shared symmetries to reduce the problem, obtains exact and approximate results for common magic states, and improves the associated simulation runtime. The approach also provides polynomial-time upper-bound hierarchies and remains applicable to noisy circuits and mixed states.
Problem
Directly computing R(ρ^⊗n) requires optimisation in a 4^n-dimensional space over exponentially many stabiliser states, making the task computationally difficult.
Method
The paper quotients out symmetries shared by tensor-power magic states and the stabiliser polytope, then constructs entanglement-restricted approximation hierarchies.
Results
The method evaluates |H⟩^⊗n for n ≤ 9 and |T⟩^⊗n for n ≤ 10, and implies an RoM simulation runtime of O(20.737t) for t T gates.
Takeaways & Limitations
The approximation hierarchy provides rigorous upper bounds, agrees excellently with exact data through n ≤ 10, and each level is computable in polynomial time.
Takeaways & Limitations
The reduced optimisation remains exponential in n, and its projected-state oracle has runtime that is still super-exponential in n.
Abstract
from arXiv · showhide
We give a new algorithm for computing the robustness of magic - a measure of the utility of quantum states as a computational resource. Our work is motivated by the magic state model of fault-tolerant quantum computation. In this model, all unitaries belong to the Clifford group. Non-Clifford operations are effected by injecting non-stabiliser states, which are referred to as magic states in this context. The robustness of magic measures the complexity of simulating such a circuit using a classical Monte Carlo algorithm. It is closely related to the degree negativity that slows down Monte Carlo simulations through the infamous sign problem. Surprisingly, the robustness of magic is submultiplicative. This implies that the classical simulation overhead scales subexponentially with the number of injected magic states - better than a naive analysis would suggest. However, determining the robustness of n copies of a magic state is difficult, as its definition involves a convex optimisation problem in a 4^n-dimensional space. In this paper, we make use of inherent symmetries to reduce the problem to n dimensions. The total run-time of our algorithm, while still exponential in n, is super-polynomially faster than previously published methods. We provide a computer implementation and give the robustness of up to 10 copies of the most commonly used magic states. Guided by the exact results, we find a finite hierarchy of approximate solutions where each level can be evaluated in polynomial time and yields rigorous upper bounds to the robustness. Technically, we use symmetries of the stabiliser polytope to connect the robustness of magic to the geometry of a low-dimensional convex polytope generated by certain signed quantum weight enumerators. As a by-product, we characterised the automorphism group of the stabiliser polytope, and, more generally, of projections onto complex projective 3-designs.
1 Introduction
The paper develops a symmetry-reduced approach to computing the robustness of magic, motivated by magic-state injection and classical simulation costs. It provides exact and approximate results for common magic states and improves the resulting simulation runtime.
- Motivation: Magic-state injection supplies non-Clifford gates within a Clifford-based fault-tolerant model, while distillation converts mixed states into pure magic states using Clifford operations.The paper frames non-stabiliser states as computational resources because Clifford operations alone admit efficient classical simulation.
- Motivation: The robustness of magic quantifies affine negativity in stabiliser-state decompositions, with Monte Carlo sample complexity scaling as O(R(ρ)^2).It also provides a resource measure connected to the utility of auxiliary states and lower bounds for certain non-Clifford synthesis tasks.
- Problem: Submultiplicativity makes the robustness of n copies smaller than the naive product bound, but direct optimisation is computationally intractable and had previously reached only n = 5.For n-qubit tensor powers, the optimisation involves a 4^n-dimensional space and exponentially many stabiliser states.
- Approach: A shared symmetry group of the tensor-power state and stabiliser polytope reduces the optimisation space to dimension n for |H⟩^⊗n and |T⟩^⊗n, yielding a super-polynomial speed-up.The projected polytope still has exponentially many vertices, but the symmetry-reduced formulation makes the computation substantially faster.
- Results: The method evaluates |H⟩^⊗n through n ≤ 9 and |T⟩^⊗n through n ≤ 10, while a finite hierarchy gives polynomial-time upper bounds that agree excellently with exact data through n ≤ 10.The hierarchy restricts stabiliser states by entanglement size and converges to the exact robustness.
- Results: The resulting RoM simulation runtime is O(20.737t) for t T gates, improving on O(20.753t) while remaining applicable to noisy circuits and mixed states.The paper contrasts this with stabiliser-rank runtimes reported for pure states.
2 Robustness of Magic
The robustness of magic is defined relative to the stabiliser polytope as a resource monotone based on affine decompositions. It is faithful, monotone under stabiliser operations, and convex.
- Definition: Robustness quantifies the minimum total weight of a pseudo-mixture relative to free stabiliser resources, with an equivalent formulation related affinely to the robustness of magic.The construction generalises robustness measures from resource theories such as entanglement.
- Definition: The stabiliser polytope SP_n is the convex hull of all n-qubit stabiliser states and represents the free resources in the magic-state model.States inside this polytope can be classically simulated by sampling stabiliser states and applying Gottesman–Knill simulation.
- Properties: The robustness of magic is faithful: R(ρ) = 1 exactly for states in SP_n, and it cannot increase under stabiliser operations.Unitary stabiliser operations preserve the measure, while general stabiliser operations can reduce it.
- Properties: The robustness of magic is convex, so mixing states cannot exceed the corresponding weighted average of their robustness values.For 0 ≤ t ≤ 1, R((1 − t)ρ + tσ) ≤ (1 − t)R(ρ) + tR(σ).
3 Exploiting stabiliser symmetries
The paper reduces robustness-of-magic optimisation by exploiting stabiliser-polytope symmetries, replacing the full problem with an optimisation over invariant projected states. For tensor powers of |H⟩ or |T⟩, the invariant space has dimension n, enabling substantially faster computation while revealing the relevant symmetry structure and remaining computational limits.
- 3.1 Definition of the RoM problem.: The RoM problem is a linear program whose super-exponential stabiliser-state representation makes evaluation impractical beyond small qubit numbers.The formulation has N = 2^O(n^2) stabiliser states and D^2 = 4^n dimensions; practical evaluation is limited to n ≤5 on ordinary computers and infeasible for n ≥8.
- 3.2 Symmetry reduction: The stabiliser-polytope automorphism group is precisely the adjoint representation of the extended Clifford group, including unitary Clifford operations and global antiunitary symmetries.The result relies on the stabiliser states’ design structure and does not generally extend to odd-dimensional qudits.
- 3.2 Symmetry reduction: An optimal RoM decomposition can always be chosen invariant under a subgroup Gρ that fixes the target state, so optimisation may be restricted to projected invariant stabiliser states.The projection preserves the stabiliser polytope and maps an optimal decomposition to another optimal decomposition in the invariant subspace.
- 3.2 Symmetry reduction: For |H⟩^⊗n and |T⟩^⊗n, the symmetry-reduced invariant space has exactly n dimensions, although its projected stabiliser polytope can still have exponentially many vertices.The reduction yields a super-polynomially faster algorithm despite the remaining exponential vertex count.
- 3.3 Identification of symmetries: Projected products can be computed from their factors’ projections using signed quantum weight enumerators in polynomial time rather than O(2^n) operations for general entangled stabiliser states.This provides an efficient route for generating projected product states, although the broader generation procedure eventually becomes computationally expensive and produces many non-extremal points.
4 Computing the robustness of magic
The paper computes robustness for multi-copy |H⟩ and |T⟩ states by projecting the stabiliser polytope into a symmetry-reduced space, enabling faster optimisation and exact results up to 10 qubits. It also analyses optimal decompositions and develops polynomial-time approximation hierarchies with rigorous upper bounds.
- 4 Computing the robustness of magic: The projected-polytope linear program reduces the stabiliser-state count from 2^O(n^2) to approximately 2^n and the ambient dimension from 4^n−1 to n.This yields a super-polynomial speed-up, although the overall procedure remains exponential and the oracle for projected states is still super-exponential.
- 4.1 Robustness of the |H⟩⊗n and |T⟩⊗n states: For |H⟩^⊗n, the computed robustness follows (1.059 ± 0.015) × (1.283 ± 0.002)^n, approaching effectively multiplicative scaling for larger n.The data show submultiplicativity for n ≤ 4 and an apparent asymptotic regularised robustness of 1.283 ± 0.002.
- 4.1 Robustness of the |H⟩⊗n and |T⟩⊗n states: For |T⟩^⊗n, the algorithm reaches 10 qubits and finds the higher scaling (1.169 ± 0.011) × (1.3865 ± 0.0014)^n.The T-state results qualitatively match the H-state results while exhibiting considerably larger robustness.
- 4.2 Analysis of the optimal solutions: Positive optimal contributions for |H⟩^⊗n use products of |+⟩ and |Ψ+⟩, whereas negative contributions are more numerous and appear partially irregular.The negative terms are nevertheless dominated by products of |±⟩ and Bell states, motivating Bell-state approximations.
- 4.2 Analysis of the optimal solutions: The Bell-state approximation for |H⟩^⊗n is exact through n = 4 and deviates by at most 0.06% for 4 < n ≤ 9, while the corresponding |T⟩ approximation deviates by around 0.8%.The H approximation predicts 1.2829 ± 0.0017 asymptotically; the T approximation predicts 1.3916 ± 0.0014 and is limited to n ≤ 24 by optimisation infeasibility.
5 Conclusion & Outlook
The paper uses stabiliser-polytope symmetries to reduce robustness-of-magic computations and develops efficient approximate hierarchies with rigorous upper bounds.
- The authors determine symmetry groups and representatives for two single-qubit magic-state families, enabling robustness evaluation for |H⟩^n up to n≤9 and |T⟩^n up to n≤10.These results expose structure that reduces the combinatorial complexity of the robustness problem.
- A bipartite-entanglement approximation is efficient in n, gives an upper bound on exact robustness, and agrees excellently with exact data through n=10.The authors expect it to remain useful beyond n=10 because RoM becomes effectively multiplicative for larger n.
- Restricting stabiliser states to k-partite entanglement yields a finite approximation hierarchy that is exact at k=n and computable in poly(n) time for fixed k<n.
- The paper leaves open why two-body entangled states already provide excellent robustness bounds, relating this question to sub-additivity in quantum-information resource costs.The authors identify this explanation as a potentially broader insight.
A Equivalence of the two robustness measures
This appendix gives an explicit proof that the paper’s robustness formulation is equivalent to total robustness for compact polytopes.
- The appendix explicitly proves the equivalence between the two robustness measures, extending an implicit statement from earlier work.
- For a compact polytope, the minimum in the robustness formulation is attained, allowing the optimal value to be expressed using a minimizing point.
- Convex decompositions over the polytope’s vertices establish feasibility and bounds for the corresponding coefficient vectors.
- The proof rewrites optimal affine coefficients into a feasible pseudo-mixture whose parameter cannot be smaller than total robustness.
B On the dual RoM problem
The dual formulation provides an equivalent optimisation problem for robustness of magic and yields a Pauli-basis lower bound known as the stabiliser norm.
- Strong duality makes the dual optimisation problem an equivalent definition of the robustness of magic.The equivalence follows from Slater’s condition.
- The dual problem optimises over an operator Y subject to |tr(Y s_i)|≤1 for every n-qubit stabiliser state.
- A feasible Pauli-operator construction produces an objective value determined by the state’s Pauli coefficient vector.The Pauli operators generate the n-qubit Pauli group.
- The resulting stabiliser norm supplies a lower bound on robustness for |H⟩^n and |T⟩^n.
C Symmetries of 3-designs
The appendix characterises linear symmetries of projective designs and applies the 3-design result to identify stabiliser-polytope automorphisms with the extended Clifford group.
- For a 3-design, any linear map permuting the projectors is conjugation by either a unitary or antiunitary operator.The 1-design and 2-design cases separately imply unitality, orthogonality, and trace preservation.
- The proof establishes tight-frame structure for traceless operators and then uses invariant trilinear forms to constrain the symmetry map to a Jordan automorphism.
- The resulting Jordan automorphism is either an algebra automorphism or anti-automorphism, corresponding respectively to unitary or antiunitary conjugation.
- For qubit stabiliser states, this characterisation yields Aut(SP_n)=Ad(EC_n), the adjoint representation of the extended Clifford group.
- The qubit conclusion does not generally extend to odd-dimensional qudits, where 2-design symmetries can exist outside linear or antilinear state-vector representations.For prime d≥5, determinant constraints exhibit such additional symmetries.
D Numerical implementation
The implementation generates projected stabiliser-polytope vertices using graph-state representatives, weight-enumerator evaluations, product states, and an output-sensitive extremal-point algorithm.
- The algorithm generates projected stabiliser-polytope vertices from graph-state representatives, product states, and partition-based constructions.Graph representatives, generator matrices, local symplectic operations, and projection routines are used in the construction.
- The projection and product-state routines evaluate the weight-enumerator formulas used to construct the relevant vertices.
- The extremal-point computation uses an output-sensitive algorithm with time complexity O(dNm), where N is input size and m is the number of extremal points.This improves over a naive approach because N = O(2^n2) is much larger than m = O(2^n).
E.1 Group projections
Group projections average a group action to map vectors onto the invariant subspace, providing the symmetry-reduction operation used throughout the paper.
- A G-projection maps a vector space onto the subspace of points fixed by the represented finite group G.
- For orthogonal or unitary representations, the G-projection is itself orthogonal or unitary and is constant on group orbits.
- When G is a semidirect product N ⋊ H, its projection factors as ΠG = ΠN ◦ ΠH = ΠH ◦ ΠN.
E.2 Symmetries in convex optimisation
Symmetries preserve feasibility and objective values in the convex optimisation problem, so optimisation can be restricted to the invariant subspace without changing the optimum.
- The reduced problem remains convex, with an affine equality map and convex inequality constraints.
- A proper symmetry preserves feasibility because the objective is invariant, constraints are equivariant, and the group action preserves the component-wise order.
- Every G-symmetric convex optimisation problem has a G-invariant optimal solution.Projecting any optimal solution yields a feasible invariant solution with no larger objective value.
- The original convex optimisation problem is equivalent to a symmetry-reduced problem over the G-invariant subspaces of its variables and constraints.The reduced objective, affine map, and convex constraint are defined through equivariant projection relations.
- The original and reduced problems have the same optimal objective value because feasible solutions map between them while preserving the objective.
E.3 Affine constraints and symmetries
When a symmetry group permutes the vertices of a polytope and fixes the affine part, the associated affine constraints become equivariant and reduce to orbit-level coordinates.
- If the group leaves the vertex set invariant and fixes the affine part, it induces a permutation action that makes the affine map G-equivariant.
- The invariant coordinate dimension equals the number of vertex orbits, so affine constraints can be represented using orbit-level variables.
- The symmetry reduction assumes the group action preserves the relevant range of the affine map, although this is weaker than full G-equivariance.
- A symmetry reduction projects the polytope onto the invariant subspace, equivalently intersecting the polytope with that subspace.
- Computing the projected vertices requires only one representative from each vertex orbit because the projection is constant on orbits.