Prime-field modular inversion

The point P arrives in two 256-qubit registers, x1 and y1. The fixed point Q arrives as classical bits, and point_cbspecs turns them into the constants that the later modular additions use. That work is classical and costs no Toffolis.

The circuit allocates one more 256-qubit word, A, and a multiplier machine whose pool of workspace qubits is resized phase by phase. HmrDivstepInv binds the inversion to x1: during each walk, the integer g and the coefficient f_v live on the x1 word.

Both coordinates move relative to Q: x1 becomes P_x − Q_x and y1 becomes P_y − Q_y, modulo p. Each subtraction is a comparison, two controlled constant additions, and a second comparison that clears the flag qubit.

The slope λ = (P_y − Q_y)(P_x − Q_x)⁻¹ is now the quotient of y1 by x1.

The walk starts from (f, g) = (p, x1) with coefficients f_v = 0 and g_v = 1, and then runs 533 divsteps. g overwrites x1 in place, and f and g_v fill the empty word A. As f and g shrink, f_v and g_v grow into the positions they vacate.

The multiplier pool parks at width zero (mm.off()), because the walk allocates its own scratch qubits. Every step has the same gates; only the control values differ between inputs.

At the end of the walk, g = 0, f = ±1, and f·f_v ≡ 2^t x1⁻¹ (mod p), where t counts the active steps. The closer clears f down to its sign qubit and cancels g_v, which equals ±p and so is fixed by that sign.

row_mul adds |f_v|·y1 into the empty word A and applies the 498 halvings that every input shares. sign_fix negates A when the signs of f and f_v differ. A now holds λ·2^{t − 498}.

y1 is no longer needed here. b.hmr measures each of its qubits in the X basis. This returns the word to |0⟩ and leaves a phase that depends on y1 and the outcomes mbits. The freed word becomes the new home of f and g_v (rebind_band, closer_inv). Finally, arm_rider attaches a modular halving of A to the reverse walk.

The reverse walk undoes the 533 forward steps in the opposite order. It restores g to x1 and returns f, f_v, g_v and the record to zero; finish then frees the walk registers.

From step 499 on, each active reverse step also halves A modulo p. These t − 498 halvings remove the remaining power of two, and no register ever holds t. A now holds λ exactly.

The measurement of y1 left a phase, and λ sits in A instead of y1. With x1 and A = λ in hand, one multiplication recomputes y1 = x1·λ, which is the measured value P_y − Q_y.

A Z gate on each qubit whose outcome is 1 cancels the phase. The inverse multiplication clears y1 again, and a swap moves λ into y1. The early measurement freed the y1 word for the reverse walk, at the cost of these two multiplications, 383,522 Toffolis.

Now x1 = P_x − Q_x and y1 = λ. The new x-coordinate needs λ², but the circuit never holds it in a register. The word A is idle, so the circuit releases it to make room for the carries of the square.

_subtract_square then removes λ² from x1 one term at a time. A constant addition adds 3Q_x, which leaves x1 = P_x + 2Q_x − λ². Finally the circuit allocates A again.

The circuit now needs y1 ← x1·λ. The product forms in A (multiply); erasing λ afterwards requires λ = A/x1, so the circuit inverts x1 a second time. An X-basis measurement erases λ at once and frees the word to host f and g_v.

Walk C runs forward on x1 with a rider that halves A at each active step from 499 on. At the seam, row_mul and sign_fix rebuild λ in y1 exactly. The Z fixup cancels the phase of the measurement, and the inverse calls clear y1 again.

Walk D undoes walk C, and its rider doubles A back to x1·λ. A final swap leaves y1 = x1·λ.

x1 becomes p − x1 and then gains Q_x, which gives R_x = λ² − P_x − Q_x. Before the negation, x1 held Q_x − R_x, so y1 = λ(Q_x − R_x). Subtracting Q_y gives R_y.

The teardown releases A and the multiplier machine.