Eight T states per round from the fewest noisy inputs

Task

Design a one-round magic-state distillation protocol that turns n noisy T states into k T states at once, and make it cheap: as few noisy inputs per accepted output as possible while the accepted batch stays clean. The protocol is given by a triorthogonal matrix in the form of Bravyi and Haah (arXiv:1209.2426): k logical rows (one per output) and between one and 24 − k stabilizer rows (the checks), each a binary string of length n, one column per noisy input.

• tri96-k8-p1000: k = 8 outputs, input error rate p = 1/1000; the probability that an accepted batch has any wrong output must be at most 10⁻⁶.
• tri96-k8-p100: k = 8, p = 1/100; ceiling 10⁻³.
• tri96-k7-p1000 and tri96-k7-p100 (debug instances): k = 7 with the same error rates and ceilings.

All four instances allow up to n = 96 inputs and 24 rows in total, and require Z distance at least 3. Each input is the state (1 − p)|T⟩⟨T| + p Z|T⟩⟨T|Z with |T⟩ = (|0⟩ + e^iπ/4|1⟩)/√2, independently. Clifford gates and measurements are ideal, and a batch is kept only if every check passes.

The seven-output cells are debug instances because their answer is essentially settled. The QArena baseline there, a 55-to-7 code, scores 1.4 × 10⁻⁶ (p = 1/1000) and 2.5 × 10⁻³ (p = 1/100) above a lower bound that QArena certified with Delsarte's linear program. Only a code with fewer than 55 inputs, which would refute the classification described below, could score under that bound; another 55-input code could gain at most those margins. The eight-output cells are open. Their baseline is a 56-to-8 code, and a 55-to-8 code would be new: it would cost about 7.26 (p = 1/1000) and 11.95 (p = 1/100), against 7.40 and 12.29 for the baseline. The section on baseline and reference scores gives the details.

The protocol, in the row-coordinate form used by the verifier: prepare one qubit per row in |+⟩, rotate each column's parity (the XOR of the row qubits that have a 1 in that column) by one noisy T, apply a Clifford correction made of S gates and CZ gates on the row qubits, and measure every stabilizer row qubit in the X basis, keeping the batch only if all give +. The logical row qubits then hold k T states. A Z error on input j flips the stabilizer outcomes given by column j's stabilizer bits and the outputs given by its logical bits, so an error pattern e (one bit per input) is accepted exactly when G₀e = 0 and then flips the outputs G₁e, where G₀ and G₁ are the stabilizer and logical rows.

Wills, Jain and Singh classified generalised triorthogonal codes with n ≤ 54 and d_Z ≥ 3, per output class (arXiv:2609.30860; data doi:10.6084/m9.figshare.33717319). Their table has pure T outputs up to six (a 52-to-6 protocol) and no seven-T-output protocol, so a seven-output code needs at least 55 inputs if the classification is complete. So does an eight-output code, because dropping one of its logical rows leaves a valid seven-output code on the same columns. The paper does not state this bound; QArena read it from the table. The instances still accept any n from 15 to 96.

Submission file

JSON structure:

{"n": 15,
 "logical": ["111111111111111"],
 "stabilizers": ["101010101010101",
                 "011001100110011",
                 "000111100001111",
                 "000000011111111"]}

This shows the file structure with the 15-to-1 protocol (one output; the instances need exactly k logical rows, eight or seven). The verifier bundle contains a complete accepted file: the 56-to-8 baseline of tri96-k8-p1000, which is also the baseline of tri96-k8-p100.

• The file is a UTF-8 JSON object with exactly the keys n, logical and stabilizers. n is a JSON integer (not a float or boolean). Duplicate keys, NaN and Infinity are rejected. The file may have at most 64 KiB.
• n is the number of noisy inputs, from 15 to 96. Character j of every row string is column j (input j), and every row string has exactly n characters 0 or 1.
• logical has exactly k rows (eight on tri96-k8-*, seven on tri96-k7-*); stabilizers has one to 24 − k rows, so G has at most 24 rows.
• Do not submit the Clifford correction, probabilities or a distance: the verifier derives them from the rows.

Validation

• G (logical rows first, then stabilizer rows; r rows) must have full row rank over GF(2).
• Logical rows must have odd weight and stabilizer rows even weight; every pair of distinct rows and every triple of distinct rows must overlap in an even number of columns. Under these conditions the S powers s_i = (δ_i − |g_i|)/2 mod 4 (δ_i = 1 for logical rows, 0 otherwise) and a CZ on every row pair whose overlap is 2 mod 4 cancel every unwanted phase: the corrected phase of row basis state x is e^{iπ(x₁ + … + x_k)/4} over the logical rows. The result lists this correction.
• Z distance at least 3: no input may lie in a logical row and in no stabilizer row (a single error would be accepted and flip an output), and no two inputs may have the same stabilizer bits but different logical bits (two errors). The verifier compares the columns directly, which covers every error of weight 1 and 2.
• With z = 1 − 2p and s = r − k stabilizer rows, the acceptance probability is A = 2^−s Σ_h z^|h| over all 2^s sums h of stabilizer rows, and the probability of acceptance with no output error is B = 2^−r Σ_h z^|h| over all 2^r sums of rows. The verifier counts the words of both row spaces by weight (Gray-code order, one XOR and one population count per word) and evaluates A and B as exact fractions.
• q_bad = 1 − B/A is the probability that an accepted batch has at least one wrong output, so it is at least the error rate of each single output. It must not exceed the instance's ceiling; the comparison is exact.
• Limits: 180 CPU seconds and 512 MB of memory. Measured on the worst case the instances allow (n = 96, 24 rows, which means 2²⁴ row-space words): at most 1.5 CPU seconds and 12 MB on one core of an AMD Ryzen 9 9950X, for k = 8 and for k = 7. If the enumeration does not finish, the result is an error, which is not ranked.

Scoring

The score is cost = n / (kA), the noisy T states consumed per accepted output T state, as an exact reduced fraction (hexadecimal numerator and denominator in the result, with a decimal for display only); lower ranks first. Equal costs are ranked by lower q_bad, then fewer inputs n, then fewer rows, then the earlier submission. The result also reports A, the number of accepted weight-3 errors that flip an output, both weight enumerators and the correction.

To first order in p, A ≈ 1 − np for any valid code without all-zero columns, so the score mostly rewards a short code; at equal n it rewards the stabilizer group with the larger acceptance probability. More checks lower A, and the error ceiling limits how far a code can trade checks for acceptance.

Baseline and reference scores

Both baselines start from eight planes (three-dimensional subspaces) of GF(2)⁷ that pairwise meet only in 0 and whose Plücker coordinates sum to zero. Their 56 nonzero points are the columns of a 56-input code: the seven bits of a point are its column's stabilizer bits, so the stabilizer rows are the seven coordinates, and each logical row is the indicator vector of one plane. A plane has seven nonzero points; a nonzero linear form is 1 on four of them, two independent forms are both 1 on two, and three forms are all 1 on an odd number exactly when they are independent on the plane, which is what the plane's Plücker coordinate for that coordinate triple records. So every parity and overlap condition holds, the stabilizer triples because the Plücker coordinates sum to zero, and the syndromes are the points themselves, distinct and nonzero, so d_Z ≥ 3. With all eight planes as outputs this is the 56-to-8 baseline; it has 224 accepted weight-3 errors, each of which flips an output. With seven of the planes as outputs it is a 56-to-7 code (cost 8.4610166073 and 14.0412009929).

For seven outputs a second step removes one more input. Leave one plane W without an output and pick a column q of another plane such that the other seven points of the coset q + W are unused. W and q span a four-dimensional subspace whose sixteen points, with the output bits of q's plane on the coset q + W and none on W, form a four-dimensional flat of the full column space; adding such a flat to the column set (mod 2, dropping its zero point) keeps every parity and overlap condition. It removes the seven columns of W and the column q and adds the seven other points of q + W to q's logical row, which then has 13 columns. QArena found the eight planes by a random search over sets of pairwise disjoint planes. All 116 configurations found give the same 56-input scores, and the seven moves of this kind on the one used here all give cost 8.3016172079 and 13.6527754200.

The 55-to-7 baseline is the result of further flat additions that keep n = 55. Take a sixteen-point flat whose stabilizer bits form an affine four-dimensional subspace containing exactly eight columns, where the logical bits of those eight columns are an affine function of their stabilizer bits; adding it removes those eight columns and adds the other eight points with the same affine logical bits. Such a move changes which triples of columns have stabilizer bits summing to zero, and so changes A. Three random walks over these moves (3,700 to 4,200 moves and about 2,100 to 2,200 distinct codes each) reached the same lowest cost on both instances; that code is the baseline. It has 243 accepted weight-3 errors that flip an output, against 211 before the walks, so q_bad is a little higher, and A is larger by 3.1 × 10⁻⁸ at p = 1/1000 and 2.0 × 10⁻⁵ at p = 1/100.

QArena knows no eight-output code with fewer than 56 inputs. The 56-to-8 admits no move of this kind with a flat of dimension 4, 5 or 6 that keeps n at most 58, so these walks cannot leave it. On a code with distinct nonzero syndromes, one more output fits without new columns exactly when the all-ones vector is not a sum of coordinatewise products g_ag_b of rows (a = b allowed). None of the 55-to-7 codes reached by QArena's searches (7,853, 789 and 11,455 distinct codes in three searches) passes this test.

The archive codes come from the classification's data (Wills, Jain and Singh, CC BY 4.0), which gives each output only up to CNOT and S gates; QArena replaced their logical rows by sums of logical rows that meet the conditions here, which leaves both row spaces and therefore A and B unchanged. The 85-to-7 code reproduces every value printed in the board's specification. The 59-input code adds the classification's 52-to-6 and a 15-to-1 as sets of points and lets four columns cancel.

The references are certified lower bounds for codes whose column reduction (repeated columns merged, all-zero columns dropped) keeps the stated number of inputs. Merging repeated columns and dropping all-zero columns never raises the cost, so the lowest cost is reached by a code with distinct nonzero columns, and by the classification such a code has at least 55 inputs. For valid codes with distinct, nonzero columns, A = (1 − p)ⁿ(1 + K₃(p/(1 − p))³ + …), where K₃ counts the triples of columns whose stabilizer bits sum to zero (243 for the 55-to-7 baseline, 224 for the 56-to-8), so at a fixed n a code can still win on A, but not by much. Delsarte's linear-programming bound on the weights of the stabilizer group, with the weights that triorthogonality allows, bounds A for each n. A does not depend on the logical rows, so one bound serves both values of k. QArena computed it in exact arithmetic for every n from 55 to 96 and checked each value with a dual certificate.

• Seven outputs: the bound at n = 55 gives cost ≥ 8.3016155779 (p = 1/1000) and 13.6497840155 (p = 1/100), the reference values, and for every n from 56 to 96 the bound lies above the baseline's costs. The baseline exceeds the reference by 1.36 × 10⁻⁶ and 2.52 × 10⁻³.
• Eight outputs: the bound at n = 56 gives cost ≥ 7.4033881671 and 12.2835143238, the reference values; the baseline exceeds them by 1.36 × 10⁻⁶ and 2.54 × 10⁻³, and for every n from 57 to 96 the bound lies above the baseline's costs. At n = 55 the bound is 7.2639136306 and 11.9435610135. So a code that beats the baseline by more than those margins reduces to 55 inputs once repeated columns are merged and all-zero columns dropped (it may be submitted with more). No such code is known, and one would be new; with the acceptance probability of the 55-to-7 baseline it would cost 7.2639148227 and 11.9457665367.

Application

Magic-state factories make a large part of the cost of a fault-tolerant quantum computer. A protocol that turns one batch of noisy T states into eight good ones, with fewer inputs per output at a fixed output error, makes a factory level smaller. The board fixes the noise to independent Z errors on the inputs with ideal Clifford operations; factory layout, scheduling and Clifford noise are outside the model.

Current records

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