HHL rotation angle

The input is a 21-bit integer X with x = X/2¹⁶ ∈ [1, 32). The circuit adds the angle round(2³² arcsin(2¹⁵/X)) to a 33-bit accumulator k and leaves X unchanged (the two registers). The error must stay within 429 output units, below 10⁻⁷ radians, on every input.

The domain is cut into 345 pieces, called leaves. Each leaf is a dyadic interval [L, L + 2^b) with L a multiple of 2^b, and its width runs from 2⁸ to 2¹⁵. The table LSET maps each leaf to four integers: intercept g₀, slope g₁, curvature g₂, and a rotation amount sh.

tree_from_leafset rebuilds the binary tree over the bits of X: a node splits on one bit until it reaches a stored leaf. One subtree per octave covers 2¹⁶ to 2²¹. Leaves are narrow near x = 1, where the curve bends, and wide where it is flat. A uniform partition at the finest width would need 7,936 pieces.

A dyadic leaf of width 2^b is fixed by the leading 21 − b bits of X. The circuit therefore finds the leaf by walking the tree, with no comparison against an arbitrary boundary. At each leaf, visit1 writes the set bits of the four stored words with CNOTs controlled by the leaf's flag. Table width therefore adds no Toffolis.

The words are a 26-bit intercept, a 16-bit biased slope, a five-bit curvature, and a three-bit rotation amount. The walk visits the octaves in order. The lookup costs 343 Toffolis, about one per leaf.

Every leaf feeds the same arithmetic, but leaves have different widths. Write X = L + δ with 0 ≤ δ < 2^b. The table stores sh = 15 − b, and the circuit rotates the low 15 bits of X cyclically left by sh. The three bits of sh control rotations by 1, 2, and 4 places.

The varying bits of δ move to the top of the word. The bits that the leaf fixes wrap around to the bottom and form a constant c_L, so the coordinate is dn = 2^15−bδ + c_L. The offline fit absorbs c_L into the coefficients, so no subtraction is needed. The coordinate lives on the X wires themselves; dqb names dn ≫ 3 there.

The circuit evaluates each leaf's quadratic in nested form, g₀ − dn(g₁ − g₂dn), with the intercept and the outer product accumulated into k. The intercept goes first: an in-place addition of the stored 26-bit word at bit 6 of k. Its lowest 11 carry positions use temporary ANDs that are erased by measurement; the higher positions use the majority/unmajority ripple of Cuccaro et al. This addition costs 41 Toffolis.

The intercept word is not needed again. demolish measures each wire in the X basis and frees it. An outcome of 1 leaves a sign that depends on the leaf. The circuit keeps the outcomes in mb_c0 and repairs those signs at the end, together with the signs of the other three words.

Both products use signed radix-4 (Booth) digits. For the product, the multiplier is Y = dn ≫ 2, a 13-bit integer, and digit t is d_t = y_2t−1 + y_2t − 2y_2t+1 ∈ {−2, …, 2}. The sum Σ d_t4^t equals Y exactly, so seven rows replace thirteen. The five-bit curvature word becomes three digit rows over dn ≫ 3. prod_row_spec and q_row_spec name each digit's source wires; prod_pairs and q_pairs list the operand bits of each column.

The inner step forms v = W − Q(dn, g₂) over the slope word, where W = (g₁ ≪ 4) + 2¹⁶. Four fresh guard wires sit below the stored slope word. Complementing the low 17 bits before and after the rows turns the signed additions into a subtraction.

Signed partial sums need not move monotonically, so a safe final value says nothing about the prefixes. An exhaustive check confirms that after every row, for every input, the window stays in [0, 2¹⁷). No carry crosses bit 16, so each row's chain is 17 bits wide. The rows run highest digit first.

The outer product goes straight into the accumulator: k ← k − P(dn, v). Complementing k before and after the seven rows turns their additions into a subtraction. No register holds the product or the finished angle.

Row t adds d_t(v ≫ sig_t)·2^B_t, with B = [4, 5, 5, 5, 6, 6, 6] and sig = [13, 12, 10, 8, 7, 5, 3]. These shifts drop the low partial-product columns. The offline search fits the integer coefficients to this exact truncated computation, so truncation and rounding share one error budget. The exhaustive check finds a worst error of 427.15 output units, 9.95 × 10⁻⁸ radians.

The bias 2¹⁶ inside W enters every product row. Because Σ d_t4^t = Y exactly, the row-wise bias terms add up to exactly 2⁷Y. One carry-only addition of the 13 bits of Y removes them all. It costs 25 Toffolis, and its carry ANDs are erased by measurement.

The three curvature rows then run again in reverse order, without the complement, and add Q back, so v = W. The reverse order visits the same partial sums, so the same window check covers it. The low four bits of W are zero, so the guards hold |0⟩ and are freed without measurement.

The three inverse rotations restore the low bits of X. The slope, rotation, and curvature words now hold exactly their table values. The circuit measures the slope word, then the rotation and curvature words, in the X basis.

Reversing the lookup would clear these words with a second 343-Toffoli walk. Measurement clears them at no Toffoli cost. Each outcome leaves a sign that is a known function of the leaf, and the last stage repairs all of them.

Measuring a wire that holds leaf bit b with outcome m multiplies the state by (−1)^bm. For each recorded 1, the circuit rebuilds the leaf's flag and applies a CZ between the flag and a wire held at |1⟩. The CZ costs no Toffolis; rebuilding every flag with a full walk would cost 343.

The walk instead stops at a fixed tree level. Below it, a one-hot decode of input bits 7 and up serves all narrower leaves at once. fixup_cost adds the walk's ANDs above level m to 2^m−7 − 2 for the decode. The loop keeps the cheapest level whose bank fits under the cap. It selects level 12: the upper walk costs 182 Toffolis, and the decode of bits 7 to 11 distinguishes 211 of the 345 leaves.

onehot_build grows the decode one input bit at a time, one AND per new wire. Thirty-two one-hot wires cost 2⁵ − 2 = 30 Toffolis, so the walk and the decode cost 212 together. The bank stays live for the whole walk, so the four measured words share it.

The floored walk reaches each leaf with its flag. leaf_mbs gathers the outcomes of exactly the bits that the lookup wrote. A wide leaf gets one CZ with the kick wire per outcome, conditioned on its classical value. A narrow leaf gets CZs with its one-hot wires instead.

onehot_free erases the decode, and the kick wire returns to |0⟩. Only X and k remain, with k increased by the angle.