Gadgets › Logical Algorithm
Logical Algorithm
A logical algorithm is a program over blocks. Each instruction names the kind of place it needs; the scheduler takes the blocks there along the roads of a floorplan -- the town below, unless the program names its own -- runs the place's verified op, and rests any block the next instruction does not need, in a logical zone or in a memory that corrects it while it waits. Instructions run as early as their blocks and places allow, so a factory produces while a lattice surgery runs elsewhere. Every schedule is judged by the machine's rules, and then signed off: flattened to one circuit over every ion, simulated once symbolically, and compared with the algorithm's ideal circuit; or, for a program too large to flatten (Shor's algorithm), in parts -- every place op verified, every gate it calls proved to be its contract in every branch, every machine rule holding, and the program's outcomes computed with each call as its contract.
The algorithms
Bell pair by transversal CNOT signed off
|+0> -> CNOT -> |00>+|11>: the two Z readouts always agree
prep q0 X prep q1 Z cx q0 q1 se q0 1 se q1 1 decode q0 q1 # the rounds so far: each place sends its syndrome down its wire read q0 Z -> a read q1 Z -> b decode # and the readouts' own: now a and b are results
- ✓ a=Z̄[q0] ⊕ b=Z̄[q1] = 0
- ✓ no one or two of 1,798 fault locations flip a result unseen
Bell pair by lattice surgery signed off
|++> -> measure Z̄Z̄ -> a Bell pair up to the outcome m: a xor b = m
prep q0 X prep q1 X zz q0 q1 -> m decode q0 q1 # m is a result once the surgery's syndrome is decoded read q0 Z -> a read q1 Z -> b decode
- ✓ m=Z̄Z̄[q0,q1] ⊕ a=Z̄[q0] ⊕ b=Z̄[q1] = 0
- ✓ no one or two of 4,058 fault locations flip a result unseen
A transversal CNOT that fires only when the bit says so signed off
Classically controlled hardware, in its plainest form: "these ions do this in that gadget only if the condition is triggered". A logical block is prepared in |+-bar> and read out in Z: one honestly random bit. The transversal-CNOT workshop is then told whether to fire. The ions travel to the workshop either way and the place reserves the same slot either way -- the worst case, so the schedule stays static -- and only the pulses depend on the bit. What the two branches promise is different, and both are checked: with no CNOT, q0 is still |+-bar> so u = 0 and v is random; with the CNOT, the blocks are in a Bell state, so u and v are each random but u + v = 0. A sign-off that ignored the guard could not get both right.
prep q0 X prep q1 Z prep a X read a Z -> m decode a # the guard below reads m: it must be decoded first if m: cx q0 q1 read q0 X -> u read q1 X -> v decode
- ✓ [m=0] u=X̄[q0] = 0
- ✓ [m=1] u=X̄[q0] ⊕ v=X̄[q1] = 0
- ✓ no one or two of 1,362 fault locations flip a result unseen
Logical Paulis kept in the classical memory signed off
Corrections this machine keeps in software. A logical Pauli is a line in the classical memory, not an operation on ions: the archive holds it and flips every later outcome it anticommutes with. Both readouts must come out -1.
prep q0 Z x q0 se q0 1 read q0 Z -> m decode q0 prep q1 X z q1 read q1 X -> n decode q1
- ✓ m=Z̄[q0] = 1
- ✓ n=X̄[q1] = 1
- ✓ no one or two of 1,290 fault locations flip a result unseen
GHZ state on three blocks signed off
|+00> -> CNOT q0->q1, CNOT q0->q2: all three Z readouts agree
prep q0 X prep q1 Z prep q2 Z cx q0 q1 cx q0 q2 se q0 1 decode q0 q1 q2 read q0 Z -> a read q1 Z -> b read q2 Z -> c decode
- ✓ a=Z̄[q0] ⊕ b=Z̄[q1] = 0
- ✓ a=Z̄[q0] ⊕ c=Z̄[q2] = 0
- ✓ no one or two of 1,951 fault locations flip a result unseen
A logical magic state signed off
15-to-1 distillation, injection into a d = 3 block, three syndrome rounds, and a night in a logical zone
inject t se t 3 decode t store t
- ✓ X̄[t] → X̄[t]
- ✓ Z̄[t] → Z̄[t]
- distance: the algorithm injects a state (inject), and injection is not fault-tolerant by design (distance 1)
Teleporting a magic state signed off
the factory distills a T state, the pharmacy encodes it into block t, and the surgery Bell pair carries it to block b: any input state arrives, up to the frame
inject t prep a X prep b X zz a b -> m1 xx t a -> m2 read t Z -> m3 read a Z -> m4 decode # every outcome so far becomes a result se b 3 decode b
- ✓ X̄[t] → X̄[b] ⊕ m2=X̄X̄[t,a]
- ✓ Z̄[t] → Z̄[b] ⊕ m1=Z̄Z̄[a,b] ⊕ m3=Z̄[t] ⊕ m4=Z̄[a]
- distance: the algorithm injects a state (inject), and injection is not fault-tolerant by design (distance 1)
Two logical S gates make a Z signed off
Two logical S gates make a Z, and Z on |+> is |->: reading X must give -1 every time. Each S is the S-bar gadget: a |Y-bar> block is prepared at the pharmacy (an injection), measured against the data block by Z-bar Z-bar lattice surgery, and read out in X; the correction is Z-bar when the two outcomes disagree, and it is kept in the archive as a Pauli frame -- no ion is ever touched by it.
prep q0 X s q0 se q0 1 s q0 decode q0 # both S gadgets' rounds, their |Y> blocks' included read q0 X -> m decode q0
- ✓ m=X̄[q0] = 1
- distance: the algorithm injects a state (inject.Y), and injection is not fault-tolerant by design (distance 1)
Shor's algorithm: the order of 7 modulo 15 signed off
Shor's algorithm, fault-tolerant: the order of 7 modulo 15. Order finding for a = 7, N = 15 by iterative phase estimation (Kitaev): one control block per bit of the phase, each prepared, used, corrected and read before the next -- the form Monz et al. ran on trapped ions (Science 351:1068, 2016). U multiplies the work register by 7 modulo 15; its eigenphases are s/4, so three bits m3 m2 m1 of the phase 0.m3m2m1 hold s exactly: m1 = 0 always, and m3 m2 is s, uniformly 0, 1, 2 or 3. An odd s gives the order r = 4, and gcd(7^2 - 1, 15) = 3, gcd(7^2 + 1, 15) = 5. Every logical qubit is a d = 3 surface-code block; every gate is a verified place or one of the standard gates (include "standard"), proved to be its contract in every branch. The controlled multiplications are compiled for the values the register can hold when they act (1 before iteration 2; 1 or 4 before iteration 3), as every experimental Shor has been; the two controlled swaps of iteration 3 are two Toffolis, fourteen T gates from the factories. The inverse quantum Fourier transform is semiclassical: each control is rotated back by the phase the earlier bits fix (S̄† when m1 or m2 says so, T̄† when m1 does) before it is read in X. the work register holds 1 = |0001⟩, b0 its least significant bit iteration 1: U^4 = 1 (7^4 = 2401 = 1 mod 15), so the control picks up no phase iteration 2: U^2 multiplies by 4 (7^2 = 49 = 4 mod 15); on the register's 1 that is 1 -> 4 iteration 3: U multiplies by 7, on 1 and 4 (where iteration 2 left the register): 1 -> 7, 4 -> 13. Rotate the four bits right by one -- on these two values two controlled swaps do it -- then flip all four.
include "standard" floorplan "shor" prep b0 Z x b0 prep b1 Z prep b2 Z prep b3 Z prep c1 X read c1 X -> m1 decode c1 prep c2 X cx c2 b0 cx c2 b2 if m1: sdg c2 read c2 X -> m2 decode c2 prep c3 X cswap c3 b0 b3 cswap c3 b1 b2 cx c3 b0 cx c3 b1 cx c3 b2 cx c3 b3 if m2: sdg c3 if m1: tdg c3 read c3 X -> m3 decode
- 189 instructions, 15 magic states: signed off in parts, as a program this size must be
- ✓ every gate it calls is its contract in every branch: sdg, h, t, tdg, ccx, cswap
- ✓ the floorplan and the schedule obey every machine rule (25)
- ✓ with every call as its contract, the outcomes: m1=0 m2=0 m3=0 with probability 0.25; m1=0 m2=0 m3=1 with probability 0.25; m1=0 m2=1 m3=0 with probability 0.25; m1=0 m2=1 m3=1 with probability 0.25
A logical T by teleportation, with the S correction only when needed signed off
A logical T by gate teleportation -- the reason classically controlled hardware exists. A distilled magic state is measured against the data block by Z-bar Z-bar surgery and then read out. The outcomes decide the correction: the X readout asks for a Z-bar, which is a Pauli and can be kept in the archive as a frame, but the surgery outcome asks for an S-bar, which is NOT a Pauli -- no frame can hold it, so the S-bar gadget itself must run, and only when the bit says so. That is a dynamic circuit: the hardware does something different depending on a measurement taken while it runs. Every one of the four outcome branches is signed off separately, and each must implement the same channel from the magic block's state to q0. The factory makes T-dagger|+> (msf15's own state-vector check), and gate teleportation with this correction table needs T|+>: X-bar on the magic block turns one into the other (X T-dagger|+> is T|+> up to a phase), and costs nothing -- it is a line in the archive. Without it every branch was T-dagger or S T, never T: the flat sign-off cannot see that, because it treats the injected state as a free input; checking the gate's contract does, and the standard gates' `t` is this program.
prep q0 X inject t x t # the factory's T-dagger|+> becomes T|+>, in software zz q0 t -> m read t X -> k decode # both corrections read an outcome: decode them first if m: s q0 # the Clifford correction: the S-bar gadget runs only when m = 1 if k: z q0 # the Pauli correction: a line in the archive, no ions touched decode q0 # the S-bar gadget's own rounds
- ✓ [m=0, k=0] X̄[t] → X̄[q0]
- ✓ [m=0, k=0] Z̄[t] → Z̄[q0]
- ✓ [m=1, k=0] X̄[t] → Ȳ[q0]
- ✓ [m=1, k=0] Z̄[t] → Z̄[q0]
- ✓ [m=0, k=1] X̄[t] → X̄[q0]
- ✓ [m=0, k=1] Z̄[t] → Z̄[q0]
- ✓ [m=1, k=1] X̄[t] → Ȳ[q0]
- ✓ [m=1, k=1] Z̄[t] → Z̄[q0]
- distance: the algorithm injects a state (inject, inject.Y), and injection is not fault-tolerant by design (distance 1)
Teleportation by lattice surgery signed off
t in |+>; a Bell pair (a, b) by Z̄Z̄ surgery; X̄X̄ surgery on (t, a) and two Z readouts complete a Bell measurement: b holds the state of t, up to the recorded frame
prep t X prep a X prep b X zz a b -> m1 xx t a -> m2 read t Z -> m3 read a Z -> m4 decode # every outcome so far becomes a result se b 1 decode b
- ✓ 1 → X̄[b] ⊕ m2=X̄X̄[t,a]
- ✓ no one or two of 8,116 fault locations flip a result unseen
Teleportation whose correction is applied, not just recorded signed off
Teleportation that hands back a known state, not a state plus a note. `teleport.alg` moves |+-bar> from t to b and the sign-off reports what b holds up to a recorded outcome: "1 -> X-bar[b] + m2". That note has to be carried by everything downstream. Here the machine applies the correction instead: the archive holds a Z-bar on b exactly when the X-bar X-bar surgery said so, and the final readout of b is then deterministic in every branch -- r = 0, whatever the Bell measurement happened to give. That is what classically controlled execution buys: the state is where it should be, and no bookkeeping travels with it.
prep t X prep a X prep b X zz a b -> m1 xx t a -> m2 read t Z -> m3 read a Z -> m4 decode # the correction below reads m2 if m2: z b read b X -> r decode b
- ✓ [m2=0] r=X̄[b] = 0
- ✓ [m2=1] r=X̄[b] = 0
- ✓ no one or two of 7,752 fault locations flip a result unseen
Write one
One instruction per line; # starts a comment; any instruction may end in @ name to pin it to one instance of the design.
| instruction | meaning | place |
|---|---|---|
prep q Z · prep q X | a fresh block in |0̄⟩ or |+̄⟩ | Logical Preparation |
se q 1 · se q 3 | rounds of syndrome extraction | Syndrome Extraction |
cx c t | transversal CNOT, c controls | Logical Operation |
zz a b -> m · xx a b -> m | measure Z̄Z̄ or X̄X̄ by lattice surgery | Lattice Surgery |
read q Z -> m | destructive readout in Z or X | Logical Readout |
inject t | a block holding the factory's magic state | Magic State Factory, then Injection |
s q · sx q | S̄ or √X̄, by consuming a |Ȳ⟩ block in a lattice surgery | Injection, Lattice Surgery, Readout |
x q · y q · z q | a logical Pauli, kept in the classical memory: no ion moves | Classical Memory |
store q | rest the block | Logical Zone or Logical Memory |
decode q · decode | call the decoder: the syndromes the block left (or every one waiting) go down their wires to it, and the frame it decides to the classical memory. An outcome is a result only once decoded, and a program must decode everything it measured | Decoder |
Any instruction may be guarded, if m: s q, to run only when a measured outcome says so (m ^ k and m & k combine outcomes). A program may define gates from these instructions and call them like instructions:
gate t q implements T: inject m x m zz q m -> a read m X -> b decode q m if a: s q if b: z q
include "standard" brings the standard ones -- sdg, h, t, tdg, cz, ccx, cswap -- each proved to be the gate it says it implements, and floorplan "shor" names the machine a program runs on. In the design page, Edit composes places into a new design and Export floorplan writes it as a floorplan of your own.