Theorem 6.1 — static dissipative hard instances, , ,
OpenLindbladShallow.Supplement.theorem_6_1Fix , a wire-dimension bound and a gate range . The system is the cube , , with two qubits per site. The generators are the purely dissipative transport instances of Eq. (51), with a positive dyadic rational and . For evolve for time . A simulator implementing a channel has half-diamond error . Put .
Theorem. There are absolute constants , and for fixed constants and , such that for every , and with :
- (48) some transport instance has the property that every simulator in the depth model with half-diamond error at most has depth
- (49) some transport instance and one input state of the system have the property that every simulator with half-diamond error at most executes, on input , an expected number of gates
- (50) some transport instance has the property that every fixed-schedule simulator with half-diamond error at most has a number of gate slots
Each of the three instances has traceless jumps, every site in at most two bonds, and for the strength parameter of Section 2.
The simulators may use arbitrarily many auxiliary registers at arbitrary sites, product initial auxiliary states, arbitrary input-independent shared randomness, arbitrary measurable classical outcome alphabets, single-site instruments for free, and gates on at most two wires of dimension at most at distance at most (the models of §6.1). The leading volume and time factors match the upper bounds of Theorem 2.1.
Formalization Note The diamond norm dnorm is unhalved, so half-diamond error at most is . The three instances are chosen after and may differ.
Differences from the source:
- reading: Ω_D(·), "sufficiently large L_side" and δ₀(D, q_g, R_g) → ∃ c > 0, L₀ and δ₀ > 0 depending only on (D, q_g, R_g), chosen before L, θ, δ; reason: the standard reading of the asymptotic statement; implicit constants may depend on D, q_g, R_g (p.51).
- reading: λ = Θ(γ) for the hard instances → absolute constants c₁, c₂ > 0 with c₁γ ≤ λ ≤ c₂γ, chosen before everything; reason: the page writes Θ without subscript and the proof gives 8γ ≤ λ < 64γ.
- reading: "the lower bound holds for the expected gate count on one input common to every cut" → one system density ρ, chosen after the instance and before every simulator; reason: branch probabilities depend only on the system input's reduced state, so an untouched reference changes no expected count.
- reading: gates with at most two input and output wires of dimension ≤ q_g, arbitrary continuous elementary gates → arbitrary instruments on at most two wires of dimension ≤ q_g at sites at ℓ∞ distance ≤ R_g, every other instruction single-site; reason: the page charges "every operation coupling different sites"; a gate with different input and output wires acts on the union of its at most two wires.
- encoding: arbitrary classical outcome alphabets and shared input-independent randomness → arbitrary measurable outcome and seed types with probability measures and integrable Kraus densities; reason: this includes finite, countable and continuous alphabets, while explicit integrability excludes only undefined instruments.
- reading: classical records travel at most R_g sites per layer → each slot has an anchor site, acts on wires within ℓ∞ distance R_g of it, layers act on disjoint wires, and a slot sees only records of earlier slots with anchors within R_g(t − t′); reason: this is the light-cone condition of §6.1 and Lemma 6.2, up to a constant factor in the speed, which Ω_D absorbs.
- reading: one deterministic list of gate locations, disabled slots charged → gate slots on fixed wire sets for all seeds and branches, other slots single-site only, cost = number of gate slots; reason: locations as wires rather than site pairs give the same infimum, since single-site swaps are free in gate count.
- encoding: depth maximized over execution branches → the number of layers of the execution bound; reason: trailing layers idle in every branch can be removed without changing the channel, so the infimum over simulators is the same.
- encoding: ½‖𝒞 − e^{Tℒ}‖⋄ ≤ δ with 0 < δ < 1 → dnorm(𝒞 − e^{Tℒ}) ≤ 2δ with the hypotheses 0 < δ < 1 and δ ≤ δ₀; reason: dnorm is the unhalved diamond norm; δ < 1 is the page's standing range.
import Mathlib import Definitions.Def_LindbladShallow_gen import Definitions.Def_LindbladShallow_lam import Definitions.Def_LindbladShallow_Supplement_transport import Definitions.Def_LindbladShallow_Supplement_simulator open scoped Matrix ComplexOrder ENNReal
namespace LindbladShallow
namespace Supplement
/-- **Theorem 6.1** (Static dissipative hard instances; Shen–Wu–Yuan–Zhang, arXiv:2610.05362, held
version sha256 8f4637ef…, p.51, with the model of §6.1, pp.50–51, and the instances of Eq. (51),
p.52). There are absolute constants `c₁, c₂ > 0` and, for fixed `D ≥ 1`, `q_g ≥ 2`, `R_g ≥ 1`,
constants `c, δ₀ > 0` and `L₀` such that for every side `L ≥ L₀`, every `θ ≥ 1` and every
`0 < δ < 1` with `δ ≤ δ₀`, writing `n = L^D` and `E = log(n/δ)`:
* (48) some transport instance (`H = 0`, jumps `J_x = b S_x`) has: every depth-model simulator with
half-diamond error `½‖𝒞 − e^{Tℒ}‖⋄ ≤ δ`, `T = θ/γ`, `γ = b²`, has depth
`≥ c · min{L, R₁(θ, E)}`;
* (49) some transport instance and one system input `ρ` have: every simulator with half-diamond
error `≤ δ` executes on `ρ` an expected number of gates `≥ c · n · min{L, θ}`;
* (50) some transport instance has: every fixed-schedule simulator with half-diamond error `≤ δ`
has `≥ c · n · min{L, R_{D+1}(θ, E)}` gate slots.
Each of the three instances has traceless jumps, every site in at most two bonds, and
`c₁ γ ≤ λ ≤ c₂ γ` for the strength parameter `λ` of Section 2.
**Formalization Note** `Ω_D(·)` is read as `∃ c > 0` depending only on `(D, q_g, R_g)`,
"sufficiently large `L_side`" as `∃ L₀(D, q_g, R_g)`, and `δ₀ = δ₀(D, q_g, R_g)`; they are chosen
before `L, θ, δ`, and the instance after. The diamond norm `dnorm` is unhalved, so half-diamond
error `≤ δ` is `dnorm ≤ 2δ`. A simulator ranges over every auxiliary layout (any finite type of
registers with positive finite dimensions at any sites of `ℤ^D`), every measurable classical-outcome
alphabet, and arbitrary input-independent shared randomness. The constants in `λ = Θ(γ)` are
absolute (the proof gives `8γ ≤ λ < 64γ`). -/
theorem theorem_6_1 :
∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧
∀ (D : ℕ) (hD : 1 ≤ D) (qg Rg : ℕ), 2 ≤ qg → 1 ≤ Rg →
∃ c δ₀ : ℝ, 0 < c ∧ 0 < δ₀ ∧ ∃ L₀ : ℕ,
∀ L : ℕ, L₀ ≤ L → ∀ θ : ℝ, 1 ≤ θ → ∀ δ : ℝ, 0 < δ → δ < 1 → δ ≤ δ₀ →
let n : ℝ := (L : ℝ) ^ D
let E : ℝ := Real.log (n / δ)
(∃ (b : ℚ) (I : Instance (transportParams D hD)), IsTransportInstance L b I ∧
(∀ e : Fin I.nT, ∀ X ∈ (I.term e).jumpsC, X.trace = 0) ∧
c₁ * (b : ℝ) ^ 2 ≤ lam I ∧ lam I ≤ c₂ * (b : ℝ) ^ 2 ∧
∀ (A : Type) [Fintype A] [DecidableEq A] (site : A → Fin D → ℤ) (dim : A → ℕ)
(Seed O : Type) [MeasurableSpace Seed] [MeasurableSpace O]
(S : Simulator I A site dim Seed O), S.Valid qg Rg → S.IsDepthModel Rg →
dnorm (S.channel - ⇑(supExp (θ / (b : ℝ) ^ 2) (gen I))) ≤ ENNReal.ofReal (2 * δ) →
c * min (L : ℝ) (radius1 θ E) ≤ (S.nLayers : ℝ)) ∧
(∃ (b : ℚ) (I : Instance (transportParams D hD)), IsTransportInstance L b I ∧
(∀ e : Fin I.nT, ∀ X ∈ (I.term e).jumpsC, X.trace = 0) ∧
c₁ * (b : ℝ) ^ 2 ≤ lam I ∧ lam I ≤ c₂ * (b : ℝ) ^ 2 ∧
∃ ρ : Matrix (Sys I) (Sys I) ℂ, ρ.PosSemidef ∧ ρ.trace = 1 ∧
∀ (A : Type) [Fintype A] [DecidableEq A] (site : A → Fin D → ℤ) (dim : A → ℕ)
(Seed O : Type) [MeasurableSpace Seed] [MeasurableSpace O]
(S : Simulator I A site dim Seed O), S.Valid qg Rg →
dnorm (S.channel - ⇑(supExp (θ / (b : ℝ) ^ 2) (gen I))) ≤ ENNReal.ofReal (2 * δ) →
c * n * min (L : ℝ) θ ≤ S.expGates ρ) ∧
(∃ (b : ℚ) (I : Instance (transportParams D hD)), IsTransportInstance L b I ∧
(∀ e : Fin I.nT, ∀ X ∈ (I.term e).jumpsC, X.trace = 0) ∧
c₁ * (b : ℝ) ^ 2 ≤ lam I ∧ lam I ≤ c₂ * (b : ℝ) ^ 2 ∧
∀ (A : Type) [Fintype A] [DecidableEq A] (site : A → Fin D → ℤ) (dim : A → ℕ)
(Seed O : Type) [MeasurableSpace Seed] [MeasurableSpace O]
(S : Simulator I A site dim Seed O) (loc : ℕ → ℕ → Option (Finset (SimWire I A))),
S.Valid qg Rg → S.RespectsSchedule loc →
dnorm (S.channel - ⇑(supExp (θ / (b : ℝ) ^ 2) (gen I))) ≤ ENNReal.ofReal (2 * δ) →
c * n * min (L : ℝ) (radiusD1 D θ E) ≤ (S.scheduleCost loc : ℝ)) := by sorry
end Supplement
end LindbladShallow