Shamir's is based on the fundamental theorem of algebra — you need n+1 points to uniquely define a degree n polynomial. So you achieve an n of k setup by building a degree n-1 polynomial p(x) and taking k random points from that polynomial. The i-th share is just (xi, yi), so the number of bits is defined by the field you're building the polynomial on. Because the field has to be wide enough to store the whole secret and you have to store two values (x, y), share sizes are at least two times the size of the secret. (You'll want some sort of integrity check to make sure your share isn't corrupted, though)

As I understand it, quantum computing changes nothing here — if you're missing even one point, that last point could change the secret to anything at all, with no way to disambiguate.