Cycle-Decomposition Synthesis
You are handed a target: some permutation of the 2^n bit patterns, perhaps
as a truth table. Build a circuit for it. Where do you even start? Here is the first honest synthesis
algorithm of the course, and it is pure
permutation
group theory turned into wiring instructions. The plan has three stages, each one a
classic divide-and-conquer:
- Cycles. Write the target as disjoint cycles — they touch disjoint sets of
states, so each can be built separately and the blocks concatenated in any order.
- Transpositions. Break each cycle into simple swaps of two patterns.
- Gates. Realise each swap as a short, mechanical gate sandwich.
By the end of this page you will have synthesised a 3-bit permutation end-to-end, gate by gate — and
run the result in code to check it.
Stage 1 → 2: cycles into transpositions
A k-cycle (p_1\;p_2\;\cdots\;p_k) — meaning
p_1 \to p_2 \to \cdots \to p_k \to p_1 — factors into
k-1 transpositions. In circuit order (first block on the left):
(p_1\;p_2\;\cdots\;p_k) \;=\; \underbrace{(p_1\;p_2)}_{\text{first}},\; (p_1\;p_3),\; \ldots,\; \underbrace{(p_1\;p_k)}_{\text{last}}.
Sanity-check the 3-cycle (x\;y\;z) as the cascade
"(x\;y) then (x\;z)": the state
x becomes y in the first block and the second
block leaves y alone — net x \to y. Meanwhile
y \to x \to z and z \to z \to x. Exactly the
cycle. So a permutation whose disjoint cycles have lengths
k_1, k_2, \ldots needs
(k_1 - 1) + (k_2 - 1) + \cdots transpositions in total. All that remains
is one question: how do you build a single swap of two bit patterns?
Stage 3: one transposition as a gate sandwich
Suppose the two patterns u and v differ in
exactly one bit position. Then the swap (u\;v) is a
controlled flip of that bit: flip it precisely when all the other wires match the
shared bits of u and v. A multi-controlled NOT
does this — but its controls fire on 1s, and the shared pattern may contain 0s. The fix is a
sandwich:
- map: put a NOT on every wire where the shared pattern has a
0 — this relabels states so the pair
u, v lands on the all-ones control pattern;
- flip: apply the multi-controlled NOT (controls on every other wire, target on
the differing bit);
- unmap: repeat the same NOTs to undo the relabelling.
Concretely, take (010\;\;011) on wires a,b,c:
the patterns differ in bit c, and share a=0,
b=1. So: NOT on a, Toffoli with controls
a, b and target c, NOT on
a again. Step through it:
This is the compute–do–uncompute shape yet again — the NOTs are a temporary change of coordinates,
exactly in the spirit of
Bennett's
trick: conjugating the flip by the NOTs re-aims it at the pair you actually wanted.
What if the patterns differ in several bits?
If u and v differ in
d > 1 positions, no single controlled flip will do — but a
path will. Choose intermediate patterns
u = p_0, p_1, \ldots, p_d = v, each differing from the next in one bit
(fix one differing bit at a time). Then walk, swap, and walk back:
(u\;v) \;=\; (p_0\;p_1)\cdots(p_{d-2}\;p_{d-1}) \;\cdot\; (p_{d-1}\;p_d) \;\cdot\; (p_{d-2}\;p_{d-1})\cdots(p_0\;p_1)
— carry u next door to v, do the one swap that
matters in the middle, then retrace your steps. That is 2d - 1
distance-one swaps, each a sandwich from the previous card. Wasteful? Somewhat — and that is exactly
why better algorithms exist (next lesson). But it terminates, it is fully mechanical, and it proves
constructively that every permutation has an NCT circuit.
Worked example, end to end
Target: the 3-cycle (010\;\;011\;\;111) — send
010 \to 011 \to 111 \to 010, fix the other five states.
Transpositions (circuit order): (010\;\;011) then
(010\;\;111).
Gates. The first swap is the sandwich above. The second has
d = 2 (bits a and c
differ), so take the path 010 \to 110 \to 111 and sandwich along it —
(010\;\,110), (110\;\,111),
(010\;\,110). Each unit swap gets its own gate sandwich:
| Block | Swap | Gates |
|---|
| 1 | (010\;\,011) | NOT a · Toffoli(a,b \to c) · NOT a |
| 2 | (010\;\,110) | NOT c · Toffoli(b,c \to a) · NOT c |
| 3 | (110\;\,111) | Toffoli(a,b \to c) — the shared bits are already 1s, no sandwich needed |
| 4 | (010\;\,110) | NOT c · Toffoli(b,c \to a) · NOT c |
Total: 10 gates. Let us verify one row by hand — the state
111, which should end at 010. Block 1: the NOT
on a gives 011, the Toffoli sees
a=0 and idles, the NOT restores 111. Block 2:
111 \to 110 \to 110 \to 111 (the Toffoli's control
c is 0 mid-sandwich) — untouched. Block 3: controls
a=b=1 fire: 111 \to 110. Block 4:
110 \to 111, Toffoli fires (b=c=1) giving
011, NOT c gives
010. Correct!
Check the whole permutation in code
Hand-tracing one row is instructive; hand-tracing eight is penance. Let a simulator earn its keep —
this applies the 10-gate list to all 8 states and prints the permutation table:
interface Gate { controls: number[]; target: number; }
// Wires 0,1,2 hold bits a,b,c; states print as "abc".
// The 10-gate circuit for the 3-cycle (010 011 111):
const circuit: Gate[] = [
{ controls: [], target: 0 }, // block 1: NOT a
{ controls: [0, 1], target: 2 }, // TOF(a,b -> c)
{ controls: [], target: 0 }, // NOT a
{ controls: [], target: 2 }, // block 2: NOT c
{ controls: [1, 2], target: 0 }, // TOF(b,c -> a)
{ controls: [], target: 2 }, // NOT c
{ controls: [0, 1], target: 2 }, // block 3: TOF(a,b -> c)
{ controls: [], target: 2 }, // block 4: NOT c
{ controls: [1, 2], target: 0 }, // TOF(b,c -> a)
{ controls: [], target: 2 }, // NOT c
];
function applyGate(state: number[], g: Gate): void {
let fire = 1;
for (const c of g.controls) fire *= state[c];
if (fire === 1) state[g.target] = 1 - state[g.target];
}
for (let x = 0; x < 8; x++) {
const s = [(x >> 2) & 1, (x >> 1) & 1, x & 1];
const input = s.join("");
for (const g of circuit) applyGate(s, g);
console.log(input + " -> " + s.join(""));
}
The printout shows five fixed rows and the cycle
010 \to 011 \to 111 \to 010. Change the gate list and re-run — the
simulator is a synthesis playground.
Count the damage in the worst case. A permutation of the 8 states can need up to 7 transpositions;
each transposition of patterns at distance d costs
2d - 1 unit swaps, and each unit swap costs a multi-controlled NOT plus up
to 2(n-1) NOTs of sandwich bread. The gate counts balloon — our modest
3-cycle already took 10 gates, and a general 3-bit permutation can run to dozens, where clever
methods manage with a handful. Cycle decomposition is the existence proof of synthesis: it
shows the NCT library reaches everything reachable, with completely mechanical steps. The following
lessons are about reaching the same targets without paying triple.
Two classic slips, both fatal. Forgetting the unmap: the closing NOTs are not
decoration — leave them off and every state stays relabelled, so you have built a completely
different permutation (the flip composed with stray NOTs). A sandwich is a conjugation
g\,h\,g^{-1}: it needs both slices.
Scrambling the order: transpositions do not commute —
"(010\;011) then (010\;111)" is our 3-cycle,
but "(010\;111) then (010\;011)" is the
other 3-cycle, (010\;111\;011). When a synthesis goes wrong,
check the block order first.