A depth-95 phase oracle for the Classiq logo
My top-five entry to the Classiq Quantum Circuit Challenge, a phase oracle of depth 95 where the organisers' baseline has depth 5329, built from one compute–uncompute sandwich, two small codes, and a search over the codes instead of the circuit. Part 2 of a series on quantum circuit optimization.
The Classiq Quantum Circuit Challenge asked for a quantum circuit that puts a minus sign on the black pixels of the Classiq logo, using one- and two-qubit gates on at most 18 qubits, scored by depth. The organisers' baseline circuit has depth 5329. My entry has depth 95 with 272 CNOTs, and it finished in the top five.
The short version is four design ideas that together closed most of the gap, plus a final round of polishing:
Part 1 is a field guide to quantum compilers, but you don’t need it to follow this one. I assume you know what a qubit, a CNOT gate and a circuit diagram are, and I explain each compiler or logic-synthesis idea where it comes up. If you want the long form, there is a 19-page write-up and a companion notebook that redraws every data plot below from the shipped data in under a minute; both are linked in the last section.
Compilers and this challenge
Why not just run a compiler?
Qiskit and tket are free, and both will shorten a circuit if you ask them to. The obvious first move is to give them the baseline circuit at their strongest setting. I did that on my own reproduction of the baseline, which scores the same 5329 and 3502. Every pair of qubits could share a CNOT, as in the challenge, and I checked each output the same way I checked my entry:
| tool | depth | CNOTs |
|---|---|---|
| the baseline itself | 5329 | 3502 |
| Qiskit, optimization level 3 | 5021 | 3355 |
| tket’s FullPeepholeOptimise, then Qiskit | 5004 | 3347 |
| PyZX’s full_reduce, then extraction | 8950 | 8576 |
| my rescheduler, which only reorders gates | 4665 | 3502 |
| the circuit in this post | 95 | 272 |
The off-the-shelf tools shorten the baseline by about 6 percent, and my own rescheduler by 12.5 percent. PyZX, which rewrites the circuit as a ZX-diagram and turns it back into gates, returned a correct circuit with more than twice the CNOTs. It did cut PyZX’s count of T gates by a quarter, and T gates are the cost that matters on the fault-tolerant machines of the next section. A second PyZX recipe returned depth 4668, better than every off-the-shelf row, but that circuit failed the check: its helper qubits did not return cleanly to 0, and some pixels got the wrong sign.
These tools are transpilers: a transpiler reads a list of gates and must return a list that implements the same unitary, so the result has to be right on all \(2^{18}\) basis states. Two facts that matter here are not in the gate list.
- The six helper qubits start at 0 and must end at 0. The circuit only has to be right when they start at 0, so 63 of every 64 inputs that a transpiler must preserve are inputs the challenge never uses. Qiskit assumes by default that every qubit starts at 0. The assumption covers all 18 at once, including the twelve that hold the pixel, and with it my earlier circuits came back wrong on superpositions of pixels, so the Qiskit rows above were run with it switched off.
- The 3502 CNOTs are 18 rectangle tests run one after another, which together compute one bit per pixel. The gate list does not mark where one test ends, and nothing in it names the bit.
A rewrite that needs either fact is out of a transpiler’s reach. So the lever in this challenge is not the compiler. It is the encoding: which intermediate bits the circuit computes, which qubits they live on, and how the sign is read off them. Here is the whole path from the baseline to 95, one level at a time:
| what changed | depth |
|---|---|
| nothing: the 18 rectangle tests, one after another | 5329 |
| gate-level tools reorder and rewrite the same gates | about 5000, 4665 at best |
| a generic encoding: the pixel function’s truth table written as an XOR of products | 1886 |
| logic networks shaped to the logo by hand | 468, then 345 |
| the row and column codes of this post, then a search over the codes | 107 |
| gate-level polishing of that circuit | 95 |
The code design does the work, not the compiler
Of the 56-fold drop from 5329 to 95, gate-level tools account for a few percent at the start and the last 12 layers at the end. Everything in between came from changing what the circuit computes. A compiler packs the gates it is given; the encoding decides which gates there are to pack. Compilers still matter here, since every candidate circuit goes through a scheduler, but the rest of this post is mostly about designing the codes.
Where this sits in compiler research
Depth with free one-qubit gates is a cost model for today’s noisy hardware, where every layer of gates adds error. Much of the current research on compilers targets fault-tolerant machines instead, which run error-corrected qubits and count costs differently. There, Clifford gates such as CNOT, H and S are comparatively cheap. The expensive gate is the T gate, because each one consumes a magic state that has to be prepared separately
In this challenge an arbitrary one-qubit gate costs one layer. Under fault-tolerant costs the same gate becomes a sequence of Clifford and T gates that grows longer as the approximation is made tighter
The challenge
Put the column \(x\in\lbrace 0,\dots,63\rbrace\) of a pixel on six qubits and the row \(y\) on six more. A phase oracle for the logo, the kind of circuit Grover’s search algorithm queries
where \(\mathrm{logo}(x,y)=1\) on a black pixel. The six extra qubits are helpers. The circuit may use them as scratch space, but they must end in \(\lvert 0\rangle\) again, so that the oracle behaves the same on any superposition of pixels. That makes 18 qubits in all: \(x\) on \(q_0\)–\(q_5\), \(y\) on \(q_6\)–\(q_{11}\), and the helpers on \(q_{12}\)–\(q_{17}\).
Under the challenge rules u3 gates (any one-qubit gate) and cx gates (CNOTs) between any two qubits. It is scored by its depth, the number of layers of gates, with the cx count as a tie-breaker. Two gates can share a layer when they act on different qubits.
The logo is the union of four shapes that the challenge defines exactly: a square (\(2\le x\le 26\), \(29\le y\le 53\)), a bar (\(26\le x\le 49\), \(39\le y\le 43\)), a small disc with \((x-55)^2+(y-41)^2\le 42\), and a big disc with \((x-40)^2+(y-19)^2\le 72\). Together they make 1097 of the 4096 pixels black.
Depth is about packing
Depth counts layers, and one layer can hold many gates as long as no two of them touch the same qubit. So two pieces of work on disjoint qubits cost the longer of the two, while two pieces on the same qubits cost the sum:
The baseline circuit covers the logo with 18 rectangles and marks them one at a time. Every rectangle test needs all twelve coordinate qubits, so the rectangles cannot overlap in time, and their depths add up to 5329. I wanted a circuit whose expensive parts live on different qubits, so that a scheduler, the compiler step that assigns each gate to a layer, can stack them in the same layers.
One sandwich for the whole logo
Compute, flip the sign, uncompute
The oracle has one job: multiply each pixel’s state \(\lvert x,y\rangle\) by \(-1\) if the pixel is black, and leave it alone if it is white. Deciding black or white is a small calculation, and a quantum circuit can’t calculate the way a laptop does. Every gate is reversible, so nothing can be overwritten and forgotten. The intermediate results (“how far does the disc reach in this column?”, “how far is this row from row 41?”) need somewhere to live, and that place is the helper qubits, which start at \(\lvert 0\rangle\).
Leaving those results on the helpers after the sign flip would break the oracle. The circuit acts on a superposition of all 4096 pixels at once, and a helper still holding, say, a column’s radius would hold a different value for different pixels. It would be entangled with \(x\) and \(y\), and the pixels would no longer interfere the way a search algorithm such as Grover’s needs them to. The fix goes back to Bennett: compute the result, use it, then run the computation backwards, so the helpers return to \(\lvert 0\rangle\) and the sign is the only trace left. Almost every oracle that uses helper qubits has this three-part shape, called compute–uncompute
| step | what it does |
|---|---|
| \(E\) | compute some useful bits from \(x\) and \(y\) onto the helpers (the encoder) |
| \(\Phi\) | flip the sign, depending on those bits (the middle) |
| \(E^\dagger\) | run the encoder backwards, which returns the helpers to \(\lvert 0\rangle\) |
The smallest example is a single AND. A Toffoli writes \(a \wedge b\) onto a helper, a \(Z\) on the helper flips the sign when that bit is 1, and a second Toffoli clears the helper again. The net effect is \(\lvert a,b\rangle \mapsto (-1)^{ab}\lvert a,b\rangle\) with the helper back at 0. That case is just a CZ gate, but the same pattern works for functions far too big for one gate.
The middle only multiplies each basis state by \(\pm 1\), so running \(E\) backwards afterwards undoes everything except the sign. I call this shape a sandwich. A bonus of the exact undo is that the encoder’s multi-controlled gates may use cheaper forms that are right only up to a phase that depends on the basis state. Because the middle is a pure sign flip, those phases pass through it untouched, and the undo, built from the inverse of the very same gates, removes them
From three sandwiches to one
My first circuits used one sandwich per shape (the square and the bar shared one, so three in all) and ran them one after another. Each sandwich needed all twelve coordinate qubits, so, by the packing rule, their depths added up. That design stopped at 231 layers.
The way out was to ask each shape’s question differently. “Is \((x,y)\) inside the small disc?” needs both coordinates. But it splits into two questions that each need only one: “how far up and down does the disc reach in column \(x\)?” and “how far is row \(y\) from the disc’s centre row?” The pixel is inside when the second number is at most the first. The same split works for all four shapes, because in every column each shape covers one run of rows around row 41 or row 19.
So the design I kept uses one sandwich for the whole logo and splits its encoder in two:
- a column code \(E_{\mathrm{col}}\), which reads only the six \(x\) qubits and writes on four helpers;
- a row code \(E_{\mathrm{row}}\), which reads only the six \(y\) qubits and writes on the other two helpers.
The two codes share no qubit (with one late exception, below), so they run in the same layers, and the encoder costs the longer of the two instead of their sum. An early whole-logo circuit started at 260 layers. I then let an LLM-driven program-evolution loop, ShinkaEvolve
Two pricing rules follow from this shape, and the rest of the method leans on both:
Two pricing rules of the sandwich
- Every layer of a code is paid twice, once on the way in and once on the way out. A layer of the middle is paid once.
- The two codes run in parallel, so the circuit is roughly as deep as its longer side, the slower of the two codes. Shortening the shorter side buys nothing.
There are no spare qubits: twelve hold the coordinates and only six are helpers. So each code writes its outputs partly on top of its own input qubits, and only the exact undo at the end puts \(x\) and \(y\) back. In the final circuit the column side owns ten qubits (\(x\) plus \(q_{14}\)–\(q_{17}\)) and the row side owns eight (\(y\) plus \(q_{12}\) and \(q_{13}\)). A single gate, a Toffoli controlled by \(q_0\) and the negated \(q_{11}\) with target \(q_3\), reads both sides; it saved six CNOTs late in the campaign.
Side note: why four helpers on one side and two on the other
A reversible circuit can’t forget, and that sets how many helpers each code needs. When a code finishes, its wires must still tell every input apart, or the code could not be run backwards. Whatever the summary lumps together has to be remembered somewhere else on the code’s wires.
The two summaries lump very differently. The column summary is coarse. Columns at the same distance left and right of a disc’s centre get the same radius, and the columns under the square only need “radius at least 8”. In the codes of my depth-138 circuit, which split the wires the same way as the final one, the 64 columns give only 19 different outputs, and up to 7 columns share one. Telling 7 columns apart takes 3 more bits, so the six output bits need at least nine wires. The column code uses ten. The row summary is nearly a relabelling of the row: the distance to the centre row, the side, and two flags almost pin \(y\) down. The 64 rows give 62 different outputs and no more than two rows share one, so one extra bit is enough. Seven outputs plus that bit is the row side’s eight wires.
The finished circuit, layer by layer
The final 95-layer circuit is one sandwich, and you can see it in the gates. Layers 1–43 hold 131 of the 272 CNOTs, mostly the two codes, with the column side and the row side in the same layers. Layers 44–52 are mostly the middle and hold only 13 CNOTs. Layers 53–95 hold 128 CNOTs, and 127 of them also appear, with the same control and target, in layers 1–43: they are the codes run backwards.
Depth is set by a few crowded wires. The helper \(q_{16}\) is busy in 81 of the 95 layers, while \(q_0\) and \(q_7\) are busy in only 18. That is why the search later in this post targets the column code and the time its helpers stay busy.
Row and column codes
What the codes compute
The sandwich only helps if both codes are short, so the codes should carry as little information as the middle needs. In every column of the logo, the black pixels of each shape form one unbroken run of rows, centred on row 41 or on row 19. So a column can be summarised by how far from the centre row it still reaches, a row by how far it sits from the centre row, and a pixel is black when the second number is within the first.
| code | bits | meaning |
|---|---|---|
| column code | \(\mathsf{R}=\mathsf{R}_0\ldots\mathsf{R}_3\) | a 4-bit radius: how far from the centre row this column belongs to a disc |
| \(\mathsf{fam}\) | “this is a bar column” | |
| \(\mathsf{L}\) | “this is a disc column” | |
| row code | \(\mathsf{d}=\mathsf{d}_0\ldots\mathsf{d}_3\) | a 4-bit distance from this row to its centre row (41 or 19) |
| \(\mathsf{s}\) | 1 if the row is above its centre row | |
| \(\mathsf{f}\) | “this row crosses the square” (\(29\le y\le 53\)) | |
| \(\mathsf{b}\) | “this row crosses the bar” (\(39\le y\le 43\)) |
These meanings only need to hold where the middle reads them. Elsewhere a code may write other values, as long as the picture stays right; the examples below show some.
One distance for two centre rows
The row code has to measure distances to two different centre rows with the same four bits. It does this with a subtraction. It computes \(\text{centre}-y\) in four-bit binary and keeps the sign of the result as \(\mathsf{s}\). On or below the centre row the result is the distance. Above it the result is negative, and the code is left holding \(y-\text{centre}-1\), one less than the distance (the negative result’s four bits, inverted). Instead of spending gates to fix this, the middle tests \(\mathsf{d}+\mathsf{s}\le\mathsf{R}\), which is the true distance on both sides.
The middle, one formula for four shapes
The middle reads the thirteen code bits and flips the sign when
\[\Phi \;=\; \underbrace{\mathsf{fam}\,\mathsf{b}\,\mathsf{f}}_{\text{bar}} \;\oplus\; \underbrace{(\mathsf{f}\oplus\mathsf{fam})\,\mathsf{L}\,\mathsf{X}\,\mathsf{C}}_{\text{discs}} \;\oplus\; \underbrace{\mathsf{L}\,\mathsf{R}_3}_{\text{correction}} \;\oplus\; \underbrace{\mathsf{f}\,\mathsf{R}_3}_{\text{square}}\]is 1, where \(\mathsf{X}=\mathsf{d}_3\oplus\overline{\mathsf{R}_3}\) and \(\mathsf{C}=\mathbf{1}\left[(\mathsf{d}\bmod 8)+\mathsf{s}\le(\mathsf{R}\bmod 8)\right]\oplus\mathsf{R}_3\). Products are ANDs of bits, \(\oplus\) is addition mod 2 (XOR), \(\overline{\mathsf{R}_3}\) is the NOT of \(\mathsf{R}_3\), and \(\mathbf{1}[\cdot]\) is 1 when the condition inside holds and 0 otherwise.
Three of the four terms need no arithmetic. The bar is a column flag times two row flags, and the square is a row flag times the top radius bit. The correction term covers the five columns \(x=38,\dots,42\), where the big disc’s half-height is 8 and so needs the fourth radius bit. The disc term holds the one real comparison: on a disc column with radius below 8, the product \(\mathsf{L}\,\mathsf{X}\,\mathsf{C}\) is exactly \(\mathbf{1}[\mathsf{d}+\mathsf{s}\le\mathsf{R}]\). That comparison is why the middle contains a small adder-like circuit, a ripple-carry comparator
The remaining factor, \(\mathsf{f}\oplus\mathsf{fam}\), picks the right centre row. The big disc’s columns are also bar columns (\(\mathsf{fam}=1\)), and there the factor keeps the test to rows outside the square’s band of rows 29–53, which hold all of the big disc’s rows (11–27, measured from row 19). On the small disc’s columns (\(\mathsf{fam}=0\)) it keeps the test to rows inside the band, where the small disc’s rows (35–47) measure from row 41.
After the comparator, the middle ends in a phase block that flips the sign of the disc term. A product of four bits can be turned into a sign by 15 small rotations, one on the XOR of each nonempty subset of the four bits, and that is how the block does it. Its layers on the helper \(q_{16}\) set the final depth, as Why it stops at 95 shows.
The terms are joined by XOR rather than OR because a sign flip by an XOR of products splits into one sign flip per product, \((-1)^{a\oplus b}=(-1)^a(-1)^b\), so the middle can apply the terms one at a time. This is the standard way to turn an XOR of products into a phase oracle
Here are three pixels traced through the codes of my depth-138 circuit, whose column and row codes were found by two separate searches:
| pixel \((x,y)\) | \(\mathsf{R}\) | \(\mathsf{fam}\) | \(\mathsf{L}\) | \(\mathsf{d}\) | \(\mathsf{s}\) | \(\mathsf{f}\) | colour |
|---|---|---|---|---|---|---|---|
| (55, 44), small disc | 6 | 0 | 1 | 2 | 1 | 1 | \(\mathsf{d}+\mathsf{s}=3\le 6\): black |
| (55, 48), above it | 6 | 0 | 1 | 9 | 0 | 1 | \(\mathsf{d}+\mathsf{s}=9>6\): white |
| (10, 30), square | 13 | 0 | 0 | 11 | 0 | 1 | \(\mathsf{f}\,\mathsf{R}_3=1\): black |
At \(x=55\) the small disc reaches 6 rows from row 41, and \(\mathsf{R}=6\) says so. Row 44 is 3 above row 41: the code stores \(\mathsf{d}=2\), \(\mathsf{s}=1\), and \(2+1\le 6\). Row 48 is 7 above row 41. There the code stores \(\mathsf{d}=9\) and \(\mathsf{s}=0\), neither the distance nor the right side, but that is just as good: any \(\mathsf{d}+\mathsf{s}\) above 6 gives the right answer, white. In the square column \(x=10\) the radius is 13, but the middle only reads its top bit \(\mathsf{R}_3=1\), and \(\mathsf{f}\,\mathsf{R}_3\) marks the pixel black.
The codes themselves
Where a disc needs the number, the code is exact: the radius matches the disc’s true half-height in every disc column, and the distance matches the true distance in every row a disc covers. Elsewhere the code wanders. Under the square the radius ranges from 10 to 15 (any value from 8 to 15 would do), because only \(\mathsf{R}_3\) is read. Far from every disc the distance only has to be large enough. The search found these codes, and it used that slack to make them shorter.
Contracts and pairing
Writing down the freedom
The square columns showed that a code has choices: wherever the middle does not read a bit, any value works. I made this exact. For every column \(x\) I list the six-bit words (values of the six output bits, read together) that the column code may write there, and for every row \(y\) the words the row code may write. (The row code has one spare output bit that the middle never reads, so row words have eight bits.) A word is allowed if it still draws the right picture. Chip-design tools call such free outputs don’t-cares, and exact synthesis of reversible circuits exploits them in the same way
A column word is only right or wrong together with a row word, so the two lists depend on each other. I settle that by starting from one pair of codes known to be correct, those of my depth-138 circuit, and pruning until nothing changes:
start a column may write any word that is right against the pair's
row code, and a row any word right against its column code
repeat drop a column word if it draws a wrong pixel against SOME
allowed word of SOME row
drop a row word if it draws a wrong pixel against SOME
allowed word of SOME column
until nothing is dropped
What survives is the contract, and it still contains the starting pair. For the middle above it allows 323 column words, between 1 and 9 per column, and 2109 row words, between 4 and 60 per row. The column side splits into four groups:
| columns | allowed words | what is fixed |
|---|---|---|
| 0–1 and 62–63 (empty edges) | 8 | \(\mathsf{R}_3=\mathsf{fam}=\mathsf{L}=0\) |
| 2–26 (square) | 8 | \(\mathsf{R}_3=1\), \(\mathsf{fam}=\mathsf{L}=0\) |
| 27–31, 49 and 61 (bar only, disc edges) | 9 | only \(\mathsf{R}_3=0\) |
| 32–48 and 50–60 (discs) | 1 | all six bits |
The groups follow the picture: under the discs the radius must be exact, and under the square only \(\mathsf{R}_3\) matters. On the row side, rows that cross no shape may use up to 60 different words.
Why pairing is free
Because the pruning ran until nothing changed, every surviving column word is right against every surviving row word. So:
Pairing. Any column code that writes allowed words on all 64 columns works with any row code that writes allowed words on all 64 rows. With \(N\) column codes and \(M\) row codes, \(N+M\) independent searches give \(N\times M\) correct circuits.
This splits one hard joint search into two smaller ones that can run on different machines and never talk to each other. Checking a candidate code also becomes cheap. A column code is correct if it writes an allowed word on each of the 64 columns, which is 64 table lookups instead of 4096 pixels.
Here is one real pairing run: 6 annealed column codes against 4 annealed row codes, all 24 combinations built and compiled. Every pair draws the logo with no wrong pixel. Changing the column code moves the depth by up to 2 layers. Three of the four row codes give identical depths, and the fourth adds one layer everywhere. Because the column side is the longer side, a better row code buys nothing until the column code improves, which is the second pricing rule. From here on, I scored each side alone by compiling a half circuit: one code, the middle, and that code’s undo.
Searching the codes instead of the circuit
Up to 179 layers I designed the codes by hand, with ShinkaEvolve proposing rewrites. Every step below 179 used codes found by automatic search.
What is being searched
A column code is a small reversible circuit on ten qubits: the six \(x\) qubits and four helpers that start at 0. It is built from NOT gates with zero to three controls (x, cx, ccx and c3x, any control of which may be negated), plus a choice of which qubit holds each of the six outputs and whether it is stored inverted. The code is correct if, on every column, it writes a word the contract allows.
I search this space with simulated annealing colsa.c, is about 300 lines of C. Its moves change a control, flip a control’s polarity, change a target or a gate type, insert or delete a gate, swap two neighbouring gates, move a gate elsewhere in the list, move an output to another qubit, or flip whether an output is stored inverted. The idea is close to stochastic superoptimisation
Each candidate is checked on all 64 columns at once. In the annealer, each qubit is stored as one 64-bit integer whose bit \(x\) is that qubit’s value on column \(x\), so a gate costs one AND per control and one XOR, over all 64 columns together:
for (int k = 0; k < s->n; k++) { /* run the gate list */
const Gate *g = &s->g[k];
uint64_t m = ~0ULL; /* columns where all */
for (int j = 0; j < ncontrols(g->type); j++) /* controls hold ... */
m &= g->p[j] ? ~v[g->c[j]] : v[g->c[j]];
v[g->t] ^= m; /* ... flip their target */
}
/* then read the six output wires and count columns whose word is not allowed */
A depth estimate in nanoseconds
Compiling a candidate into u3 and cx gates and scheduling it takes seconds. My compile chain runs a tket cx, 7 per ccx and 13 per c3x, since a multi-controlled gate becomes a gadget, a block of several layers of u3 and cx gates, once compiled
The walk minimises the energy
\[\text{energy} \;=\; 20\cdot\text{wrong} \;+\; 3\cdot\max(0,\ \mathrm{est}-\text{cap}) \;+\; 0.01\cdot\mathrm{est} \;+\; 0.001\cdot\text{gates},\]where “wrong” counts columns whose word breaks the contract. Each time the walk finds a correct code with \(\mathrm{est}\le\text{cap}\), it prints the code and lowers the cap to \(\mathrm{est}-1\), so it keeps pushing for a shallower code. Simplified from colsa.c, the main loop is:
double T = T0 * pow(T1 / T0, (double)it / iters); /* cool down slowly */
State t = s; mutate(&t); /* propose a change */
double e2 = energy(&t, cap, &w2, &est2);
if (e2 <= e || runif() < exp((e - e2) / T)) { /* Metropolis rule */
s = t; e = e2;
if (w2 == 0 && est2 <= cap) { print_state(&s, est2, it); cap = est2 - 1; }
}
One core checks between two and three million candidates per second this way.
What the search found
The first large run used 24 chains, independent annealing walks, of 300 million steps each: 12 from random gate lists and 12 seeded with my best hand-made column code. Nine of the twelve random chains never reached a correct code, and the three that did got there late. But those three found codes with estimates of 69, 72 and 76. The seeded chains all repaired the hand-made code (which, against this run’s contract, was wrong on 5 columns) and then stalled between 78 and 96, close to the code they started from.
The code with estimate 72 became a circuit of depth 147, thirty-two layers below the hand-made 179 in one step. Annealing the row side the same way and pairing gave 138. From there, rounds of anneal, compile, keep the best on each side, a SAT-scheduled phase block, and the refined estimate brought the circuit to 107.
Is the estimate a good stand-in for depth?
The annealer never sees the real depth, so the method works only if a lower \(\mathrm{est}\) means a shallower circuit. There are three reasons to expect it.
- The codes are most of the circuit. In the 106-layer circuit, removing the middle’s phase block left 93 layers. In the 95-layer circuit, everything except that block fits in 86 layers.
- The prices roughly follow the compiler. A multi-controlled gate costs several layers once compiled, and the estimate charges it that way.
- Codes are paid twice. By the first pricing rule, a layer saved in the longer code saves two layers of the circuit, so the estimate measures the part of the circuit that counts double.
The plot below tests it. On the left, codes from my archive of 296,770 column codes are grouped by estimate and compiled. Lower estimate means shallower circuits: the median compiled half circuit climbs from 111 to 131 layers as the estimate goes from 57 to 64. Over 13,830 compiled half circuits, the refined estimate ranks codes in nearly the right order: its rank correlation with compiled depth, which would be 1 for a perfect ordering and 0 for a random one, is 0.89 (its prices were fitted on those same circuits), against 0.87 for plain as-soon-as-possible depth.
The right panel, from a benchmark taken earlier in the search, shows the limit: sixty codes with estimates of 59 or 60 compiled to anything from 127 to 148 layers. Near the best codes the estimate does worse still. The best codes all share an estimate of 57, so it cannot order them at all, and even timing prices refitted on those codes rank unseen ones at only 0.27. In the first run, the code with estimate 69 became a circuit of 167 layers, while the code with estimate 72 gave the 147. The spread comes from the last step of compilation, the scheduler that reorders gates that commute. Depth after the earlier compile steps ranks the final depth at only 0.35 to 0.36, and no cheap formula I tried predicted the scheduler.
So the search ran as a funnel. The annealer explores with the estimate, every correct code it prints is compiled, and only compiled depth decides what is kept and what seeds the next round. STOKE, the superoptimiser mentioned above, works the same way: it searches with cheap test cases and keeps only programs that a formal check validates
Polishing, from 107 to 95
At 107 layers the code search stopped improving: every search I ran came back with the same best column code. The last twelve layers came from tools that change the circuit without changing what it computes. Most of them either reorder gates that commute
| depth / cx | what bought it |
|---|---|
| 107 / 279 | one gate that reads both sides (the Toffoli from \(q_0\) and the negated \(q_{11}\) onto \(q_3\)): six fewer CNOTs, same depth |
| 106 / 279 | the phase block has 238 equivalent schedules; one of them saves a layer |
| 98 / 269 | a cheaper three-control gadget, the full tket pass, and an exact CP-SAT |
| 97 / 267 | how each multi-control gadget is compiled, chosen for pairs of neighbouring gadgets at once |
| 96 / 273 | one-qubit gates moved out of runs of gates they commute with |
| 95 / 279 | the phase block rebuilt by a SAT solver |
| 95 / 272 | three more small regions rebuilt with fewer CNOTs; the last, the phase block merged with the sign gates, now has 19, the fewest that region can have |
The ladder below puts these steps at the end of the whole history. The largest single drops came from changing what I searched over: one sandwich instead of three, then codes instead of circuits. No polishing step gained more than eight layers.
Why it stops at 95
As the occupancy plot showed, the helper \(q_{16}\) is busy in every one of the nine middle layers. Every longest chain of gates in the circuit runs through the phase block on \(q_{16}\). If that block takes \(K\) layers on \(q_{16}\), the whole circuit needs exactly \(86+K\) layers, for every \(K\) from 0 to 9. And the block cannot take fewer than 9 layers on \(q_{16}\): the solver proves 8 impossible even when the block’s other qubits get all the time they want. So \(86+9=95\). On this circuit, then, 94 needs either a phase block that spends fewer layers on \(q_{16}\), which the solver rules out for this block on its own qubits, or new codes that let the rest fit in fewer than 86 layers. A screen of all 1,738 circuits I had stored, with the same test, found 534 that fit 95 and none that fit 94.
What did not work
Besides polishing, I spent a long time trying to make the codes themselves shorter than those of the 106-layer circuit. Twelve routes failed, three for each of four reasons. Some ran out of helper qubits: a clean spare qubit would have helped, and with six helpers neither side could give one up. Some made one side cheaper only by making the other side’s contract tighter, and the column side, which sets the depth, always paid. Some searches spent their whole budget and returned nothing. And some rested on a number measured in one setting and reused in another. For example, the phase block’s 238 equivalent schedules had been ranked once, against an older 113-layer circuit; ranking them again inside the 107-layer circuit was the free layer in the polishing table.
The closed routes, sorted by why they failed
What carried the result
Five things carried the result:
- Pick a shape that packs. One sandwich with the two codes on disjoint qubits costs the longer code, where per-shape sandwiches cost the sum of all of them.
- Describe the picture with small codes. A radius per column and a distance per row turn four shapes into one comparison and a few products of flags.
- Write down the freedom. The contract lists every word each column and each row may use. It makes the two codes independent, so pairing costs nothing, and it makes checking a candidate a table lookup.
- Search with a cheap compass, decide with the real compiler. The estimate steered billions of annealing steps; only compiled depth decided what I kept.
- Polish last. Exact rescheduling and SAT re-synthesis of small blocks took the final twelve layers without searching the codes again.
Reproduce it
Everything needed to check the result and rerun the plots is here:
- logo-oracle-95-272.qasm: the final circuit, OpenQASM 2
with u3andcxgates on 18 qubits (depth 95, 272cx). - The write-up (PDF, 19 pages): the same method in more detail, with the worked numbers.
- The companion bundle (zip): a Jupyter notebook, its one helper script, and every circuit, code, contract and search log it reads, including the annealer's C source.
To run the notebook, unzip the bundle, install numpy, matplotlib and jupyter (Python 3.9 or newer), and run all cells from inside the folder. It needs no Classiq account and no network, and it takes under a minute. A C compiler is optional: with one, the notebook compiles the annealer and runs a 20-million-step search live; without one, it plots a stored run of the same search.
Besides my own annealer, the work relied on open tools. Code circuits were compiled with tket
Thanks to the Classiq team for a well-posed challenge with an exact scoring rule, and for encouraging participants to publish their solutions.