Operational arithmetic decoder circuits with compositional cost
DefinitionQuantumCupGates644_ConstantWeight_Supplement_decoderAn arithmetic decoder program has finitely many registers and a finite instruction list. Its instructions assign a field constant, copy, add, multiply, negate, invert, test for zero, or halt. Each transition costs one. A bounded primitive must actually halt on every input within its clock. Circuits compose these primitives sequentially or in parallel and sum their clocks; wiring only selects, duplicates, discards or reorders coordinates.
A classical radius-ρ decoder returns the transmitted codeword whenever
A quantum decoder returns representatives of the two ambient cosets from Definition 2.8 under the separate conditions |e_X|,|e_Z|<ρ. No arbitrary semantic function can be installed with an assigned cost.
This model retains the exact product-decoder operation bound in Theorem 4.1. For polynomial claims, the uniform quantum clock is c(T+Δ+|V|+1)^{kr}; c and k are chosen before the graph, systems and received words. The family definitions separately use the published executable Turing decoder, so exact RAM operation counts are never asserted for that simulation.
import Definitions.Def_QuantumCupGates644_ConstantWeight_Supplement_complexes
import Definitions.Def_QuantumCupGates644_ConstantWeight_operational_decoder
noncomputable section
namespace QuantumCupGates644.ConstantWeight.Supplement
open scoped BigOperators
open Classical
/-- Elementary arithmetic RAM operations with finite control. No semantic
oracle or arbitrary function can be installed as an instruction. -/
inductive Instruction (F : Type) (R : ℕ) where
| constant (dst : Fin R) (value : F) (next : ℕ)
| copy (dst src : Fin R) (next : ℕ)
| add (dst a b : Fin R) (next : ℕ)
| mul (dst a b : Fin R) (next : ℕ)
| neg (dst a : Fin R) (next : ℕ)
| inv (dst a : Fin R) (next : ℕ)
| branchZero (src : Fin R) (ifZero ifNonzero : ℕ)
| halt
structure ArithmeticProgram (F : Type) (a b : ℕ) where
registers : ℕ
input : Fin registers → Option (Fin a)
output : Fin b → Fin registers
code : List (Instruction F registers)
variable {F : Type} [Field F]
structure ArithmeticState (F : Type) (R : ℕ) where
pc : Option ℕ
registers : Fin R → F
def ArithmeticProgram.step {a b : ℕ} (P : ArithmeticProgram F a b)
(s : ArithmeticState F P.registers) : ArithmeticState F P.registers :=
match s.pc.bind (fun pc => P.code[pc]?) with
| none | some .halt => ⟨none,s.registers⟩
| some (.constant dst value next) => ⟨some next, Function.update s.registers dst value⟩
| some (.copy dst src next) => ⟨some next, Function.update s.registers dst (s.registers src)⟩
| some (.add dst a b next) => ⟨some next, Function.update s.registers dst (s.registers a + s.registers b)⟩
| some (.mul dst a b next) => ⟨some next, Function.update s.registers dst (s.registers a * s.registers b)⟩
| some (.neg dst a next) => ⟨some next, Function.update s.registers dst (-s.registers a)⟩
| some (.inv dst a next) => ⟨some next, Function.update s.registers dst (s.registers a)⁻¹⟩
| some (.branchZero src z nz) => ⟨some (if s.registers src = 0 then z else nz),s.registers⟩
def ArithmeticProgram.run {a b : ℕ} (P : ArithmeticProgram F a b) (x : Fin a → F) (T : ℕ) :
ArithmeticState F P.registers :=
P.step^[T] ⟨some 0,fun j => (P.input j).elim 0 x⟩
/-- Composition counts the sum of the elementary program clocks. Wires
only copy, reorder, discard or duplicate coordinates and cost zero. -/
inductive OpCircuit (F : Type) [Field F] : ℕ → ℕ → Type where
| wire {a b : ℕ} (w : Fin b → Fin a) : OpCircuit F a b
| primitive {a b : ℕ} (P : ArithmeticProgram F a b) (T : ℕ)
(halts : ∀ x, (P.run x T).pc = none) : OpCircuit F a b
| seq {a b c : ℕ} (P : OpCircuit F a b) (Q : OpCircuit F b c) : OpCircuit F a c
| parallel {a b c d : ℕ} (P : OpCircuit F a b) (Q : OpCircuit F c d) :
OpCircuit F (a+c) (b+d)
def OpCircuit.cost {a b : ℕ} : OpCircuit F a b → ℕ
| .wire _ => 0
| .primitive _ T _ => T
| .seq P Q => P.cost + Q.cost
| .parallel P Q => P.cost + Q.cost
def OpCircuit.eval {a b : ℕ} : OpCircuit F a b → (Fin a → F) → (Fin b → F)
| .wire w, x => fun j => x (w j)
| .primitive P T _, x => fun j => (P.run x T).registers (P.output j)
| .seq P Q, x => Q.eval (P.eval x)
| .parallel (a := a) (c := c) P Q, x =>
Fin.addCases (P.eval (fun j => x (Fin.castAdd c j)))
(Q.eval (fun j => x (Fin.natAdd a j)))
/-- Strict-radius classical decoding, with an operational witness. -/
def DecodesClassical {I : Type} [Fintype I] (C : Code F I) (ρ : ℝ) (T : ℕ) : Prop :=
∃ P : OpCircuit F (Fintype.card I) (Fintype.card I), P.cost ≤ T ∧
∀ c ∈ C, ∀ e : I → F, (hammingNorm e : ℝ) < ρ →
∀ j : I, P.eval (fun k => (c+e) ((Fintype.equivFin I).symm k))
(Fintype.equivFin I j) = c j
/-- Quantum output representatives determine precisely the ambient cosets
of Definition 2.8. X and Z errors each obey the strict radius. -/
def DecodesQuantum {n : ℕ} (Q : CSSSubsystem F n) (ρ : ℝ) (T : ℕ) : Prop :=
∃ P : OpCircuit F (n+n) (n+n), P.cost ≤ T ∧
∀ cX ∈ Q.QX, ∀ cZ ∈ Q.QZ, ∀ eX eZ : Fin n → F,
(hammingNorm eX : ℝ) < ρ → (hammingNorm eZ : ℝ) < ρ →
let out := P.eval (Fin.addCases (cX+eX) (cZ+eZ))
(fun j => out (Fin.castAdd n j) - cX j) ∈ dual Q.LZ ∧
(fun j => out (Fin.natAdd n j) - cZ j) ∈ dual Q.LX
/-- The paper's poly(Δ,|V|)^r clock is made uniform: a polynomial in
constituent clocks and graph size, raised to a constant multiple of r.
The constants are quantified before every graph and local system in the
claims, rather than chosen separately for each finite instance. -/
def quantumClock (c k r Δ nv T : ℕ) : ℕ :=
c * (T + Δ + nv + 1) ^ (k * r)
def radius {r : ℕ} (ρ : Fin r → ℝ) (Δ : ℕ) : ℝ :=
min ((∏ j ∈ Finset.univ.filter (fun j : Fin r => j.val + 1 < r), ρ j) /
(Δ : ℝ)^(r-1)) (∑ j ∈ Finset.univ.filter (fun j : Fin r => j.val + 1 = r), ρ j)
end QuantumCupGates644.ConstantWeight.Supplement