Computational complexity of non-equilibrium steady states of quantum spin chains
arXiv:1601.08066 · doi:10.1103/PhysRevA.93.032306
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.
arXiv comment10 pages, 4 figures
References in corpus (34)
- Elementary gates for quantum computation
- The density-matrix renormalization group
- Efficient classical simulation of slightly entangled quantum computations
- Efficient simulation of one-dimensional quantum many-body systems
- Measurement-based quantum computation with cluster states
- Strengths and Weaknesses of Quantum Computing
- Matrix Product Density Operators: Simulation of finite-T and dissipative systems
- Thermodynamic limit of the density matrix renormalization for the spin-1 Heisenberg chain
- Quantum Inverse Scattering Method and Correlation Functions
- Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
- Criticality, the area law, and the computational power of PEPS
- Open XXZ spin chain: Nonequilibrium steady state and strict bound on ballistic transport
- The computational complexity of PEPS
- Exact nonequilibrium steady state of a strongly driven open XXZ chain
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- 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
- Open Quantum Dynamics: Complete Positivity and Entanglement
- Thermal conductivity via magnetic excitations in spin-chain materials
- Unified derivations of measurement-based schemes for quantum computation
- Quasilocal conservation laws in XXZ spin-1/2 chains: open, periodic and twisted boundary conditions
- Matrix product solutions of boundary driven quantum chains
- Universal quantum computation with little entanglement
- Quantum information-geometry of dissipative quantum phase transitions
- Matrix product operators and states: NP-hardness and undecidability
- Thermodyamic bounds on Drude weights in terms of almost-conserved quantities
- Computational Complexity in Electronic Structure
- Quantum metrology with non-equilibrium steady states of quantum spin chains
- Dynamical Response Theory for Driven-Dissipative Quantum Systems
- Entanglement in stationary nonequilibrium states at high energies
- Computational Complexity of Some Quantum Theories in 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