Does bitcoin mining take work? I'm neither a professional in cryptocurrency nor physics, but an interesting idea occurred to me. Bitcoin involves mining, which generates a lot of heat as waste.
Is the amount of heat produced by a computer mining bitcoin the same as a traditional heater, if they have the same input power?
I know of course about the law of conservation of energy, but it feels that some "work" has been done on the information in the system, and thus the waste heat energy produced would be less.
I know this mining is not work in the sense $W=Fd$, but it does seem to be decreasing the entropy in the universe by organising information. It feels intuitive that some energy should be used up in the very computation itself. If not, then wouldn't computation be free and hence it could be used to decrease entropy (by organizing information) without using energy?
 A: I wouldn't say it is organising information
Bitcoin uses one thing called Proof of Work (PoW), which consists in varying some numbers until the hash function matches a target number of zeros.
You're not generating information differently than solving a numerical equation. The energy used in the PoW comes from the power supply. One part is inverted in the computer performance itself, and the rest is heat... but this is not too different than solving a numerical problem, or drawing in a really high resolution image, or any other computer action.
PoW consumes tons of energy, because it is made with that purpose: have a big obstacle so that you cannot get the block for free
There are many people searching for more sustainable alternatives, such as Proof of Useful Work (POUW)
A: Organising information requires energy but most of that energy ends up as heat because current computing technology depends on irreversible processes. If you try to use only reversible processes you will find that random changes in the environment quickly undo your organisation - like trying to sweep up the leaves on your lawn in a high wind - unless you take great care to isolate your computer from the outside world.
We can tell very precisely where the electrical energy that flows from your wall socket to your bitcoin miner ends up. Some of it is used to push electrons around circuits on PCBs. This energy ends up as heat, due to resistance in the circuits. Some of it is used to flash LEDs on or off - some of this energy ends up in light waves, but most of it ends up as heat. Some of is used to run fans to move the heat produced by all those busy electrons away from the PCBs. This energy also mostly ends up as heat - due to friction - although a small amount ends up as sound waves. Some of it ends up as energy in electromagnetic waves as the miner talks to your WiFi router.
But if we leave aside the small amount of energy sent out in EM waves and sound waves, all the rest of the energy used by your miner ends up as heat. And this is the same regardless of whether the PCBs are mining bitcoins or just flipping bits billions of times a second.
So your bitcoin miner is basically a room heater that might generate a very small amount of income as a side effect to offset its running costs. Indeed, there are companies that market cryptocurrency miners as (very expensive) room heaters.
A: 
It feels intuitive that some energy should be used up in the very computation itself. If not, then wouldn't computation be free and hence it could be used to decrease entropy (by organizing information) without using energy.

Computation is not a physics concept. There is no principle in physics which would restrict all kinds of computation to take at least some minimum energy per "bits processed" or something like that; maybe there can be zero-energy-cost computation and maybe even zero-energy-cost useful computation. For example, according to some people, molecular motion of gas in a bottle is nature doing computation; this process takes no energy.
What you are close to describing is not a useful computation in computers (which does not produce anything resembling low entropy state), but rather a process in which large block of memory cells gets reset so each cell represents zero at the same temperature. If initially the block represented some random data, and zeroes after the resetting process is done adn the memory block is back at original temperature, then entropy of the block arguably got decreased by some small amount. So this process, while dissipating energy into heat, also decreases entropy of the memory block in the end (when the produced heat gets removed). Total entropy of the memory block and environment however will still increase, so there is no problem with 2nd law.
This memory resetting takes energy in practice because to switch a memory cell, at least energy of order $k_BT$ is needed and this gets dissipated. This is because the different logical states have to be separated by energy barrier at least of this magnitude to be stable against thermal motion, and there is no way to recover the energy after the switching process is over.
So from physics perspective, switching memory cells certainly takes energy, but things are much less clear for computation.
A: 
Is the amount of heat produced by a computer mining bitcoin the same as a traditional heater, if they have the same input power?

Yes$^1$. In fact all heat is the same. There is only one heat. Be it the thermal energy stored in a mass by virtue of its temperature or be it the heat being generated at the core of stars. In fact, all forms of energy are same and in theory, inter-convertible. They differ only in the manner they are generated.

I know of course about the law of conservation of energy, but it feels that some "work" has been done on the information in the system, and thus the waste heat energy produced would be less.

The amount of waste energy is not dependent on what the input power is being used for. A traditional heater of the same effective power and efficiency as a mining computer would also do the same work as the computer: the difference is that it  does work to produce thermal energy (separate form the waste, err, thermal energy) while the computer does work to process "information".
I would like to point out here, that the waste heat generated in a computer, during mining or any other regular task is mostly not the heat generated during erasure of information (which coincidentally, also generated heat but is far less than what current architecture efficiencies already loose) but rather the joule heating of circuits, leakage currents and other losses.

I know this mining is not work in the sense W=Fd

It is. All work is ultimately, at the fundamental level, $W=\vec{F}.\vec{d}$ since that is the definition of work. Be it work done to heat stuff, work done in muscles, work done in computers. Reasoning how exactly that happens if its not evident at the face of the system, is another matter altogether.

but it does seem to be decreasing the entropy in the universe by organizing information. It feels intuitive that some energy should be used up in the very computation itself.

I commend your intuition. The fact that information erasure must necessarily accompany an energy cost is in fact true, at least in classical thermodynamics. Erasure of information is an irreversible process. Such erasures are necessary in any device using boolean logic since classical gates are irreversible. This loss then sets the lower limit on how much energy must be wasted in irreversible information erasures. As mentioned before, real-world devices waste a lot more than this.

If not, then wouldn't computation be free and hence it could be used to decrease entropy (by organizing information) without using energy?

The fact that irreversible information erasure must accompany energy expenditure and net entropy increase are related as both deal with counting the states of the system. However, I am not clear on the specifics.
So, finally

Does bitcoin mining take work waste energy ?

Yes, but not in any way different from any other heat engine. From an information perspective, the only unique thing about a compute process,  is the energy loss from information erasure, which in the real world is minuscule relative to other losses.

$^1$ if they have the same efficiency but that's understood I guess.
A: There no lower bound that I am aware of to the possible energy efficiency of Bitcoin mining here on Earth where the temperature is about $300K$ since with sufficiently good engineering Bitcoin mining can be done using completely reversible computation, and Landauer's limit is not relevant in this case.
Recall that Landauer's principle states that in computing, it costs at least $k_B\cdot T\cdot\ln(2)$ energy to delete a bit of information. Here, $k_B$ is Boltzmann's constant, and $T$ is the temperature. For example, if one has 1 billion uniformly random independent bits in memory, then it will cost at least $k_B\cdot T\cdot\ln(2)\cdot 10^9$ energy to replace each of those bits with zeros; the decrease in entropy in the memory implies that entropy increases elsewhere. Recall that reversible computation is the type of computation where one does not delete information. Since with fully reversible computation, one does not delete information, Landauer's limit does not apply to fully reversible computation, and fully reversible computation can theoretically be made arbitrarily energy efficient. With that being said, we currently do not have these energy efficient reversible computers, and constructing these energy efficient reversible computers and making them profitable will be a difficult engineering challenge. Cryptocurrency mining including SHA-256 Bitcoin mining can make this engineering challenge a bit easier; cryptographic hash functions like SHA-256 are somewhat naturally suited for reversible computational hardware, and one can design cryptocurrency mining algorithms in order to make this engineering challenge as easy as possible. There is evidence that reversible computers where the energy expenditure per logic gate is well below Landauer's limit will eventually be built. Ralph Merkle and his collaborators have demonstrated that it should be possible to produce mechanical reversible computing systems using only links and rotary joints whose energy efficiencies are "several orders of magnitude smaller than $k_BT = 4.1 × 10^{−21}J$ at $T = 300 K$."
One should think of fully reversible computation as a restricted version of classical computation. Researchers such as Charles Bennett have shown that reversible computation can simulate all classical computation with a manageable computational complexity overhead.
Brute force search algorithms (more generally, backtracking algorithms) such as the algorithm for Bitcoin mining can easily be made into completely reversible algorithms with minimal computational complexity overhead. Therefore, the theoretical infimum amount of energy expenditure for this reversible Bitcoin mining algorithm per hash is zero.
The goal of the following brute force search problem is to find an input i where w=12321 after we perform the assignments w=i; x=((i+214)^(i+142211))+(w&1231); w-=(x&13321). The algorithm is written in the reversible programming language Janus.
i w x

procedure proofofwork
    w+=i
    x^=((i+214)^(i+142211))+(w&1231)
    w-=(x&13321)


procedure main
    call proofofwork
    from i=0 do
        uncall proofofwork
        i+=1
        call proofofwork

    until (w=12321)
        uncall proofofwork

The output of this program for solving a brute force search problem (and this output includes all possible garbage information) is
i = 20513
w = 0
x = 0

and i=20513 is a solution to this brute force search problem. Observe that we do not have any garbage information. One should also observe that we need to uncall the function proofofwork in order to reversibly clean up the garbage information. This means that the reversible brute force search algorithm will require twice the operations as the irreversible brute force search algorithm and possibly much more memory (for reversible brute force search problems, there are tradeoffs between time, space, and the amount of reversibility; there may come a point in time where a partially reversible Bitcoin mining machine is the most efficient).
