arXiv:2609.26769
On the Complexity of Finding Decoherence Free Subspaces
Evan Borras
Abstract
Decoherence free subspaces are a steady-state structure of the open quantum system which preserves quantum coherence between the states lying with in it and thus has found a variety of applications throughout quantum information science and technology. In this paper we study the computational complexity of deciding whether an open quantum system admits a decoherence free subspace or not. More specifically we study this problem with in the context of Markovian open quantum systems, governed by the time-independent Lindblad master equation. Along the way we introduce the $k$-Local Lindbladian problem, which captures the difficulty of computing purity decay rates under Lindbladian dynamics. We show that both problems are hard for the complexity class Quantum Merlin Arthur (QMA) when the locality $k \geq 5$, with the first under perfect completeness and the second being complete for QMA. Our hardness construction generalizes Kitaev's clock Hamiltonian construction to the open quantum system setting by encoding the execution of a quantum circuit into the steady subspace of a Lindbladian containing both pure and mixed history states. This subspace is then mixed depending on the output of the encoded circuit. Our results suggest that deciding whether a generic Markovian open quantum system admits a decoherence free subspace is intractable even for quantum computation.
AI Summary
The paper studies the computational complexity of detecting decoherence-free structure in time-independent, local Lindblad dynamics. It focuses on purely dissipative generators and treats a decoherence-free subspace as a subspace on which every operator is stationary. Its central decision problem asks whether a pure steady state exists—a one-dimensional decoherence-free subspace—or whether every steady state is at least inverse-polynomial trace distance from every pure state. For constant locality $k\geq5$, this pure-steady-state problem is shown to be $\mathrm{QMA}_1$-hard. A related optimization problem, deciding whether some pure state has an initial purity-decay rate below a threshold or all pure states exceed a higher threshold, is $\mathrm{QMA}$-complete with an inverse-polynomial promise gap. Hardness holds even with Hermitian jump operators. The paper also establishes $\mathrm{QMA}$-completeness of a separable local-Hamiltonian variant whose yes-instances admit conjugate-symmetric product witnesses. The reductions encode quantum verification circuits using Feynman–Kitaev-style history states. Propagation Hamiltonian constraints become jump operators, producing a stationary operator space containing both pure and mixed history states; the propagation dissipator has spectral gap at least $1/(8T^4)$ for circuit length $T$. Input and output checks, a Hermitian unary-clock dissipator, and a pure-state decay projection lemma establish soundness and five-locality. Vectorization connects purity decay to the separable Hamiltonian problem for membership in $\mathrm{QMA}$. The pure-steady-state problem’s membership in $\mathrm{QMA}_1$ remains open, as do hardness at lower locality and extensions to more physically restricted models and other information-preserving stationary structures.
Central claim may not hold: The explicitly defined unary-clock dissipator depolarizes legal clock windows, so even the legal all-zero clock state is not stationary, contradicting the kernel and completeness properties required by the constant-locality reduction. Substituting the specified dissipation rates into the soundness proof's displayed propagation-projection error bound gives 64/T rather than the asserted 1/(2T), leaving the claimed promise thresholds unjustified.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- comments welcome