\sim \mathcal{O}(mN 2^{2S+1}) \sim \mathcal{O}(mN 2^{2N+1})\sim \mathcal{O}\left(-N 2^{2N+1}\log_2\varepsilon_\text{int}\right)$$ This represents an exponential saving over the space $\mathcal{O}(2^{Nm})\sim \mathcal{O}(\varepsilon_{int}^{-1})$ required to store the full wavefunction in general classical algorithms.

This exponential improvement is similar in origin to the one in quantum computers, as it also exploits the rapid growth of the Hilbert space with the number of qubits. However, in the MPS quantum register the gain is heuristic: it only appears for distributions with nice sampling properties. There are infinitely many problems where this improvement vanishes, due to the growth of $S$ and the exponential blowup of the bond dimensions $\xi.$ However, it seems that there are still many problems of interest where the MPS quantum register approach is useful, as we see below.

Integrals and expected values {#sec:expected}
-----------------------------

![Linear MPS representation. (a) Both observables $\ket{f}$ and a probability distributions $\ket{p}$ have MPS representations with bond dimensions of order $\xi,$ and they combine to give a mean value $\bar{f}=\braket{p|f}$. (b) When there are m qubits, the optimal contraction is sequence of $m\times 2$ steps, with the structure shown here, taking $\mathcal{O}(2d\chi^3)$ operations.[]{data-label="fig:mps-linear"}](fig-mps-linear.pdf){width="0.8\linewidth"}

In the linear MPS representation, the scalar product $\braket{f|p}$ is an approximation to the integral between both functions 