Logical-operator representatives and the logical decision tasks of the three decoding scenarios
DefinitionQECDecodingHardness_AllThree_Supplement_logical_operatorsA Pauli operator modulo phase on a finite qubit set is a map , , where , , stand for , , (the same per-qubit encoding as the base mission's errors). Two Paulis anticommute exactly when their symplectic product
equals . A stabilizer code is given by a finite list of generators; the stabilizer group modulo phase is the -span of the generators. A representative of a logical operator is a Pauli with for every generator and not in that span. Any Pauli type and any support shape is allowed.
The three codes are built from the base mission's published coordinates:
- Color code of order (distance ): qubits are the triangles of
colorQubits k; each check vertex ofcolorChecks kcarries an generator and a generator, both supported on the triangles incident to . - Surface code on the patch: qubits are the edges of
surfaceQubits L; an generator at every vertex ofsurfaceXChecks Lon its incident edges and a generator at every face on its boundary edges. - Two-patch code of the transversal CNOT setting: two copies (patch 1 = control, patch 2 = target) of the surface code, with every generator of each patch acting as the identity on the other.
The logical effect of an error is the error itself in the two code-capacity settings. In tCNOTZ, it is the end-of-circuit Pauli frame: each data fault on patch 1 contributes on its edge of patch 1; a data fault on patch 2 at time (before the gate) is conjugated by the CNOT () into on its edge of both patches; a data fault at (after the gate) stays on patch 2; measurement bit-flips contribute nothing; contributions are summed in .
A query of the logical decision problem in a scenario consists of a base decoding instance (size parameter and full syndrome ) together with a logical representative of that instance's code. Its predicate is
which is false when is infeasible. The encoded task's input is the base nonsuccinct encoding of the instance followed by the bits of ; its only accepted answer is the one-bit word if the predicate holds and otherwise. This gives the three tasks colorLogicalTask, surfaceLogicalTask and cnotLogicalTask whose NP-hardness is Theorem 7.
Formalization Note The base colorCodeZ lists only the checks (only errors occur); the checks needed to define logical operators are added here from the same vertex list. Square-lattice families use as in the base familySystem, so every positive lattice size is a query. The tCNOTZ timing follows the base model: , data faults at occur after the gate, data layers .
import Definitions.Def_QECDecodingHardness_AllThree_search_hardness
namespace QECDecodingHardness.AllThree.Supplement
/-- A Pauli operator modulo phase on the finite qubit set `Q`, one binary pair
`(x, z)` per qubit exactly as in the base `LocalFault`: `(1,0)` is X, `(0,1)` is Z,
`(1,1)` is Y. Composition modulo phase is addition. -/
abbrev Pauli (Q : Type) := Q → LocalFault
/-- Binary symplectic product: `1` iff the two Paulis anticommute. A Y on a qubit
anticommutes with an X or a Z on that qubit. -/
def symplectic {Q : Type} [Fintype Q] (P R : Pauli Q) : Bit :=
∑ q, ((P q).1 * (R q).2 + (P q).2 * (R q).1)
/-- A stabilizer code on the qubit set `Q`, given by a finite list of generators
(Paulis modulo phase). -/
structure StabilizerCode (Q : Type) where
generators : List (Pauli Q)
/-- Membership in the stabilizer group modulo phase: the binary vector lies in the
`F₂`-span of the generators. -/
def InStabilizerGroup {Q : Type} (C : StabilizerCode Q) (P : Pauli Q) : Prop :=
P ∈ Submodule.span (ZMod 2) {g : Pauli Q | g ∈ C.generators}
/-- A representative of a (nontrivial) logical operator: commutes with every
stabilizer generator and is not itself a stabilizer modulo phase. Any Pauli type
and any support shape is allowed. -/
def IsLogicalRep {Q : Type} [Fintype Q] (C : StabilizerCode Q) (P : Pauli Q) : Prop :=
(∀ g ∈ C.generators, symplectic g P = 0) ∧ ¬ InStabilizerGroup C P
/-- Section II.1, p.3: the triangular color code of order `k` (distance `2k+1`).
Qubits are the base `colorQubits k` (the columns of `colorCodeZ k`); every check
vertex of `colorChecks k` carries both an X and a Z generator, supported on the
incident triangles. `colorCodeZ` lists only the X checks; the Z checks are added here
from the same coordinates. -/
def colorStabilizerCode (k : ℕ) : StabilizerCode (Fin (colorCodeZ k).locations) where
generators :=
(colorChecks k).flatMap (fun v =>
[fun q => (if v ∈ triangleVertices ((colorQubits k).get q) then 1 else 0, 0),
fun q => (0, if v ∈ triangleVertices ((colorQubits k).get q) then 1 else 0)])
/-- Section II.2, p.4: the `L×L` surface code on the base `surfaceQubits L` (the
qubit locations of `surfaceCodeXYZ L`). X generators at the vertices
`surfaceXChecks L` on the incident edges; Z generators at the faces
`surfaceZChecks L` on their boundary edges. -/
def surfaceStabilizerCode (L : ℕ) : StabilizerCode (Fin (surfaceCodeXYZ L).locations) where
generators :=
(surfaceXChecks L).map (fun v =>
fun q => (if edgeAtVertex v ((surfaceQubits L).get q) then 1 else 0, 0)) ++
(surfaceZChecks L).map (fun f =>
fun q => (0, if edgeAtFace f ((surfaceQubits L).get q) then 1 else 0))
/-- The two-patch code of tCNOTZ: qubit `(false, q)` is edge `q` of patch 1
(control), `(true, q)` of patch 2 (target). Generators are every generator of each
patch, tensored with the identity on the other patch. -/
def twoPatchStabilizerCode (L : ℕ) :
StabilizerCode (Bool × Fin (surfaceCodeXYZ L).locations) where
generators :=
([false, true] : List Bool).flatMap (fun a =>
(surfaceStabilizerCode L).generators.map (fun g =>
fun bq => if bq.1 = a then g bq.2 else 0))
/-- Contribution of one tCNOTZ fault location to the Z bit of the end-of-circuit
Pauli frame on qubit `(b, q)`. A data Z fault `(a, e, t)` on edge `e` stays on that
edge of patch `a`; if it sits on patch 2 (`a = true`) before the gate, i.e.
`t ≤ t_G - 1 = L - 2` (`t + 1 < L`), the transversal CNOT (control patch 1, target
patch 2, `Z_t ↦ Z_c Z_t`) copies it onto patch 1. Data faults at `t ≥ t_G = L - 1`
are after the gate (base convention). Measurement bit-flips contribute nothing. -/
def cnotFrameContribution (L : ℕ) (fault : CNOTFault) (b : Bool) (e : SquareEdge) : Bit :=
match fault with
| .inl (a, e', t) =>
if e' = e ∧ (b = a ∨ (a = true ∧ b = false ∧ t + 1 < L)) then 1 else 0
| .inr _ => 0
/-- Logical effect of a tCNOTZ spacetime error: its Z Pauli frame propagated to the
end of the circuit (after the last data-fault layer `t_f = 2L-2`), summed over time
in `F₂`. -/
def cnotLogicalEffect (L : ℕ) (err : Error (transversalCNOTZ L)) :
Pauli (Bool × Fin (surfaceCodeXYZ L).locations) :=
fun bq => (0, ∑ i : Fin (transversalCNOTZ L).locations,
(err i).2 * cnotFrameContribution L ((cnotFaults L).get i) bq.1 ((surfaceQubits L).get bq.2))
/-- Bits of a Pauli on `Fin n`, `(x, z)` per qubit in order (as `encodeError`). -/
def encodePauli {n : ℕ} (P : Pauli (Fin n)) : List Bool :=
(List.finRange n).flatMap (fun q => [decide ((P q).1 = 1), decide ((P q).2 = 1)])
/-- A query of the logical decision problem: a base decoding instance (size
parameter and full syndrome) and a logical representative of that instance's code. -/
abbrev LogicalQuery (f : DecodingFamily) (Q : ℕ → Type) [∀ k, Fintype (Q k)]
(code : ∀ k, StabilizerCode (Q k)) :=
Σ I : DecodingInstance f, {P : Pauli (Q I.1) // IsLogicalRep (code I.1) P}
/-- Some minimum-weight error with the query's syndrome anticommutes with the query's
logical representative (through `effect`). False on infeasible syndromes. -/
def AnticommutingMinimumExists (f : DecodingFamily) (Q : ℕ → Type) [∀ k, Fintype (Q k)]
(code : ∀ k, StabilizerCode (Q k))
(effect : ∀ k, Error (familySystem f k) → Pauli (Q k))
(q : LogicalQuery f Q code) : Prop :=
∃ e : Error (familySystem f q.1.1),
IsMinimumError (familySystem f q.1.1) q.1.2 e ∧ symplectic (effect q.1.1 e) q.2.1 = 1
/-- The encoded one-bit decision task: input is the base nonsuccinct encoding of the
decoding instance followed by the bits of `P`; the unique accepted answer is `[true]`
if some minimum-weight error anticommutes with `P`, and `[false]` otherwise. -/
def logicalDecisionTask (f : DecodingFamily) (Q : ℕ → Type) [∀ k, Fintype (Q k)]
(code : ∀ k, StabilizerCode (Q k))
(effect : ∀ k, Error (familySystem f k) → Pauli (Q k))
(encodeP : ∀ k, Pauli (Q k) → List Bool) : EncodedSearchTask where
Query := LogicalQuery f Q code
encode q := encodeDecodingInstance q.1 ++ encodeP q.1.1 q.2.1
accepts q a :=
(a = [true] ∧ AnticommutingMinimumExists f Q code effect q) ∨
(a = [false] ∧ ¬ AnticommutingMinimumExists f Q code effect q)
/-- ColorCodeZ: a Z error is itself its logical effect. -/
def colorLogicalTask : EncodedSearchTask :=
logicalDecisionTask .colorCodeZ (fun k => Fin (colorCodeZ k).locations)
colorStabilizerCode (fun _ e => e) (fun _ P => encodePauli P)
/-- SurfaceCodeXYZ (size parameter `k`, lattice `L = k+1` as in `familySystem`):
a Pauli error is itself its logical effect. -/
def surfaceLogicalTask : EncodedSearchTask :=
logicalDecisionTask .surfaceCodeXYZ (fun k => Fin (surfaceCodeXYZ (k + 1)).locations)
(fun k => surfaceStabilizerCode (k + 1)) (fun _ e => e) (fun _ P => encodePauli P)
/-- tCNOTZ (lattice `L = k+1`): logical effect is the propagated end-of-circuit frame;
`P` is encoded patch 1 then patch 2. -/
def cnotLogicalTask : EncodedSearchTask :=
logicalDecisionTask .transversalCNOTZ
(fun k => Bool × Fin (surfaceCodeXYZ (k + 1)).locations)
(fun k => twoPatchStabilizerCode (k + 1)) (fun k e => cnotLogicalEffect (k + 1) e)
(fun _ P => encodePauli (fun q => P (false, q)) ++ encodePauli (fun q => P (true, q)))
end QECDecodingHardness.AllThree.Supplement