Imagine you're managing a massive warehouse where every shelf slowly rots. You want to know: is there any corner of this warehouse that's naturally immune to rot — a zone where you could store delicate goods indefinitely without protection? Now imagine you can't even walk the warehouse to check; the structure is so vast and interconnected that verifying whether a rot-free zone exists is computationally prohibitive even if someone hands you a candidate map. That's the core problem this paper addresses, translated from quantum noise to shelf decay. The committed claim: deciding whether a Markovian open quantum system (governed by a time-independent Lindblad master equation) admits a decoherence-free subspace (DFS) is QMA-hard for locality k ≥ 5. In parallel, the newly introduced k-Local Lindbladian problem — which asks about purity decay rates under Lindbladian dynamics — is QMA-complete. These are complexity-theoretic results, not algorithmic ones: the paper proves structural intractability, not a speed record. The technical engine is a generalization of Kitaev's celebrated clock Hamiltonian construction from closed to open quantum systems. Where Kitaev encoded circuit computation into the ground state of a local Hamiltonian, Borras encodes it into the steady-state subspace of a Lindbladian — a subspace that contains both pure and mixed 'history states.' Whether the encoded circuit accepts or rejects determines whether that steady subspace stays pure (admitting a DFS) or becomes mixed (no DFS). The construction is elegant: it takes the core idea that made the Local Hamiltonian problem QMA-complete and transplants it to the dissipative setting, which required handling fundamentally new objects — mixed states, superoperators, Lindblad jump operators — that don't arise in the closed-system case. The ladder here is Kitaev's Local Hamiltonian Problem (QMA-complete, closed systems) and prior work on the complexity of Lindbladian problems such as Cubitt and Montanaro's results on the complexity of simulating Lindbladians. The paper extends the frontier from closed-system ground-state problems into open-system steady-state problems. This is not a marginal extension — the open-system setting introduces decoherence, mixed states, and non-unitary dynamics that require genuinely new proof techniques. The locality threshold of k ≥ 5 matches the original Local Hamiltonian construction before subsequent tightening to k = 2 by Kempe, Kitaev, and Regev. Integrity is strong for a complexity theory paper: the results are mathematical proofs, not simulations or experiments. There is no benchmarking to cherry-pick, no training set to overfit. The validation is a reduction from a known QMA-complete problem. The DFS existence problem is shown to be QMA-hard (under perfect completeness), while the k-Local Lindbladian problem achieves full QMA-completeness. The distinction matters: hardness means 'at least as hard as anything in QMA,' completeness means 'exactly captures QMA.' The paper is careful about this asymmetry. The milestone question for this line of work isn't about hitting a qubit count — it's about lowering the locality parameter. The current result requires k ≥ 5. The natural target is k = 2, mirroring the trajectory of the Local Hamiltonian problem. Achieving QMA-hardness or completeness at k = 2 for the Lindbladian DFS problem would be a definitive statement about the complexity of physically realistic open quantum systems, since 2-local interactions are what nature actually gives you. The gap from 5 to 2 is where the hard combinatorial work lives. The obvious experiment not run: tightening the locality bound below 5. This almost certainly falls into category (c) — saving it for the next paper. The perturbative gadget techniques required to reduce locality are well-known in the Hamiltonian setting but non-trivial to adapt to Lindbladians. It's the natural follow-up, and its absence is a sign of honest scoping rather than concealment.
