Computational complexity of non-equilibrium steady states of quantum spin chains

Abstract

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.

10 pages, 4 figures

References in corpus (13)

• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Criticality, the area law, and the computational power of PEPS
• Open XXZ spin chain: Nonequilibrium steady state and strict bound on ballistic transport
• Measurement-based quantum computation beyond the one-way model
• Modeling heat transport through completely positive maps
• Variational Matrix Product Operators for the Steady State of Dissipative Quantum Systems
• Quantum phase transition in a far from equilibrium steady state of XY spin chain
• Thermal conductivity via magnetic excitations in spin-chain materials
• Quasilocal conservation laws in XXZ spin-1/2 chains: open, periodic and twisted boundary conditions
• Universal quantum computation with little entanglement
• Matrix product operators and states: NP-hardness and undecidability
• Dynamical Response Theory for Driven-Dissipative Quantum Systems
• Computational Complexity of Some Quantum Theories in $1+1$ Dimensions

Cited by in corpus (11)

• Quantum enhanced measurements without entanglement
• Dynamical quantum phase transitions in non-Hermitian lattices
• At the limits of criticality-based quantum metrology: apparent super-Heisenberg scaling revisited
• Quantum dynamics of thermalizing systems
• Fisher information approach to non-equilibrium phase transitions in quantum XXZ spin chain with boundary noise
• Dynamical phase transitions in sampling complexity
• Coherence enhanced quantum metrology in a nonequilibrium optical molecule
• Spin high-harmonic generation through terahertz laser-driven phonons
• Nonuniform phases in the geometrically frustrated dissipative XYZ model
• Entanglement and complexity of interacting qubits subject to asymmetric noise
• Certifying steady-state properties of open quantum systems