  We study non-equilibrium steady states (NESS) of spin chains with boundary
Markovian dissipation from the computational complexity point of view. We focus
on XX chains whose NESS are matrix product operators (MPO), i.e. with
coefficients of a tensor operator basis described by transition amplitudes in
an auxiliary space. Encoding quantum algorithms in the auxiliary space, we show
that estimating expectations of operators, being local in the sense that each
acts on disjoint sets of few spins covering all the system, provides the
answers of problems at least as hard as, and believed by many computer
scientists to be much harder than, those solved by quantum computers. We draw
conclusions on the hardness of the above estimations.
