Fewest stabilizer terms for magic states

Task

Write a magic state as a linear combination of as few stabilizer states as possible. The target amplitudes below are unnormalized. Bit q of x corresponds to qubit q, and w = |x| is the number of ones in x.

• T-m (m = 1 to 14, on m qubits): amplitude ζ^w, with ζ = e^iπ/4.
• CCZ-k (k = 1 to 4, on 3k qubits): amplitude ∏_b (−1)^{x_3bx_3b+1x_3b+2}.
• face-m (m = 1 to 14, on m qubits): amplitude (1 + √3)^m−w (1 + i)^w. This is m copies of the face state, whose Bloch vector is (1, 1, 1)/√3 (the T-type magic state of Bravyi and Kitaev). It is a different state from |T>.
• sqrtT-m (m = 1 to 14, on m qubits): amplitude η^w, with η = e^iπ/8, so m copies of |0> + e^iπ/8|1>.
• CS-m (m = 1 to 7, on 2m qubits): amplitude i^{Σ_j x_2jx_2j+1}, so copy j of CS|++> sits on qubits 2j and 2j+1.
• cat-m (m = 2 to 14, on m qubits): amplitude i^w/2 when w is even and 0 when w is odd. This is the magic cat state of Qassim, Pashayan and Gosset, (|T>^⊗m + (Z|T>)^⊗m)/2. It is one state on m qubits, not m copies of a smaller state.
• C3Z-m (m = 1 to 3, on 4m qubits): amplitude ∏_j (−1)^{x_4jx_4j+1x_4j+2x_4j+3}, so copy j of CCCZ|++++> sits on qubits 4j to 4j+3.

Each instance file states its family, the number of copies, the number of qubits n and the limit of 256 states.

Submission file

JSON structure:

{"n": 2, "states": [{"h": "00", "G": ["10", "01"], "Q": [], "L": [0, 0]}, {"h": "11", "G": [], "Q": [], "L": []}]}

This example is valid for CS-1: CS|++> is the all-ones vector plus (i − 1)|11>. The verifier bundle contains a larger example.

Each submitted state has the amplitude i^{Σ l_i y_i} (−1)^{Σ_(i,j)∈Q y_iy_j} at the basis state h ⊕ yG, for every y ∈ {0,1}^k, and amplitude 0 elsewhere.

• Bit strings use the same convention as the targets: character i is qubit i.
• k is the number of rows of G. G must have full row rank over GF(2).
• Pairs in Q satisfy 0 ≤ i ≤ j < k, with no repeats. Each l_i is 0, 1, 2 or 3.
• This representation can express every stabilizer state (Dehaene and De Moor, quant-ph/0304125). The witnesses of the Unitary Foundation challenge use the same convention (x0 = h, W = G, the upper triangle of their Q, l = L).
• Submit at most 256 states. Do not send coefficients; the verifier solves for them.

Validation

The verifier decides whether the target lies in the span of your states, using exact arithmetic for the validity check. Stabilizer amplitudes are Gaussian integers, so the target is first written as a sum of a few vectors with Gaussian-integer entries times fixed numbers that are linearly independent over the Gaussian rationals:

• T: 1 and ζ. face: 1 and √3, using (1 + √3)^j = a_j + b_j√3. sqrtT: 1, η, η² and η³, using η⁴ = i. CCZ, CS, cat and C3Z: 1 alone.

The target lies in the span exactly when every component does. For each component:

1. Gaussian elimination modulo a fixed prime selects an invertible block of the amplitude matrix.
2. The verifier then solves the selected systems over the rational numbers.
3. It checks every amplitude using modular arithmetic with enough primes to establish exact equality.

Sets with redundant states are accepted if they reproduce the target; the report shows their exact rank. If the fixed primes cannot prove a result (a lost rank modulo all three pivot primes, or a bound beyond the 200 fixed primes), the verifier reports an error and gives no verdict.

Scoring

Each instance is ranked by the number of submitted states. Fewer states rank first; equal counts are ranked by submission number (lower first). For T states the leaderboard also reports log₂(r)/m.

Baseline and reference scores

T states:

Sources: Kissinger, van de Wetering and Vilmart (arXiv:2202.09202), whose recursion χ(T^⊗t) ≤ 3χ(T^⊗(t−4)) gives 9 at m = 7 and 12 at m = 8; Qassim, Pashayan and Gosset (arXiv:2106.07740), 18 at m = 10; the Unitary Foundation stabilizer rank challenge (github.com/unitaryfoundation/stabrank), which holds checked constructions up to m = 10 and proofs of optimality up to m = 6. The values for m = 11 to 14 are derived bounds from the recursion, not published entries. The listed reference constructions have log₂(r)/m above log₂(3)/4, approximately 0.39624. χ(CCZ) = 2 because |CCZ> is not a stabilizer state; for k ≥ 2 the reference is the product bound 2^k. Stabilizer rank does not change under local Clifford gates, so |T> and |H> have the same ranks.

For the other families, the instances below the first ranked size (face 1 to 6, sqrtT 1 to 5, CS 1 and 2, cat 2 to 6, C3Z-1) are solved and serve as debug instances.

The small decompositions are the public witnesses of the Unitary Foundation challenge (face up to 10 copies, sqrtT up to 7, CS up to 3, cat up to 8 qubits), converted term by term and checked by this verifier. The face decompositions at 7 to 10 copies come from Bevins (arXiv:2610.17500) and the challenge's own searches; the cat witnesses are those of Qassim, Pashayan and Gosset. The face-12 baseline is Bevins' 24-term decomposition (his Table 1: 24 words in three two-qubit stabilizer states), and face-11 applies ⟨0| to one qubit of each of its terms. The other large face, sqrtT and CS baselines are tensor products of these, choosing the split with the fewest terms. C3Z uses |C³Z> = |+>^⊗4 − 2|1111> (unnormalized) and its products. Cat states do not factor, but two of them can be joined: applying ⟨cat₂| = ⟨00| − i⟨11| to the last qubit of cat_a and the first qubit of cat_b gives cat_a+b−2, and every joined pair of stabilizer terms is again a stabilizer state. So cat₁₀ needs at most 3 × 3 = 9 terms from two copies of the 3-term cat₆; the cat-9 to cat-14 baselines are built this way. Reference values for larger sizes come from the listed constructions by tensor products or, for cat states, by gluing (derived bounds, not published entries). Lower bounds on the challenge's site: at least 6 terms for 7 to 10 face copies, at least 7 for 6 and 7 sqrtT copies, at least 4 for 3 CS copies, and at least 5 for cat states on 7 and 8 qubits.

Application

A decomposition with fewer terms can reduce the work required by a stabilizer simulation of circuits with T, CCZ, controlled-S and other non-Clifford gates.

Current records

Reference scores come from cited papers or derived constructions. Only accepted submissions can hold a QArena record.