  Machine learning tasks are an exciting application for quantum computers, as
it has been proven that they can learn certain problems more efficiently than
classical ones. Applying quantum machine learning algorithms to classical data
can have many important applications, as qubits allow for dealing with
exponentially more data than classical bits. However, preparing the
corresponding quantum states usually requires an exponential number of gates
and therefore may ruin any potential quantum speedups. Here, we show that
classical data with a sufficiently quickly decaying Fourier spectrum after
being mapped to a quantum state can be well-approximated by states with a small
Schmidt rank (i.e., matrix product states) and we derive explicit error bounds.
These approximated states can, in turn, be prepared on a quantum computer with
a linear number of nearest-neighbor two-qubit gates. We confirm our results
numerically on a set of $1024\times1024$-pixel images taken from the
'Imagenette' dataset. Additionally, we consider different variational circuit
ans\"atze and demonstrate numerically that one-dimensional sequential circuits
achieve the same compression quality as more powerful ans\"atze.
