Definitions for Quantum Channel Capacity of Very Noisy Channels
DefinitionQAlgorithms_Papers_Independent_Support50_P40The objects the formalized statements of Quantum Channel Capacity of Very Noisy Channels (arXiv:quant-ph/9706061) are stated in. Each was checked against the paper by a blind read-back and a moderator.
ErrorLabel: PDF pp.5--7: phase-free physical Pauli labels.labelMul: PDF p.6: multiplication with its scalar phase discarded.noiseG: PDF p.3: each nonidentity Pauli has probability(1-f)/3.weightPolynomial: PDF p.7, Eq.(2): probability polynomial of a set of error labels.slWeight: PDF p.7, Eq.(3), with the Rains normalization used on that page.slEnumerator: PDF p.7, Eq.(4): the Shor--Laflamme generating polynomial.stabilizerLabels: PDF pp.6--8: the label set of a phase-inclusive stabilizer subgroup.centralizerLabels: PDF p.6: the phase-free commutation centralizer of the stabilizer.labelCoset: PDF pp.6--7: a phase-free left coset; the label group is Abelian.InnerCode: PDF pp.6,12: an additive inner code encoding exactly one logical qubit. The valid phase-inclusive stabilizer has no-I. Its2^mdistinct labels meanmindependent generators; the normalized basis spans its full +1 space.innerEncoderMatrix: PDF pp.8--9: the isometric encoder in the selected code basis. This matrix is distinct from the frozen folded classical Vandermonde encoder.CosetChoices: PDF pp.6--8,13: complete transversals, with logical I,X,Y,Z fixed in the same code basis.logicalActionis equality on every logical operator, so it does not mistake a logical Z fixing one vector for the identity channel.syndromeMass: PDF pp.7--8,13, Eq.(18): the coset mass for a syndrome.jointMass: PDF p.13, Eq.(19): joint logical-Pauli/syndrome mass, before conditioning.finiteEntropyBits: PDF p.12, Eq.(16): finite Shannon entropy in bits, with0 log 0 = 0. This takes a finite real mass vector, unlike the frozen quantum/relative entropies.signedYield: PDF p.13, Eq.(20): signed concatenation yield per physical channel use. A negative value is not interpreted as negative operational capacity.conditionalBellEntropy: PDF p.12, Eq.(14): syndrome-conditioned Bell entropy. A zero-mass branch contributes zero without evaluating a conditional distribution.independentPauliChannel: PDF pp.3,7: independent depolarization on a whole physical block. The parameter f is the identity-Pauli fidelity; this is the tensor product of single-qubit channels, not global replacement of the whole block.codeBellInput: PDF pp.9,15, Eqs.(7)--(9),(29): normalized encoded Bell input. The printed1/2coefficients in Eq.(29) are corrected to1/sqrt(2); Eq.(7), the density normalization and Eq.(35) determine the correction. This input uses the selected stabilizer-code basis, rather than a dense-coding label.outputRQ: PDF pp.13--15: the actual output on RQ, with noiseless reference R.outputQ: PDF pp.14--15: the actual output on Q, obtained by tracing out R.errorBasis: PDF p.14, Eq.(24): the error-space code basis.bellBasis: PDF p.15, Eq.(30): the generalized normalized Bell basis, with the same syndrome and logical representatives used in the probabilities.syndromeProjector: PDF pp.8--9: the syndrome-space projector.recoveredBranch: PDF pp.9,13: unnormalized logical output for syndrome i after its specified correction; no division by a possibly zero syndrome probability.errorEventMass: PDF pp.7--8: mass of an event in the actual independent Pauli error law.blockEncoder: PDF pp.10--12: tensor product of the fixed inner encoder on n blocks.IsAdditiveEncoder: PDF pp.10--12: an outer additive encoder. The full image, not merely its basis vectors, is the stabilizer code; the isometry preserves all inputs.FixedInnerAchievable: PDF pp.3,10--12,28: attainability by the fixed-inner/additive-outer scheme. The inner block is fixed before n tends to infinity. One encoder and decoder works for every normalized unknown input, and its Bell-pair fidelity also tends to one. Only the physical noise and local CPTP decoding occur: no preshared entanglement or communication side channel is provided. Outer encoders can be selected by the source's random-code existence argument.catEncoder: PDF p.16, Eqs.(32)--(33): the ordinary cat encoder, including p=1.catSpace: PDF p.16: the full cat code space, not a single cat vector.amplitudeBit: PDF pp.2--3,17: the amplitude-error bit of a Pauli.phaseBit: PDF pp.2--3,17: the phase-error bit of a Pauli.catSyndrome: PDF pp.16--17, Fig.7: the measured CNOT-decoder syndrome.catLogical: PDF p.17: residual Pauli after the CNOT cat decoder. Bool addition is xor. The phase bit is the parity of all physical phase-error bits.catJoint: PDF pp.17--18, Eqs.(36)--(39): joint mass of one specified syndrome and logical outcome, computed from the error law rather than from the claimed formula.catSyndromeMass: PDF p.12, Eq.(15): the marginal mass of one specified cat syndrome.catYield: PDF pp.12--13,17--18: signed cat yield, with each syndrome counted separately.catClosedMass: PDF pp.17--18, Eqs.(36)--(39): closed formula for one syndrome of weight r. Its use in the theorem is restricted to r at most m.positivityThreshold: PDF pp.18--19,25,31: high-fidelity positivity threshold of a signed yield. For the codes in the theorems the set contains 1 and lies in [3/4,1], so this real infimum is neither empty nor unbounded.catThreshold: PDF pp.18--19,25: threshold for block sizem+1.rotatedFive: PDF p.19, Eq.(43): the rotated cat module reverses both physical and logical amplitude/phase axes,H^(tensor 5) V_cat H. The logical H is needed when concatenating with the next ordinary cat encoder.fiveInFive: PDF p.19: ordinary five-cat first at encoding, then a rotated five-cat on each of its five outputs. Flattening has physical wire5*block+within. This fixes the inner 25-qubit code, rather than allowing an unrelated code witness.singleZ: PDF p.20: a single physical phase error on the specified wire.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_QECC
import Definitions.Def_QAlgorithms_Defs_Ensemble
/-!
Statements from DiVincenzo--Shor--Smolin, arXiv:quant-ph/9706061v3.
PDF page numbers refer to the supplied 31-page original. All new definitions
are local to this paper. In `InnerCode m` the physical block size is `m + 1`;
this includes the identity code (`m = 0`) and excludes an empty physical block.
-/
namespace QAlgorithms.Papers.Independent.Support50.P40
open QAlgorithms QAlgorithms.Stabilizer
open scoped ComplexConjugate Matrix
noncomputable section
/-- PDF pp.5--7: phase-free physical Pauli labels. -/
abbrev ErrorLabel (p : ℕ) := Fin p → Pauli
/-- PDF p.6: multiplication with its scalar phase discarded. -/
def labelMul {p : ℕ} (a b : ErrorLabel p) : ErrorLabel p :=
fun q => (Pauli.mul (a q) (b q)).2
/-- PDF p.3: each nonidentity Pauli has probability `(1-f)/3`. -/
def noiseG (f : ℝ) : ℝ := (1 - f) / 3
/-- PDF p.7, Eq.(2): probability polynomial of a set of error labels. -/
def weightPolynomial {p : ℕ} (f : ℝ) (C : Finset (ErrorLabel p)) : ℝ :=
∑ e ∈ C, f ^ (p - opsWeight e) * noiseG f ^ opsWeight e
/-- PDF p.7, Eq.(3), with the Rains normalization used on that page. -/
def slWeight {p : ℕ} (d : ℕ) (O1 O2 : Matrix (Qubits p) (Qubits p) ℂ) : ℂ :=
∑ e ∈ Finset.univ.filter (fun e : ErrorLabel p => opsWeight e = d),
(pauliOps e * O1).trace * (pauliOps e * O2).trace
/-- PDF p.7, Eq.(4): the Shor--Laflamme generating polynomial. -/
def slEnumerator {p : ℕ} (z : ℂ) (O1 O2 : Matrix (Qubits p) (Qubits p) ℂ) : ℂ :=
∑ d ∈ Finset.range (p + 1), slWeight d O1 O2 * z ^ d
/-- PDF pp.6--8: the label set of a phase-inclusive stabilizer subgroup. -/
def stabilizerLabels {p : ℕ} (S : Subgroup (Matrix.unitaryGroup (Qubits p) ℂ)) :
Finset (ErrorLabel p) := by
classical
exact Finset.univ.filter fun e => ∃ U ∈ S, ∃ c : ZMod 4,
pauliOps e = Complex.I ^ c.val • (U : Matrix (Qubits p) (Qubits p) ℂ)
/-- PDF p.6: the phase-free commutation centralizer of the stabilizer. -/
def centralizerLabels {p : ℕ} (S : Subgroup (Matrix.unitaryGroup (Qubits p) ℂ)) :
Finset (ErrorLabel p) := by
classical
exact Finset.univ.filter fun e => ∀ U ∈ S,
pauliOps e * (U : Matrix (Qubits p) (Qubits p) ℂ) =
(U : Matrix (Qubits p) (Qubits p) ℂ) * pauliOps e
/-- PDF pp.6--7: a phase-free left coset; the label group is Abelian. -/
def labelCoset {p : ℕ} (e : ErrorLabel p) (A : Finset (ErrorLabel p)) :
Finset (ErrorLabel p) := by
classical
exact A.image (labelMul e)
/-- PDF pp.6,12: an additive inner code encoding exactly one logical qubit.
The valid phase-inclusive stabilizer has no `-I`. Its `2^m` distinct labels
mean `m` independent generators; the normalized basis spans its full +1 space. -/
structure InnerCode (m : ℕ) where
stabilizer : Subgroup (Matrix.unitaryGroup (Qubits (m + 1)) ℂ)
valid : IsStabilizerGroup stabilizer
labelCount : (stabilizerLabels stabilizer).card = 2 ^ m
basis : Bool → EuclideanSpace ℂ (Qubits (m + 1))
orthonormal : Orthonormal ℂ basis
basisSpan : Submodule.span ℂ (Set.range basis) = stabilizedSpace stabilizer
/-- PDF pp.8--9: the isometric encoder in the selected code basis.
This matrix is distinct from the frozen folded classical Vandermonde encoder. -/
def innerEncoderMatrix {m : ℕ} (C : InnerCode m) : Matrix (Qubits (m + 1)) Bool ℂ :=
fun x b => C.basis b x
/-- PDF pp.6--8,13: complete transversals, with logical I,X,Y,Z fixed in
the same code basis. `logicalAction` is equality on every logical operator,
so it does not mistake a logical Z fixing one vector for the identity channel. -/
structure CosetChoices {m : ℕ} (C : InnerCode m) where
syndromeRep : Qubits m → ErrorLabel (m + 1)
logicalRep : Pauli → ErrorLabel (m + 1)
syndromeZero : syndromeRep (fun _ => false) = fun _ => Pauli.I
logicalIdentity : logicalRep .I = fun _ => Pauli.I
syndromeTransversal : ∀ e : ErrorLabel (m + 1), ∃! i : Qubits m,
e ∈ labelCoset (syndromeRep i) (centralizerLabels C.stabilizer)
logicalCentralizes : ∀ j, logicalRep j ∈ centralizerLabels C.stabilizer
logicalTransversal : ∀ e ∈ centralizerLabels C.stabilizer, ∃! j : Pauli,
e ∈ labelCoset (logicalRep j) (stabilizerLabels C.stabilizer)
logicalAction : ∀ j, ∀ rho : Matrix Bool Bool ℂ,
conjSuperop (pauliOps (logicalRep j)) (conjSuperop (innerEncoderMatrix C) rho) =
conjSuperop (innerEncoderMatrix C) (conjSuperop j.mat rho)
/-- PDF pp.7--8,13, Eq.(18): the coset mass for a syndrome. -/
def syndromeMass {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (f : ℝ)
(i : Qubits m) : ℝ :=
weightPolynomial f (labelCoset (T.syndromeRep i) (centralizerLabels C.stabilizer))
/-- PDF p.13, Eq.(19): joint logical-Pauli/syndrome mass, before conditioning. -/
def jointMass {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (f : ℝ)
(i : Qubits m) (j : Pauli) : ℝ :=
weightPolynomial f (labelCoset (labelMul (T.syndromeRep i) (T.logicalRep j))
(stabilizerLabels C.stabilizer))
/-- PDF p.12, Eq.(16): finite Shannon entropy in bits, with `0 log 0 = 0`.
This takes a finite real mass vector, unlike the frozen quantum/relative entropies. -/
def finiteEntropyBits {A : Type*} [Fintype A] (a : A → ℝ) : ℝ :=
-∑ x, a x * Real.logb 2 (a x)
/-- PDF p.13, Eq.(20): signed concatenation yield per physical channel use.
A negative value is not interpreted as negative operational capacity. -/
def signedYield {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (f : ℝ) : ℝ :=
(1 + finiteEntropyBits (syndromeMass C T f) -
finiteEntropyBits (fun ij : Qubits m × Pauli => jointMass C T f ij.1 ij.2)) / (m + 1)
/-- PDF p.12, Eq.(14): syndrome-conditioned Bell entropy. A zero-mass
branch contributes zero without evaluating a conditional distribution. -/
def conditionalBellEntropy {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (f : ℝ) : ℝ :=
∑ i : Qubits m, if syndromeMass C T f i = 0 then 0 else
syndromeMass C T f i * finiteEntropyBits (fun j : Pauli => jointMass C T f i j / syndromeMass C T f i)
/-- PDF pp.3,7: independent depolarization on a whole physical block.
The parameter f is the identity-Pauli fidelity; this is the tensor product of
single-qubit channels, not global replacement of the whole block. -/
def independentPauliChannel (p : ℕ) (f : ℝ) : Superop (Qubits p) (Qubits p) :=
fun rho => ∑ e : ErrorLabel p,
((f ^ (p - opsWeight e) * noiseG f ^ opsWeight e : ℝ) : ℂ) •
conjSuperop (pauliOps e) rho
/-- PDF pp.9,15, Eqs.(7)--(9),(29): normalized encoded Bell input.
The printed `1/2` coefficients in Eq.(29) are corrected to `1/sqrt(2)`;
Eq.(7), the density normalization and Eq.(35) determine the correction.
This input uses the selected stabilizer-code basis, rather than a dense-coding label. -/
def codeBellInput {m : ℕ} (C : InnerCode m) : EuclideanSpace ℂ (Bool × Qubits (m + 1)) :=
((Real.sqrt 2)⁻¹ : ℂ) •
(tensorVec (ket false) (C.basis false) + tensorVec (ket true) (C.basis true))
/-- PDF pp.13--15: the actual output on RQ, with noiseless reference R. -/
def outputRQ {m : ℕ} (C : InnerCode m) (f : ℝ) :
Matrix (Bool × Qubits (m + 1)) (Bool × Qubits (m + 1)) ℂ :=
idTensorSuperop (R := Bool) (independentPauliChannel (m + 1) f) (pureDensity (codeBellInput C))
/-- PDF pp.14--15: the actual output on Q, obtained by tracing out R. -/
def outputQ {m : ℕ} (C : InnerCode m) (f : ℝ) :
Matrix (Qubits (m + 1)) (Qubits (m + 1)) ℂ :=
traceLeft (outputRQ C f)
/-- PDF p.14, Eq.(24): the error-space code basis. -/
def errorBasis {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (i : Qubits m) (b : Bool) :
EuclideanSpace ℂ (Qubits (m + 1)) :=
act (pauliOps (T.syndromeRep i)) (C.basis b)
/-- PDF p.15, Eq.(30): the generalized normalized Bell basis, with the
same syndrome and logical representatives used in the probabilities. -/
def bellBasis {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (i : Qubits m) (j : Pauli) :
EuclideanSpace ℂ (Bool × Qubits (m + 1)) :=
act (Matrix.kronecker (1 : Matrix Bool Bool ℂ)
(pauliOps (labelMul (T.syndromeRep i) (T.logicalRep j)))) (codeBellInput C)
/-- PDF pp.8--9: the syndrome-space projector. -/
def syndromeProjector {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (i : Qubits m) :
Matrix (Qubits (m + 1)) (Qubits (m + 1)) ℂ :=
∑ b : Bool, pureDensity (errorBasis C T i b)
/-- PDF pp.9,13: unnormalized logical output for syndrome i after its
specified correction; no division by a possibly zero syndrome probability. -/
def recoveredBranch {m : ℕ} (C : InnerCode m) (T : CosetChoices C) (f : ℝ) (i : Qubits m) :
Superop Bool Bool :=
conjSuperop ((innerEncoderMatrix C)ᴴ * (pauliOps (T.syndromeRep i))ᴴ) ∘
independentPauliChannel (m + 1) f ∘ conjSuperop (innerEncoderMatrix C)
/-- PDF pp.7--8: mass of an event in the actual independent Pauli error law. -/
def errorEventMass {p : ℕ} (f : ℝ) (P : ErrorLabel p → Prop) : ℝ := by
classical
exact weightPolynomial f (Finset.univ.filter P)
/-- PDF pp.10--12: tensor product of the fixed inner encoder on n blocks. -/
def blockEncoder {m : ℕ} (C : InnerCode m) (n : ℕ) :
Matrix (Fin n → Qubits (m + 1)) (Qubits n) ℂ :=
fun y x => ∏ i, innerEncoderMatrix C (y i) (x i)
/-- PDF pp.10--12: an outer additive encoder. The full image, not merely
its basis vectors, is the stabilizer code; the isometry preserves all inputs. -/
def IsAdditiveEncoder {n k : ℕ} (E : Matrix (Qubits n) (Qubits k) ℂ) : Prop :=
k ≤ n ∧ Eᴴ * E = 1 ∧
∃ S : Subgroup (Matrix.unitaryGroup (Qubits n) ℂ),
IsStabilizerGroup S ∧ LinearMap.range (Matrix.toEuclideanLin E) = stabilizedSpace S
/-- PDF pp.3,10--12,28: attainability by the fixed-inner/additive-outer
scheme. The inner block is fixed before n tends to infinity. One encoder
and decoder works for every normalized unknown input, and its Bell-pair
fidelity also tends to one. Only the physical noise and local CPTP decoding
occur: no preshared entanglement or communication side channel is provided.
Outer encoders can be selected by the source's random-code existence argument. -/
def FixedInnerAchievable {m : ℕ} (C : InnerCode m) (f R : ℝ) : Prop :=
∀ epsilon > (0 : ℝ), ∀ delta > (0 : ℝ), ∃ n0 : ℕ, ∀ n ≥ n0,
∃ k : ℕ, (R - delta) * ((m + 1) * n : ℕ) ≤ (k : ℝ) ∧
∃ E : Matrix (Qubits n) (Qubits k) ℂ, IsAdditiveEncoder E ∧
∃ D : Superop (Fin n → Qubits (m + 1)) (Qubits k), IsChannel D ∧
let transmission := D ∘ piSuperop (fun _ : Fin n => independentPauliChannel (m + 1) f) ∘
conjSuperop (blockEncoder C n) ∘ conjSuperop E
1 - epsilon ≤ entanglementFidelity transmission ∧
∀ psi : EuclideanSpace ℂ (Qubits k), IsState psi →
1 - epsilon ≤ effectProb (pureDensity psi) (transmission (pureDensity psi))
/-- PDF p.16, Eqs.(32)--(33): the ordinary cat encoder, including p=1. -/
def catEncoder (m : ℕ) : Matrix (Qubits (m + 1)) Bool ℂ :=
fun x b => if x = (fun _ => b) then 1 else 0
/-- PDF p.16: the full cat code space, not a single cat vector. -/
def catSpace (m : ℕ) : Submodule ℂ (EuclideanSpace ℂ (Qubits (m + 1))) :=
Submodule.span ℂ (Set.range fun b : Bool => ket (fun _ : Fin (m + 1) => b))
/-- PDF pp.2--3,17: the amplitude-error bit of a Pauli. -/
def amplitudeBit : Pauli → Bool
| .I => false
| .X => true
| .Y => true
| .Z => false
/-- PDF pp.2--3,17: the phase-error bit of a Pauli. -/
def phaseBit : Pauli → Bool
| .I => false
| .X => false
| .Y => true
| .Z => true
/-- PDF pp.16--17, Fig.7: the measured CNOT-decoder syndrome. -/
def catSyndrome {m : ℕ} (e : ErrorLabel (m + 1)) : Qubits m :=
fun q => amplitudeBit (e q.succ) + amplitudeBit (e 0)
/-- PDF p.17: residual Pauli after the CNOT cat decoder. Bool addition
is xor. The phase bit is the parity of all physical phase-error bits. -/
def catLogical {m : ℕ} (e : ErrorLabel (m + 1)) : Pauli :=
pauliOfBits (amplitudeBit (e 0)) (∑ q, phaseBit (e q))
/-- PDF pp.17--18, Eqs.(36)--(39): joint mass of one specified syndrome
and logical outcome, computed from the error law rather than from the claimed formula. -/
def catJoint (m : ℕ) (f : ℝ) (i : Qubits m) (j : Pauli) : ℝ :=
errorEventMass f (fun e : ErrorLabel (m + 1) => catSyndrome e = i ∧ catLogical e = j)
/-- PDF p.12, Eq.(15): the marginal mass of one specified cat syndrome. -/
def catSyndromeMass (m : ℕ) (f : ℝ) (i : Qubits m) : ℝ :=
∑ j : Pauli, catJoint m f i j
/-- PDF pp.12--13,17--18: signed cat yield, with each syndrome counted separately. -/
def catYield (m : ℕ) (f : ℝ) : ℝ :=
(1 + finiteEntropyBits (catSyndromeMass m f) -
finiteEntropyBits (fun ij : Qubits m × Pauli => catJoint m f ij.1 ij.2)) / (m + 1)
/-- PDF pp.17--18, Eqs.(36)--(39): closed formula for one syndrome of
weight r. Its use in the theorem is restricted to r at most m. -/
def catClosedMass (m : ℕ) (f : ℝ) (r : ℕ) : Pauli → ℝ
| .X | .Y => (2 : ℝ) ^ (m + 1 - r - 1) * noiseG f ^ (m + 1 - r) * (f + noiseG f) ^ r
| .I => if r = 0 then ((f + noiseG f) ^ (m + 1) + (f - noiseG f) ^ (m + 1)) / 2
else (2 : ℝ) ^ (r - 1) * noiseG f ^ r * (f + noiseG f) ^ (m + 1 - r)
| .Z => if r = 0 then ((f + noiseG f) ^ (m + 1) - (f - noiseG f) ^ (m + 1)) / 2
else (2 : ℝ) ^ (r - 1) * noiseG f ^ r * (f + noiseG f) ^ (m + 1 - r)
/-- PDF pp.18--19,25,31: high-fidelity positivity threshold of a signed yield.
For the codes in the theorems the set contains 1 and lies in [3/4,1],
so this real infimum is neither empty nor unbounded. -/
def positivityThreshold (q : ℝ → ℝ) : ℝ :=
sInf {f : ℝ | (3 / 4 : ℝ) ≤ f ∧ f ≤ 1 ∧ 0 < q f}
/-- PDF pp.18--19,25: threshold for block size `m+1`. -/
def catThreshold (m : ℕ) : ℝ := positivityThreshold (catYield m)
/-- PDF p.19, Eq.(43): the rotated cat module reverses both physical
and logical amplitude/phase axes, `H^(tensor 5) V_cat H`. The logical H is
needed when concatenating with the next ordinary cat encoder. -/
def rotatedFive : Matrix (Qubits 5) Bool ℂ :=
fun x b => ∑ a : Bool, (∏ q : Fin 5, hadamard (x q) a) * hadamard a b
/-- PDF p.19: ordinary five-cat first at encoding, then a rotated five-cat
on each of its five outputs. Flattening has physical wire `5*block+within`.
This fixes the inner 25-qubit code, rather than allowing an unrelated code witness. -/
def fiveInFive : Matrix (Qubits 25) Bool ℂ :=
fun x b => ∏ a : Fin 5,
rotatedFive (fun q : Fin 5 => x ⟨5 * a.val + q.val, by omega⟩) b
/-- PDF p.20: a single physical phase error on the specified wire. -/
def singleZ {p : ℕ} (a : Fin p) : Matrix (Qubits p) (Qubits p) ℂ :=
pauliOps (fun q => if q = a then Pauli.Z else Pauli.I)
/-! Small, proved normalization and convention checks for the local definitions. -/
example : noiseG 1 = 0 := by norm_num [noiseG]
example (f : ℝ) : weightPolynomial f (∅ : Finset (ErrorLabel 1)) = 0 := by
simp [weightPolynomial]
example (f : ℝ) : weightPolynomial f ({fun _ : Fin 1 => Pauli.I} : Finset (ErrorLabel 1)) = f := by
simp [weightPolynomial, opsWeight]
example (a b : Pauli) (q : Fin 1) :
labelMul (fun _ => a) (fun _ => b) q = (Pauli.mul a b).2 := rfl
example : amplitudeBit .Y = true ∧ phaseBit .Y = true := ⟨rfl, rfl⟩
example (x : Qubits 1) (b : Bool) : catEncoder 0 x b =
if x = (fun _ => b) then 1 else 0 := rfl
example (e : ErrorLabel 1) : catSyndrome (m := 0) e = (fun q => Fin.elim0 q) := by
funext q
exact Fin.elim0 q
example (a : Unit → ℝ) : finiteEntropyBits a = -(a () * Real.logb 2 (a ())) := by
simp [finiteEntropyBits]
example {m : ℕ} (C : InnerCode m) (x : Fin 0 → Qubits (m + 1)) (b : Qubits 0) :
blockEncoder C 0 x b = 1 := by simp [blockEncoder]
end
end QAlgorithms.Papers.Independent.Support50.P40
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Support50.P40.CosetChoices
For every natural number and supplied inner code , let be its subgroup and its matrix of basis columns. The supplied code requires that be a commutative subgroup of the unitary matrices on , contained in the subgroup generated by phase multiples of Pauli tensor products and excluding the negative identity; that exactly labels satisfy for some and ; and that the two vectors be orthonormal and span the common fixed space of . Here denotes the tensor product selected by from the standard matrices , with . Define the sets of labels
This structure supplies functions and with these properties: and are both the all- label; every label has exactly one index such that ; every belongs to ; every has exactly one such that ; and, for every and every complex matrix ,
The operation multiplies labels position by position with phases discarded: is an identity, each nonidentity label squares to , and two distinct nonidentity labels multiply to the third. The matrix is arbitrary, with no positivity or trace assumption. The case is included, when the syndrome index set has one element.
QAlgorithms.Papers.Independent.Support50.P40.ErrorLabel
For every natural number , an error label of length is a function from to the four labels . Thus it specifies one Pauli label at each position. When , there is exactly one error label, the empty function.
QAlgorithms.Papers.Independent.Support50.P40.FixedInnerAchievable
For every natural number , inner code , and real numbers , this predicate has the following meaning. Put , let denote the standard Pauli matrices, and write and . The code supplies an abelian subgroup of the unitary group on qubits, contained in the subgroup generated by scalar-phase Pauli strings and excluding ; exactly labels agree up to a power of with an element of ; and an orthonormal pair spans its common fixed space. Define , , and
For every real and every real , there must exist a natural number such that, for every natural number , there exist a natural number , a matrix , and a function from matrices on tuples of length- Boolean strings to matrices on length- Boolean strings, satisfying
Moreover, the range of must be the common fixed space of some abelian subgroup of the -qubit unitary group contained in the subgroup generated by scalar-phase Pauli strings and excluding . The function must admit a finite Kraus representation: for some natural number and matrices , and for every matrix . Define
where the product extension used here is explicitly
Writing , the two required inequalities are
and, for every complex vector on length- strings with ,
The identity extension in the first inequality applies to each block indexed by the two reference-register indices. No restriction on or is included. The values , , and are permitted; if is among the required block lengths, its products are empty products, its tuple indexing sets are singletons, and forces .
QAlgorithms.Papers.Independent.Support50.P40.InnerCode
For every natural number , this structure consists of a subgroup of the unitary matrices indexed by and two vectors , indexed by , together with the following properties: lies in the subgroup generated by all matrices , where and is a tensor product of standard identity or Pauli matrices; every two elements of commute; no element of equals the negative identity; exactly labels satisfy for some and ; the vectors are orthonormal; and their complex linear span is precisely
The standard factor is . The parameter may be zero, in which case the vectors are indexed by one-bit strings and the required label count is one.
QAlgorithms.Papers.Independent.Support50.P40.IsAdditiveEncoder
For every pair of natural numbers and complex matrix with rows indexed by length- Boolean strings and columns indexed by length- Boolean strings, this predicate means that , , and there exists a subgroup of the unitary group on such that is contained in the subgroup generated by all matrices , where and ; every two elements of commute; no element of is the matrix ; and
Both and are permitted; a zero-qubit space is one-dimensional.
QAlgorithms.Papers.Independent.Support50.P40.amplitudeBit
This defines a function from the four Pauli labels to Booleans, assigning false to and , and true to and .
QAlgorithms.Papers.Independent.Support50.P40.bellBasis
For every natural number , including , set . For labels , write , and let mean coordinatewise Pauli multiplication after discarding phases. The code provides a commuting subgroup of the group generated by , excluding , and orthonormal vectors spanning its common fixed space. Set and ; is required. The choices provide for and for , with and the all-identity label, such that each label belongs to for exactly one , every , and each element of belongs to for exactly one . Writing for the matrix with columns , they additionally satisfy for every complex matrix . For each syndrome and Pauli , the returned vector is
or, in coordinates,
Here is the coordinate unit vector at ; the matrix uses the phase-discarded product label . The case has one syndrome index.
QAlgorithms.Papers.Independent.Support50.P40.blockEncoder
For every natural number , inner code , and natural number , this defines a complex matrix whose rows are tuples of length- Boolean strings and whose columns are length- Boolean strings . Here consists of an abelian subgroup of the unitary group on length- strings, contained in the subgroup generated by all scalar-phase Pauli strings , and excluding ; exactly Pauli labels agree up to a power of with an element of ; and an orthonormal pair spans the space of vectors fixed by every element of . Its matrix entry is
The case is included. When , both indexing sets are singletons and the sole entry is the empty product .
QAlgorithms.Papers.Independent.Support50.P40.catClosedMass
For every pair of natural numbers and every real number , set . This defines a real-valued function on the four Pauli labels by
Every subtraction in an exponent is natural-number subtraction, truncated at ; in particular, the first exponent is obtained by first truncating and then subtracting with truncation. There is no assumption that , that , or that . Powers with exponent , including , equal .
QAlgorithms.Papers.Independent.Support50.P40.catEncoder
For every natural number , this defines a complex matrix with rows indexed by length- Boolean strings and columns indexed by a Boolean , whose entry is precisely when every coordinate of equals , and is otherwise. Thus its two columns are the coordinate unit vectors at the all-false and all-true strings, respectively. The case gives the identity matrix indexed by a single Boolean coordinate.
QAlgorithms.Papers.Independent.Support50.P40.catJoint
For every natural number , real number , length- Boolean string , and Pauli label , this defines the real number
where , the Boolean coordinate is the exclusive-or of the assertions and , and is determined by the two bits and , using , , , and . There is no restriction on , so the sum need not have nonnegative summands; an empty selected set gives zero. For , is the empty string, and the value is for and for each of .
QAlgorithms.Papers.Independent.Support50.P40.catLogical
For every natural number and Pauli-label string , this defines a Pauli label from two Boolean bits: is true exactly when , and is true exactly when the number of coordinates with is odd. The output is for , respectively. When , the output is .
QAlgorithms.Papers.Independent.Support50.P40.catSpace
For every natural number , this defines the complex linear subspace of vectors indexed by length- Boolean strings spanned by the two coordinate unit vectors at the all-false and all-true strings:
Each displayed ket has entry at its indicated string and elsewhere. The case is included and gives the entire one-qubit vector space.
QAlgorithms.Papers.Independent.Support50.P40.catSyndrome
For every natural number and Pauli-label string , this defines a length- Boolean string whose coordinate , for , is
where each indicator is a Boolean and is exclusive-or. Thus is true exactly when precisely one of and belongs to . When , the result is the unique empty Boolean string.
QAlgorithms.Papers.Independent.Support50.P40.catSyndromeMass
For every natural number , real number , and Boolean string of length , this defines
Here, for a Pauli label string , let be the number of its entries unequal to , and assign the bit pairs , , , and , writing these bits as and . Its syndrome is the length- string with entry modulo , and its logical label is the Pauli with bit pair , again modulo . The quantity is the sum of
over precisely those strings whose syndrome is and whose logical label is . There is no restriction on , so the summands need not be nonnegative. The definition includes , when is the unique empty string.
QAlgorithms.Papers.Independent.Support50.P40.catThreshold
For every natural number , this defines
The array is indexed by a length- Boolean string and a Pauli label , and . To define , assign the bit pairs , , , , denoted by . For a length- Pauli string , let count its nonidentity entries; its syndrome has entries modulo , and its logical label has bit pair modulo . Then sums over strings having syndrome and logical label . The two entropy sums range over all , and all , respectively; a zero entry contributes under the total logarithm convention. The definition includes . It does not assert that the displayed positivity set is nonempty or that its infimum is attained; if that set is empty, the defined value is .
QAlgorithms.Papers.Independent.Support50.P40.catYield
For every natural number and real number , this defines
where the entropy sums run respectively over all length- Boolean strings and over all pairs consisting of such a string and a Pauli label. Explicitly, assign the bit pairs , , , , denoted by . For each length- Pauli string , let count its nonidentity entries, let its syndrome have entries modulo , and let its logical label have bit pair modulo . Then is the sum of over strings with syndrome and logical label , and . The logarithm is Lean’s total real logarithm to base : it is at and equals at nonzero ; consequently a zero entry contributes . No assumption requires or these arrays to be probability distributions. The denominator is always positive, including at , when it equals .
QAlgorithms.Papers.Independent.Support50.P40.centralizerLabels
For every natural number and every subgroup of the unitary matrices on the complex vector space indexed by , this defines the finite set of labels satisfying
where the factors are the standard identity and Pauli matrices, with . The subgroup need not be commutative or consist of Pauli matrices. For , the unique empty label belongs to this set.
QAlgorithms.Papers.Independent.Support50.P40.codeBellInput
For every natural number , including , the input code has a commuting subgroup of the group generated by all phased Pauli tensor products , where and , with . Exactly distinct labels have for some such and some . The code also supplies orthonormal vectors in the complex Euclidean space indexed by -bit strings, whose span is precisely the space fixed by every element of . The definition returns the vector indexed by given by
Here is the vector equal to at and elsewhere, and the tensor product has coordinates . At , the code vectors are indexed by one-bit strings.
QAlgorithms.Papers.Independent.Support50.P40.conditionalBellEntropy
For every natural number , including , set . A label represents and has weight ; denotes coordinatewise Pauli multiplication with phases discarded. The code supplies a commuting subgroup of the group generated by , excluding , and orthonormal vectors spanning its common fixed space. Define and ; is required. The choices supply labels for and for , with and the all-identity label, so that every label belongs to for exactly one , each , and every element of belongs to for exactly one . Writing for the matrix with columns , they also require for all complex matrices . For any real , put
using distinct-label sums, and let , where for and . The definition assigns
Thus every zero-mass syndrome contributes zero regardless of its joint values. The parameter is unrestricted, and the sum includes the single empty syndrome when .
QAlgorithms.Papers.Independent.Support50.P40.errorBasis
For every natural number , including , put . Labels are tuples , representing , and denotes coordinatewise Pauli multiplication with phases discarded. The code supplies a commuting subgroup of the group generated by , excluding , and orthonormal vectors spanning its common fixed space. Define and ; the code requires . The choices supply syndrome labels , , and logical labels , , with the all-identity label, such that each label belongs to for exactly one , each , and each element of belongs to for exactly one . With having columns , they satisfy for every complex matrix . For each syndrome and Boolean , the definition returns the vector
When , the syndrome index is the empty tuple.
QAlgorithms.Papers.Independent.Support50.P40.errorEventMass
For every natural number , real number , and predicate on length- strings of Pauli labels , this defines the real number
There is no restriction on , so the summands need not be nonnegative. An empty selected set gives zero. For , there is one empty string, and the value is if that string satisfies , and otherwise; powers with exponent zero equal , including .
QAlgorithms.Papers.Independent.Support50.P40.finiteEntropyBits
For any type equipped with a finite enumeration, including the empty type, and any function , the definition assigns
Here describes the total real base-two logarithm used in the definition. No nonnegativity or normalization assumption is imposed on . Zero entries contribute zero, and the value for an empty index type is zero.
QAlgorithms.Papers.Independent.Support50.P40.fiveInFive
This defines a complex matrix whose rows are Boolean strings of length and whose columns are Boolean values , with entries
All factors are regarded as complex numbers. The five factors use the consecutive blocks of coordinates , , , , and , and every factor uses the same column bit .
QAlgorithms.Papers.Independent.Support50.P40.independentPauliChannel
For every natural number , including , and every real , this definition gives a function from complex matrices indexed by -bit strings to matrices with the same indices. For each label , let be the number of its nonidentity entries and , using the usual Pauli matrices. On every complex matrix , the function is
with each real coefficient regarded as a complex scalar. No restriction on or on is imposed. Since , the natural-number subtraction in the exponent equals the ordinary nonnegative difference. For , there is one empty label, its tensor product is the identity on the one-dimensional space indexed by the empty bit string, and the function is the identity.
QAlgorithms.Papers.Independent.Support50.P40.innerEncoderMatrix
For every natural number and every supplied inner code , this defines the complex matrix with rows and columns by
where is the corresponding basis vector stored in . The supplied code includes a subgroup of the unitary matrices that lies in the subgroup generated by phase multiples of tensor products of standard Pauli matrices, is commutative, and excludes the negative identity; exactly labels satisfy for some and . Its two stored vectors are orthonormal and span exactly the vectors fixed by every element of . Here uses the standard . The definition also applies when .
QAlgorithms.Papers.Independent.Support50.P40.jointMass
For every natural number , including , set . For a label , let , let count nonidentity entries, and let be coordinatewise Pauli multiplication with scalar phases discarded. The code supplies a commuting subgroup of the group generated by , excluding , and orthonormal vectors spanning its common fixed space. Put and ; is required. The choices supply syndrome labels , indexed by , and logical labels , indexed by : and are the all-identity label; the sets contain every label for a unique ; each ; and the sets contain every element of for a unique . With having columns , the choices additionally require for every complex matrix . For any real , syndrome , and Pauli , the definition is
The summation counts each resulting label once. The parameter is unrestricted, and gives a single syndrome index.
QAlgorithms.Papers.Independent.Support50.P40.labelCoset
For every natural number , every label , and every finite set of such labels, this defines the finite image
Here multiplies labels at each position while discarding phases: is an identity, each of squares to , and the product of two distinct nonidentity labels is the third nonidentity label. The set is arbitrary; no subgroup assumption is imposed. If is empty, the image is empty. For , this image equals .
QAlgorithms.Papers.Independent.Support50.P40.labelMul
For every natural number and two error labels , their label product is the error label obtained by multiplying at each position and discarding the phase. Explicitly, acts as an identity, , and , , and . For , the result is the unique empty label.
QAlgorithms.Papers.Independent.Support50.P40.noiseG
For every real number , this defines the real number
There is no restriction that belong to .
QAlgorithms.Papers.Independent.Support50.P40.outputQ
For every natural number , including , let . The code supplies a commuting subgroup of the group generated by phased Pauli tensors , where and , excluding , and orthonormal vectors spanning its common fixed space. It requires exactly labels for which for some and . For every real , put and . The definition returns the matrix on -bit strings obtained by summing the two diagonal Boolean blocks of the joint matrix formed from the vector after the Pauli-conjugation sum on its -bit register. Explicitly,
where range over -bit strings. There is no restriction on .
QAlgorithms.Papers.Independent.Support50.P40.outputRQ
For every natural number , including , put . The input code consists of a commuting subgroup of the group generated by phased Pauli tensors , where and , with , and orthonormal vectors spanning its common fixed space. The set of labels satisfying for some and has cardinality . For every real , define ,
Then the definition returns the matrix indexed by pairs whose entries are
This expands applying the Pauli-conjugation sum separately to each block of the matrix , where , while retaining the Boolean block indices. The parameter is any real number.
QAlgorithms.Papers.Independent.Support50.P40.phaseBit
This defines a function from the four Pauli labels to Booleans, assigning false to and , and true to and .
QAlgorithms.Papers.Independent.Support50.P40.positivityThreshold
For every function , this defines
No continuity, monotonicity, or existence of a point satisfying these conditions is assumed. If the set is nonempty, it is bounded and this is its ordinary real infimum, which need not belong to the set. If the set is empty, the total real-infimum operation used here returns .
QAlgorithms.Papers.Independent.Support50.P40.recoveredBranch
For every natural number , inner code , choice of representatives , real number , and Boolean string of length , this defines a function from complex matrices to complex matrices. Write , using the standard Pauli matrices, and for a Pauli string write , , and . The code supplies a subgroup of the unitary group contained in the subgroup generated by all , with , such that is abelian and excludes ; exactly labels have for some and ; and an orthonormal pair spans the common fixed space of . Set . To describe the data in , let be those phase-equivalent labels of , let , and let mean coordinatewise Pauli multiplication with its scalar phase discarded. Then supplies strings and , indexed respectively by length- Boolean strings and , with ; every Pauli string belongs to exactly one set ; each belongs to ; every element of belongs to exactly one set ; and, for every complex matrix , . The defined function is
Here is allowed, is arbitrary, and no restriction on , positivity of the weights, or normalization of the resulting matrix is imposed by this definition.
QAlgorithms.Papers.Independent.Support50.P40.rotatedFive
This defines a complex matrix whose rows are Boolean strings of length and whose columns are Boolean values , with entries
The real entries are regarded as complex numbers. The same summation bit is used in all five factors of the product and in the final factor.
QAlgorithms.Papers.Independent.Support50.P40.signedYield
For every natural number , including , put . Labels are tuples in , with , weight , and product given by coordinatewise Pauli multiplication after discarding phases. The input code provides a commuting subgroup of the group generated by , excluding , together with orthonormal vectors spanning its common fixed space. Let and ; the code requires . The input provides labels for and for , with the all-identity label, such that every label lies in for exactly one , each , and every label in lies in for exactly one . If has columns , these choices also satisfy for every complex matrix . For any real , define
where these are sums over distinct labels, and define , with for and . The assigned value is
There is no restriction on and no clipping of the resulting value. The denominator is always positive; at , there is one syndrome index and the denominator is .
QAlgorithms.Papers.Independent.Support50.P40.singleZ
For every natural number and every coordinate , this defines the complex matrix indexed by length- Boolean strings whose entries are
Equivalently, it is the tensor product with the matrix at coordinate and the identity matrix at every other coordinate, with overall phase . When , there is no coordinate , so there is no instance of the definition with such an argument.
QAlgorithms.Papers.Independent.Support50.P40.slEnumerator
For every natural number , every complex number , and arbitrary complex matrices indexed by , this defines
where is the tensor product, in position order, of the standard matrices , , , and selected by . No conjugation is applied to either trace, and no conditions are imposed on the matrices. The degree-zero term uses , also when . For , the value is .
QAlgorithms.Papers.Independent.Support50.P40.slWeight
For every natural number , every natural number , and arbitrary complex matrices indexed by the bit strings , this defines
where
with rows and columns ordered as false, true. The two traces are multiplied without complex conjugation. There are no Hermiticity or positivity assumptions on . If , the sum is zero. For , the empty tensor product is the identity, so the value at is .
QAlgorithms.Papers.Independent.Support50.P40.stabilizerLabels
For every natural number and every subgroup of the unitary matrices on the complex vector space indexed by , this defines the finite set of labels for which there exist and such that
where represents , and are the standard identity and Pauli matrices, with . No commutativity or other stabilizer condition is assumed of . For , this set consists of the unique empty label, whose matrix is the identity.
QAlgorithms.Papers.Independent.Support50.P40.syndromeMass
For every natural number , including , put . A Pauli label is a tuple ; write , let count its nonidentity entries, and let denote coordinatewise Pauli multiplication with the scalar phases discarded. The input code consists of a commuting subgroup of the group generated by the matrices , with , and two orthonormal vectors spanning the space fixed by every element of . Define and ; the code requires . The input supplies labels for and for , with equal to the all-identity label, such that every label belongs to for exactly one , each belongs to , and every element of belongs to for exactly one . Writing for the matrix with columns , they also satisfy for every complex matrix . For every real and every , the definition assigns
The sum is over a set of distinct labels, without multiplicity. There is no restriction ; when , the syndrome index set contains just the empty tuple.
QAlgorithms.Papers.Independent.Support50.P40.syndromeProjector
For every natural number , including , let . A label represents , and denotes coordinatewise Pauli multiplication with scalar phases discarded. The code supplies a commuting subgroup of the group generated by , excluding , together with orthonormal vectors spanning its common fixed space. Define and ; the code requires . The choices supply labels for and for , with the all-identity label, so that every label belongs to for a unique , each , and every element of belongs to for a unique . If has columns , these choices also satisfy for every complex matrix . For each syndrome , put . The definition returns the matrix
that is, the sum of the two outer products of the vectors and . At , the syndrome index set consists of the empty tuple.
QAlgorithms.Papers.Independent.Support50.P40.weightPolynomial
For every natural number , every real number , and every finite set of functions , let be the number of positions at which is not . This defines
The parameter is unrestricted. Since , the natural-number subtraction does not truncate a negative value. An empty gives zero; for , the value is zero if is empty and one if contains the unique empty label. Powers with exponent zero equal one, including .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.