It uses energy to do so— just like a heat pump can heat your home with greater output than electrical input, but not no electrical input.

The more exciting detail is that computation itself doesn't increase entropy, at least not if reversible computing is use. Only errors or, rather, their correction do... So things may be more rosy than you might guess: http://arxiv.org/abs/quant-ph/9908043