[Feature Request] Come up with an instruction set for lattice surgery that is layout independant

[gwwatkin]

Issue Description

Talking with @alexandrupaler, it came up that it is very desirable to have a language to express lattice surgery instruction before layout and routing.

Proposed Solution

The following instructions, new line separated. Note that each instruction (except for the qubit declaration) also have a numeric opcode to reduce file size)

DeclareLogicalQubitPatches <patch_id>,<patch_id>,... // must be the first instruction
(Init|0) <patch_id> ("|0>" | "|+>" | + | 0)
(RequestMagicState|1) <patch_id>
(MultiBodyMeasure|2) <patch_id>:(X|Z),<patch_id>:("X"|"Z"),...
(MeasureSinglePatch|3) <patch_id> (X|Z)
(LogicalPauli|4) <patch_id> (X|Z)
(SGate|5) <patch_id>
(HGate|6) <patch_id>
(RequestYState|7) <patch_id>

Where<patch_id> is a 32 bit unsigned integer.

Reference implementation

• Writing in the __repr__ methods of LS-Instructions and the short-hand version .
• Parsing in liblsqecc#4

Corrective terms/ Conditional Extension

A problem for which we are still discussing a solution for are corrective terms. LS-Instructions need corrective terms when the measurement reads the negative eigenvalue. E.g. from Litinski for pi/8, but the same applies to all teleported gates via multibody measurement:

• Ideally, these corrective terms would just be tracked by updating the Pauli frame. In this case all we have to assume is that an implementation reading from this protocol will automatically know how to update the Pauli frame based on measurement outcomes. However, this is not trivial because, as shown above, the sequence of corrections is not immediate and is making assumptions about what the operation from which the multibody measurements come from is. (a pi/8 rotation in the example)
• Practically, Pauli frame tracking is not direct. It is not immediate how software only reading the above instruction set would know when corrective terms need to be applied.

I propose tracking measurement outcomes in classical variables and using them in combination with a conditional construct (as it is already implemented in LogicalLatticeOps). Then, a scheduler implementation that reads the protocol can optimize out these corrections by updating the Pauli frame, along with other stabilizer operations.

A possible implementation of an extension could look something like:

MultiBodyMeasure patch1:X,patch2:Z,patch15:X  correctionFlag1
IfSet correctionFlag1 Pauli X patch1
IfSet correctionFlag1 Pauli Z patch2

This would work especially well if we extend the instruction set to include specific instructions to interact with the Pauli frame tracker.

S Gates

Instead of having only having Y state distillation, as we did before, now we have an SGate, to perform directly single qubit rotations by pi/4:

SGate <patch_id>

This would also solve |Y> state initialization, as we would do:

Init 1 |+>
SGate 1

The S gate operation could be seen as routing the the X boundary with the Z boundary (as a regular multi body measurement) or an operation with a twist defect, or a 2x2x2 box with the patch in a corner.

Also note that Y state initialization right now is broken in the Python Slicer. #73

Additional References

Litnski's Game of Surface Codes from which we got the picture on corrective terms.
Alexandru et al.'s paper on tracking the Pauli Frame for QEC.
Horsman et. al on Lattice surgery for transversal Hadamards

[gwwatkin]

@alexandrupaler I think the specification for the opcodes (0 to 7) is ready to be added to the official docs. We can close this issue and move the solution of the corrective term problem to a different issue I think

@alexnguyenn I would add the spec to the markup docs