  Spin-boson (SB) model plays a central role in studies of dissipative quantum
dynamics, both due its conceptual importance and relevance to a number of
physical systems. Here we provide rigorous bounds of the computational
complexity of the SB model for the physically relevant case of a zero
temperature Ohmic bath. We start with the description of the bosonic bath via
its Feynman-Vernon influence functional (IF), which is a tensor on the space of
spin's trajectories. By expanding the kernel of the IF functional via a sum of
decaying exponentials, we obtain an analytical approximation of the continuous
bath by a finite number of damped bosonic modes. We bound the error induced by
restricting bosonic Hilbert spaces to a finite-dimensional subspace with small
boson numbers, which yields an analytical form of a matrix-product state (MPS)
representation of the IF. We show that the MPS bond dimension $D$ scales
polynomially in the error on physical observables $\epsilon$, as well as in the
evolution time $T$, $D\propto T^4/\epsilon^2$. This bound indicates that the
spin-boson model can be efficiently simulated using polynomial in time
computational resources.
