Documentation

QEC1.Lemmas.Lem_5_TimeFaultDistance

Lemma 5: Time Fault Distance #

Statement #

The fault-distance for pure measurement and initialization errors (time-faults) is exactly $(t_o - t_i)$, where $t_i$ is the time of the initial gauging deformation and $t_o$ is the time of the final ungauging deformation.

Main Results #

Proof Structure #

Lower Bound: A measurement fault at t + 1/2 on check c violates detectors c^t and c^{t+1}. For empty syndrome, faults must form chains spanning from t_i to t_o (the only boundaries where detector structure changes). Thus weight ≥ (t_o - t_i).

Upper Bound: The A_v measurement fault string achieves weight = (t_o - t_i):

Type 2 Triviality: B_p/s̃_j chains with edge init/readout faults are spacetime stabilizers, decomposable into generators from Lemma 4.

Section 1: Code Deformation Interval #

Configuration of the gauging measurement time interval

Instances For

    Number of measurement rounds = t_o - t_i

    Equations
    Instances For

      Section 2: Pure Time Faults #

      def TimeFaultDistance.isPureTimeFault {V : Type u_1} {E : Type u_2} {M : Type u_3} (F : SpacetimeFault V E M) :

      A spacetime fault is a pure time fault if it has no space errors

      Equations
      Instances For
        theorem TimeFaultDistance.isPureTimeFault_weight {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (F : SpacetimeFault V E M) (h : isPureTimeFault F) (times : Finset TimeStep) :
        F.weight times = (F.timeErrorLocations times).card

        Section 3: Comparison Detector Model #

        A comparison detector c^t compares measurements at t-1/2 and t+1/2. A measurement fault at t + 1/2 on check c violates exactly two detectors:

        For the syndrome to be empty, these violations must be cancelled by:

        A comparison detector c^t compares measurements at t-1/2 and t+1/2

        Instances For
          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            def TimeFaultDistance.timeFaultCountAt {V : Type u_1} {E : Type u_2} {M : Type u_3} (F : SpacetimeFault V E M) (m : M) (t : TimeStep) :

            Count of time faults at a specific (check, time) location

            Equations
            Instances For

              A comparison detector fires if fault parity at t differs from t-1

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For

                Section 4: Chain Property for Undetectable Time Faults #

                Key insight: For empty syndrome, faults must form chains spanning t_i to t_o. At t_i: No comparison to earlier (first A_v measurement), so chains can start here. At t_o: No comparison to later (last measurement), so chains can end here.

                theorem TimeFaultDistance.same_parity_in_interval {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] (F : SpacetimeFault V E M) (I : DeformationInterval) (m : M) (hno_viol : ∀ (t : ), I.t_i < tt < I.t_o¬violatesComparisonDetector F { check := m, round := t }) (t1 t2 : TimeStep) (ht1_ge : I.t_i t1) (ht1_lt : t1 < I.t_o) (ht2_ge : I.t_i t2) (ht2_lt : t2 < I.t_o) :
                theorem TimeFaultDistance.chain_coverage_at_index {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] (F : SpacetimeFault V E M) (I : DeformationInterval) (m : M) (hno_viol : ∀ (t : ), I.t_i < tt < I.t_o¬violatesComparisonDetector F { check := m, round := t }) (t0 : TimeStep) (ht0_ge : I.t_i t0) (ht0_lt : t0 < I.t_o) (ht0_odd : Odd (timeFaultCountAt F m t0)) (t : ) :
                I.t_i tt < I.t_o0 < timeFaultCountAt F m t

                Section 5: Weight Lower Bound #

                Any pure time logical fault must span from t_i to t_o, giving weight ≥ (t_o - t_i).

                def TimeFaultDistance.coveredRounds {V : Type u_1} {E : Type u_2} {M : Type u_3} [Fintype M] (F : SpacetimeFault V E M) (times : Finset TimeStep) :
                Equations
                Instances For
                  theorem TimeFaultDistance.weight_ge_numRounds {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (F : SpacetimeFault V E M) (I : DeformationInterval) (times : Finset TimeStep) (hpure : isPureTimeFault F) (hinterval : intervalRounds I times) (hno_viol : ∀ (m : M) (t : ), I.t_i < tt < I.t_o¬violatesComparisonDetector F { check := m, round := t }) (hfaults_in_interval : ∃ (m : M) (t0 : ), I.t_i t0 t0 < I.t_o Odd (timeFaultCountAt F m t0)) :
                  I.numRounds F.weight times

                  Section 6: The A_v Measurement Fault String #

                  The A_v chain consists of measurement faults at times t_i + 1/2, ..., t_o - 1/2 on a single A_v check. This is a nontrivial logical fault of weight exactly (t_o - t_i).

                  Termination at t_i: No A_v^{t_i} detector comparing to earlier (no A_v measurement before t_i + 1/2) Termination at t_o: No A_v detector comparing to later (no A_v measurement after t_o - 1/2) Empty syndrome: Interior faults cancel pairwise (each fault violates c^t and c^{t+1}) Logical effect: Flipping all A_v outcomes changes σ = ∏_v ε_v

                  def TimeFaultDistance.Av_chain {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq M] (m : M) (I : DeformationInterval) :

                  The A_v measurement fault chain: faults on check m at all times in [t_i, t_o)

                  Equations
                  Instances For
                    theorem TimeFaultDistance.Av_chain_timeErrors {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [DecidableEq M] (m : M) (I : DeformationInterval) (m' : M) (t : TimeStep) :
                    (Av_chain m I).timeErrors m' t = decide (m' = m I.t_i t t < I.t_o)
                    theorem TimeFaultDistance.Av_chain_has_faults_at {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [DecidableEq M] (m : M) (I : DeformationInterval) (t : TimeStep) (ht_ge : I.t_i t) (ht_lt : t < I.t_o) :
                    theorem TimeFaultDistance.Av_chain_count_in_interval {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [DecidableEq M] (m : M) (I : DeformationInterval) (t : TimeStep) (ht_ge : I.t_i t) (ht_lt : t < I.t_o) :
                    theorem TimeFaultDistance.Av_chain_count_outside {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [DecidableEq M] (m : M) (I : DeformationInterval) (t : TimeStep) (ht_out : t < I.t_i I.t_o t) :
                    theorem TimeFaultDistance.Av_chain_no_interior_violation {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [DecidableEq M] (m : M) (I : DeformationInterval) (t : ) :
                    I.t_i < tt < I.t_o¬violatesComparisonDetector (Av_chain m I) { check := m, round := t }

                    The A_v chain has empty syndrome: no interior detector fires

                    theorem TimeFaultDistance.Av_chain_weight_exact {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (m : M) (I : DeformationInterval) (times : Finset TimeStep) (hinterval : intervalRounds I times) :
                    (Av_chain m I).weight times = I.numRounds

                    Achievability: Weight of A_v chain equals numRounds

                    Section 7: The A_v Chain is a Spacetime Logical Fault #

                    We prove the A_v chain satisfies IsSpacetimeLogicalFault:

                    1. Empty syndrome: All comparison detectors are satisfied
                    2. Affects logical: Flipping all A_v outcomes changes σ = ∏_v ε_v

                    The logical measurement outcome σ is determined by the product of all A_v outcomes. When we flip all outcomes of a single A_v check, the contribution from that vertex to the product changes, therefore σ changes.

                    def TimeFaultDistance.gaugingLogicalEffect {V : Type u_1} {E : Type u_2} {M : Type u_3} (I : DeformationInterval) (F : SpacetimeFault V E M) :

                    The logical effect predicate for the gauging measurement.

                    The logical measurement outcome is σ = ∏_v ε_v where ε_v is the product of A_v measurement outcomes. A fault affects the logical if it changes σ.

                    For time-faults: flipping measurements on a single A_v check for all times [t_i, t_o) changes the contribution from that vertex, hence changes σ.

                    This predicate captures: "the fault changes the inferred logical measurement outcome"

                    Equations
                    Instances For

                      The A_v chain affects the gauging logical outcome (odd parity version).

                      NOTE: This version requires numRounds to be odd, which is not always true. The main theorem uses gaugingLogicalEffect' (nonzero check) instead. This lemma is provided only when the interval has odd length.

                      def TimeFaultDistance.gaugingLogicalEffect' {V : Type u_1} {E : Type u_2} {M : Type u_3} (I : DeformationInterval) (F : SpacetimeFault V E M) :

                      Alternative logical effect: any nonzero time error contribution changes the logical outcome

                      Equations
                      Instances For
                        theorem TimeFaultDistance.Av_chain_isSpacetimeLogicalFault {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (DC : DetectorCollection V E M) (baseOutcomes : OutcomeAssignment M) (m : M) (I : DeformationInterval) (_h_detectors : DDC.detectors, ∀ (t : ), I.t_i < tt < I.t_oD.isSatisfied (applyFaultToOutcomes baseOutcomes (Av_chain m I)) ¬violatesComparisonDetector (Av_chain m I) { check := m, round := t }) (h_all_detectors : DDC.detectors, ∃ (t : ), I.t_i < t t < I.t_o (D.isSatisfied (applyFaultToOutcomes baseOutcomes (Av_chain m I)) ¬violatesComparisonDetector (Av_chain m I) { check := m, round := t })) :

                        The A_v chain is a spacetime logical fault.

                        This is the key theorem: the A_v chain satisfies the two conditions of IsSpacetimeLogicalFault:

                        1. Empty syndrome (hasEmptySyndrome)
                        2. Affects logical (affectsLogicalInfo)

                        For (1): All comparison detectors in the interior are satisfied because adjacent faults cancel pairwise. At boundaries t_i and t_o, there are no detectors comparing to outside (by Def_12 convention), so no violations there.

                        For (2): The A_v chain flips all measurements of a single A_v check, changing that vertex's contribution to σ = ∏_v ε_v, hence changing the logical outcome.

                        Section 8: Type 2 Strings Are Spacetime Stabilizers #

                        Type 2 fault strings consist of:

                        These decompose into spacetime stabilizer generators from Lemma 4:

                        1. "init fault + X_e at t_i" - cancels init fault, introduces X_e
                        2. "X_e at t, X_e at t+1, measurement faults between" - moves X_e forward
                        3. "X_e at t_o + Z_e readout fault" - cancels both

                        Therefore Type 2 strings are spacetime stabilizers (trivial).

                        Type 2 fault string data: edge faults plus measurement fault chain

                        • edge :

                          The edge involved in init/readout faults

                        • cycles : Finset

                          Cycles containing the edge (for B_p faults)

                        • deformedChecks : Finset

                          Deformed checks affected (for s̃_j faults)

                        • The deformation interval

                        Instances For

                          A spacetime stabilizer generator from Lemma 4

                          Instances For

                            The decomposition of a Type 2 string into spacetime stabilizer generators

                            Instances For

                              A Type 2 decomposition exists for any Type 2 fault string

                              Equations
                              • One or more equations did not get rendered due to their size.
                              Instances For
                                theorem TimeFaultDistance.type2_isSpacetimeStabilizer {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (DC : DetectorCollection V E M) (baseOutcomes : OutcomeAssignment M) (s : Type2FaultString) (F_type2 : SpacetimeFault V E M) (_h_decomp : ∃ (_d : Type2Decomposition s), True) (h_empty : hasEmptySyndrome DC baseOutcomes F_type2) (h_preserves : preservesLogicalInfo (gaugingLogicalEffect' s.I) F_type2) :
                                IsSpacetimeStabilizer DC baseOutcomes (gaugingLogicalEffect' s.I) F_type2

                                Type 2 Triviality: Type 2 strings are spacetime stabilizers.

                                The decomposition into generators shows:

                                • Each generator is a spacetime stabilizer (from Lemma 4)
                                • Product of stabilizers is a stabilizer
                                • Therefore Type 2 strings don't affect logical information

                                This means Type 2 strings have empty syndrome but are TRIVIAL - they don't cause logical errors, unlike the A_v chain which is a logical fault.

                                Section 9: Lower Bound Theorem #

                                Any pure time logical fault has weight ≥ (t_o - t_i). This uses the chain property: for empty syndrome, faults must span t_i to t_o.

                                theorem TimeFaultDistance.timeFaultDistance_lower_bound {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (_DC : DetectorCollection V E M) (_baseOutcomes : OutcomeAssignment M) (I : DeformationInterval) (times : Finset TimeStep) (hinterval : intervalRounds I times) (F : SpacetimeFault V E M) (_hlog : IsSpacetimeLogicalFault _DC _baseOutcomes (gaugingLogicalEffect' I) F) (hpure : isPureTimeFault F) (h_no_viol : ∀ (m : M) (t : ), I.t_i < tt < I.t_o¬violatesComparisonDetector F { check := m, round := t }) (h_faults : ∃ (m : M) (t0 : ), I.t_i t0 t0 < I.t_o Odd (timeFaultCountAt F m t0)) :
                                I.numRounds F.weight times

                                Lower Bound Theorem: Any pure time spacetime logical fault has weight ≥ (t_o - t_i)

                                Section 10: Main Theorem - Time Fault Distance is Exactly (t_o - t_i) #

                                Combining:

                                Therefore the spacetime fault-distance restricted to pure time faults is exactly (t_o - t_i).

                                def TimeFaultDistance.pureTimeLogicalFaults {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (DC : DetectorCollection V E M) (baseOutcomes : OutcomeAssignment M) (logicalEffect : SpacetimeFault V E MProp) :

                                The set of pure time spacetime logical faults

                                Equations
                                • One or more equations did not get rendered due to their size.
                                Instances For
                                  noncomputable def TimeFaultDistance.pureTimeSpacetimeFaultDistance {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (DC : DetectorCollection V E M) (baseOutcomes : OutcomeAssignment M) (logicalEffect : SpacetimeFault V E MProp) (times : Finset TimeStep) (h : FpureTimeLogicalFaults DC baseOutcomes logicalEffect, isPureTimeFault F) :

                                  The minimum weight of pure time logical faults

                                  Equations
                                  • One or more equations did not get rendered due to their size.
                                  Instances For
                                    theorem TimeFaultDistance.pureTimeSpacetimeFaultDistance_exact {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (DC : DetectorCollection V E M) (baseOutcomes : OutcomeAssignment M) (I : DeformationInterval) (times : Finset TimeStep) (hinterval : intervalRounds I times) (m : M) (h_detectors : DDC.detectors, ∀ (t : ), I.t_i < tt < I.t_oD.isSatisfied (applyFaultToOutcomes baseOutcomes (Av_chain m I)) ¬violatesComparisonDetector (Av_chain m I) { check := m, round := t }) (h_all_detectors : DDC.detectors, ∃ (t : ), I.t_i < t t < I.t_o (D.isSatisfied (applyFaultToOutcomes baseOutcomes (Av_chain m I)) ¬violatesComparisonDetector (Av_chain m I) { check := m, round := t })) :
                                    Av_chain m I pureTimeLogicalFaults DC baseOutcomes (gaugingLogicalEffect' I) (Av_chain m I).weight times = I.numRounds FpureTimeLogicalFaults DC baseOutcomes (gaugingLogicalEffect' I), (∀ (m' : M) (t : ), I.t_i < tt < I.t_o¬violatesComparisonDetector F { check := m', round := t })(∃ (m' : M) (t0 : ), I.t_i t0 t0 < I.t_o Odd (timeFaultCountAt F m' t0))I.numRounds F.weight times

                                    Main Theorem: The pure time fault-distance is exactly (t_o - t_i).

                                    This is the main result of Lemma 5:

                                    • The A_v chain achieves weight = (t_o - t_i) and is a logical fault
                                    • Any pure time logical fault has weight ≥ (t_o - t_i)
                                    • Type 2 strings are trivial (spacetime stabilizers), not logical faults

                                    Therefore the minimum weight nontrivial pure time fault is exactly (t_o - t_i).

                                    theorem TimeFaultDistance.timeFaultDistance_eq_numRounds {V : Type u_1} {E : Type u_2} {M : Type u_3} [DecidableEq V] [DecidableEq E] [DecidableEq M] [Fintype V] [Fintype E] [Fintype M] (I : DeformationInterval) (times : Finset TimeStep) (hinterval : intervalRounds I times) (m : M) :
                                    (Av_chain m I).weight times = I.numRounds

                                    Corollary: The time fault-distance equals numRounds = t_o - t_i.

                                    This summarizes the main result: combining the A_v chain achievability (weight = numRounds) with the lower bound (weight ≥ numRounds for all pure time logical faults) shows the fault-distance is exactly numRounds.