The advent of noisy-intermediate scale quantum computers has introduced the exciting possibility of achieving quantum speedups in machine learning tasks. These devices, however, are composed of a small number of qubits, and can faithfully run only short circuits. This puts many proposed approaches for quantum machine learning beyond currently available devices. We address the problem of efficiently compressing and loading classical data for use on a quantum computer. Our proposed methods allow both the required number of qubits and depth of the quantum circuit to be tuned. We achieve this by using a correspondence between matrix-product states and quantum circuits, and further propose a hardware-efficient quantum circuit approach, which we benchmark on the Fashion-MNIST dataset. Finally, we demonstrate that a quantum circuit based classifier can achieve competitive accuracy with current tensor learning methods using only 11 qubits.