Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.26769

On the Complexity of Finding Decoherence Free Subspaces

Evan Borras

quant-phcs.CCmath-phSubmitted Sep 22, 2026• Announced Sep 23, 2026• 0 citations
arXivHTMLPDF

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.

No sign of AI-generated textOverclaimsUnclear writingPossible error

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

Related papers

On the Complexity of Finding Decoherence Free Subspaces — E8 Intelligence Research

Andrew Stewart Caldin

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 syste Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 10, 2026•0 citations

Stabilizer codes for open quantum systems

Francisco Revson F. Pereira, Stefano Mancini, Giuliano G. La Guardia

The Lindblad master equation describes the evolution of a large variety of open quantum systems. An important property of some open quantum systems is the existence of decoherence-free subspaces. A quantum state from a decoherence-free subspace will evolve unitarily. However, there is no procedural and optimal method for constructing a decoherence-free subspace. In this paper, we develop tools for constructing decoherence-free stabilizer codes for open quantum systems governed by the Lindblad master equation. This is done by pursuing an extension of the stabilizer formalism beyond the celebrated group structure of Pauli error operators. We then show how to utilize decoherence-free stabilizer codes in quantum metrology in order to attain the Heisenberg limit scaling with low computational complexity.

arXiv:2107.11914•Scientific Reports•Jun 29, 2023•6 citations

Adiabatic evolution of decoherence-free subspaces and its shortcuts

S. L. Wu, X. L. Huang, H. Li +1 more

The adiabatic theorem and shortcuts to adiabaticity for time-dependent open quantum systems are explored in this paper. Starting from the definition of dynamical stable decoherence-free subspace, we show that, under a compact adiabatic condition, the quantum state remains in the time-dependent decoherence-free subspace with an extremely high purity, even though the dynamics of the open quantum system may not be adiabatic. The adiabatic condition mentioned here in the adiabatic theorem for open systems is very similar to that for closed quantum systems, except that the operators required to change slowly are the Lindblad operators. We also show that the adiabatic evolution of decoherence-free subspaces depends on the existence of instantaneous decoherence-free subspaces, which requires that the Hamiltonian of open quantum systems be engineered according to the incoherent control protocol. In addition, shortcuts to adiabaticity for adiabatic decoherence-free subspaces are also presented based on the transitionless quantum driving method. Finally, we provide an example that consists of a two-level system coupled to a broadband squeezed vacuum field to show our theory. Our approach employs Markovian master equations and the theory can apply to finite-dimensional quantum open systems.

arXiv:1705.01695•Physical Review A•Oct 10, 2017•24 citations

General approach to find steady-state manifolds in Markovian and non-Markovian systems

Da-Jian Zhang, Xiao‐Dong Yu, Hua-Lin Huang +1 more

Steady-state manifolds of open quantum systems, such as decoherence-free subspaces and noiseless subsystems, are of great practical importance to the end of quantum information processing. Yet, it is a difficult problem to find steady-state manifolds of open quantum systems, especially of non-Markovian systems. In this paper, we propose an approach to find the steady-state manifolds, which is generally applicable to both Markovian and non-Markovian systems. Our approach is based on an arbitrarily given steady state, and by following the standard steps of the approach, the steady-state manifold on the support subspace of the given state can be obtained. Our work reduces the problem of finding a manifold of steady states to that of finding only one steady state, which is indeed an interesting progress towards completely solving the difficult problem. Besides, in deriving our approach, we introduce the notions of the modified noise algebra and its commutant, and prove two theorems on the structure of steady-state manifolds of general open systems, which themselves are interesting findings too.

arXiv:1611.02800•Physical Review A•Nov 28, 2016•4 citations

Reduced decoherence in non-Markovian systems lacking decoherence free subspaces

Curtis J. Broadbent, Jun Jing, Ting Yu +1 more

By numerically simulating the exact master equation for the degenerate vee-type three-level systems, we demonstrate the existence of states with drastically reduced decoherence in an open quantum systems which does not admit decoherence free subspaces.

Frontiers in Optics•Jan 1, 2011•0 citations

Engineering of a quantum state by time-dependent decoherence-free subspaces

S. L. Wu

We apply the time-dependent decoherence-free subspace theory to a Markovian open quantum system in order to present a proposal for a quantum-state engineering program. By quantifying the purity of the quantum state, we verify that the quantum-state engineering process designed via our method is completely unitary within any total engineering time. Even though the controls on the open quantum system are not perfect, the asymptotic purity is still robust. Owing to its ability to completely resist decoherence and the lack of restraint in terms of the total engineering time, our proposal is suitable for multitask quantum-state engineering program. Therefore, this proposal is not only useful for achieving the quantum-state engineering program experimentally, it also helps us build both a quantum simulation and quantum information equipment in reality.

arXiv:1502.07967•Physical Review A•Mar 3, 2015•9 citations
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 kkk-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≥5k \geq 5k≥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.
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≥5k\geq5k≥5, this pure-steady-state problem is shown to be QMA1\mathrm{QMA}_1QMA1​-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 QMA\mathrm{QMA}QMA-complete with an inverse-polynomial promise gap. Hardness holds even with Hermitian jump operators. The paper also establishes QMA\mathrm{QMA}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/(8T4)1/(8T^4)1/(8T4) for circuit length TTT. 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 QMA\mathrm{QMA}QMA.
The pure-steady-state problem’s membership in QMA1\mathrm{QMA}_1QMA1​ remains open, as do hardness at lower locality and extensions to more physically restricted models and other information-preserving stationary structures.
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 kkk-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≥5k \geq 5k≥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 syste Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
The Lindblad master equation describes the evolution of a large variety of open quantum systems. An important property of some open quantum systems is the existence of decoherence-free subspaces. A quantum state from a decoherence-free subspace will evolve unitarily. However, there is no procedural and optimal method for constructing a decoherence-free subspace. In this paper, we develop tools for constructing decoherence-free stabilizer codes for open quantum systems governed by the Lindblad master equation. This is done by pursuing an extension of the stabilizer formalism beyond the celebrated group structure of Pauli error operators. We then show how to utilize decoherence-free stabilizer codes in quantum metrology in order to attain the Heisenberg limit scaling with low computational complexity.
The adiabatic theorem and shortcuts to adiabaticity for time-dependent open quantum systems are explored in this paper. Starting from the definition of dynamical stable decoherence-free subspace, we show that, under a compact adiabatic condition, the quantum state remains in the time-dependent decoherence-free subspace with an extremely high purity, even though the dynamics of the open quantum system may not be adiabatic. The adiabatic condition mentioned here in the adiabatic theorem for open systems is very similar to that for closed quantum systems, except that the operators required to change slowly are the Lindblad operators. We also show that the adiabatic evolution of decoherence-free subspaces depends on the existence of instantaneous decoherence-free subspaces, which requires that the Hamiltonian of open quantum systems be engineered according to the incoherent control protocol. In addition, shortcuts to adiabaticity for adiabatic decoherence-free subspaces are also presented based on the transitionless quantum driving method. Finally, we provide an example that consists of a two-level system coupled to a broadband squeezed vacuum field to show our theory. Our approach employs Markovian master equations and the theory can apply to finite-dimensional quantum open systems.
Steady-state manifolds of open quantum systems, such as decoherence-free subspaces and noiseless subsystems, are of great practical importance to the end of quantum information processing. Yet, it is a difficult problem to find steady-state manifolds of open quantum systems, especially of non-Markovian systems. In this paper, we propose an approach to find the steady-state manifolds, which is generally applicable to both Markovian and non-Markovian systems. Our approach is based on an arbitrarily given steady state, and by following the standard steps of the approach, the steady-state manifold on the support subspace of the given state can be obtained. Our work reduces the problem of finding a manifold of steady states to that of finding only one steady state, which is indeed an interesting progress towards completely solving the difficult problem. Besides, in deriving our approach, we introduce the notions of the modified noise algebra and its commutant, and prove two theorems on the structure of steady-state manifolds of general open systems, which themselves are interesting findings too.
We apply the time-dependent decoherence-free subspace theory to a Markovian open quantum system in order to present a proposal for a quantum-state engineering program. By quantifying the purity of the quantum state, we verify that the quantum-state engineering process designed via our method is completely unitary within any total engineering time. Even though the controls on the open quantum system are not perfect, the asymptotic purity is still robust. Owing to its ability to completely resist decoherence and the lack of restraint in terms of the total engineering time, our proposal is suitable for multitask quantum-state engineering program. Therefore, this proposal is not only useful for achieving the quantum-state engineering program experimentally, it also helps us build both a quantum simulation and quantum information equipment in reality.