" it would still need to have storage equal to the size of the entire original data."

I think it's worse than this. You need the intermediate steps as well. So, for every and/or type calculation which looks like multiple inputs one output, you need to keep all the input bits.

Feynman has an interesting chapter on this in his lectures on computation, including a cool billiard ball computer (a la Ed Fredkin I think).