A recent study has shown that determining whether an open quantum system possesses a decoherence-free subspace (DFS) is a computationally hard problem, on par with the most complex problems in quantum computation theory. Specifically, it has been classified as QMA-complete (Quantum Merlin Arthur-complete) for Markovian systems described by the time-independent Lindblad master equation. DFSs are crucial in quantum information, as they allow the preservation of quantum coherence for states within them, protecting them from detrimental environmental interaction and facilitating the development of robust quantum technologies.

The research addresses this problem within the context of Markovian open quantum systems, governed by the time-independent Lindblad master equation. To do this, the authors introduce the k-Local Lindbladian problem, which captures the difficulty of computing purity decay rates under Lindbladian dynamics. It is shown that both problems are hard for the QMA complexity class when the locality k ≥ 5. The first problem (existence of DFS) is classified as QMA-hard with perfect completeness, while the second (k-Local Lindbladian) is QMA-complete.

The hardness construction generalizes Kitaev's clock Hamiltonian construction to the open quantum system setting. This method encodes the execution of a quantum circuit into the steady subspace of a Lindbladian, which contains both pure and mixed history states. This subspace is then mixed depending on the output of the encoded circuit. These findings suggest that deciding whether a generic Markovian open quantum system admits a decoherence-free subspace is intractable even for quantum computation, with significant implications for the design of error-resilient quantum systems.