CS Paper Radar

On the Complexity of Finding Decoherence Free Subspaces

Evan Borras

cs.CC quant-phmath-ph ·submitted 2026-09-22 17:49 UTC · v1

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.

Comment
comments welcome

Closest papers

Nearest neighbours by meaning across the whole index.

The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness

cs.CC quant-ph ·2026-09-30 ·Itay Shalit, Mark Zhandry
hot direction similarity 0.66
Abstract

The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.

0.27

The computational complexity of bosonic Lindbladian fixed points

cs.CC quant-ph ·2026-11-19 ·En-Jui Kuo, Arsalan Motamedi, Mohammad Hafezi, Saeed Mehraban
theory similarity 0.65
Abstract

We study the computational complexity of estimating observables and sampling from stationary states, or fixed points, of bosonic Lindbladian dynamics with bounded-degree polynomial interactions. While the complexity of transient bosonic dynamics has been investigated, understanding the computational power of bosonic fixed points requires addressing subtleties of infinite-dimensional systems, including the existence, uniqueness, and convergence of stationary states. We establish a broad complexity landscape spanning universal quantum computation, efficient classical simulation, sampling hardness, and undecidability. First, we show that universal quantum computation can be embedded into observable estimation at the unique fixed point of a bosonic Lindbladian with a Hamiltonian of degree at most twelve and only linear photon loss. Moreover, this fixed point can be prepared from vacuum in polynomial time. On the classical side, we identify Gaussian regimes with incoherent pumping that admit efficient photon-number sampling and establish stability of classical approximability under sufficiently weak non-Gaussian Kerr perturbations. Conversely, for Gaussian fixed points without incoherent pumping, we establish hardness of exact sampling under constant-rate linear loss and hardness of approximate sampling at inverse-polynomial loss rates under standard boson-sampling conjectures. We also relate sampling from non-Gaussian fixed points to variants of boson sampling. Finally, we prove that deciding the existence of a stationary density operator is $\mathsf{RE}$-hard, even for purely dissipative Lindbladians with degree-five jump operators acting on at most four modes.

0.31

Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms

cs.CC quant-phcs.DS ·2026-09-28 ·Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi, Suguru Tamaki
theoryhot direction similarity 0.64
Abstract · 21 pages, 2 tables, 0 figures

Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound $O^\ast(2^{n/2})$ for both problems, with the improvement depending on the relative accuracy $\varepsilon$ and the locality $k$. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small $\varepsilon/k$, our algorithms improve the exponent by a factor of $\log(k/\varepsilon)$ over [BGLGST, PRL 2025]. Our main technical result is an entropy-governed lower bound on the dimension of the Hamiltonian's low-energy subspace, obtained by depolarizing its ground state. For fixed $k$, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, $XY$, and Ising models on arbitrary interaction graphs.

0.29

Gap Amplification for Local Hamiltonians with Combinatorial Soundness

cs.CC quant-ph ·2026-10-04 ·Mitali Bafna, Quynh T. Nguyen, Tina Zhang
top venuetheory similarity 0.62
Abstract · Accepted to FOCS 2026

The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.

0.63

A physical and universal model of bosonic computations with Solovay-Kitaev theorem

cs.CC quant-ph ·2026-09-30 ·Dorian Rudolph, Arsalan Motamedi, Dhruva Sambrani, Hamid Reza Naeij, Ulysse Chabaud +2 more
theory similarity 0.61
Abstract

Bosonic quantum systems are among the leading architectures for quantum information processing, offering continuous-variable degrees of freedom with strong error-correction capabilities. However, standard bosonic quantum computation models such as the Lloyd-Braunstein [Lloyd and Braunstein, 1999] and hybrid oscillator-qubit models [Brenner, Dias, and Koenig, 2025; Liu et al., 2026] permit dramatic energy growth, leading to unphysical computational power and the breakdown of fundamental algorithmic tools such as universal and efficient compilation [Brenner et al., 2026; Rudolph et al., 2025]. To address this, we introduce a new model of bosonic quantum computation, Bosonic Energy-Preserving Quantum Computation (BEQC), in which energy is treated as a computational resource. Namely, energy is supplied solely through input coherent states, and all gates are generated by energy-preserving Hamiltonians. Thus, by construction, dramatic energy growth is impossible, making the model physically grounded. We next show that BEQC is a computationally robust and universal model in many respects, including: (1. Computational power) BEQC efficiently simulates all polynomial-energy computations in existing models, and exactly recovers BQP in the polynomial energy setting. It further admits several complexity-theoretic upper bounds when varying the energy, precision, and space parameters of the model. (2. Universal gate sets and state synthesis) BEQC has natural universal gate sets based on linear optics and Kerr interactions. In particular, we obtain a Solovay-Kitaev theorem which circumvents previous no-go results. We give various applications, including (a) a protocol for engineering GKP states with rigorous preparation guarantees, (b) Fock state preparation to exponential precision, and (c) native Fock space simulation of any qubit-based unitary.

0.49

Query-Optimal and Gate-Efficient Lindbladian Simulation

cs.DS quant-ph ·2026-09-16 ·Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou
theoryhighly cited similarity 0.61
Abstract · 62 pages, 5 figures

We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $α_H$ and $α_B$, respectively. For evolution time $t$, set $τ=(α_H+α_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.

0.33

Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT

cs.CC quant-phcs.DS ·2026-09-29 ·Atsuya Hasegawa, Jonas Kamminga, François Le Gall, Suguru Tamaki
theoryhot direction similarity 0.60
Abstract · 40 pages

The local Hamiltonian problem is the canonical $\mathsf{QMA}$-complete problem, and $O(2^n)$ time classical algorithms and $O(2^{n/2})$ time quantum algorithms are known to solve the problem in the worst case. It is not clear how to improve these brute force strategies for a broad class of the problem because ground states are highly entangled in general, and we cannot directly apply known strategies for classical CSPs. In this work, we present exponentially faster classical and quantum algorithms under two mild assumptions: (1) the Hamiltonian is frustration-free on YES instances, and (2) it is approximately regular, meaning that every qubit is acted upon by approximately the same number of constraints. We complement these upper bounds by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup. Our lower bound further demonstrates that the dependence of our algorithms on regularity is in some sense nearly optimal. Specifically, quantum 5-SAT remains (Q)SETH-hard even for Hamiltonians in which all but $O(\sqrt{n})$ qubits participate in only constantly many constraints, while the remaining $O(\sqrt{n})$ qubits each participate in $O(\sqrt{n})$ constraints. By contrast, if either the size of this high-degree subset or the degrees of its qubits is reduced by a factor of $n^δ$, for any $δ>0$, our algorithm solves the problem in time $O(2^{(1- \varepsilon)n})$ for some $\varepsilon>0$. Together, our upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability.

0.31

Computational Work Extraction: The Complexity of Catalysts

cs.CC quant-ph ·2026-09-30 ·Atul Singh Arora, Shantanav Chakraborty, Alexandru Cojocaru, Sreyas Saminathan, Uttam Singh
theoryhot direction similarity 0.60
Abstract · 70 pages, 3 Figures; See https://atulsingharora.github.io/cat for updates

We prove maximal separations: $n$-qubit systems can have $Θ(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of quantum-secure pseudorandom functions, this separation extends to the plain model. This work uncovers an important connection between ergotropy and the complexity of catalytic computation---computation where auxiliary qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with $λ$ catalysts; but (ii) cannot be solved by any algorithm with $cλ$ catalysts, for any $c<1$. We show this by proving query lower bounds for quantum-space bounded algorithms. As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful---there is a family of Hamiltonians and states for which catalysts enable efficient extraction of the full $Θ(n)$ ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy---analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy. Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and quantum catalytic ergotropy.

0.38