You can represent any unit vector in a vector space with 2^n basis elements using only n qubits.

Constructing an arbitrary vector might not be more efficient than doing it on a classical computer, but constructing certain vectors that would probably be very large and/or unwieldy on a classical computer is possible. For example, it’s easy to represent any single standard basis vector in a vector space with size 2^64 on a classical computer; just use a list of (64-bit word to describe which basis vector you’re talking about and a weight). Now go ahead and try to use that same representation for a Fourier transform, and you’re out of luck. But this is no problem on a quantum computer. You just end up with a 64-qubit system that has a non-zero value for all of those 2^64 basis states (using only 64 qubits). You can also construct the circuit required to do the Fourier transform with ~64log(64) gates.

So for this problem, there’s definitely a space advantage. The trouble is that most of these advantages don’t generalize in any obvious way. Maybe there’s even a representation on classical computers that’s equally efficient and we just haven’t found it yet.

And as you mention below, this isn’t useful for arbitrary linear operations (many of them seem to be just as expensive on a quantum computer as on a classical computer) but there are certain known-to-be-useful linear operations that are extremely cheap to represent compared to what we know how to do on a classical computer.