PhaseTripleProduct

A recursive Toom-Cook construction for a three-register phase, and what is proved about it

Scope: read this first

This page is about a different primitive from the one in ForShor's order-finding circuit. PhaseProduct applies \(\exp(i\pi\varphi\,xz)\) to two registers and is what ForShor's modular multiplication is built from. PhaseTripleProduct (PTP) applies \(\exp(i\pi\varphi\,xyz)\) to three registers. As such, it is distinct from ForShor's correctness and gate-count theorems, but is a part of the larger ForShor.ai challenge.

We construct PhaseTripleProduct in the same layout as PhaseProduct, defining the key theorems and claimed validity in Statement.lean, storing the lemmas in Proofs/ and proving the claims in Main.lean proves the claims. We will explain the primitives similarly here, and point to these files for a reader to learn more. See the structure here.

A phase triple product, just like a phase product, performs multiplication, but focuses on a basis state by \(\exp(i\pi\varphi\,x\,y\,z)\), where \(x,y,z\) are the signed integers held in three \(n\)-qubit registers. A direct product application will use \(O(n^3)\) gates. The recursion will act the same way as PhaseProduct, splitting an operand into \(k\) limbs the product of three degree-\((k-1)\) limb polynomials has degree \(3(k-1)\). At the limb radix, the polynomial is a fixed rational combination of its values at \(3(k-1)+1 = 3k-2\) distinct points. Evaluating each of the three operands at each point with a short program of additions, negations and shifts, taking one smaller phase triple product per point, and recursing gives \(O(n^{\log_k(3k-2)})\) gates for a fixed table. As such, the triple product gate complexity will be \(O(n^{2})\) at \(k=2\), \(O(n^{1.77})\) at \(k=3\), etc.\(\log_k(3k-2)\) for \(k = 2,3,4,5,6\): \(2.000,\ 1.771,\ 1.661,\ 1.609,\ 1.547\). The PhaseProduct exponent \(\log_k(2k-1)\) is \(1.585,\ 1.465,\ 1.404,\ 1.365,\ 1.343\). The comparison is between the exponents of the two constructions, not between two ways of computing the same thing.

We can write the instruction set at some level of the recursion as a table, just like PhaseProduct, defining a straight-line program of addScaled, negate, shiftL, shiftR and PhaseProduct i checkpoints, with now \(3k-2\) interpolation points. We formally verify this at the gate level in ForShor's LowGate language, for whole banded policies. We state its claims as propositions, primarily that for every checked policy and every width there is a circuit following the policy that acts as the specification operator on every clean state, with an exact gate census. Extensions give a controlled version, the \(O(n^{\log_k(3k-2)})\) gate count, operands of unequal width and a qubit count: the framework's count of the circuit's peak live qubits, scratch included, is at most \(3n\) plus the recursion's workspace and the negation's clean ancilla, and for the policies on the results board that bound is evaluated in the kernel.

An interactive diagram is given below to visualize the flow of the argument. We provide the proof as a directed graph, alongside a figure for the recursion itself.

How one node is computed

Given three registers and a width, the policy either stops at a leaf or picks a table. Registers are split into limbs, moved to each interpolation point by the table's program, a smaller phase triple product is taken there, and everything is undone. Each of the \(3k-2\) smaller products is the same problem at a smaller width, which is the loop on the left.

The proof, layer by layer

The development follows ForShor's own layout, wherein Statement holds each definition and claim; Main proves these claims true with the blocks between the two are the lemmas (Proofs/). Building Main.lean is the guarantee that the claims are proved. The rule that makes Statement plus Main enough is checked rather than asserted: scripts/StatementClosure.lean computes every constant the claims reach, unfolding definitions, and fails if one lives outside Mathlib, Framework/ or a Statement.lean, and CI runs it. Open a block for its role, the files within, what it rests on and feeds, and the statements it carries, quoted verbatim.

Inside PTP

The figure below draws a reference policy, where at \(n = 2048\), its four bands use \(k = 6, 4, 2, 2\); at exact widths the recursion goes \(2048 \to 375 \to 189 \to 96 \to 50\), using the first, third, third and fourth bands and then the leaf, so the \(k = 4\) band is never reached. The middle panel draws the \(k = 2\) table of the third band, which splits one product into four, and the right panel what happens to each band for the full policy composition.

Left: a policy chooses a table for each range of widths; the underlined \(\underline{w}_j\) are its thresholds, the plain \(w_i\) the widths the recursion reaches. Middle: one recursion level of a \(k=2\) table. Registers \(r_0, r_1\) hold the two limbs of each of \(x, y, z\); each operation \(\Pi^{(j)}\) acts on all three alike, drawn as one gate per operand: a dot on the limb it reads, a box on the limb it writes, and the other wires pass across; four phase triple products are taken at \(p = 1, 0, -1, \infty\). Right: each of the four is itself lowered the same way, until a policy gives no table. Click anything.

One recursion level. \(\Pi^{(0)}\) turns \((x_0, x_1)\) into \((x_0, x_0+x_1)\); two phase triple products are taken, at \(p=1\) on \(r_1\) and at \(p=0\) on \(r_0\). \(\Pi^{(1)}\) moves the registers to \((x_0 - x_1,\ x_1)\), for \(p=-1\) and \(p=\infty\). \(\Pi^{(2)}\) adds \(r_1\) back into \(r_0\), restoring \((x_0, x_1)\). Each product has its own angle, \(\varphi\,c_t\), with \(c_t\) the interpolation weight of its point at the limb radix \(B\): for this table \(c = (B+B^2)/2,\ 1-B^2,\ (B^2-B)/2,\ B^3-B\), and node_identity says they combine the four products into \(\varphi\,xyz\). The arithmetic is shared by all three operands, so a table operation becomes three gates, one per operand.

Why this has to be checked. A table is trusted only through its contract: \(3k-2\) distinct valid points, each checkpoint consuming the next point in order with the registers holding exactly that point's values, and the program returning the registers to where they started. The fault witnesses show the conditions are load-bearing. Declaring the points in the wrong order is rejected by the contract, where evaluated anyway applies \(B^3+3B^2-5B+1\) rather than \((B+1)^3\) at \(x=y=z=B+1\). Running the children one bit below the exact width gives a circuit that is provably wrong on a concrete state, because an intermediate value overflows and is then read by a child.