On the Complexity of Finding Decoherence Free Subspaces
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 ≥ 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.
Related
- On the Complexity of Finding Fixed Points for Set-Valued Contractions
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- Directed Cut-Query Complexity of Finding a King
- On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
BibTeX
@misc{borras2026complexity,
title = {{On the Complexity of Finding Decoherence Free Subspaces}},
author = {Evan Borras},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26769},
eprint = {2609.26769},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26769},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Complexity of Finding Decoherence Free Subspaces
AU - Evan Borras
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26769
UR - https://arxiv.org/abs/2609.26769
AB - 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 ≥ 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.
ER -