Fewest CX gates for a Hubbard Trotter step of Pauli rotations

Task

Each instance gives n qubits and an ordered list of M Pauli strings P₀, …, P_M−1. The target is the product of rotations

U = R_PM−1(θ_M−1) ··· R_P1(θ₁) R_P0(θ₀),   with R_P(θ) = exp(−iθP/2),

so P₀ acts first. Every angle θ_i is an independent symbol, and the circuit must be right for all values at once. Build a circuit of Clifford gates (H, S, S^†, X, Z, CX) and single-qubit Z rotations that implements U with as few CX gates as possible. Each target rotation appears exactly once, as a Z rotation of one qubit by +θ_i or −θ_i. There are no spare qubits, and the Clifford part must cancel completely by the end of the circuit.

The ranked instances are one first-order Trotter step of the Fermi-Hubbard model on an open L × L square lattice with two spins per site, in the Jordan-Wigner encoding. The list is made by the generator jw-hubbard-open-v1:

1. Site u = yL + x, for 0 ≤ x, y < L. Qubit 2u + s holds spin s ∈ {0, 1}, so n = 2L².
2. The bonds are all horizontal and vertical nearest-neighbour site pairs (u, v) with u < v (open boundaries, no wraparound), sorted lexicographically.
3. For each bond, spin 0 and then spin 1, with p = 2u + s and q = 2v + s, append the hopping terms X_pZ_p+1···Z_q−1X_q and then Y_pZ_p+1···Z_q−1Y_q.
4. Then append the on-site term Z_2uZ_2u+1 for every site u in increasing order.

Every string has sign +, and character i of a string acts on qubit i. A horizontal hop acts on 3 qubits. A vertical hop acts on 2L + 1 qubits, because its Jordan-Wigner string of Z factors covers everything between the two sites in the qubit order.

A ranked instance file names the generator and L. It also lists the strings for convenience, and the verifier regenerates the list and requires the two to agree. The debug instance pn-parity3 has only n and its two strings, and the verifier reads both forms. Few pairs of terms anticommute, so most rotations may be reordered. The encoding and the term list are fixed here; choosing a better fermion encoding is the subject of the separate fermion-workload board.

Submission file

JSON structure:

{"ops": [["CX", 0, 1], ["R", 0, 1, 1], ["CX", 1, 2], ["R", 1, 2, 1], ["CX", 1, 2], ["CX", 0, 1]]}

This is the specification's accepted circuit for pn-parity3 (4 CX, 6 operations). The verifier bundle contains an accepted pn-hub8 example; every instance's baseline is listed on its leaderboard.

• ops: at most 50,000 operations, applied in order. Each one has one of these exact forms, and every operand is a JSON integer (not true or 1.0):
  • ["H",q], ["S",q], ["SDG",q], ["X",q], ["Z",q]: Hadamard, S = diag(1, i), S^† = diag(1, −i), Pauli X and Pauli Z on qubit q.
  • ["CX",c,t]: CNOT with control c and target t, which must be different qubits.
  • ["R",i,q,s]: the rotation exp(−i s θ_i Z_q/2) of qubit q for term i, where 0 ≤ i < M and the sign s is 1 or −1.
• Qubits are numbered 0 to n − 1. There is no other key: no spare qubits, numeric angles or declared scores. The file may be at most 2,097,152 bytes (2 MiB). Parsing is strict: no duplicate keys, no NaN or Infinity, and operation names are case-sensitive.

Validation

Let F be the product of the Clifford gates applied so far, with the rotations left out. A rotation exp(−i s θ Z_q/2) placed after F equals F · exp(−i θ (s F^†Z_qF)/2): it rotates about the Pauli operator s F^†Z_qF, its pulled-back axis. The verifier keeps F^†X_qF and F^†Z_qF for every qubit as two bit strings and a phase i^k, and updates them exactly at each gate (an H exchanges the two, a CX multiplies some of them, an X or Z flips a sign). It accepts the file if and only if:

1. every term label from 0 to M − 1 occurs in exactly one R;
2. at that R, the pulled-back axis s F^†Z_qF equals the target P_i exactly, sign included;
3. for every pair j < i whose target strings anticommute, rotation j comes before rotation i;
4. at the end, F^†X_qF = +X_q and F^†Z_qF = +Z_q for every qubit, so the Clifford part is the identity up to a global phase. Signs count: a leftover Z = S·S fails here.

When all four hold, the circuit is the product of the target rotations in an order that differs from the target order only by exchanges of commuting rotations, which leave the product unchanged. So the file implements U for every value of the angles. The rule is stricter than equality of unitaries. A circuit that merges two rotations about the same axis or splits one rotation into several is rejected even when it implements the same operation, and so is any other use of identities among the rotations. The report of a rejected file names the first failing operation, the pulled-back axis and the target, or the first qubit whose frame is not restored.

The work is one bit-string update per gate and one commutation test per pair of terms (130,816 pairs on pn-hub8). On one core of an AMD Ryzen 9 9950X (limit 30 s, 256 MiB), the slowest 50,000-operation file tried on pn-hub8 took 0.11 s of CPU time and 23 MiB of memory at peak, interpreter start included, and the pn-hub8 baseline takes 0.03 s. A second program, written independently from the specification, pulls each rotation axis back gate by gate as a string of Pauli letters and pushes every X_q and Z_q forward through the whole circuit. On up to 6 qubits it also compares explicit unitary matrices with random angles. It agreed with the verifier on all 117,560 random and adversarial files, accepted and rejected alike, and the matrix comparison agreed on all 41,739 small circuits.

Scoring

Fewer CX gates rank first. Equal CX counts are ranked by fewer operations in total (every H, S, SDG, X, Z, CX and R counts 1), then by submission number (lower first). Both numbers are counted from the file. There is no depth score and no connectivity limit: a CX may act on any two qubits.

Baseline and reference scores

No compiler has published a score for these exact lists, so no instance shows a reference score. Rustiq (de Brugière and Martiel, arXiv:2404.03280, code at rustiq-core) synthesizes such sequences while keeping their order and is the natural comparison, but it has not been run on these lists yet, and its output only counts here together with its complete final Clifford. Paulihedral (arXiv:2109.03371) is another compiler for this task. QArena verified three constructions; the first two are starting points and come from the board's specification and its review:

• Fallback (specification). Each rotation on its own: H on every X factor, S^† then H on every Y factor, a CX from every other qubit of the term to its largest qubit, the rotation there, then everything undone. It needs 16L(L² − 1) + 2L² CX.
• Pair sharing (review of the specification). The X···X and Y···Y terms of one hop share a frame: CX(p,q), H(p) and a CX from every string qubit to p, the X···X rotation on p, CX(q,p), the Y···Y rotation on p with sign −1, CX(q,p), then the first part undone; each on-site term is CX, rotation, CX. Its CX count equals the total Pauli weight of the list.
• Sliding-parity sweep (the QArena baseline). Number the vertical hops t = 2u + s (bond from site u to site u + L, spin s): hop t acts on qubits t and t + 2L, and its Jordan-Wigner string is the window of qubits t + 1 to t + 2L − 1. Taken in the order t = 0, 1, 2, … over all rows and both spins, the window moves up by one qubit per hop. One qubit c of the window carries the parity of the whole window: with CX gates from the other window qubits to c, the pulled-back Z_c is the product of Z over the window. Moving the window then costs 2 CX (one qubit leaves, one enters), and inside this frame every vertical hop is the 3-qubit pair X_pZ_cX_q, Y_pZ_cY_q. When c reaches the bottom of the window it hands the parity to the new top qubit with 2L CX. A 3-qubit hop pair alone takes 4 CX: a 2-CX Clifford turns both terms into single-qubit Z at once, and an exhaustive search shows that one CX cannot. A hop together with the window move after it takes 5 CX instead of 4 + 2 (exhaustive search: 4 is impossible). The four hopping terms of a horizontal bond (both spins) are done together with 6 CX, through a 3-CX Clifford that is also minimal by exhaustive search. The first row's bonds run before the sweep. Bonds of the middle rows run inside the frame, at moments when the frame leaves their terms unchanged (the parity qubit is not on the bond and the window edge does not split it); finding such moments costs a few early handovers. The last row's bonds and all on-site terms (2 CX each) run after the frame is undone. Every site meets its bonds in the order up, left, right, down, which is their order in the sorted list, so every anticommuting pair stays in order. Runs of single-qubit gates are finally merged into shortest words. On pn-hub8 the 1,171 CX split into 707 for the vertical hops, 336 for the horizontal bonds and 128 for the on-site terms; the count grows like the number of qubits, while the two constructions above grow like L³.

The fallback and pair-sharing files are kept with the verifier's tests. The baseline spends more single-qubit gates per rotation, so on pn-hub4 and pn-hub6 the pair-sharing files have fewer operations in total. On pn-parity3, 4 CX is the minimum: the term Z Z Z needs at least 2 CX to reach a frame in which it is a single-qubit Z, and 2 more to leave it.

No lower bound is known for a whole Hubbard instance. The 4-, 5- and 6-CX pieces are minimal on their own, but a whole circuit may carry one frame across larger groups of rotations or use another legal order, and the Jordan-Wigner strings can be shared in other ways.

Application

Trotter (product-formula) simulation of the Fermi-Hubbard model applies the same step many times, and compilers for quantum simulation and for variational circuits reduce the two-qubit gates of such a step while keeping each rotation's angle a free parameter, so that the circuit can be reused for any time step or set of couplings. The board fixes the encoding and the order of terms and asks only for the compiled circuit. The score does not model qubit connectivity, circuit depth, or the cost of the rotations themselves, which dominate in a fault-tolerant computer where each one is synthesized from T gates.

Current records

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