Fe₂S₂ alias–Select

One step of a chemistry simulation for an iron–sulfur cluster. The discovered circuit reorders its table so that neighboring words repeat, and the lookup skips the repeats.

In brief

The step draws one of 41,052 Pauli terms by the alias method, applies it, and erases the draw. The baseline (Babbush et al., 2018) reads its data in two independent passes: a lookup of the alias word (13,000 Toffolis) and a row-by-row Select (41,000 Toffolis). Together they take over 97% of the Toffolis.

The discovered circuit uses two freedoms. First, the terms may be listed in any order. Operators related by a few fixed transformations, such as exchanging spin up and spin down, sit side by side and are selected by one representative plus cheap switches. Second, many alias tables give the same distribution. The discovered table puts identical words next to each other, so the lookup reads only one half of a block wherever both halves match.

TQ = 2·10⁶TQ = 5·10⁶TQ = 10⁷1001502·10⁴5·10⁴peak qubits Q →Toffoli count T →Babbush et al. (2018)Discovered circuitLive qubits as Toffolis execute55k15k139
1

Registers and the two banks

init

The circuit is the data-dependent part of one qubitization walk step for the Fe2S2 Hamiltonian, a table of 41,052 signed Pauli operators on 40 system qubits. It selects a row by the alias method, applies the selected Pauli operator, and erases the selection. The boundary registers are the row index i (16 qubits), the comparand sigma (16 qubits), and the system register x (40 qubits).

Two banks receive the alias fields of row i. The keep threshold goes to 15 word wires plus one carrier for bit 15. The alternate index goes to the 16-wire selection scratch sel, which later holds the selected row.

b = Builder()
regs = declare_registers(b, [("i", A), ("sigma", S), ("x", X)])
idx, sigma, x = regs["i"], regs["sigma"], regs["x"]
for name in ("i", "sigma", "x"):
b.claim(name, regs[name])
# ONE walk carries BOTH payloads: keep bits 0-14 into the 15-wire
# word bank plus one carrier for bit 15, alt into the 16-wire
# selection scratch (alt before the swap, sel during SELECT).
word = b.qubits(B)
b.claim("word", word)
kc = b.qubit()
b.claim("word", [kc])
keep_carriers = list(word) + [kc]
sel = b.qubits(A)
b.claim("sel", sel)
2

One walk loads keep and alt

lookup

A single table walk carries both payloads: each leaf XORs the keep word and the alternate index into their banks under one control.

The table itself is chosen to make this walk cheap. Many alias tables realize the same rounded distribution, because the totals per term do not fix which underfilled row receives weight from which heavy term. The melt schedule spends that freedom on repetition: it keeps equal-weight light rows in aligned runs and drains each heavy term through whole runs. In the spin-indexed part of the table, 18,463 of 20,374 adjacent pairs then store identical alias words. The schedule changes no probability, so it adds no error.

A row-by-row walk over this table costs 41,050 Toffolis; the pruned walk costs 10,271.

def leaf(lo, ctrl):
xor_word(b, ctrl, KEEPW[lo], keep_carriers)
xor_word(b, ctrl, ALTW[lo], sel)
Alias lookup 10,271 Toffolis · peak 119 qubits
with b.phase("lookup"):
lookup_walk(b, list(idx[::-1]), leaf)
3

Skip a split when both halves agree

_content_tree, lookup_walk

_content_tree turns the table into the tree that the walk visits. A span whose words are all equal becomes one leaf. When the two halves of a span hold the same word sequence (_lk_skip), the address bit that separates them cannot change the loaded word, so the node keeps only one child and forms no AND. A span that lies wholly at or beyond row 41,052 is dropped, because the grader never tests those rows.

Each remaining split still chooses how to carry its control: hold a conjunction for both children, which costs a qubit, or rebuild it, which costs a Toffoli. An exact dynamic program, _walk_policy, makes that choice at every node. Its hold budget is the headroom below the 126-qubit peak that the frame walk sets later: 22 wires. The program saturates at 15 holds, so the extra allowance raises no peak.

PEAK = 112 + 14 # the SELECT-stage peak
H_LOOK = PEAK - 104 # lookup-walk hold budget: the lookup holds 104 live wires
⋯ 429 lines
def _content_tree(lo, span, limit, uniform, skip, leaf_load):
if lo >= limit:
return None
if span == 1 or (uniform is not None and uniform(lo, span)):
return _WNode("leaf", lo=lo, span=span, load=leaf_load(lo) if leaf_load else 0)
half = span >> 1
if skip is not None and skip(lo, span):
return _WNode("skip", (_content_tree(lo, half, limit, uniform, skip, leaf_load),), lo, span)
left = _content_tree(lo, half, limit, uniform, skip, leaf_load)
right = _content_tree(lo + half, half, limit, uniform, skip, leaf_load)
if right is None:
return _WNode("one", (left,), lo, span)
return _WNode("two", (left, right), lo, span)
⋯ 138 lines
def _lk_uniform(lo, span):
hi = min(lo + span, L)
first = DATA[lo]
return all(v == first for v in DATA[lo + 1 : hi])
def _lk_skip(lo, span):
half = span >> 1
rh = min(lo + span, L) - (lo + half)
return rh > 0 and DATA[lo : lo + rh] == DATA[lo + half : lo + half + rh]
_LK_ROOT = _content_tree(0, 1 << A, L, _lk_uniform, _lk_skip, None)
_LK_ANDS, _LK_POLICY = _walk_policy(_LK_ROOT, H_LOOK)
assert _LK_ANDS < _INF
def lookup_walk(b, idx_msb, leaf_at):
"""One content-pruned descent over [0, 2^A): periodic skip (two
halves with identical in-domain content recurse once, no AND) and
one-sided descent past L are free; everywhere else the load-time
DP policy places the held chain, split, and accumulator wires.
"""
_policy_walk(
b, _LK_ROOT, _LK_POLICY, H_LOOK, lambda n: idx_msb[A - (n.span.bit_length() - 1)], leaf_at
)
4

Compare, then swap the selection into place

cmp, cmp/select

The comparator XORs f = [σ < keep] onto one fresh wire. Its 16 borrow stages each use a temporary AND, one Toffoli, which measurement later releases without a second Toffoli.

A controlled swap under f then exchanges sel and i, one Toffoli per bit. Afterward sel holds the selected row: i when f = 1, the alternate index otherwise. The index wires carry the other branch through the Pauli stage. The keep bank stays live, because the second comparator needs the original threshold to clear f.

Compare and select 32 Toffolis · peak 122 qubits
with b.phase("cmp"):
f = b.qubit()
b.claim("carry", [f])
compare_into(b, sigma, keep_carriers, f)
# the selection swap: sel <-> i under f — the index wires carry the
# unselected branch through SELECT and the identical swap restores
# them after it
with b.phase("cmp/select"):
for j in range(A):
b.cswap(f, sel[j], idx[j])
5

Set the frame flags and apply the frames

select-blk, select-conj

The terms may be listed in any order. The ordering places Pauli operators related by fixed Clifford transformations, called frames, in contiguous blocks of power-of-two size. Seven commuting frames generate the blocks: two from exact spin symmetries, five from similar parts of the cluster. Address bits inside a block choose which frames apply, so one representative stands for up to 32 rows.

The circuit allocates one flag per frame. A frame is active only on certain address intervals; xor_gate_flags XORs each of the 14 interval tests, combined with its address bit, onto the frame's flag. The tests share borrow prefixes through a trie instead of comparing every boundary afresh.

Each flag then conjugates the system register by its frame, once for the whole table rather than once per block.

tail, ×29 scaleblockrows 0–7,328: 229 blocks of 32 rows; frames F, C, D, D2, s_thio2⁵rows 7,328–14,016: 209 blocks of 32 rows; frames F, C, D, D2, s_d452⁵rows 14,016–18,464: 139 blocks of 32 rows; frames F, C, D, D2, x_muS2⁵rows 18,464–26,400: 496 blocks of 16 rows; frames F, C, D, D22⁴rows 26,400–28,384: 124 blocks of 16 rows; frames F, C, D, s_d45rows 28,384–29,280: 56 blocks of 16 rows; frames F, C, D, x_muSrows 29,280–33,216: 492 blocks of 8 rows; frames F, C, D2³rows 33,216–36,648: 429 blocks of 8 rows; frames F, C, D22³rows 36,648–37,488: 105 blocks of 8 rows; frames F, D, D2rows 37,488–40,608: 780 blocks of 4 rows; frames F, C2²rows 40,608–40,748: 35 blocks of 4 rows; frames F, D2²rows 40,748–40,968: 55 blocks of 4 rows; frames C, D2²rows 40,968–40,992: 12 blocks of 2 rows; frames Crows 40,992–41,052: 60 blocks of 1 row; frames noneFF flag: rows 0–40,748, address bit 0F flag: rows 0–40,748, address bit 0CC flag: rows 0–36,648, address bit 1C flag: rows 37,488–40,608, address bit 1C flag: rows 40,748–40,992, address bit 0DD flag: rows 0–33,216, address bit 2D flag: rows 36,648–37,488, address bit 1D flag: rows 40,608–40,968, address bit 1D2D2 flag: rows 0–26,400, address bit 3D2 flag: rows 33,216–37,488, address bit 2s_thios_thio flag: rows 0–7,328, address bit 4s_d45s_d45 flag: rows 7,328–14,016, address bit 4s_d45 flag: rows 26,400–28,384, address bit 3x_muSx_muS flag: rows 14,016–18,464, address bit 4x_muS flag: rows 28,384–29,280, address bit 3010k20k30k40,60841,052term-table row →
The 41,052-row term table split into 14 regions of 2k-row blocks, with one lane per frame shaded where that frame is active. Each shaded run is one interval test. The 444-row tail is drawn at 29× scale past the break.
Frame flags 136 Toffolis · peak 126 qubits
with b.phase("select-blk"):
flags = {}
for g in PRIORITY:
if not GEN_IVS[g]:
continue
fq = b.qubit()
b.claim("flag", [fq])
flags[g] = fq
xor_gate_flags(b, sel_bits, flags)
Frames on 131 Toffolis · peak 112 qubits
with b.phase("select-conj"):
for g in reversed(PRIORITY): # outermost first, F innermost last
if g in flags:
conjugate_open(b, flags[g], x, g)
6

A controlled frame at minimal rank

conjugate_open, _run_form

A real Clifford frame maps a basis state by a linear map of its bits and adds a sign given by a quadratic Boolean form q(x). Permutation frames first swap modes under the flag; the spin exchange conjugate_f does so on each orbital pair. Under a flag g, the sign becomes g·q(x).

The polarization of q is an alternating matrix of even rank 2r. A CNOT network moves to coordinates in which q has r independent products. Each controlled product costs one CCZ, the linear terms cost CZs, and the network is undone. One CCZ adds polar rank at most two, so r CCZs is the minimum.

In these coordinates the X↔Y frame C needs 10 CCZs per spin sector instead of 19. The iron-site reflection uses 10, the composed reflection 6, and the three orbital swaps 2, 2, and 1. min_form_net checks each form against the original frame action at build time. A gauge layer of free CNOTs and CZs shifts known signs between frames and representatives.

def conjugate_f(b, ctrl, x):
for p in range(X // 2):
lo, hi = x[2 * p], x[2 * p + 1]
b.cx(hi, lo)
b.ccx(ctrl, lo, hi)
b.cx(hi, lo)
b.ccz(ctrl, lo, hi)
⋯ 197 lines
_MIN_FORM = {g: min_form_net(PERM_MACH[g][3], PERM_MACH[g][4], prefix_mat(X), X) for g in PERM_MACH}
_C_FORM = min_form_net([(j - 1, j) for j in range(1, 20)], list(range(19)), prefix_mat(20), 20)
⋯ 2 lines
def _run_form(b, ctrl, wires, form):
net, ccz, cz = form
for s, d in net:
b.cx(wires[s], wires[d])
for a, bb in ccz:
b.ccz(ctrl, wires[a], wires[bb])
for c in cz:
b.cz(ctrl, wires[c])
for s, d in reversed(net):
b.cx(wires[s], wires[d])
⋯ 2 lines
def conjugate_c(b, ctrl, x):
"""C^ctrl: per spin sector, e2(y) at its bilinear rank — 10 CCZs
behind a free congruence net (19 in prefix coordinates).
"""
for par in (0, 1):
sec = [x[2 * p + par] for p in range(X // 2)]
_run_form(b, ctrl, sec, _C_FORM)
⋯ 2 lines
def _pf_perm(b, ctrl, x, perm):
done = set()
for k in range(X):
j = perm[k]
if k in done or j == k:
continue
done.add(j)
b.cx(x[j], x[k])
b.ccx(ctrl, x[k], x[j])
b.cx(x[j], x[k])
⋯ 29 lines
def conjugate_open(b, ctrl, x, g):
if g == 0:
conjugate_f(b, ctrl, x)
return
if g == 1:
conjugate_c(b, ctrl, x)
return
perm = PERM_MACH[g][0]
_pf_perm(b, ctrl, x, perm)
_run_form(b, ctrl, x, _MIN_FORM[g])
_gauge_layer(b, ctrl, x, g) # inner gauge layer (free CX/CZ)
7

Walk the block roots

select-pauli

With the frames on, the circuit walks the selected index down to the 3,221 block roots instead of the 41,052 rows. At each root, apply_row applies the representative's Z part as CZs and its X part as CNOTs. The surrounding frames turn it into the Pauli operator of the selected row.

Only the Pauli relation inside a block must be exact; the rows keep independent coefficients and signs. The leftover sign of each block is a polynomial in its frame bits. Linear terms are free CZs, and the higher monomials cost CCZs, with one shared AND per group of terms of degree three or more. A gauge search cuts this sign channel from 769 Toffolis to 117, and node_enter places seven recurring monomials on walk nodes that already exist, which leaves 108.

Block select 3,327 Toffolis · peak 124 qubits
with b.phase("select-pauli"):
select_walk(b, list(reversed(sel_bits)), node_enter, lambda lo, ctrl: apply_row(ctrl, lo))
assert hosted == set(node_monos), "node-hosted monomial span missed"
8

A descent that stops at blocks

select_walk

SPAN_AT records the row count of every block base. The walk descends the address tree and stops at a node that is exactly one block, so a block of 2k rows costs one leaf.

At a two-sided node, one AND serves both children: a CNOT from the parent control flips it from the right child's control to the left child's. Measurement releases it. At a node whose right half lies wholly beyond the table, the parent control already implies the branch on every tested input, so the walk descends without a new AND. The walk costs 3,327 Toffolis, and the frame apparatus around it costs 534.

SPAN_AT = {}
for _t, _lo, _hi in REGIONS:
_n = 1 << len(_t)
for _base in range(_lo, _hi, _n):
assert _base % _n == 0, (_t, _base)
SPAN_AT[_base] = _n
del _t, _lo, _hi, _n, _base
⋯ 942 lines
def select_walk(b, bits_msb, enter, leaf):
"""Content-pruned descent over the block partition. At a
one-sided node (right half entirely >= L) the parent control
already implies the branch on every graded shot, so the walk
descends with it unchanged — no narrowing AND (the spare copies
land on sel values no shot reaches). ``enter(lo, span, ctrl)``
hooks every controlled node entry — the walk-node monomial channel
emits there; ``leaf(lo, ctrl)`` fires per block.
"""
def rec(bits, lo, span, ctrl):
if lo >= L:
return
if ctrl is not None:
enter(lo, span, ctrl)
if span == 1 or SPAN_AT.get(lo) == span:
leaf(lo, ctrl)
return
hb = bits[0]
half = span >> 1
if ctrl is None:
b.x(hb)
rec(bits[1:], lo, half, hb)
b.x(hb)
rec(bits[1:], lo + half, half, hb)
elif lo + half < L:
anc = b.and_compute(ctrl, hb)
rec(bits[1:], lo + half, half, anc)
b.cx(ctrl, anc)
rec(bits[1:], lo, half, anc)
b.cx(ctrl, anc)
b.and_release(anc, ctrl, hb)
else:
rec(bits[1:], lo, half, ctrl) # one-sided node: no narrowing
rec(bits_msb, 0, 1 << A, None)
9

Frames off, flags cleared

select-unconj, select-unblk

The frames close in reverse order, innermost first. The same interval trie XORs every flag back to zero, and the flag wires return to the pool.

The flag passes reach the peak of the whole circuit, 126 qubits: the 72 boundary wires, 16 keep carriers, 16 selection wires, f, seven flags, and up to 14 transient trie wires. The keep carriers cause this peak, since they must outlive the Pauli stage. Every other walk uses the remaining headroom below it.

Frames off 131 Toffolis · peak 112 qubits
with b.phase("select-unconj"):
for g in PRIORITY: # innermost first
if g in flags:
conjugate_close(b, flags[g], x, g)
Flags cleared 136 Toffolis · peak 126 qubits
with b.phase("select-unblk"):
xor_gate_flags(b, sel_bits, flags)
for g in reversed(PRIORITY):
if g not in flags:
continue
b.release_recycle("flag", [flags[g]])
10

Undo the selection, erase both banks

cmp/unselect, cmp/rev, unlookup

The identical swap restores i and the alternate index, and the identical comparator clears f against the threshold that the keep bank still holds. The two comparisons and two swaps cost 64 Toffolis.

The circuit does not run the lookup a second time. It measures the keep bank and the alternate bank in the X basis. A bank holding d(i) with outcome m leaves the phase (−1)m·d(i). Both phases depend on the same row address, so their exponents add classically and one pass repairs them.

The pass walks 642 windows of 64 rows. Within a window, a one-hot register on address bits 2 to 5 selects one of 16 slots, and Reed–Muller planes in the two low bits carry the remaining variation. Once the nonlinear planes exist, outcome-conditioned CZs apply the corrections without Toffolis. Preparing the one-hot register costs 15 Toffolis and the repair 767.

Unselect and uncompare 32 Toffolis · peak 122 qubits
with b.phase("cmp/unselect"):
for j in range(A):
b.cswap(f, sel[j], idx[j])
with b.phase("cmp/rev"):
compare_into(b, sigma, keep_carriers, f)
b.release_recycle("carry", [f])
b.release("word", word)
b.release("word", [kc])
Banks measured 0 Toffolis · peak 104 qubits
with b.phase("unlookup/measure-keep"):
m_keep = erase_wires(b, keep_carriers)
for q in keep_carriers:
b.recycle(q)
b.release("sel", sel)
with b.phase("unlookup/measure-alt"):
m_alt = erase_wires(b, sel)
for q in sel:
b.recycle(q)
Phase repair 782 Toffolis · peak 99 qubits
b2_fixup(b, idx, m_keep, m_alt)
11

The repair, window by window

b2_fixup

Sixteen wires form the one-hot register, built from address bits 2 to 5 by controlled swaps. fixup_leaf handles one window of 64 rows: it reads the classical outcomes of both banks for each row and applies the matching phase corrections.

def b2_fixup(b, idx, m_keep, m_alt): # noqa: C901 - straight-line circuit emitter
"""Emit the joint deferred unlookup repair at B(2) granularity: a dense
window walk over bits 6-15 (642 windows of 64 rows, DP-capped at
hold budget H_FIX), the 16-slot one-hot routing of bits 2-5,
per-slot outcome-conditioned CZs for the quad-base fix, and
Reed-Muller plane ANDs for the low two bits — one temporary AND
per (window, plane) with free conditioned CZs. Out-of-domain rows
inside the last window inherit their quad base (rows i >= L are
untested).
"""
def row_terms(iv):
t = [m_keep[t2] for t2 in range(16) if (KEEPW[iv] >> t2) & 1]
t += [m_alt[t2] for t2 in range(16) if (ALTW[iv] >> t2) & 1]
return t
mid, hu = idx[2:6], idx[6:]
with b.phase("unlookup/window:prep"):
u = b.qubits(KW)
b.claim("window", u)
b.x(u[0])
for i in reversed(range(LOG_KW)):
for s in range(0, KW, 1 << (i + 1)):
b.cswap(mid[i], u[s], u[s + (1 << i)])
def fixup_leaf(ctrl, wv):
base = wv * FIX_WIN
planes = {}
for Smask in (1, 2, 3):
need = False
for lv in range(KW):
gbase = base + (lv << 2)
if gbase >= L:
continue
acc = []
for rr in range(4):
if rr & ~Smask:
continue
row = gbase + rr
acc = _xor_terms(acc, row_terms(row if row < L else gbase))
if xor_outcomes(acc) is not None:
need = True
break
if need:
planes[Smask] = None
assert frozenset(planes) == _PLANE_SETS[wv]
win_terms = {}
for lv in range(KW):
gbase = base + (lv << 2)
if gbase >= L:
continue
win_terms[lv] = {
rr: row_terms(gbase + rr if gbase + rr < L else gbase) for rr in range(4)
}
gb = xor_outcomes(win_terms[lv][0])
if gb is not None:
b.cz(ctrl, u[lv], cond=gb)
def emit_plane(pw, Smask):
for lv, terms in win_terms.items():
acc = []
for rr in range(4):
if rr & ~Smask:
continue
acc = _xor_terms(acc, terms[rr])
gb = xor_outcomes(acc)
if gb is not None:
b.cz(pw, u[lv], cond=gb)
# the r0r1 plane chains through a HELD single-bit plane: two
# plane wires live only across the pair's emission (the same
# transient the build itself has), so its release recomputes
# nothing, and a needed single rides the held wire for free
done = set()
if 3 in planes:
lo_S = 1 if 1 in planes else 2
lo_bit, hi_bit = (idx[0], idx[1]) if lo_S == 1 else (idx[1], idx[0])
plo = b.and_compute(ctrl, lo_bit)
p3 = b.and_compute(plo, hi_bit)
emit_plane(p3, 3)
b.and_release(p3, plo, hi_bit)
if lo_S in planes:
emit_plane(plo, lo_S)
done.add(lo_S)
b.and_release(plo, ctrl, lo_bit)
done.add(3)
for Sm, ibit in ((1, idx[0]), (2, idx[1])):
if Sm in planes and Sm not in done:
pw = b.and_compute(ctrl, ibit)
emit_plane(pw, Sm)
b.and_release(pw, ctrl, ibit)
with b.phase("unlookup/window:fixup"):
_capped_window_walk(b, hu, fixup_leaf)
with b.phase("unlookup/window:unprep"):
for i in range(LOG_KW):
for s in range(0, KW, 1 << (i + 1)):
v = u[s + (1 << i)]
b.cx(v, u[s])
b.release("window", [v])
b.and_release(v, mid[i], u[s])
b.x(u[0])
b.release_recycle("window", [u[0]])
Start (init): 0 Toffolis, peak 104 qubitsAlias lookup (lookup): 10,271 Toffolis, peak 119 qubitsCompare and select (cmp): 32 Toffolis, peak 122 qubitsFrame flags (select-blk): 136 Toffolis, peak 126 qubitsFrames on (select-conj): 131 Toffolis, peak 112 qubitsBlock select (select-pauli): 3,327 Toffolis, peak 124 qubitsFrames off (select-unconj): 131 Toffolis, peak 112 qubitsFlags cleared (select-unblk): 136 Toffolis, peak 126 qubitsUnselect and uncompare (uncmp): 32 Toffolis, peak 122 qubitsBanks measured (unlookup): 0 Toffolis, peak 104 qubitsPhase repair (fixup): 782 Toffolis, peak 99 qubits12672peak live qubits per phase, above the 72 I/O qubits1.5 × 10⁴ Toffolis →
def select_pauli(b, sel_bits, x):
"""One content-pruned descent over the 3,221 frame blocks; seven
flag wires XOR-accumulate the 14 interval gates; frames nest in
the fixed application order (F innermost); per-block sign
polynomials ride free channels plus one CCZ per surviving
monomial (shared prefix AND per degree-3 group), the seven
node-hosted monomials emitting once at their walk nodes.
"""
_gauge_c, lin_signs, mono_signs, node_monos = sign_tables()
def apply_row(ctrl, iv):
m = MASKS[iv]
for j in range(X): # Z-part first: CZ sees the INPUT x values
if (m >> (X + j)) & 1:
b.cz(ctrl, x[j])
xor_word(b, ctrl, m & XMASK, x) # then the X-part flips
if SIGN[iv]: # constant sign (-1)^(theta ^ ny2)
b.z(ctrl)
for i in lin_signs.get(iv, ()):
b.cz(ctrl, sel_bits[i])
pref = pref_bit = None
for mn in mono_signs.get(iv, ()):
if len(mn) == 2:
b.ccz(ctrl, sel_bits[mn[0]], sel_bits[mn[1]])
else: # degree >= 3: prefix AND per group
if pref_bit != mn[0]:
if pref is not None:
b.and_release(pref, ctrl, sel_bits[pref_bit])
pref = b.and_compute(ctrl, sel_bits[mn[0]])
pref_bit = mn[0]
if len(mn) == 3:
b.ccz(pref, sel_bits[mn[1]], sel_bits[mn[2]])
else:
t2 = b.and_compute(pref, sel_bits[mn[1]])
b.ccz(t2, sel_bits[mn[2]], sel_bits[mn[3]])
b.and_release(t2, pref, sel_bits[mn[1]])
if pref is not None:
b.and_release(pref, ctrl, sel_bits[pref_bit])
hosted = set()
def node_enter(lo, span, ctrl):
monos = node_monos.get((lo, span))
if not monos:
return
for mn in monos:
if len(mn) == 2:
b.ccz(ctrl, sel_bits[mn[0]], sel_bits[mn[1]])
else:
t2 = b.and_compute(ctrl, sel_bits[mn[0]])
b.ccz(t2, sel_bits[mn[1]], sel_bits[mn[2]])
b.and_release(t2, ctrl, sel_bits[mn[0]])
hosted.add((lo, span))
Frame flags 136 Toffolis · peak 126 qubits
with b.phase("select-blk"):
flags = {}
for g in PRIORITY:
if not GEN_IVS[g]:
continue
fq = b.qubit()
b.claim("flag", [fq])
flags[g] = fq
xor_gate_flags(b, sel_bits, flags)
Frames on 131 Toffolis · peak 112 qubits
with b.phase("select-conj"):
for g in reversed(PRIORITY): # outermost first, F innermost last
if g in flags:
conjugate_open(b, flags[g], x, g)
Block select 3,327 Toffolis · peak 124 qubits
with b.phase("select-pauli"):
select_walk(b, list(reversed(sel_bits)), node_enter, lambda lo, ctrl: apply_row(ctrl, lo))
assert hosted == set(node_monos), "node-hosted monomial span missed"
Frames off 131 Toffolis · peak 112 qubits
with b.phase("select-unconj"):
for g in PRIORITY: # innermost first
if g in flags:
conjugate_close(b, flags[g], x, g)
Flags cleared 136 Toffolis · peak 126 qubits
with b.phase("select-unblk"):
xor_gate_flags(b, sel_bits, flags)
for g in reversed(PRIORITY):
if g not in flags:
continue
b.release_recycle("flag", [flags[g]])
⋯ 2 lines
def build():
b = Builder()
regs = declare_registers(b, [("i", A), ("sigma", S), ("x", X)])
idx, sigma, x = regs["i"], regs["sigma"], regs["x"]
for name in ("i", "sigma", "x"):
b.claim(name, regs[name])
# ONE walk carries BOTH payloads: keep bits 0-14 into the 15-wire
# word bank plus one carrier for bit 15, alt into the 16-wire
# selection scratch (alt before the swap, sel during SELECT).
word = b.qubits(B)
b.claim("word", word)
kc = b.qubit()
b.claim("word", [kc])
keep_carriers = list(word) + [kc]
sel = b.qubits(A)
b.claim("sel", sel)
def leaf(lo, ctrl):
xor_word(b, ctrl, KEEPW[lo], keep_carriers)
xor_word(b, ctrl, ALTW[lo], sel)
Alias lookup 10,271 Toffolis · peak 119 qubits
with b.phase("lookup"):
lookup_walk(b, list(idx[::-1]), leaf)
# f = [sigma < keep] on one scratch wire; the keep bank stays live
# through SELECT so the identical comparator pass can erase f after
# the selection is unwound
Compare and select 32 Toffolis · peak 122 qubits
with b.phase("cmp"):
f = b.qubit()
b.claim("carry", [f])
compare_into(b, sigma, keep_carriers, f)
# the selection swap: sel <-> i under f — the index wires carry the
# unselected branch through SELECT and the identical swap restores
# them after it
with b.phase("cmp/select"):
for j in range(A):
b.cswap(f, sel[j], idx[j])
select_pauli(b, sel, x)
Unselect and uncompare 32 Toffolis · peak 122 qubits
with b.phase("cmp/unselect"):
for j in range(A):
b.cswap(f, sel[j], idx[j])
with b.phase("cmp/rev"):
compare_into(b, sigma, keep_carriers, f)
b.release_recycle("carry", [f])
b.release("word", word)
b.release("word", [kc])
Banks measured 0 Toffolis · peak 104 qubits
with b.phase("unlookup/measure-keep"):
m_keep = erase_wires(b, keep_carriers)
for q in keep_carriers:
b.recycle(q)
b.release("sel", sel)
with b.phase("unlookup/measure-alt"):
m_alt = erase_wires(b, sel)
for q in sel:
b.recycle(q)
Phase repair 782 Toffolis · peak 99 qubits
b2_fixup(b, idx, m_keep, m_alt)
return b, regs