Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Degenerate Quantum Codes for Pauli Channels

Definition
QAlgorithms_Papers_Independent_Intakenext100_P93

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of Degenerate Quantum Codes for Pauli Channels (arXiv:quant-ph/0604107) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • pauliMass: PDF p.2: the physical one-qubit Pauli law, with Y carrying both bits.
  • pauliErrorWordMass: PDF p.2: reuse the accepted product law on paired physical amplitude/phase labels, so all three Pauli parameters are retained.
  • catLogicalSyndromeMass: PDF p.2, Eq.(6) left side: actual pushforward of physical errors to one logical Pauli and one specific syndrome. No weight multiplicity is inserted.
  • iidCatSyndromeMass: PDF p.2: marginal probability of one syndrome string.
  • amplitudeCount: PDF p.2, Eq.(6): number of physical amplitude errors for fixed logical amplitude and syndrome. The subtraction is only k+1-|s|, always positive.
  • noAmplitudeCount: PDF p.2, Eq.(6): number of positions without amplitude errors.
  • orderedPauli: PDF p.2: matrix of the accepted ordered physical Pauli, on every vector.
  • iidPauliNoise: PDF p.2: the tensor power of the three-parameter Pauli channel.
  • decoderBranch: PDF p.2: accepted cat decoder followed by the indicated syndrome branch; this is a rectangular Kraus matrix, with the logical qubit remaining.
  • branchChannel: PDF p.2: actual encode/noise/measure/decode branch before normalization.
  • catBellInput: PDF p.2: reindex the frozen one-pair Bell vector by Bool, reference first.
  • branchBell: PDF p.2: Bell output of the ACTUAL branch instrument, not a mixture postulated from Eq.(6).
  • conditionalChannel: PDF p.2: the conditional channel; an impossible branch is assigned the identity, whose weighted contribution is zero.
  • catInstrumentOutput: PDF p.2: actual output with the entire classical syndrome in the receiver.
  • catRate: PDF p.2, Eq.(5): signed Bell-input cat rate, without optimizing the input.
  • catBlockEncoder: PDF p.2: tensor product of this fixed inner cat encoder on n blocks.
  • CatAchievable: PDF p.2, Eq.(5): operational fixed-cat/additive-outer achievability. The encoder is fixed before the unknown input. All sufficiently large positive outer blocklengths work, with rate measured per (k+1)n physical qubits. The only resources are the specified encoder, independent noise and a CPTP decoder.
  • syndromeWeightMass: PDF pp.2--3: distribution of the syndrome Hamming weight, summing strings only here.
  • concentrationTail: PDF pp.2--3: mass away from BOTH limiting syndrome-weight centers. The k=0 branch is defined separately, avoiding a meaningless empty-word ratio.
  • xCatEncoder: PDF p.3: X-basis cat, including the logical Hadamard H^tensor(b+1) Enc H.
  • concatenatedEncoder: PDF p.3: encode the outer X cat, then an inner Z cat on EACH output. The physical register consists of b+1 blocks of a+1 qubits.
  • concatenatedBlockEncoder: PDF pp.2--3: tensor copies of the fixed two-level inner encoder. Every physical wire is indexed by (copy, outer-cat wire, inner-cat wire).
  • ConcatenatedAchievable: PDF pp.2--3, Eq.(5) and Concatenated Repetition Codes: communication through the fixed two-level inner cat and an additive random-code outer layer. Rates count (a+1)(b+1)n physical uses; one code handles every unknown input.
  • concatenatedRawOutput: PDF p.3: actual encoded Bell output before the two-level syndrome instrument.
  • concatenatedDecoderBranch: PDF p.3: inner Z-check branches followed by the outer X-check branch. The logical Hadamard is included in the inverse of the X-basis encoder.
  • concatenatedOutput: PDF p.3: actual two-level instrument output. Both the outer X-check syndrome and ALL inner Z-check syndromes are retained at the receiver.
  • concatenatedRate: PDF p.3: signed concatenated-cat rate per (a+1)(b+1) channel uses.
  • noiseThreshold: PDF p.3, Fig.2: zero-rate noise threshold, restricted to physical noise p in [0,3/4]. The explicit zero ensures a nonempty bounded supremum domain.
  • twoPauliChannel: PDF pp.3--4: N_p^tp with equal X/Z errors and no Y error.
  • twoPauliDilation: PDF pp.3--4: concrete Stinespring matrix, with environment order X,Z,I. Its two partial traces define the receiver and complement of the SAME dilation.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Papers_Independent_Advance50_P15
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P67
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P40
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P38

/-!
Smith--Smolin, arXiv:quant-ph/0604107v2, PDF pp.2--4.
All new interfaces belong to this paper. A cat has length k+1; k=0 is the
identity cat. Physical and logical Paulis have the ordered convention X^u Z^v.
Syndromes are retained without majority correction. Rates and entropies use bits.
Numerical and underspecified claims are inventoried separately in HARD.md.
-/

noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P93

open QAlgorithms
open scoped BigOperators ComplexConjugate Matrix

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF p.2: the physical one-qubit Pauli law, with Y carrying both bits. -/
def pauliMass (px py pz : ℝ) (u v : Bool) : ℝ :=
  if u then (if v then py else px) else (if v then pz else 1 - px - py - pz)

/-- PDF p.2: reuse the accepted product law on paired physical amplitude/phase
labels, so all three Pauli parameters are retained. -/
def pauliErrorWordMass {m : ℕ} (px py pz : ℝ) (u v : Qubits m) : ℝ :=
  QAlgorithms.Papers.Independent.Support50.P38.wordMass
    (fun e : Bool × Bool => pauliMass px py pz e.1 e.2) (fun i => (u i, v i))

/-- PDF p.2, Eq.(6) left side: actual pushforward of physical errors to one
logical Pauli and one specific syndrome. No weight multiplicity is inserted. -/
def catLogicalSyndromeMass (k : ℕ) (px py pz : ℝ) (u v : Bool) (s : Qubits k) : ℝ :=
  ∑ x : Qubits (k + 1), ∑ z : Qubits (k + 1),
    if x 0 = u ∧ dotBits z (fun _ => true) = v ∧ QAlgorithms.Papers.Independent.Advance50.P15.repetitionSyndrome x = s
    then pauliErrorWordMass px py pz x z else 0

/-- PDF p.2: marginal probability of one syndrome string. -/
def iidCatSyndromeMass (k : ℕ) (px py pz : ℝ) (s : Qubits k) : ℝ :=
  ∑ u : Bool, ∑ v : Bool, catLogicalSyndromeMass k px py pz u v s

/-- PDF p.2, Eq.(6): number of physical amplitude errors for fixed logical
amplitude and syndrome. The subtraction is only k+1-|s|, always positive. -/
def amplitudeCount (k : ℕ) (u : Bool) (s : Qubits k) : ℕ :=
  if u then k + 1 - hammingWeight s else hammingWeight s

/-- PDF p.2, Eq.(6): number of positions without amplitude errors. -/
def noAmplitudeCount (k : ℕ) (u : Bool) (s : Qubits k) : ℕ :=
  if u then hammingWeight s else k + 1 - hammingWeight s

/-- PDF p.2: matrix of the accepted ordered physical Pauli, on every vector. -/
def orderedPauli {m : ℕ} (u v : Qubits m) : Matrix (Qubits m) (Qubits m) ℂ :=
  fun x y => QAlgorithms.Papers.Independent.Advance50.P15.physicalPauli u v (ket y) x

/-- PDF p.2: the tensor power of the three-parameter Pauli channel. -/
def iidPauliNoise (m : ℕ) (px py pz : ℝ) : Superop (Qubits m) (Qubits m) :=
  fun rho => ∑ u : Qubits m, ∑ v : Qubits m,
    (pauliErrorWordMass px py pz u v : ℂ) • conjSuperop (orderedPauli u v) rho

/-- PDF p.2: accepted cat decoder followed by the indicated syndrome branch;
this is a rectangular Kraus matrix, with the logical qubit remaining. -/
def decoderBranch (k : ℕ) (s : Qubits k) : Matrix Bool (Qubits (k + 1)) ℂ :=
  fun b x => if QAlgorithms.Papers.Independent.Advance50.P15.repetitionCoordinates k x = (b, s) then 1 else 0

/-- PDF p.2: actual encode/noise/measure/decode branch before normalization. -/
def branchChannel (k : ℕ) (px py pz : ℝ) (s : Qubits k) : Superop Bool Bool :=
  conjSuperop (decoderBranch k s) ∘ iidPauliNoise (k + 1) px py pz ∘
    conjSuperop (QAlgorithms.Papers.Independent.Support50.P40.catEncoder k)

/-- PDF p.2: reindex the frozen one-pair Bell vector by Bool, reference first. -/
def catBellInput : EuclideanSpace ℂ (Bool × Bool) :=
  WithLp.toLp 2 fun x => maxEntangled 1 ((fun _ => x.1), (fun _ => x.2))

/-- PDF p.2: Bell output of the ACTUAL branch instrument, not a mixture
postulated from Eq.(6). -/
def branchBell (k : ℕ) (px py pz : ℝ) (s : Qubits k) :
    Matrix (Bool × Bool) (Bool × Bool) ℂ :=
  idTensorSuperop (R := Bool) (branchChannel k px py pz s) (pureDensity catBellInput)

/-- PDF p.2: the conditional channel; an impossible branch is assigned the
identity, whose weighted contribution is zero. -/
def conditionalChannel (k : ℕ) (px py pz : ℝ) (s : Qubits k) : Superop Bool Bool :=
  if iidCatSyndromeMass k px py pz s = 0 then id
  else fun rho => ((iidCatSyndromeMass k px py pz s)⁻¹ : ℂ) • branchChannel k px py pz s rho

/-- PDF p.2: actual output with the entire classical syndrome in the receiver. -/
def catInstrumentOutput (k : ℕ) (px py pz : ℝ) :
    Matrix (Bool × (Bool × Qubits k)) (Bool × (Bool × Qubits k)) ℂ :=
  fun x y => if x.2.2 = y.2.2 then
    branchBell k px py pz x.2.2 (x.1, x.2.1) (y.1, y.2.1) else 0

/-- PDF p.2, Eq.(5): signed Bell-input cat rate, without optimizing the input. -/
def catRate (k : ℕ) (px py pz : ℝ) : ℝ :=
  (vnEntropy (traceLeft (catInstrumentOutput k px py pz)) -
    vnEntropy (catInstrumentOutput k px py pz)) / (k + 1 : ℕ)

/-- PDF p.2: tensor product of this fixed inner cat encoder on n blocks. -/
def catBlockEncoder (k n : ℕ) : Matrix (Fin n → Qubits (k + 1)) (Qubits n) ℂ :=
  fun y x => ∏ i, QAlgorithms.Papers.Independent.Support50.P40.catEncoder k (y i) (x i)

/-- PDF p.2, Eq.(5): operational fixed-cat/additive-outer achievability.
The encoder is fixed before the unknown input. All sufficiently large positive
outer blocklengths work, with rate measured per (k+1)n physical qubits. The only
resources are the specified encoder, independent noise and a CPTP decoder. -/
def CatAchievable (k : ℕ) (px py pz R : ℝ) : Prop :=
  0 ≤ R ∧ ∀ epsilon > (0 : ℝ), ∀ delta > (0 : ℝ), ∃ n0 : ℕ, 1 ≤ n0 ∧
    ∀ n ≥ n0, ∃ l : ℕ, (R - delta) * ((k + 1) * n : ℕ) ≤ (l : ℝ) ∧
    ∃ E : Matrix (Qubits n) (Qubits l) ℂ, QAlgorithms.Papers.Independent.Support50.P40.IsAdditiveEncoder E ∧
    ∃ D : Superop (Fin n → Qubits (k + 1)) (Qubits l), IsChannel D ∧
      let transmission := D ∘ piSuperop (fun _ : Fin n => iidPauliNoise (k + 1) px py pz) ∘
        conjSuperop (catBlockEncoder k n) ∘ conjSuperop E
      1 - epsilon ≤ entanglementFidelity transmission ∧
      ∀ psi : EuclideanSpace ℂ (Qubits l), IsState psi →
        1 - epsilon ≤ effectProb (pureDensity psi) (transmission (pureDensity psi))

/-- PDF pp.2--3: distribution of the syndrome Hamming weight, summing strings
only here. -/
def syndromeWeightMass (k : ℕ) (px py pz : ℝ) (r : ℕ) : ℝ :=
  ∑ s : Qubits k, if hammingWeight s = r then iidCatSyndromeMass k px py pz s else 0

/-- PDF pp.2--3: mass away from BOTH limiting syndrome-weight centers.
The k=0 branch is defined separately, avoiding a meaningless empty-word ratio. -/
def concentrationTail (k : ℕ) (qx qz epsilon : ℝ) : ℝ :=
  if k = 0 then 0 else ∑ s : Qubits k,
    if epsilon < min |(hammingWeight s : ℝ) / k - qx|
      |(hammingWeight s : ℝ) / k - (1 - qx)|
    then iidCatSyndromeMass k (qx * (1 - qz)) (qx * qz) (qz * (1 - qx)) s else 0

/-- PDF p.3: X-basis cat, including the logical Hadamard H^tensor(b+1) Enc H. -/
def xCatEncoder (b : ℕ) : Matrix (Qubits (b + 1)) Bool ℂ :=
  fun y c => ∑ d : Bool, (∏ j : Fin (b + 1), hadamard (y j) d) * hadamard d c

/-- PDF p.3: encode the outer X cat, then an inner Z cat on EACH output.
The physical register consists of b+1 blocks of a+1 qubits. -/
def concatenatedEncoder (a b : ℕ) : Matrix (Fin (b + 1) → Qubits (a + 1)) Bool ℂ :=
  fun x c => ∑ y : Qubits (b + 1),
    xCatEncoder b y c * ∏ j : Fin (b + 1), QAlgorithms.Papers.Independent.Support50.P40.catEncoder a (x j) (y j)

/-- PDF pp.2--3: tensor copies of the fixed two-level inner encoder.
Every physical wire is indexed by (copy, outer-cat wire, inner-cat wire). -/
def concatenatedBlockEncoder (a b n : ℕ) :
    Matrix (Fin n → (Fin (b + 1) → Qubits (a + 1))) (Qubits n) ℂ :=
  fun y x => ∏ i, concatenatedEncoder a b (y i) (x i)

/-- PDF pp.2--3, Eq.(5) and Concatenated Repetition Codes: communication
through the fixed two-level inner cat and an additive random-code outer layer.
Rates count (a+1)(b+1)n physical uses; one code handles every unknown input. -/
def ConcatenatedAchievable (a b : ℕ) (p R : ℝ) : Prop :=
  0 ≤ R ∧ ∀ epsilon > (0 : ℝ), ∀ delta > (0 : ℝ), ∃ n0 : ℕ, 1 ≤ n0 ∧
    ∀ n ≥ n0, ∃ l : ℕ, (R - delta) * (((a + 1) * (b + 1)) * n : ℕ) ≤ (l : ℝ) ∧
    ∃ E : Matrix (Qubits n) (Qubits l) ℂ,
      QAlgorithms.Papers.Independent.Support50.P40.IsAdditiveEncoder E ∧
    ∃ D : Superop (Fin n → (Fin (b + 1) → Qubits (a + 1))) (Qubits l), IsChannel D ∧
      let innerNoise := piSuperop (fun _ : Fin (b + 1) =>
        iidPauliNoise (a + 1) (p / 3) (p / 3) (p / 3))
      let transmission := D ∘ piSuperop (fun _ : Fin n => innerNoise) ∘
        conjSuperop (concatenatedBlockEncoder a b n) ∘ conjSuperop E
      1 - epsilon ≤ entanglementFidelity transmission ∧
      ∀ psi : EuclideanSpace ℂ (Qubits l), IsState psi →
        1 - epsilon ≤ effectProb (pureDensity psi) (transmission (pureDensity psi))

/-- PDF p.3: actual encoded Bell output before the two-level syndrome instrument. -/
def concatenatedRawOutput (a b : ℕ) (p : ℝ) :
    Matrix (Bool × (Fin (b + 1) → Qubits (a + 1)))
      (Bool × (Fin (b + 1) → Qubits (a + 1))) ℂ :=
  idTensorSuperop (R := Bool)
    (piSuperop (fun _ : Fin (b + 1) => iidPauliNoise (a + 1) (p / 3) (p / 3) (p / 3)))
    (idTensorSuperop (R := Bool) (conjSuperop (concatenatedEncoder a b))
      (pureDensity catBellInput))

/-- PDF p.3: inner Z-check branches followed by the outer X-check branch.
The logical Hadamard is included in the inverse of the X-basis encoder. -/
def concatenatedDecoderBranch (a b : ℕ) (t : Qubits b)
    (s : Fin (b + 1) → Qubits a) : Matrix Bool (Fin (b + 1) → Qubits (a + 1)) ℂ :=
  hadamard * decoderBranch b t * hadamardN (b + 1) *
    (Matrix.of fun (y : Qubits (b + 1)) (x : Fin (b + 1) → Qubits (a + 1)) =>
      ∏ j : Fin (b + 1), decoderBranch a (s j) (y j) (x j))

/-- PDF p.3: actual two-level instrument output. Both the outer X-check
syndrome and ALL inner Z-check syndromes are retained at the receiver. -/
def concatenatedOutput (a b : ℕ) (p : ℝ) :
    Matrix (Bool × (Bool × (Qubits b × (Fin (b + 1) → Qubits a))))
      (Bool × (Bool × (Qubits b × (Fin (b + 1) → Qubits a)))) ℂ :=
  fun x y => if x.2.2 = y.2.2 then
    idTensorSuperop (R := Bool)
      (conjSuperop (concatenatedDecoderBranch a b x.2.2.1 x.2.2.2))
      (concatenatedRawOutput a b p) (x.1, x.2.1) (y.1, y.2.1)
  else 0

/-- PDF p.3: signed concatenated-cat rate per (a+1)(b+1) channel uses. -/
def concatenatedRate (a b : ℕ) (p : ℝ) : ℝ :=
  (vnEntropy (traceLeft (concatenatedOutput a b p)) -
    vnEntropy (concatenatedOutput a b p)) / ((a + 1) * (b + 1) : ℕ)

/-- PDF p.3, Fig.2: zero-rate noise threshold, restricted to physical noise
p in [0,3/4]. The explicit zero ensures a nonempty bounded supremum domain. -/
def noiseThreshold (R : ℝ → ℝ) : ℝ :=
  sSup ({0} ∪ {p : ℝ | 0 ≤ p ∧ p ≤ 3 / 4 ∧ 0 < R p})

/-- PDF pp.3--4: N_p^tp with equal X/Z errors and no Y error. -/
def twoPauliChannel (p : ℝ) : Superop Bool Bool :=
  fun rho => ((1 - p : ℝ) : ℂ) • rho +
    ((p / 2 : ℝ) : ℂ) • conjSuperop pauliX rho +
    ((p / 2 : ℝ) : ℂ) • conjSuperop pauliZ rho

/-- PDF pp.3--4: concrete Stinespring matrix, with environment order X,Z,I.
Its two partial traces define the receiver and complement of the SAME dilation. -/
def twoPauliDilation (p : ℝ) : Matrix (Bool × Fin 3) Bool ℂ :=
  fun be c => match be.2.val with
    | 0 => (Real.sqrt (p / 2) : ℂ) * pauliX be.1 c
    | 1 => (Real.sqrt (p / 2) : ℂ) * pauliZ be.1 c
    | _ => (Real.sqrt (1 - p) : ℂ) * (1 : Matrix Bool Bool ℂ) be.1 c

/-! Small checks pin the conventions and degenerate branches, without proving
any of the source results. -/

example (px py pz : ℝ) : pauliMass px py pz true true = py := rfl

example (px py pz : ℝ) (u v : Qubits 0) : pauliErrorWordMass px py pz u v = 1 := by
  simp [pauliErrorWordMass, QAlgorithms.Papers.Independent.Support50.P38.wordMass]

example (k : ℕ) (s : Qubits k) : amplitudeCount k false s = hammingWeight s := rfl

example (k : ℕ) (s : Qubits k) : noAmplitudeCount k true s = hammingWeight s := rfl

example (k : ℕ) (s : Qubits k) (b : Bool) :
    decoderBranch k s b ((QAlgorithms.Papers.Independent.Advance50.P15.repetitionCoordinates k).symm (b, s)) = 1 := by
  simp [decoderBranch]

example (b c : Bool) :
    catBellInput (b, c) = maxEntangled 1 ((fun _ => b), (fun _ => c)) := rfl

example (a b : ℕ) (x : Fin 0 → (Fin (b + 1) → Qubits (a + 1))) (y : Qubits 0) :
    concatenatedBlockEncoder a b 0 x y = 1 := by
  simp [concatenatedBlockEncoder]

example (y : Qubits 1) (c : Bool) :
    xCatEncoder 0 y c = ∑ d : Bool, hadamard (y 0) d * hadamard d c := by
  simp [xCatEncoder]

example (a b : ℕ) (p : ℝ)
    (x y : Bool × (Bool × (Qubits b × (Fin (b + 1) → Qubits a))))
    (h : x.2.2 ≠ y.2.2) : concatenatedOutput a b p x y = 0 := by
  simp [concatenatedOutput, h]

example (k : ℕ) (px py pz : ℝ) (x y : Bool × (Bool × Qubits k))
    (h : x.2.2 ≠ y.2.2) : catInstrumentOutput k px py pz x y = 0 := by
  simp [catInstrumentOutput, h]

example (k : ℕ) (px py pz : ℝ) (s : Qubits k)
    (h : iidCatSyndromeMass k px py pz s = 0) : conditionalChannel k px py pz s = id := by
  simp [conditionalChannel, h]

example (k : ℕ) (x : Fin 0 → Qubits (k + 1)) (y : Qubits 0) :
    catBlockEncoder k 0 x y = 1 := by simp [catBlockEncoder]

example (qx qz epsilon : ℝ) : concentrationTail 0 qx qz epsilon = 0 := by
  simp [concentrationTail]

example (p : ℝ) (b c : Bool) :
    twoPauliDilation p (b, (0 : Fin 3)) c = (Real.sqrt (p / 2) : ℂ) * pauliX b c := rfl

end QAlgorithms.Papers.Independent.Intakenext100.P93
Source
Degenerate Quantum Codes for Pauli Channels, arXiv:quant-ph/0604107v2, https://arxiv.org/abs/quant-ph/0604107v2
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Intakenext100.P93.CatAchievable

For a natural number kkk and arbitrary real numbers px,py,pz,Rp_x,p_y,p_z,Rpx​,py​,pz​,R, this property means that R≥0R\ge0R≥0 and that, for every ϵ>0\epsilon>0ϵ>0 and δ>0\delta>0δ>0, there is a natural number n0≥1n_0\ge1n0​≥1 such that for every natural number n≥n0n\ge n_0n≥n0​ there exist a natural number ℓ\ellℓ, a complex matrix E:C{0,1}ℓ→C{0,1}nE:\mathbb C^{\{0,1\}^{\ell}}\to\mathbb C^{\{0,1\}^{n}}E:C{0,1}ℓ→C{0,1}n, and a function DDD from matrices indexed by nnn-tuples of length-k+1k+1k+1 binary words to matrices indexed by length-ℓ\ellℓ binary words, satisfying

(R−δ)(k+1)n≤ℓ,ℓ≤n,E†E=I.(R-\delta)(k+1)n\le\ell,\qquad \ell\le n,\qquad E^\dagger E=I.(R−δ)(k+1)n≤ℓ,ℓ≤n,E†E=I.

The range of EEE must be the common fixed-vector space of some subgroup SSS of the nnn-qubit unitary group such that SSS lies in the subgroup generated by matrices ic⨂j<nPji^c\bigotimes_{j<n}P_jic⨂j<n​Pj​, with c∈{0,1,2,3}c\in\{0,1,2,3\}c∈{0,1,2,3} and Pj∈{I,X,Y,Z}P_j\in\{I,X,Y,Z\}Pj​∈{I,X,Y,Z}, all elements of SSS commute, and no element of SSS equals −I-I−I. The function DDD must admit a finite Kraus representation D(X)=∑hKhXKh†D(X)=\sum_hK_hXK_h^\daggerD(X)=∑h​Kh​XKh†​ with ∑hKh†Kh=I\sum_hK_h^\dagger K_h=I∑h​Kh†​Kh​=I. Define Jk,nJ_{k,n}Jk,n​ by (Jk,n)y,x=1(J_{k,n})_{y,x}=1(Jk,n​)y,x​=1 exactly when yi(j)=xiy_i(j)=x_iyi​(j)=xi​ for every i<n,j<k+1i<n,j<k+1i<n,j<k+1, and 000 otherwise. Put q00=1−px−py−pzq_{00}=1-p_x-p_y-p_zq00​=1−px​−py​−pz​, q10=pxq_{10}=p_xq10​=px​, q11=pyq_{11}=p_yq11​=py​, q01=pzq_{01}=p_zq01​=pz​; for length-k+1k+1k+1 words u,vu,vu,v, put w(u,v)=∏jqujvjw(u,v)=\prod_jq_{u_jv_j}w(u,v)=∏j​quj​vj​​ and (Pu,v)x,y=(−1)∑jvjyj(P_{u,v})_{x,y}=(-1)^{\sum_jv_jy_j}(Pu,v​)x,y​=(−1)∑j​vj​yj​ if x=y⊕ux=y\oplus ux=y⊕u, and 000 otherwise. Let N(X)=∑u,vw(u,v)Pu,vXPu,v†\mathcal N(X)=\sum_{u,v}w(u,v)P_{u,v}XP_{u,v}^\daggerN(X)=∑u,v​w(u,v)Pu,v​XPu,v†​, and let N⊗n\mathcal N^{\otimes n}N⊗n denote its tensor product over the nnn blocks. For

T(X)=D ⁣(N⊗n(Jk,nEXE†Jk,n†)),∣Φℓ⟩=2−ℓ/2∑z∈{0,1}ℓ∣z⟩⊗∣z⟩,\mathcal T(X)=D\!\left(\mathcal N^{\otimes n} (J_{k,n}EXE^\dagger J_{k,n}^\dagger)\right), \qquad |\Phi_\ell\rangle=2^{-\ell/2} \sum_{z\in\{0,1\}^{\ell}}|z\rangle\otimes|z\rangle,T(X)=D(N⊗n(Jk,n​EXE†Jk,n†​)),∣Φℓ​⟩=2−ℓ/2z∈{0,1}ℓ∑​∣z⟩⊗∣z⟩,

the required bounds are

1−ϵ≤Re⁡tr⁡ ⁣[∣Φℓ⟩⟨Φℓ∣(id⁡⊗T)(∣Φℓ⟩⟨Φℓ∣)],1−ϵ≤Re⁡tr⁡ ⁣[∣ψ⟩⟨ψ∣ T(∣ψ⟩⟨ψ∣)]1-\epsilon\le \operatorname{Re}\operatorname{tr}\!\left[ |\Phi_\ell\rangle\langle\Phi_\ell| (\operatorname{id}\otimes\mathcal T) (|\Phi_\ell\rangle\langle\Phi_\ell|)\right], \qquad 1-\epsilon\le \operatorname{Re}\operatorname{tr}\!\left[ |\psi\rangle\langle\psi|\, \mathcal T(|\psi\rangle\langle\psi|)\right]1−ϵ≤Retr[∣Φℓ​⟩⟨Φℓ​∣(id⊗T)(∣Φℓ​⟩⟨Φℓ​∣)],1−ϵ≤Retr[∣ψ⟩⟨ψ∣T(∣ψ⟩⟨ψ∣)]

for every ψ∈C{0,1}ℓ\psi\in\mathbb C^{\{0,1\}^{\ell}}ψ∈C{0,1}ℓ with ∥ψ∥=1\|\psi\|=1∥ψ∥=1. In these expressions, extension by the identity acts separately on each matrix block of the reference register. The definition includes k=0k=0k=0 and ℓ=0\ell=0ℓ=0; it assumes no inequalities on px,py,pzp_x,p_y,p_zpx​,py​,pz​.

QAlgorithms.Papers.Independent.Intakenext100.P93.ConcatenatedAchievable

For natural numbers a,ba,ba,b and unrestricted real numbers p,Rp,Rp,R, this defines the following property. Write Bj={0,1}j\mathcal B_j=\{0,1\}^jBj​={0,1}j, use bitwise exclusive-or for addition of bit strings, and let Hr,s=(−1)rs/2H_{r,s}=(-1)^{rs}/\sqrt2Hr,s​=(−1)rs/2​. Define matrices

Ka,b(z,c)=∑v∈Bb+1∑d∈{0,1}Hd,c∏j=0b(Hvj,d 1{every bit of zj=vj}),Ba,b,n(y,x)=∏i=0n−1Ka,b(yi,xi).K_{a,b}(z,c)= \sum_{v\in\mathcal B_{b+1}}\sum_{d\in\{0,1\}} H_{d,c}\prod_{j=0}^{b} \left(H_{v_j,d}\,\mathbf1_{\{\text{every bit of }z_j=v_j\}}\right), \qquad B_{a,b,n}(y,x)=\prod_{i=0}^{n-1}K_{a,b}(y_i,x_i).Ka,b​(z,c)=v∈Bb+1​∑​d∈{0,1}∑​Hd,c​j=0∏b​(Hvj​,d​1{every bit of zj​=vj​}​),Ba,b,n​(y,x)=i=0∏n−1​Ka,b​(yi​,xi​).

Here zzz is a list of b+1b+1b+1 strings in Ba+1\mathcal B_{a+1}Ba+1​, ccc is a bit, yyy is a list of nnn such lists, and x∈Bnx\in\mathcal B_nx∈Bn​. For u,v∈Bju,v\in\mathcal B_ju,v∈Bj​, define

Pu,v(z,x)=1{x=z⊕u} (−1)∑q=0j−1vq(zq⊕uq),wp(r,s)={1−p,(r,s)=(0,0),p/3,(r,s)≠(0,0),P_{u,v}(z,x)= \mathbf1_{\{x=z\oplus u\}}\, (-1)^{\sum_{q=0}^{j-1}v_q(z_q\oplus u_q)}, \qquad w_p(r,s)= \begin{cases} 1-p,&(r,s)=(0,0),\\ p/3,&(r,s)\ne(0,0), \end{cases}Pu,v​(z,x)=1{x=z⊕u}​(−1)∑q=0j−1​vq​(zq​⊕uq​),wp​(r,s)={1−p,p/3,​(r,s)=(0,0),(r,s)=(0,0),​

and the matrix map

Nj,p(X)=∑u,v∈Bj(∏q=0j−1wp(uq,vq))Pu,vXPu,v†.\mathcal N_{j,p}(X)= \sum_{u,v\in\mathcal B_j} \left(\prod_{q=0}^{j-1}w_p(u_q,v_q)\right) P_{u,v}XP_{u,v}^{\dagger}.Nj,p​(X)=u,v∈Bj​∑​(q=0∏j−1​wp​(uq​,vq​))Pu,v​XPu,v†​.

For any matrix map Φ\PhiΦ, its rrr-fold extension in this definition means the map specified by

[Φ⊗r(X)]y,y′=∑x,x′Xx,x′∏i=0r−1[Φ(∣xi⟩⟨xi′∣)]yi,yi′.[\Phi^{\otimes r}(X)]_{y,y'} = \sum_{x,x'}X_{x,x'} \prod_{i=0}^{r-1} [\Phi(|x_i\rangle\langle x'_i|)]_{y_i,y'_i}.[Φ⊗r(X)]y,y′​=x,x′∑​Xx,x′​i=0∏r−1​[Φ(∣xi​⟩⟨xi′​∣)]yi​,yi′​​.

The defined property requires R≥0R\ge0R≥0 and, for every ϵ>0\epsilon>0ϵ>0 and δ>0\delta>0δ>0, an integer n0≥1n_0\ge1n0​≥1 such that for every natural number n≥n0n\ge n_0n≥n0​ there are a natural number lll, a complex matrix E:CBl→CBnE:\mathbb C^{\mathcal B_l}\to\mathbb C^{\mathcal B_n}E:CBl​→CBn​, and a map DDD from matrices indexed by (Ba+1 b+1)n(\mathcal B_{a+1}^{\,b+1})^n(Ba+1b+1​)n to matrices indexed by Bl\mathcal B_lBl​, satisfying

(R−δ)(a+1)(b+1)n≤l.(R-\delta)(a+1)(b+1)n\le l.(R−δ)(a+1)(b+1)n≤l.

The matrix EEE must satisfy l≤nl\le nl≤n and E†E=IE^\dagger E=IE†E=I; moreover, there must be a subgroup SSS of the unitary matrices on CBn\mathbb C^{\mathcal B_n}CBn​ such that SSS lies in the subgroup generated by all matrices ic⨂q=0n−1Qqi^c\bigotimes_{q=0}^{n-1}Q_qic⨂q=0n−1​Qq​, with c∈{0,1,2,3}c\in\{0,1,2,3\}c∈{0,1,2,3} and Qq∈{I,X,Y,Z}Q_q\in\{I,X,Y,Z\}Qq​∈{I,X,Y,Z}, every two elements of SSS commute, −I∉S-I\notin S−I∈/S, and the range of EEE is exactly {ξ:Uξ=ξ for every U∈S}\{\xi:U\xi=\xi\text{ for every }U\in S\}{ξ:Uξ=ξ for every U∈S}. The map DDD must have a finite Kraus representation D(X)=∑hAhXAh†D(X)=\sum_h A_hXA_h^\daggerD(X)=∑h​Ah​XAh†​ with ∑hAh†Ah=I\sum_hA_h^\dagger A_h=I∑h​Ah†​Ah​=I. Set

T=D∘(Na+1,p⊗(b+1))⊗n∘(X↦Ba,b,nXBa,b,n†)∘(X↦EXE†),∣Φl⟩=2−l/2∑x∈Bl∣x,x⟩.\mathcal T= D\circ(\mathcal N_{a+1,p}^{\otimes(b+1)})^{\otimes n} \circ\bigl(X\mapsto B_{a,b,n}XB_{a,b,n}^{\dagger}\bigr) \circ\bigl(X\mapsto EXE^\dagger\bigr), \qquad |\Phi_l\rangle=2^{-l/2}\sum_{x\in\mathcal B_l}|x,x\rangle.T=D∘(Na+1,p⊗(b+1)​)⊗n∘(X↦Ba,b,n​XBa,b,n†​)∘(X↦EXE†),∣Φl​⟩=2−l/2x∈Bl​∑​∣x,x⟩.

It is required that

1−ϵ≤Re⁡⟨Φl∣(id⁡⊗T)(∣Φl⟩⟨Φl∣)∣Φl⟩1-\epsilon\le \operatorname{Re}\langle\Phi_l| (\operatorname{id}\otimes\mathcal T) (|\Phi_l\rangle\langle\Phi_l|) |\Phi_l\rangle1−ϵ≤Re⟨Φl​∣(id⊗T)(∣Φl​⟩⟨Φl​∣)∣Φl​⟩

and that, for every vector ψ∈CBl\psi\in\mathbb C^{\mathcal B_l}ψ∈CBl​ with ∥ψ∥=1\|\psi\|=1∥ψ∥=1,

1−ϵ≤Re⁡Tr⁡(∣ψ⟩⟨ψ∣ T(∣ψ⟩⟨ψ∣)).1-\epsilon\le \operatorname{Re}\operatorname{Tr} \left(|\psi\rangle\langle\psi|\, \mathcal T(|\psi\rangle\langle\psi|)\right).1−ϵ≤ReTr(∣ψ⟩⟨ψ∣T(∣ψ⟩⟨ψ∣)).

Here ∣ψ⟩⟨ψ∣|\psi\rangle\langle\psi|∣ψ⟩⟨ψ∣ has entries ψxψx′‾\psi_x\overline{\psi_{x'}}ψx​ψx′​​, and id⁡⊗T\operatorname{id}\otimes\mathcal Tid⊗T applies T\mathcal TT separately to each matrix block determined by the first register. No bound on ppp is part of this property; in particular the displayed weights are used algebraically even outside the probability range. The values a=0a=0a=0, b=0b=0b=0, and l=0l=0l=0 are included; for l=0l=0l=0, the logical register is one-dimensional.

QAlgorithms.Papers.Independent.Intakenext100.P93.amplitudeCount

For every natural number kkk, Boolean value uuu, and Boolean word sss of length kkk, let hhh be the number of true entries of sss. This defines the natural number k+1−hk+1-hk+1−h when uuu is true, and hhh when uuu is false. Subtraction is natural-number subtraction, truncated at zero, although h≤kh\le kh≤k ensures that no truncation occurs here. When k=0k=0k=0, the value is 111 for true uuu and 000 for false uuu.

QAlgorithms.Papers.Independent.Intakenext100.P93.branchBell

For every natural number kkk, arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, and Boolean word sss of length kkk, this defines the complex matrix indexed by Boolean pairs

∑u,v∈{0,1}k+1(∏i=0kw(ui,vi))(I2⊗Ku,v,s) ΦΦ† (I2⊗Ku,v,s)†,Ku,v,s=DsPu,vE,\sum_{u,v\in\{0,1\}^{k+1}} \left(\prod_{i=0}^{k}w(u_i,v_i)\right) (I_2\otimes K_{u,v,s})\,\Phi\Phi^\dagger\, (I_2\otimes K_{u,v,s})^\dagger, \qquad K_{u,v,s}=D_sP_{u,v}E,u,v∈{0,1}k+1∑​(i=0∏k​w(ui​,vi​))(I2​⊗Ku,v,s​)ΦΦ†(I2​⊗Ku,v,s​)†,Ku,v,s​=Ds​Pu,v​E,

where Φ(a,b)=1/2\Phi(a,b)=1/\sqrt2Φ(a,b)=1/2​ for a=ba=ba=b and 000 otherwise. The matrix E(x,b)E(x,b)E(x,b) is 111 exactly when every bit of xxx equals bbb; Pu,v(x,y)P_{u,v}(x,y)Pu,v​(x,y) is (−1)∑iviyi(-1)^{\sum_i v_i y_i}(−1)∑i​vi​yi​ when x=y⊕ux=y\oplus ux=y⊕u, and 000 otherwise; and Ds(b,x)D_s(b,x)Ds​(b,x) is 111 exactly when x0=bx_0=bx0​=b and x0⊕xj+1=sjx_0\oplus x_{j+1}=s_jx0​⊕xj+1​=sj​ for all j<kj<kj<k, with all other entries zero. Here ⊕\oplus⊕ denotes exclusive-or, †\dagger† denotes conjugate transpose, and w(0,0)=1−px−py−pzw(0,0)=1-p_x-p_y-p_zw(0,0)=1−px​−py​−pz​, w(1,0)=pxw(1,0)=p_xw(1,0)=px​, w(1,1)=pyw(1,1)=p_yw(1,1)=py​, w(0,1)=pzw(0,1)=p_zw(0,1)=pz​. This applies the specified branch function to the second Boolean register while leaving the first unchanged; k=0k=0k=0 is included, and no positivity assumptions or branch normalization are imposed.

QAlgorithms.Papers.Independent.Intakenext100.P93.branchChannel

For every natural number kkk, arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, and Boolean word sss of length kkk, this defines a function on all two-by-two complex matrices ρ\rhoρ:

ρ⟼∑u,v∈{0,1}k+1(∏i=0kw(ui,vi))Ku,v,sρKu,v,s†,Ku,v,s=DsPu,vE.\rho\longmapsto \sum_{u,v\in\{0,1\}^{k+1}} \left(\prod_{i=0}^{k}w(u_i,v_i)\right) K_{u,v,s}\rho K_{u,v,s}^{\dagger}, \qquad K_{u,v,s}=D_sP_{u,v}E.ρ⟼u,v∈{0,1}k+1∑​(i=0∏k​w(ui​,vi​))Ku,v,s​ρKu,v,s†​,Ku,v,s​=Ds​Pu,v​E.

Here E(x,b)=1E(x,b)=1E(x,b)=1 if every bit of xxx equals bbb, and is 000 otherwise; Pu,v(x,y)=(−1)∑iviyiP_{u,v}(x,y)=(-1)^{\sum_i v_i y_i}Pu,v​(x,y)=(−1)∑i​vi​yi​ if x=y⊕ux=y\oplus ux=y⊕u, and is 000 otherwise; and Ds(b,x)=1D_s(b,x)=1Ds​(b,x)=1 if x0=bx_0=bx0​=b and x0⊕xj+1=sjx_0\oplus x_{j+1}=s_jx0​⊕xj+1​=sj​ for every j<kj<kj<k, and is 000 otherwise. The weights are w(0,0)=1−px−py−pzw(0,0)=1-p_x-p_y-p_zw(0,0)=1−px​−py​−pz​, w(1,0)=pxw(1,0)=p_xw(1,0)=px​, w(1,1)=pyw(1,1)=p_yw(1,1)=py​, and w(0,1)=pzw(0,1)=p_zw(0,1)=pz​. The dagger denotes conjugate transpose. The definition includes k=0k=0k=0, imposes no positivity restrictions, and does not normalize the selected branch.

QAlgorithms.Papers.Independent.Intakenext100.P93.catBellInput

This defines the vector Φ\PhiΦ in the complex Euclidean space indexed by pairs of Boolean values, with amplitudes

Φ(a,b)={1/2,a=b,0,a≠b.\Phi(a,b)= \begin{cases} 1/\sqrt2,&a=b,\\ 0,&a\ne b. \end{cases}Φ(a,b)={1/2​,0,​a=b,a=b.​

Thus Φ=(∣00⟩+∣11⟩)/2\Phi=(|00\rangle+|11\rangle)/\sqrt2Φ=(∣00⟩+∣11⟩)/2​, where each displayed basis vector has amplitude 111 at its indicated Boolean pair and 000 elsewhere.

QAlgorithms.Papers.Independent.Intakenext100.P93.catBlockEncoder

For all natural numbers k,nk,nk,n, this defines a complex matrix with rows indexed by nnn-tuples y=(yi)i<ny=(y_i)_{i<n}y=(yi​)i<n​ of binary words of length k+1k+1k+1, and columns indexed by binary words xxx of length nnn, whose entry is

Ey,x=∏i=0n−11{ yi(j)=xi for every j<k+1 }.E_{y,x}=\prod_{i=0}^{n-1} \mathbf1_{\{\,y_i(j)=x_i\text{ for every }j<k+1\,\}}.Ey,x​=i=0∏n−1​1{yi​(j)=xi​ for every j<k+1}​.

Equivalently, the entry is 111 exactly when each block yiy_iyi​ consists entirely of the bit xix_ixi​, and is 000 otherwise. Both k=0k=0k=0 and n=0n=0n=0 are included; when n=0n=0n=0, the empty product is 111, so the sole matrix entry is 111.

QAlgorithms.Papers.Independent.Intakenext100.P93.catInstrumentOutput

For every natural number kkk and arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, this defines a complex matrix Ω\OmegaΩ indexed by triples (r,c,s)∈{0,1}×{0,1}×{0,1}k(r,c,s)\in\{0,1\}\times\{0,1\}\times\{0,1\}^k(r,c,s)∈{0,1}×{0,1}×{0,1}k. Put q00=1−px−py−pzq_{00}=1-p_x-p_y-p_zq00​=1−px​−py​−pz​, q10=pxq_{10}=p_xq10​=px​, q11=pyq_{11}=p_yq11​=py​, q01=pzq_{01}=p_zq01​=pz​, and w(u,v)=∏i=0kquiviw(u,v)=\prod_{i=0}^{k}q_{u_i v_i}w(u,v)=∏i=0k​qui​vi​​. For length-k+1k+1k+1 binary words, let σ(x)j=x0⊕xj+1\sigma(x)_j=x_0\oplus x_{j+1}σ(x)j​=x0​⊕xj+1​; let Jx,cJ_{x,c}Jx,c​ be 111 if every bit of xxx equals ccc, and 000 otherwise; let (Ls)c,x(L_s)_{c,x}(Ls​)c,x​ be 111 if x0=cx_0=cx0​=c and σ(x)=s\sigma(x)=sσ(x)=s, and 000 otherwise; and let (Pu,v)x,y(P_{u,v})_{x,y}(Pu,v​)x,y​ be (−1)∑iviyi(-1)^{\sum_i v_i y_i}(−1)∑i​vi​yi​ if x=y⊕ux=y\oplus ux=y⊕u, and 000 otherwise. Then its entries are

Ω(r,c,s),(r′,c′,s′)={12∑u,vw(u,v)(LsPu,vJ)c,r (LsPu,vJ)c′,r′‾,s=s′,0,s≠s′.\Omega_{(r,c,s),(r',c',s')}= \begin{cases} \displaystyle\frac12\sum_{u,v}w(u,v) (L_sP_{u,v}J)_{c,r}\, \overline{(L_sP_{u,v}J)_{c',r'}},&s=s',\\ 0,&s\ne s'. \end{cases}Ω(r,c,s),(r′,c′,s′)​=⎩⎨⎧​21​u,v∑​w(u,v)(Ls​Pu,v​J)c,r​(Ls​Pu,v​J)c′,r′​​,0,​s=s′,s=s′.​

Thus each diagonal syndrome block is obtained by encoding the second half of (∣00⟩+∣11⟩)/2(|00\rangle+|11\rangle)/\sqrt2(∣00⟩+∣11⟩)/2​, applying the displayed weighted Pauli conjugations, and applying LsL_sLs​ on that half. There is no division by the syndrome mass. The definition includes k=0k=0k=0 and imposes no positivity or normalization assumptions on the real parameters.

QAlgorithms.Papers.Independent.Intakenext100.P93.catLogicalSyndromeMass

For any natural number kkk, arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, Boolean values u,vu,vu,v, and Boolean word sss of length kkk, this defines

∑x,z∈{0,1}k+1x0=u,⨁i=0kzi=vx0⊕xj+1=sj for every 0≤j<k ∏i=0kw(xi,zi),\sum_{\substack{x,z\in\{0,1\}^{k+1}\\ x_0=u,\;\bigoplus_{i=0}^{k}z_i=v\\ x_0\oplus x_{j+1}=s_j\ \text{for every }0\le j<k}} \ \prod_{i=0}^{k}w(x_i,z_i),x,z∈{0,1}k+1x0​=u,⨁i=0k​zi​=vx0​⊕xj+1​=sj​ for every 0≤j<k​∑​ i=0∏k​w(xi​,zi​),

where ⊕\oplus⊕ is Boolean exclusive-or and w(0,0)=1−px−py−pzw(0,0)=1-p_x-p_y-p_zw(0,0)=1−px​−py​−pz​, w(1,0)=pxw(1,0)=p_xw(1,0)=px​, w(1,1)=pyw(1,1)=p_yw(1,1)=py​, and w(0,1)=pzw(0,1)=p_zw(0,1)=pz​. The parity condition comes from summing the Boolean conjunctions of zzz with the all-true word. The parameters need not give nonnegative weights. When k=0k=0k=0, sss is empty, the syndrome conditions are vacuous, and the value is w(u,v)w(u,v)w(u,v).

QAlgorithms.Papers.Independent.Intakenext100.P93.catRate

For every natural number kkk and arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, this defines the real number

S(ΩCS)−S(Ω)k+1,(ΩCS)(c,s),(c′,s′)=∑r∈{0,1}Ω(r,c,s),(r,c′,s′),\frac{S(\Omega_{CS})-S(\Omega)}{k+1}, \qquad (\Omega_{CS})_{(c,s),(c',s')}=\sum_{r\in\{0,1\}} \Omega_{(r,c,s),(r,c',s')},k+1S(ΩCS​)−S(Ω)​,(ΩCS​)(c,s),(c′,s′)​=r∈{0,1}∑​Ω(r,c,s),(r,c′,s′)​,

where S(A)=−Re⁡tr⁡[f(A)]S(A)=-\operatorname{Re}\operatorname{tr}\bigl[f(A)\bigr]S(A)=−Retr[f(A)], with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied through continuous functional calculus. Here Ω\OmegaΩ has indices (r,c,s)∈{0,1}2×{0,1}k(r,c,s)\in\{0,1\}^2\times\{0,1\}^k(r,c,s)∈{0,1}2×{0,1}k and entries

Ω(r,c,s),(r′,c′,s′)={12∑u,vw(u,v)(LsPu,vJ)c,r(LsPu,vJ)c′,r′‾,s=s′,0,s≠s′,\Omega_{(r,c,s),(r',c',s')}= \begin{cases} \displaystyle\frac12\sum_{u,v}w(u,v) (L_sP_{u,v}J)_{c,r}\overline{(L_sP_{u,v}J)_{c',r'}},&s=s',\\ 0,&s\ne s', \end{cases}Ω(r,c,s),(r′,c′,s′)​=⎩⎨⎧​21​u,v∑​w(u,v)(Ls​Pu,v​J)c,r​(Ls​Pu,v​J)c′,r′​​,0,​s=s′,s=s′,​

with u,vu,vu,v ranging over length-k+1k+1k+1 binary words, w(u,v)=∏iquiviw(u,v)=\prod_iq_{u_i v_i}w(u,v)=∏i​qui​vi​​, and (q00,q10,q11,q01)=(1−px−py−pz,px,py,pz)(q_{00},q_{10},q_{11},q_{01})=(1-p_x-p_y-p_z,p_x,p_y,p_z)(q00​,q10​,q11​,q01​)=(1−px​−py​−pz​,px​,py​,pz​). The matrix JJJ has entry Jx,c=1J_{x,c}=1Jx,c​=1 exactly when all bits of xxx equal ccc; LsL_sLs​ has entry (Ls)c,x=1(L_s)_{c,x}=1(Ls​)c,x​=1 exactly when x0=cx_0=cx0​=c and x0⊕xj+1=sjx_0\oplus x_{j+1}=s_jx0​⊕xj+1​=sj​ for every j<kj<kj<k; and Pu,vP_{u,v}Pu,v​ has entry (−1)∑iviyi(-1)^{\sum_i v_i y_i}(−1)∑i​vi​yi​ at (x,y)(x,y)(x,y) when x=y⊕ux=y\oplus ux=y⊕u, with all other entries zero. No assumption that these matrices are density matrices is imposed. The case k=0k=0k=0 is included, and the denominator is always positive.

QAlgorithms.Papers.Independent.Intakenext100.P93.concatenatedBlockEncoder

For arbitrary natural numbers a,b,na,b,na,b,n, this defines a complex matrix whose rows are indexed by arrays y=(yi,j)y=(y_{i,j})y=(yi,j​), where 0≤i<n0\le i<n0≤i<n, 0≤j<b+10\le j<b+10≤j<b+1, and each yi,jy_{i,j}yi,j​ is an (a+1)(a+1)(a+1)-bit string, and whose columns are indexed by nnn-bit strings xxx. Identify Boolean values with 0,10,10,1, put Hr,s=(−1)rs/2H_{r,s}=(-1)^{rs}/\sqrt2Hr,s​=(−1)rs/2​, and write 1{z≡c}\mathbf1_{\{z\equiv c\}}1{z≡c}​ for 111 when every bit of zzz equals ccc, and 000 otherwise. The matrix entry is

Ba,b,n(y,x)=∏i=0n−1Ka,b(yi,xi),Ka,b(z,c)=∑v∈{0,1}b+1∑d∈{0,1}Hd,c∏j=0b(Hvj,d 1{zj≡vj}).B_{a,b,n}(y,x)=\prod_{i=0}^{n-1}K_{a,b}(y_i,x_i), \qquad K_{a,b}(z,c)= \sum_{v\in\{0,1\}^{b+1}}\sum_{d\in\{0,1\}} H_{d,c}\prod_{j=0}^{b} \left(H_{v_j,d}\,\mathbf1_{\{z_j\equiv v_j\}}\right).Ba,b,n​(y,x)=i=0∏n−1​Ka,b​(yi​,xi​),Ka,b​(z,c)=v∈{0,1}b+1∑​d∈{0,1}∑​Hd,c​j=0∏b​(Hvj​,d​1{zj​≡vj​}​).

Thus each factor uses the explicitly displayed matrix Ka,bK_{a,b}Ka,b​. The parameters aaa and bbb may be zero, so their corresponding strings still have lengths a+1a+1a+1 and b+1b+1b+1. When n=0n=0n=0, both indexing sets contain their unique empty array or string, and the sole matrix entry is the empty product 111.

QAlgorithms.Papers.Independent.Intakenext100.P93.concatenatedDecoderBranch

For all natural numbers a,ba,ba,b, a binary word ttt of length bbb, and a tuple s=(sj)j<b+1s=(s_j)_{j<b+1}s=(sj​)j<b+1​ of binary words of length aaa, this defines a complex matrix from tuples of length-a+1a+1a+1 binary words to a single bit. For any natural number hhh and word r∈{0,1}hr\in\{0,1\}^hr∈{0,1}h, define the matrix

(Lr(h))c,x=1{ x0=c, x0⊕xi+1=ri ∀i<h },(L^{(h)}_r)_{c,x} =\mathbf1_{\{\,x_0=c,\ x_0\oplus x_{i+1}=r_i\ \forall i<h\,\}},(Lr(h)​)c,x​=1{x0​=c, x0​⊕xi+1​=ri​ ∀i<h}​,

with bit row ccc and length-h+1h+1h+1 word column xxx. Define Hc,d=(−1)cd/2H_{c,d}=(-1)^{cd}/\sqrt2Hc,d​=(−1)cd/2​, define (HN)y,z=2−N/2(−1)∑iziyi(H_N)_{y,z}=2^{-N/2}(-1)^{\sum_i z_i y_i}(HN​)y,z​=2−N/2(−1)∑i​zi​yi​ for length-NNN binary words, and define My,x=∏j=0b(Lsj(a))yj,xjM_{y,x}=\prod_{j=0}^{b}(L^{(a)}_{s_j})_{y_j,x_j}My,x​=∏j=0b​(Lsj​(a)​)yj​,xj​​. The matrix being defined is exactly

Dt,s=H Lt(b) Hb+1 M,D_{t,s}=H\,L^{(b)}_t\,H_{b+1}\,M,Dt,s​=HLt(b)​Hb+1​M,

with ordinary matrix multiplication, so the rightmost factor acts first. Both a=0a=0a=0 and b=0b=0b=0 are permitted; the corresponding syndrome words are empty, and L(0)L^{(0)}L(0) reads the sole bit.

QAlgorithms.Papers.Independent.Intakenext100.P93.concatenatedEncoder

For all natural numbers a,ba,ba,b, this defines a complex matrix with rows indexed by tuples x=(xj)j<b+1x=(x_j)_{j<b+1}x=(xj​)j<b+1​ of binary words of length a+1a+1a+1, and columns indexed by a bit ccc, whose entries are

Ex,c=∑y∈{0,1}b+1 ∑d∈{0,1}(∏j=0bHyj,d)Hd,c∏j=0b1{ xj(i)=yj for every i<a+1 },Hr,t=(−1)rt2.E_{x,c}= \sum_{y\in\{0,1\}^{b+1}}\ \sum_{d\in\{0,1\}} \left(\prod_{j=0}^{b}H_{y_j,d}\right)H_{d,c} \prod_{j=0}^{b} \mathbf1_{\{\,x_j(i)=y_j\text{ for every }i<a+1\,\}}, \qquad H_{r,t}=\frac{(-1)^{rt}}{\sqrt2}.Ex,c​=y∈{0,1}b+1∑​ d∈{0,1}∑​(j=0∏b​Hyj​,d​)Hd,c​j=0∏b​1{xj​(i)=yj​ for every i<a+1}​,Hr,t​=2​(−1)rt​.

Here 1\mathbf11 is 111 when its condition holds and 000 otherwise, and bits in the exponent are interpreted numerically. The definition includes a=0a=0a=0, b=0b=0b=0, and a=b=0a=b=0a=b=0; each block still has at least one bit.

QAlgorithms.Papers.Independent.Intakenext100.P93.concatenatedOutput

For all natural numbers a,ba,ba,b and arbitrary real ppp, this defines a complex matrix indexed by (r,c,t,s)(r,c,t,s)(r,c,t,s), where r,cr,cr,c are bits, t∈{0,1}bt\in\{0,1\}^bt∈{0,1}b, and s=(sj)j<b+1s=(s_j)_{j<b+1}s=(sj​)j<b+1​ with sj∈{0,1}as_j\in\{0,1\}^asj​∈{0,1}a. Let Hc,d=(−1)cd/2H_{c,d}=(-1)^{cd}/\sqrt2Hc,d​=(−1)cd/2​, let (HN)y,z=2−N/2(−1)∑iziyi(H_N)_{y,z}=2^{-N/2}(-1)^{\sum_i z_i y_i}(HN​)y,z​=2−N/2(−1)∑i​zi​yi​, and define (Lr(h))c,x=1(L^{(h)}_r)_{c,x}=1(Lr(h)​)c,x​=1 exactly when x0=cx_0=cx0​=c and x0⊕xi+1=rix_0\oplus x_{i+1}=r_ix0​⊕xi+1​=ri​ for every i<hi<hi<h, with other entries zero. Set

Ms(y,x)=∏j=0b(Lsj(a))yj,xj,Dt,s=HLt(b)Hb+1Ms,M_s(y,x)=\prod_{j=0}^{b}(L^{(a)}_{s_j})_{y_j,x_j}, \qquad D_{t,s}=H L^{(b)}_t H_{b+1}M_s,Ms​(y,x)=j=0∏b​(Lsj​(a)​)yj​,xj​​,Dt,s​=HLt(b)​Hb+1​Ms​,

and define

Ex,c=∑y∈{0,1}b+1∑d∈{0,1}Hd,c∏j=0b(Hyj,d1{xj(i)=yj ∀i<a+1}).E_{x,c}=\sum_{y\in\{0,1\}^{b+1}}\sum_{d\in\{0,1\}} H_{d,c}\prod_{j=0}^{b} \left(H_{y_j,d}\mathbf1_{\{x_j(i)=y_j\ \forall i<a+1\}}\right).Ex,c​=y∈{0,1}b+1∑​d∈{0,1}∑​Hd,c​j=0∏b​(Hyj​,d​1{xj​(i)=yj​ ∀i<a+1}​).

For tuples u,vu,vu,v of b+1b+1b+1 length-a+1a+1a+1 words, put w(u,v)=∏j,iquj(i),vj(i)w(u,v)=\prod_{j,i}q_{u_j(i),v_j(i)}w(u,v)=∏j,i​quj​(i),vj​(i)​, with q00=1−pq_{00}=1-pq00​=1−p and q10=q11=q01=p/3q_{10}=q_{11}=q_{01}=p/3q10​=q11​=q01​=p/3, and put Ku,v=⨂j=0bPuj,vjK_{u,v}=\bigotimes_{j=0}^{b}P_{u_j,v_j}Ku,v​=⨂j=0b​Puj​,vj​​, where (Pu,v)x,y=(−1)∑iviyi(P_{u,v})_{x,y}=(-1)^{\sum_i v_i y_i}(Pu,v​)x,y​=(−1)∑i​vi​yi​ if x=y⊕ux=y\oplus ux=y⊕u, and 000 otherwise. The defined entries are

Ω(r,c,t,s),(r′,c′,t′,s′)={12∑u,vw(u,v)(Dt,sKu,vE)c,r(Dt,sKu,vE)c′,r′‾,(t,s)=(t′,s′),0,(t,s)≠(t′,s′).\Omega_{(r,c,t,s),(r',c',t',s')}= \begin{cases} \displaystyle\frac12\sum_{u,v}w(u,v) (D_{t,s}K_{u,v}E)_{c,r} \overline{(D_{t,s}K_{u,v}E)_{c',r'}}, &(t,s)=(t',s'),\\ 0,&(t,s)\ne(t',s'). \end{cases}Ω(r,c,t,s),(r′,c′,t′,s′)​=⎩⎨⎧​21​u,v∑​w(u,v)(Dt,s​Ku,v​E)c,r​(Dt,s​Ku,v​E)c′,r′​​,0,​(t,s)=(t′,s′),(t,s)=(t′,s′).​

Thus distinct combined syndrome labels have zero off-diagonal blocks, and the individual blocks are retained without normalization by their traces. The definition includes a=0a=0a=0 and b=0b=0b=0, and imposes no probability assumptions on ppp.

QAlgorithms.Papers.Independent.Intakenext100.P93.concatenatedRate

For every pair of natural numbers a,ba,ba,b, including zero, and every real ppp, this defines a real number as follows. Write Br={0,1}r\mathcal B_r=\{0,1\}^rBr​={0,1}r, use ⊕\oplus⊕ for bitwise XOR, and let HrH_rHr​ have entries Hr(x,y)=2−r/2(−1)∑ixiyiH_r(x,y)=2^{-r/2}(-1)^{\sum_i x_i y_i}Hr​(x,y)=2−r/2(−1)∑i​xi​yi​; write HHH for the corresponding single-bit Hadamard matrix. Let Cr(x,c)=1C_r(x,c)=1Cr​(x,c)=1 when every bit of x∈Br+1x\in\mathcal B_{r+1}x∈Br+1​ equals c∈{0,1}c\in\{0,1\}c∈{0,1}, and 000 otherwise, and define

Xb(y,c)=∑d∈{0,1}(∏j=0bH(yj,d))H(d,c),Ea,b(x,c)=∑y∈Bb+1Xb(y,c)∏j=0bCa(xj,yj).X_b(y,c)=\sum_{d\in\{0,1\}}\left(\prod_{j=0}^{b}H(y_j,d)\right)H(d,c), \qquad E_{a,b}(x,c)=\sum_{y\in\mathcal B_{b+1}}X_b(y,c)\prod_{j=0}^{b}C_a(x_j,y_j).Xb​(y,c)=d∈{0,1}∑​(j=0∏b​H(yj​,d))H(d,c),Ea,b​(x,c)=y∈Bb+1​∑​Xb​(y,c)j=0∏b​Ca​(xj​,yj​).

For u,v∈Bru,v\in\mathcal B_ru,v∈Br​, let Pu,v∣z⟩=(−1)∑ivizi∣z⊕u⟩P_{u,v}|z\rangle=(-1)^{\sum_i v_i z_i}|z\oplus u\ranglePu,v​∣z⟩=(−1)∑i​vi​zi​∣z⊕u⟩, and set

Nr,p(X)=∑u,v∈Br(∏i=0r−1wp(ui,vi))Pu,vXPu,v†,wp(0,0)=1−p,wp(1,0)=wp(1,1)=wp(0,1)=p/3.\mathcal N_{r,p}(X)= \sum_{u,v\in\mathcal B_r} \left(\prod_{i=0}^{r-1}w_p(u_i,v_i)\right)P_{u,v}XP_{u,v}^{\dagger}, \quad w_p(0,0)=1-p,\quad w_p(1,0)=w_p(1,1)=w_p(0,1)=p/3.Nr,p​(X)=u,v∈Br​∑​(i=0∏r−1​wp​(ui​,vi​))Pu,v​XPu,v†​,wp​(0,0)=1−p,wp​(1,0)=wp​(1,1)=wp​(0,1)=p/3.

Here tensor products of maps act separately on the indicated blocks. With ∣Φ⟩=(∣00⟩+∣11⟩)/2|\Phi\rangle=(|00\rangle+|11\rangle)/\sqrt2∣Φ⟩=(∣00⟩+∣11⟩)/2​, define the raw matrix

Ωraw=(id⁡⊗Na+1,p⊗(b+1))((I⊗Ea,b)∣Φ⟩⟨Φ∣(I⊗Ea,b†)).\Omega_{\mathrm{raw}} =(\operatorname{id}\otimes\mathcal N_{a+1,p}^{\otimes(b+1)}) \bigl((I\otimes E_{a,b})|\Phi\rangle\langle\Phi|(I\otimes E_{a,b}^{\dagger})\bigr).Ωraw​=(id⊗Na+1,p⊗(b+1)​)((I⊗Ea,b​)∣Φ⟩⟨Φ∣(I⊗Ea,b†​)).

For s∈Brs\in\mathcal B_rs∈Br​, define Br,s(c,x)B_{r,s}(c,x)Br,s​(c,x) to be 111 if x0=cx_0=cx0​=c and x0⊕xj+1=sjx_0\oplus x_{j+1}=s_jx0​⊕xj+1​=sj​ for every j<rj<rj<r, and 000 otherwise. For t∈Bbt\in\mathcal B_bt∈Bb​ and s=(s0,…,sb)∈Ba b+1s=(s_0,\ldots,s_b)\in\mathcal B_a^{\,b+1}s=(s0​,…,sb​)∈Bab+1​, put

Ls(y,x)=∏j=0bBa,sj(yj,xj),Dt,s=HBb,tHb+1Ls.L_s(y,x)=\prod_{j=0}^{b}B_{a,s_j}(y_j,x_j), \qquad D_{t,s}=H B_{b,t}H_{b+1}L_s.Ls​(y,x)=j=0∏b​Ba,sj​​(yj​,xj​),Dt,s​=HBb,t​Hb+1​Ls​.

Define Ω\OmegaΩ, indexed by (r,c,t,s)(r,c,t,s)(r,c,t,s) with r,c∈{0,1}r,c\in\{0,1\}r,c∈{0,1}, to have zero entries between distinct (t,s)(t,s)(t,s) blocks, and within each block to equal (I⊗Dt,s)Ωraw(I⊗Dt,s†)(I\otimes D_{t,s})\Omega_{\mathrm{raw}}(I\otimes D_{t,s}^{\dagger})(I⊗Dt,s​)Ωraw​(I⊗Dt,s†​). Then the defined value is

S(Tr⁡rΩ)−S(Ω)(a+1)(b+1),S(X)=−Re⁡Tr⁡[f(X)],f(x)=xlog⁡2x,\frac{S(\operatorname{Tr}_{r}\Omega)-S(\Omega)}{(a+1)(b+1)}, \qquad S(X)=-\operatorname{Re}\operatorname{Tr}\bigl[f(X)\bigr],\quad f(x)=x\log_2 x,(a+1)(b+1)S(Trr​Ω)−S(Ω)​,S(X)=−ReTr[f(X)],f(x)=xlog2​x,

where f(X)f(X)f(X) uses continuous functional calculus and the real logarithm is totalized, with log⁡20=0\log_2 0=0log2​0=0 and log⁡2x=log⁡2∣x∣\log_2 x=\log_2|x|log2​x=log2​∣x∣ for negative xxx. The partial trace removes the first, reference-bit register. No restriction on ppp or density-matrix hypothesis is imposed; the denominator is always positive.

QAlgorithms.Papers.Independent.Intakenext100.P93.concatenatedRawOutput

For all natural numbers a,ba,ba,b and arbitrary real ppp, this defines a complex matrix indexed by pairs (r,x)(r,x)(r,x), where rrr is a bit and x=(xj)j<b+1x=(x_j)_{j<b+1}x=(xj​)j<b+1​ is a tuple of length-a+1a+1a+1 binary words. Define

Ex,c=∑y∈{0,1}b+1∑d∈{0,1}Hd,c∏j=0b(Hyj,d 1{xj(i)=yj ∀i<a+1}),Hr,t=(−1)rt2.E_{x,c}=\sum_{y\in\{0,1\}^{b+1}}\sum_{d\in\{0,1\}} H_{d,c}\prod_{j=0}^{b} \left(H_{y_j,d}\, \mathbf1_{\{x_j(i)=y_j\ \forall i<a+1\}}\right), \qquad H_{r,t}=\frac{(-1)^{rt}}{\sqrt2}.Ex,c​=y∈{0,1}b+1∑​d∈{0,1}∑​Hd,c​j=0∏b​(Hyj​,d​1{xj​(i)=yj​ ∀i<a+1}​),Hr,t​=2​(−1)rt​.

For tuples u=(uj),v=(vj)u=(u_j),v=(v_j)u=(uj​),v=(vj​) of words of length a+1a+1a+1, put

w(u,v)=∏j=0b∏i=0aquj(i),vj(i),q00=1−p,q10=q11=q01=p/3,w(u,v)=\prod_{j=0}^{b}\prod_{i=0}^{a}q_{u_j(i),v_j(i)}, \qquad q_{00}=1-p,\quad q_{10}=q_{11}=q_{01}=p/3,w(u,v)=j=0∏b​i=0∏a​quj​(i),vj​(i)​,q00​=1−p,q10​=q11​=q01​=p/3,

and define Ku,vK_{u,v}Ku,v​ by (Ku,v)x,y=∏j(Puj,vj)xj,yj(K_{u,v})_{x,y}=\prod_j(P_{u_j,v_j})_{x_j,y_j}(Ku,v​)x,y​=∏j​(Puj​,vj​​)xj​,yj​​, where (Puj,vj)z,z′=(−1)∑ivj(i)zi′(P_{u_j,v_j})_{z,z'}=(-1)^{\sum_i v_j(i)z'_i}(Puj​,vj​​)z,z′​=(−1)∑i​vj​(i)zi′​ if z=z′⊕ujz=z'\oplus u_jz=z′⊕uj​, and 000 otherwise. The output entries are

ρ(r,x),(r′,x′)=12∑u,vw(u,v)(Ku,vE)x,r(Ku,vE)x′,r′‾.\rho_{(r,x),(r',x')}= \frac12\sum_{u,v}w(u,v)(K_{u,v}E)_{x,r} \overline{(K_{u,v}E)_{x',r'}}.ρ(r,x),(r′,x′)​=21​u,v∑​w(u,v)(Ku,v​E)x,r​(Ku,v​E)x′,r′​​.

Equivalently, the definition starts with (∣00⟩+∣11⟩)/2(|00\rangle+|11\rangle)/\sqrt2(∣00⟩+∣11⟩)/2​, conjugates its second register by EEE, and then applies the displayed weighted Pauli conjugations independently to its b+1b+1b+1 blocks, leaving the first register untouched. Zero values of aaa and bbb are included, and no restriction on ppp is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P93.concentrationTail

For every natural number kkk and arbitrary real numbers qx,qz,ϵq_x,q_z,\epsilonqx​,qz​,ϵ, this defines 000 when k=0k=0k=0; otherwise it defines

∑s∈{0,1}kϵ<min⁡{∣∣s∣/k−qx∣, ∣∣s∣/k−(1−qx)∣} ∑u,v∈{0,1}k+1u0⊕uj+1=sj for every j<k∏i=0kquivi,\sum_{\substack{s\in\{0,1\}^k\\ \epsilon< \min\{\,||s|/k-q_x|,\ ||s|/k-(1-q_x)|\,\}}} \ \sum_{\substack{u,v\in\{0,1\}^{k+1}\\ u_0\oplus u_{j+1}=s_j\ \text{for every }j<k}} \prod_{i=0}^{k}q_{u_i v_i},s∈{0,1}kϵ<min{∣∣s∣/k−qx​∣, ∣∣s∣/k−(1−qx​)∣}​∑​ u,v∈{0,1}k+1u0​⊕uj+1​=sj​ for every j<k​∑​i=0∏k​qui​vi​​,

where ∣s∣|s|∣s∣ counts true bits and

q10=qx(1−qz),q11=qxqz,q01=qz(1−qx),q00=1−qx(1−qz)−qxqz−qz(1−qx).q_{10}=q_x(1-q_z),\quad q_{11}=q_xq_z,\quad q_{01}=q_z(1-q_x),\quad q_{00}=1-q_x(1-q_z)-q_xq_z-q_z(1-q_x).q10​=qx​(1−qz​),q11​=qx​qz​,q01​=qz​(1−qx​),q00​=1−qx​(1−qz​)−qx​qz​−qz​(1−qx​).

The selection condition is strict: the normalized syndrome weight must have distance greater than ϵ\epsilonϵ from both qxq_xqx​ and 1−qx1-q_x1−qx​. There are no assumptions that qx,qzq_x,q_zqx​,qz​ lie in [0,1][0,1][0,1], or that ϵ\epsilonϵ is nonnegative.

QAlgorithms.Papers.Independent.Intakenext100.P93.conditionalChannel

For every natural number kkk, arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, and binary word s∈{0,1}ks\in\{0,1\}^ks∈{0,1}k, this defines a function on complex 2×22\times22×2 matrices. To specify it, put q00=1−px−py−pzq_{00}=1-p_x-p_y-p_zq00​=1−px​−py​−pz​, q10=pxq_{10}=p_xq10​=px​, q11=pyq_{11}=p_yq11​=py​, q01=pzq_{01}=p_zq01​=pz​, and w(u,v)=∏i=0kquiviw(u,v)=\prod_{i=0}^{k}q_{u_i v_i}w(u,v)=∏i=0k​qui​vi​​ for binary words u,vu,vu,v of length k+1k+1k+1. Write σ(x)j=x0⊕xj+1\sigma(x)_j=x_0\oplus x_{j+1}σ(x)j​=x0​⊕xj+1​, define Jx,c=1J_{x,c}=1Jx,c​=1 when every bit of xxx equals ccc and 000 otherwise, define (Ls)c,x=1(L_s)_{c,x}=1(Ls​)c,x​=1 when x0=cx_0=cx0​=c and σ(x)=s\sigma(x)=sσ(x)=s and 000 otherwise, and define (Pu,v)x,y=(−1)∑iviyi(P_{u,v})_{x,y}=(-1)^{\sum_i v_i y_i}(Pu,v​)x,y​=(−1)∑i​vi​yi​ when x=y⊕ux=y\oplus ux=y⊕u and 000 otherwise. Here ⊕\oplus⊕ denotes bitwise exclusive-or. With

μs=∑u,v∈{0,1}k+1σ(u)=sw(u,v),Bs(ρ)=∑u,vw(u,v)LsPu,vJρJ†Pu,v†Ls†,\mu_s=\sum_{\substack{u,v\in\{0,1\}^{k+1}\\\sigma(u)=s}}w(u,v), \qquad B_s(\rho)=\sum_{u,v}w(u,v)L_sP_{u,v}J\rho J^\dagger P_{u,v}^\dagger L_s^\dagger,μs​=u,v∈{0,1}k+1σ(u)=s​∑​w(u,v),Bs​(ρ)=u,v∑​w(u,v)Ls​Pu,v​JρJ†Pu,v†​Ls†​,

the defined function sends ρ\rhoρ to ρ\rhoρ if μs=0\mu_s=0μs​=0, and to μs−1Bs(ρ)\mu_s^{-1}B_s(\rho)μs−1​Bs​(ρ) otherwise. No restrictions ensuring that the quvq_{uv}quv​ are probabilities are assumed, and ρ\rhoρ is arbitrary. The case k=0k=0k=0, with its unique empty syndrome, is included.

QAlgorithms.Papers.Independent.Intakenext100.P93.decoderBranch

For every natural number kkk and Boolean word sss of length kkk, this defines a complex matrix DsD_sDs​ with Boolean row index bbb and length-(k+1)(k+1)(k+1) Boolean column index xxx, by

Ds(b,x)={1,x0=b and x0⊕xj+1=sj for every 0≤j<k,0,otherwise.D_s(b,x)= \begin{cases} 1,&x_0=b\ \text{and }x_0\oplus x_{j+1}=s_j \text{ for every }0\le j<k,\\ 0,&\text{otherwise}. \end{cases}Ds​(b,x)={1,0,​x0​=b and x0​⊕xj+1​=sj​ for every 0≤j<k,otherwise.​

Here ⊕\oplus⊕ is exclusive-or: the coordinate map used in the definition sends xxx to its first bit together with these kkk exclusive-or values. When k=0k=0k=0, the syndrome is empty and the entry is 111 exactly when x0=bx_0=bx0​=b.

QAlgorithms.Papers.Independent.Intakenext100.P93.iidCatSyndromeMass

For any natural number kkk, arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, and Boolean word sss of length kkk, this defines

∑u,v∈{0,1} ∑x,z∈{0,1}k+1x0=u,⨁i=0kzi=vx0⊕xj+1=sj for every 0≤j<k ∏i=0kw(xi,zi),\sum_{u,v\in\{0,1\}} \ \sum_{\substack{x,z\in\{0,1\}^{k+1}\\ x_0=u,\;\bigoplus_{i=0}^{k}z_i=v\\ x_0\oplus x_{j+1}=s_j\ \text{for every }0\le j<k}} \ \prod_{i=0}^{k}w(x_i,z_i),u,v∈{0,1}∑​ x,z∈{0,1}k+1x0​=u,⨁i=0k​zi​=vx0​⊕xj+1​=sj​ for every 0≤j<k​∑​ i=0∏k​w(xi​,zi​),

where ⊕\oplus⊕ denotes exclusive-or and w(0,0)=1−px−py−pzw(0,0)=1-p_x-p_y-p_zw(0,0)=1−px​−py​−pz​, w(1,0)=pxw(1,0)=p_xw(1,0)=px​, w(1,1)=pyw(1,1)=p_yw(1,1)=py​, and w(0,1)=pzw(0,1)=p_zw(0,1)=pz​. Thus both the first-bit label and the phase-parity label are summed over. No positivity assumptions are imposed. For k=0k=0k=0, the unique empty syndrome has value 111.

QAlgorithms.Papers.Independent.Intakenext100.P93.iidPauliNoise

For every natural number mmm and arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, this defines a function on all complex matrices ρ\rhoρ indexed by length-mmm Boolean words:

ρ⟼∑u,v∈{0,1}m(∏i=0m−1w(ui,vi))Pu,vρPu,v†,\rho\longmapsto \sum_{u,v\in\{0,1\}^{m}} \left(\prod_{i=0}^{m-1}w(u_i,v_i)\right)P_{u,v}\rho P_{u,v}^{\dagger},ρ⟼u,v∈{0,1}m∑​(i=0∏m−1​w(ui​,vi​))Pu,v​ρPu,v†​,

where w(0,0)=1−px−py−pzw(0,0)=1-p_x-p_y-p_zw(0,0)=1−px​−py​−pz​, w(1,0)=pxw(1,0)=p_xw(1,0)=px​, w(1,1)=pyw(1,1)=p_yw(1,1)=py​, w(0,1)=pzw(0,1)=p_zw(0,1)=pz​, and Pu,v(x,y)=(−1)∑iviyiP_{u,v}(x,y)=(-1)^{\sum_i v_i y_i}Pu,v​(x,y)=(−1)∑i​vi​yi​ if x=y⊕ux=y\oplus ux=y⊕u, and 000 otherwise. The dagger denotes conjugate transpose. Neither ρ\rhoρ nor the parameters are subject to positivity hypotheses, and the definition itself imposes no channel condition. For m=0m=0m=0, the function is the identity on one-by-one complex matrices.

QAlgorithms.Papers.Independent.Intakenext100.P93.noAmplitudeCount

For every natural number kkk, Boolean value uuu, and Boolean word sss of length kkk, let hhh be the number of true entries of sss. This defines the natural number hhh when uuu is true, and k+1−hk+1-hk+1−h when uuu is false. Subtraction is natural-number subtraction, truncated at zero, although h≤kh\le kh≤k ensures that no truncation occurs here. When k=0k=0k=0, the value is 000 for true uuu and 111 for false uuu.

QAlgorithms.Papers.Independent.Intakenext100.P93.noiseThreshold

For every function R:R→RR:\mathbb R\to\mathbb RR:R→R, with no continuity, monotonicity, or sign assumption, this defines

noiseThreshold⁡(R)=sup⁡({0}∪{p∈R:0≤p≤3/4 and R(p)>0}).\operatorname{noiseThreshold}(R) =\sup\left(\{0\}\cup\{p\in\mathbb R:0\le p\le 3/4\ \text{and}\ R(p)>0\}\right).noiseThreshold(R)=sup({0}∪{p∈R:0≤p≤3/4 and R(p)>0}).

Thus 000 is included regardless of R(0)R(0)R(0), both endpoints of the search interval are permitted, and strict positivity of R(p)R(p)R(p) is required for membership through the second set. The supremum is 000 if that second set is empty; it need not itself be a point where RRR is positive.

QAlgorithms.Papers.Independent.Intakenext100.P93.orderedPauli

For every natural number mmm and Boolean words u,vu,vu,v of length mmm, this defines a complex matrix Pu,vP_{u,v}Pu,v​ with rows and columns indexed by Boolean words x,yx,yx,y of length mmm, whose entries are

Pu,v(x,y)={(−1)∑i=0m−1viyi,x=y⊕u,0,x≠y⊕u.P_{u,v}(x,y)= \begin{cases} (-1)^{\sum_{i=0}^{m-1}v_i y_i},&x=y\oplus u,\\ 0,&x\ne y\oplus u. \end{cases}Pu,v​(x,y)={(−1)∑i=0m−1​vi​yi​,0,​x=y⊕u,x=y⊕u.​

Here bits are interpreted as 000 or 111, and exclusive-or is applied coordinatewise. Equivalently, its action on a vector ψ\psiψ has amplitude (−1)∑ivi(xi⊕ui)ψ(x⊕u)(-1)^{\sum_i v_i(x_i\oplus u_i)}\psi(x\oplus u)(−1)∑i​vi​(xi​⊕ui​)ψ(x⊕u) at xxx; the column indexed by yyy is obtained by taking ψ\psiψ to have amplitude 111 at yyy and 000 elsewhere. For m=0m=0m=0, this is the one-by-one matrix with entry 111.

QAlgorithms.Papers.Independent.Intakenext100.P93.pauliErrorWordMass

For any natural number mmm, arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, and Boolean words u,vu,vu,v of length mmm, this defines

∏i=0m−1w(ui,vi),w(0,0)=1−px−py−pz,w(1,0)=px,w(1,1)=py,w(0,1)=pz,\prod_{i=0}^{m-1}w(u_i,v_i), \qquad w(0,0)=1-p_x-p_y-p_z,\quad w(1,0)=p_x,\quad w(1,1)=p_y,\quad w(0,1)=p_z,i=0∏m−1​w(ui​,vi​),w(0,0)=1−px​−py​−pz​,w(1,0)=px​,w(1,1)=py​,w(0,1)=pz​,

where 000 and 111 denote false and true. No restrictions on the real parameters are imposed. When m=0m=0m=0, both words are empty and the empty product is 111.

QAlgorithms.Papers.Independent.Intakenext100.P93.pauliMass

For arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​ and Boolean values u,vu,vu,v, this defines the real number

w(u,v)={1−px−py−pz,(u,v)=(false,false),px,(u,v)=(true,false),py,(u,v)=(true,true),pz,(u,v)=(false,true).w(u,v)= \begin{cases} 1-p_x-p_y-p_z,&(u,v)=(\mathrm{false},\mathrm{false}),\\ p_x,&(u,v)=(\mathrm{true},\mathrm{false}),\\ p_y,&(u,v)=(\mathrm{true},\mathrm{true}),\\ p_z,&(u,v)=(\mathrm{false},\mathrm{true}). \end{cases}w(u,v)=⎩⎨⎧​1−px​−py​−pz​,px​,py​,pz​,​(u,v)=(false,false),(u,v)=(true,false),(u,v)=(true,true),(u,v)=(false,true).​

There are no nonnegativity or normalization hypotheses on the parameters; in particular, these values may be negative.

QAlgorithms.Papers.Independent.Intakenext100.P93.syndromeWeightMass

For every natural number kkk, arbitrary real numbers px,py,pzp_x,p_y,p_zpx​,py​,pz​, and natural number rrr, this defines the real sum

∑s∈{0,1}k∣s∣=r ∑u,v∈{0,1}k+1u0⊕uj+1=sj for all j<k∏i=0kquivi,\sum_{\substack{s\in\{0,1\}^k\\|s|=r}} \ \sum_{\substack{u,v\in\{0,1\}^{k+1}\\ u_0\oplus u_{j+1}=s_j\ \text{for all }j<k}} \prod_{i=0}^{k}q_{u_i v_i},s∈{0,1}k∣s∣=r​∑​ u,v∈{0,1}k+1u0​⊕uj+1​=sj​ for all j<k​∑​i=0∏k​qui​vi​​,

where ∣s∣|s|∣s∣ counts the true bits of sss, ⊕\oplus⊕ is exclusive-or, and (q00,q10,q11,q01)=(1−px−py−pz,px,py,pz)(q_{00},q_{10},q_{11},q_{01})=(1-p_x-p_y-p_z,p_x,p_y,p_z)(q00​,q10​,q11​,q01​)=(1−px​−py​−pz​,px​,py​,pz​). Thus it adds the prescribed syndrome masses over precisely the syndromes of weight rrr. No probability assumptions on the parameters are made. If r>kr>kr>k, the sum is empty and equals 000; when k=0k=0k=0, only r=0r=0r=0 selects the unique empty syndrome.

QAlgorithms.Papers.Independent.Intakenext100.P93.twoPauliChannel

For every real ppp, this defines a map on all complex 2×22\times22×2 matrices by

ρ⟼(1−p)ρ+p2XρX†+p2ZρZ†,X=(0110),Z=(100−1),\rho\longmapsto(1-p)\rho+\frac p2X\rho X^\dagger+\frac p2Z\rho Z^\dagger, \qquad X=\begin{pmatrix}0&1\\1&0\end{pmatrix}, \quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},ρ⟼(1−p)ρ+2p​XρX†+2p​ZρZ†,X=(01​10​),Z=(10​0−1​),

with rows and columns ordered by the Boolean values false, true. The definition accepts arbitrary matrices ρ\rhoρ, without positivity or trace assumptions, and arbitrary ppp, including values outside [0,1][0,1][0,1].

QAlgorithms.Papers.Independent.Intakenext100.P93.twoPauliDilation

For every real ppp, this defines a complex matrix UpU_pUp​ with input index c∈{0,1}c\in\{0,1\}c∈{0,1} and output index (b,e)∈{0,1}×{0,1,2}(b,e)\in\{0,1\}\times\{0,1,2\}(b,e)∈{0,1}×{0,1,2} by

Up((b,e),c)={p/2 Xbc,e=0,p/2 Zbc,e=1,1−p δbc,e=2,X=(0110),Z=(100−1).U_p((b,e),c)= \begin{cases} \sqrt{p/2}\,X_{bc},&e=0,\\ \sqrt{p/2}\,Z_{bc},&e=1,\\ \sqrt{1-p}\,\delta_{bc},&e=2, \end{cases} \qquad X=\begin{pmatrix}0&1\\1&0\end{pmatrix}, \quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.Up​((b,e),c)=⎩⎨⎧​p/2​Xbc​,p/2​Zbc​,1−p​δbc​,​e=0,e=1,e=2,​X=(01​10​),Z=(10​0−1​).

The square roots are real square roots, embedded in C\mathbb CC; for a negative argument this total real-square-root operation returns 000. No range assumption on ppp or isometry assertion is part of this definition.

QAlgorithms.Papers.Independent.Intakenext100.P93.xCatEncoder

For every natural number bbb, this defines a complex matrix with rows indexed by binary words yyy of length b+1b+1b+1 and columns indexed by a bit ccc, with entry

Ey,c=∑d∈{0,1}(∏j=0bHyj,d)Hd,c,Ha,d=(−1)ad2,E_{y,c}=\sum_{d\in\{0,1\}} \left(\prod_{j=0}^{b}H_{y_j,d}\right)H_{d,c}, \qquad H_{a,d}=\frac{(-1)^{ad}}{\sqrt2},Ey,c​=d∈{0,1}∑​(j=0∏b​Hyj​,d​)Hd,c​,Ha,d​=2​(−1)ad​,

where bits in exponents are interpreted as 000 or 111. Thus the product uses the same bit ddd at every position before summing over ddd. The case b=0b=0b=0 is included; its matrix is H2=IH^2=IH2=I after identifying a one-bit word with its bit.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me