Fewest T gates for field multiplication

Task

Find a circuit made of CNOT and T gates, with no ancillas, that implements the diagonal part of GF(2^m) multiplication. Minimize the number of T gates. Diagonal Clifford corrections using S, Z and CZ do not count toward the score.

The circuit acts on n = 3m qubits in the order a₀..a_m-1, b₀..b_m-1, c₀..c_m-1. The target is D_m|a,b,c> = (-1)^{Σ T_ijl a_i b_j c_l}|a,b,c>, where T_ijl is the coefficient of x^l in x^i+j mod P_m. Each instance file lists its modulus P_m. Applying Hadamard gates to register c before and after D_m gives the multiplication |a,b,c> → |a,b,c ⊕ a·b>.

Submission file

JSON structure:

{"n": 30, "columns": ["011000000000000000000100000000", ...]}

This shows the file structure. The verifier bundle contains a valid example.

• n is 3m.
• Each column is a bit string of length n. Character p corresponds to qubit p.
• Column y_j is the parity y_j·x on which the j-th T gate acts.
• Repeated columns are allowed and each occurrence counts toward the score. Columns of all zeros are rejected.
• Submit at most 8m² columns.

Validation

The submission is valid if and only if the symmetric signature tensor S[α,β,γ] = Σ_j A_αjA_βjA_γj mod 2 equals the target's signature tensor for every index triple, repeated indices included. The target tensor is 1 exactly on the permutations of (a_i, b_j, c_l) with T_ijl = 1. This is equivalent to the circuit equaling D_m up to a diagonal Clifford (Amy and Mosca; Heyfron and Campbell, arXiv:1712.01557).

Scoring

The score is the number of columns, which is the number of T gates. Fewer T gates rank first. Equal counts are ranked by submission number (lower first).

An accepted parity list defines a circuit in this model, so its count is an upper bound on the ancilla-free Clifford+T count. It is not known whether circuits with internal Hadamard gates can use fewer T gates.

Baseline and reference scores

Sources: for m = 4 to 10, the decompositions published with AlphaTensor-Quantum (arXiv:2402.14396), mapped to these instances by a change of basis and checked by this verifier. For m = 3, 16 and 32, Vandaele (arXiv:2407.08695, Table 3); these values have not been checked here. For m = 2, an exhaustive search by the QArena design group; the search is not yet published.

Application

Field multiplication is used in quantum algorithms for elliptic curve discrete logarithms. Reducing its T count reduces the magic states needed by this arithmetic step.

Current records

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