Fewest Toffoli gates for coherent table lookup

Task

Each instance file gives a table D of 2^a words with b bits each. Write a reversible circuit of X, CNOT and Toffoli gates that loads the table coherently: for every address x it must map

|x⟩ |0^b⟩ |0^s⟩  →  |x⟩ |D[x]⟩ |0^s⟩,

where the first register holds the a address qubits, the second the b output qubits and the third s workspace qubits that start and end in |0⟩. On a superposition of addresses the circuit then writes each entry next to its address. Use at most the instance's number of workspace qubits and as few Toffoli gates as possible.

The output and the workspace always start in |0⟩. The circuit only has to be correct on these inputs; it does not have to add D[x] into an output register that already holds data.

• pairA-bB-small and pairA-bB-wide: a table with 2^A entries of B bits. The tables are 2⁸ × 16 bits, 2¹² × 32 bits and 2¹⁶ × 16 bits. The small version allows a − 1 workspace qubits (7, 11 and 15), the wide version 4b + a − 1 (71, 139 and 79). The two versions of one size are ranked separately. pair16-b16-wide has its own table of random words (below); the other five use the pair recipe.
• gray2-a1: the debug table [0, 1, 3, 2] with two address bits, two output bits and at most one workspace qubit.

The instance file lists the whole table in data, entry x first for x = 0, 1, 2, … The pair tables come from a fixed integer recipe. With L = 2^a/4 and S = L², site u (0 ≤ u < S) sits at grid point (u mod L, ⌊u/L⌋) and gets a weight c_u between 1 and 31 from a linear congruential generator. Address x = u + S·v holds ⌊(2^b − 1)·c_u·c_v / (961·(1 + r²))⌋, where r² is the squared distance between the grid points of u and v:

L = 1 << (a // 4); S = L * L
state = 0x51415245 ^ a ^ (b << 8)      # the instance's "seed"
charge = []
for u in range(S):
    state = (1664525 * state + 1013904223) & 0xffffffff
    charge.append(1 + state % 31)
data = [((1 << b) - 1) * charge[u] * charge[v] // (961 * (1 + (u % L - v % L)**2 + (u // L - v // L)**2))
        for v in range(S) for u in range(S)]

pair16-b16-wide keeps this layout and the symmetry, but each unordered pair of sites gets a random 16-bit word from SHA-256, so the arithmetic shortcut that the pair recipe allows (computing an entry from the two sites' charges) no longer applies. For u ≤ v the word at addresses u + S·v and v + S·u is

S = 1 << (a // 2)                     # 256 sites, as above
seed = 0x51415245 ^ a ^ (b << 8)       # the instance's "seed", same formula
for v in range(S):
    for u in range(v + 1):
        h = hashlib.sha256(b"qrom %d %d %d" % (seed, u, v)).digest()
        data[u + S * v] = data[v + S * u] = int.from_bytes(h[:2], "little")   # b = 16

The pair tables are symmetric under u ↔ v and repeat many words: 95 distinct words among 256 entries, 1,303 among 4,096 and 2,344 among 65,536. The random table is symmetric too, with 25,862 distinct words among 65,536. They are synthetic test tables, not molecular integrals. No output bit is constant and no pair or hashpair table is an affine function of the address, so Toffoli gates are needed on the ranked instances.

Submission file

JSON structure:

{"ancillas": 1,
 "ops": [["CCX", 0, 1, 4], ["CX", 4, 2], ["CX", 0, 3], ["CCX", 0, 1, 4]]}

This example shows the format and is not an instance. With two address bits and two output bits it loads the table [0, 2, 0, 3]: output bit 0 = x₀x₁, output bit 1 = x₀, with the AND computed on the workspace qubit and uncomputed again. The verifier bundle contains an accepted file for pair12-b32-small.

• ancillas: the number s of workspace qubits, from 0 to the instance limit. It is the third ranking key, so declare only the ones you use.
• Wires are numbered: address bit i (weight 2ⁱ in x) is wire i, output bit j (weight 2^j in D[x]) is wire a + j, and workspace qubit k is wire a + b + k. Every operand must be one of the wires 0 to a + b + s − 1.
• ops: at most 1,000,000 gates, applied in order, each in one of these exact forms:
  • ["X",t] flips wire t.
  • ["CX",c,t] flips t when c is 1.
  • ["CCX",c1,c2,t] (Toffoli) flips t when c1 and c2 are both 1.
  The wires of one gate must be different. There are no other operations: no phase gates, measurements, resets, swaps or subroutine calls. An empty list is valid syntax.
• Only the final state is checked. During the circuit any wire may hold intermediate values, including the address and output wires, as long as every wire ends as required. There are no other qubits.
• Files may be at most 20 MiB. Write compact JSON, without spaces or line breaks: a gate then takes at most 20 bytes, so 1,000,000 gates always fit, and the 16-bit baselines take about 4 and 9 MB. With spaces after the commas a file of 1,000,000 Toffoli gates on three-digit wires passes 20 MiB, and an indented file passes it much sooner, so for such files the size limit binds before the gate limit.
• Parsing is strict: exactly the two keys, no duplicate keys, and wire numbers must be JSON integers (not true, 1.0 or "1").

Validation

The verifier checks all 2^a addresses at once by bit slicing:

1. It checks the format, the workspace limit, the gate limit and every wire number.
2. Each wire holds one integer with 2^a bits, where bit x is the wire's value when the input address is x. The address wires start as the bit patterns of the addresses and all other wires start at 0. An X gate is an XOR with all ones, a CNOT an XOR of two wires, and a Toffoli an AND followed by an XOR.
3. After the last gate it compares every address wire with its starting pattern, every output wire a + j with bit j of the table entries, and every workspace wire with 0.

X, CNOT and Toffoli gates permute the computational basis states and never add a phase, so a circuit that is right on every basis input |x⟩|0⟩|0⟩ is right on every superposition of them, and no separate phase check is needed. A rejection reports how many addresses fail, how many of them have a wrong output, a changed address or a dirty workspace qubit, and the details for the first failing address. On one PC core the 16-bit baselines, with about 310,000 and 620,000 gates, verify in under a second, and the slowest circuit the limits allow, 1,000,000 Toffoli gates on a 2¹⁶-entry table, in about two seconds.

Scoring

Each instance is ranked by the number of Toffoli (CCX) gates. Fewer Toffoli gates rank first; equal counts are ranked by fewer gates in total (X, CX and CCX together), then by fewer declared workspace qubits, then by submission number (lower first). Gates are counted as written: the verifier does not simplify the circuit, so two cancelling gates both count.

Baseline and reference scores

The QArena baselines build on two standard lookup circuits, made fully unitary. Write N = 2^a and P for the total number of 1 bits in the table.

• Small workspace: unary iteration over the address bits, least significant first (Babbush et al., arXiv:1805.03662). The first bit needs no Toffoli: X on address wire 0 makes it the control of the branch x₀ = 0, and a second X restores it as the control of the branch x₀ = 1. Below it, a node with control wire p and next address wire d uses the workspace qubit q of its depth (all nodes at one depth share it): X(d) CCX(p,d,q) X(d) gives q = p·not d for the 0 branch, CX(p,q) turns it into q = p·d for the 1 branch, and CCX(p,d,q) clears q again. At each leaf x, one CNOT from the leaf's control to output bit j for every 1 bit j of D[x]. This uses s = a − 1 workspace qubits, 2N − 4 Toffoli gates and 5N − 8 + P gates.
• Wide workspace: SelectSwap with four buffers (Low, Kliuchnikov and Schaeffer, arXiv:1812.00954). Unary iteration over address wires 2 to a − 1 writes the four words D[4h], …, D[4h+3] into four b-bit buffers. Controlled SWAPs on address wire 0 exchange buffers 0 and 1 and buffers 2 and 3, a controlled SWAP on address wire 1 exchanges buffers 0 and 2, and b CNOTs copy buffer 0 into the output. Then the swaps and the whole lookup run again in reverse order, which clears the buffers. Each controlled SWAP of two bits u and v costs CX(u,v) CCX(c,v,u) CX(u,v). This uses s = 4b + a − 3 workspace qubits, N − 8 + 6b Toffoli gates and 5N/2 − 16 + 2P + 19b gates.

The published baselines add the symmetry D[u + S·v] = D[v + S·u] and look up only about half of the entries. With n = a/2, u on address wires 0 to n − 1 and v on wires n to 2n − 1, the circuit first rewrites the address in place: v ^= u, so the v wires hold w = u xor v, and then, with t the highest 1 bit of w, u_i ^= u_t·w_i for every i < t. Both steps can be undone, and bit t of u is kept, so no extra qubit records which case occurred. Afterwards the entry depends only on w and on the u bits other than bit t, so a unary iteration that branches on the w bits first (most significant first) and then on those u bits reaches about N/2 leaves instead of N. Small cells write the words straight into the output; wide cells run this lookup inside the four-buffer SelectSwap, with u bits 0 and 1 selecting the buffer. The rewrite borrows n workspace qubits that are clean at that point, costs 4(n − 1) + n(n − 1)/2 Toffoli gates each way, and is undone at the end, so the workspace limits are the same as for the plain circuits.

For reference, the plain circuits score as follows. The wide 2¹⁶ row is for the pair table, which that cell used in an earlier draft; on the random table SelectSwap would need 1,211,406 gates, more than the 1,000,000 allowed.

For gray2-a1 the baseline is CX(0,2) CX(1,2) CX(1,3), with no Toffoli gate and no workspace. The table is linear in the address bits, so 0 Toffoli gates is the optimum.

No published Toffoli count is known for these tables in this model. Published costs for these circuits are given in T gates, and their cheapest versions uncompute with measurements and classically controlled corrections, or borrow extra qubits in unknown states. Version 1 of this board has no measurements and no qubits beyond the address, output and declared workspace wires, so those records do not apply here. The baselines already use the u ↔ v symmetry; the repeated words of the pair tables are further structure that a better circuit can exploit.

Application

Fault-tolerant simulation algorithms, such as qubitization of chemistry Hamiltonians, load coefficient tables coherently many times, and the Toffoli gates of these lookups are a large share of their cost. The pair tables have the shape of pair interactions: the value is symmetric in the two sites and decays with their distance, and many entries repeat. The random table keeps the layout and the symmetry without that structure. The ranking uses Toffoli gates first, with total gates and workspace qubits as tie-breaks; it does not model T-count savings from measurement-based uncomputation, circuit depth or qubit connectivity.

Current records

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