Complexity of finding noise resistant states in quantum systems
On the Complexity of Finding Decoherence Free Subspaces
Computational Complexity
Summary
Some quantum systems have special groups of states that don’t lose their quantum properties easily, called decoherence free subspaces. This paper examines how hard it is to figure out if these groups exist in certain open quantum systems that interact with their environments. The authors show that deciding this is computationally very difficult—even for quantum computers—by linking the problem to a known tough class in quantum computing called QMA. This means that finding these stable quantum states might be practically impossible for complex systems.
What this means in practice
- •For quantum hardware designers: Recognize intrinsic hardness in certifying noise-resistant subspaces in quantum devices evolving under Markovian noise.
- •For quantum error correction engineers: Understand limits on algorithmically verifying decoherence free subspaces that protect quantum information from noise.
A theory result. No direct application yet.
Authors
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.