Don’t take this the wrong way, but if you actually have a way to do irreversible erasures whp at energy << 40kT, that is a publish-worthy result!
Yeah, that Frank quote is intriguing. I was previously suspecting that if I talked to an actual expert about this they’d be saying: “yeah yeah, we know all this rudimentary stuff already, stop wasting my time”. It would be exciting if this was a new result.
For us not to be talking past each other, you need to focus discussion on the probability of erasing a single specific bit from the system [...] The expected cost of erasure is completely irrelevant, we are talking specifically and only about the probability of erasure success, for a single specific bit, for a single specific compute cycle of a machine (although we can assume thermal equilibrium).
Yes, I’m indeed claiming to get high reliability erasures every time we do a bit erase operation. The error probabilities are 10−15, etc. The expectation is over energy cost, so the operation sometimes dissipates more energy and sometimes less, but the bit is always erased (unless you’re in one of the unlucky cases, but the chance of that is 10−15). If you look at the graph, you’ll see that the probability trace for successful erasure asymptotes to 1. (At the point where the graph ends, it’s reached 1−10−15.)
You can’t just magically reliably raise/lower the energy wall, as reliably lowering the 40kT energy wall is obviously now just moving a new bit, which you need to either 1. keep track of (reversible computing), or 2. forget/erase and thus pay 40kT.
This isn’t obvious at all to me, so I think you’ll need to explain your objection here. Raising and lowering the energies of states isn’t associated with any extra information: It happens exactly the same way on every bit erase cycle. There’s no extra information produced that needs to be erased. If there were, then it would also prove Landauer’s analysis of the double well is incorrect, since Landauer needs to lift the energy of the 1 state so that the particle will diffuse over to the 0 state. If I looked at what the particle was doing before deciding how to move the wall, that would be a different story, but both Landauer and I are moving the state energies around in exactly the same way each time, so we don’t have to worry about creating an infinite recursive turtle stack of extra bits to erase.
Only at zero temp and or with zero reliability. You give an arbitrary example of a Hamiltonian where you’ve already assumed your conclusion. Let’s focus this discussion exclusively on classical physics/systems, unless you believe your argument only applies due to QM effects.
My argument does apply in the classical case too. See here to cover moving a particle between states for a very low energy cost even in an environment with lots of thermal noise. To translate that into moving a bit, do the same thing for two states in parallel (with energy wall in between for high reliability).
Erasure is just a bit moving outside of the computational system, but otherwise is exactly the same as moving a bit inside the system.
Yes, but the analogy says that if I move the bit from one part of the system to the other, I have to give the associated energy cost to that part of the system. I don’t have to dissipate it to the environment. I only have to dissipate energy to the environment if I’m trying to send a bit to the environment. Hence why erasure is costly while bit movement between internal computer parts is not. (Speaking in terms of the fundamental thermodynamic limits, of course.)
(There’s a relatively minor technical point here, which is that parts of the computer are generally not assumed to be in thermal equilibrium, though the environment is. So the parts of the computer can contain unused negentropy inside them, and they can use that to accept a bit, rather forcing me to send them energy. It’s not a free lunch, of course, a resource is still used, namely the negentropy, so the importance of the point is relatively minor.)
I’ve looked over your math/code a bit and I don’t understand this in particular:
“”“ diagonal elements of connection matrix should be 0 “””
And looking at your steady state condition it looks like it converges to a transition probability of 1 if the energy levels are the same? Which doesn’t seem right, the convergence should be only to 0.5 - if we consider two possible locations/states the particle could be in, and they have the same energy, at equilibrium they have the same probability. Perhaps your connections are symmetric and normalization makes it equivalent, but that isn’t clear if so.
Regardless, the code comment above seems to indicate you are not allowing the particle to stay in its starting state, which seems probably fatal.
Erasure is just a bit moving outside of the computational system, but otherwise is exactly the same as moving a bit inside the system.
Yes, but the analogy says that if I move the bit from one part of the system to the other, I have to give the associated energy cost to that part of the system. I don’t have to dissipate it to the environment. I only have to dissipate energy to the environment if I’m trying to send a bit to the environment.
If there are two locations/states for the particle: A and B, then the probability distribution converges to the Boltzmann based on relative energy levels. If there is no energy gap between A and B, the probability is 50:50.
If we assume that both A and B are stable states whp then they must be lower potential energy favored states with a gap of ΔE vs nearby background states. Moving the particle up and out of one such well and into the other simply requires energy ΔE.
Any such potential energy wells are only created by yet other particles which themselves must also be in equally stable low energy configurations for the well to be stable, and so the argument applies recursively—manipulating the wells is just equivalent to moving particles out of wells.
Consider a simple minimal example of a computer built from dominoes. The starting up “0” state of a domino must have energy ΔE to be stable against noise so ΔE≈40KBT (imagine a continuous windstorm/earthquake). The down “1″ state is typically even more stable with energy ~2ΔE. A small force imparting on order ΔE to an input domino can then start a propagating flow of computation which results in perhaps half of the dominoes in the lowest energy 1 state.
The energy cost of one such cycle is very low as it’s just a constant on order ΔE, but only because it hasn’t yet erased any bits. In this system clearing the computational garbage by erasing all the 1 bits requires on order ~2ΔE per bit for moving each 1 bit back to the starting 0 state, and in general it requires at least ΔE to move a particle/bit out of some static low energy local minima (well) which must be ΔE lower than the background for stability.
Reversible computers avoid erasure costs by some combination of propagating bits ballistically through moving particles/waves and/or logically reversing time and uncomputing bits, but they don’t reduce the energy cost of reliable erasure.
The connection matrix is symmetric and has entries that are 0 or 1, and it represents a graph (you can put in entries that are fractions to represent a case where states are partially connected (i.e. connected but the maximum flow rate between them is lower than 1/τ)). Non-zero diagonal entries represent a state being connected to itself, which is kind of pointless since the flow is going to be 0 in any case.
And looking at your steady state condition it looks like it converges to a transition probability of 1 if the energy levels are the same?
For E1=E2, the steady state condition is:
p1p2=e−βE1e−βE2=1
The normalized distribution which satisfies this requirement is p1=p2=12.
Regardless, the code comment above seems to indicate you are not allowing the particle to stay in its starting state, which seems probably fatal.
It’s a continuous-time differential equation, so the outward flow of probability is continuous in the model. In a small timestep Δt, most particles are not going to change which state they’re in.
Any such potential energy wells are only created by yet other particles which themselves must also be in equally stable low energy configurations for the well to be stable, and so the argument applies recursively—manipulating the wells is just equivalent to moving particles out of wells.
I ask again: If any manipulation of wells recursively creates another bit that we have to erase, then what’s the difference between my well manipulations and Landauer’s? Or for that matter, your domino resetting device? Why doesn’t you model imply that all 3 get mired in an eternal cycle of “create a bit to erase a bit”?
Our initial particle has an entropy associated with it, since it has two possible states, and these allow it to represent a bit. The other particles producing the energy wells do not need to have any entropy, they can be sitting in a single state at the bottom of their own well with high energy walls all around. Because those parts of the device require no information, they can operate ballistically. To take a concrete model, we can build a big wheel with charges glued to various points along its circumference. The wheel spins and charges move past the set of states where we’re keeping our particle, and depending on which charge is close, the energy of each states is raised and lowered. If we’ve designed a good bearing for the wheel, then the slowing of the wheel will be entirely due to its interaction with the particle.
It’s a continuous-time differential equation, so the outward flow of probability is continuous in the model. In a small timestep Δt, most particles are not going to change which state they’re in.
This still seem fatal, as it implies that any arbitrarily tiny transition energy will converge to the bit exiting the bit well, which obviously is not physically correct (and contradicts the claim that the bit well was stable against noise). Once you include the required diagonals I think your mechanism no longer works.
I ask again: If any manipulation of wells recursively creates another bit that we have to erase, then what’s the difference between my well manipulations and Landauer’s? Or for that matter, your domino resetting device? Why doesn’t you model imply that all 3 get mired in an eternal cycle of “create a bit to erase a bit”?
The difference is the domino resetting device (or any practical actual current CMOS computer, or bio neural network etc) erases/thermalizes bits, so it doesn’t have to continue keeping track of them.
None of the published reversible computers designs I’ve seen claim to erase reliably for much less than 1eV btw. That’s not the focus at all, instead they save energy by eliminating unnecessary erasures.
If we’ve designed a good bearing for the wheel, then the slowing of the wheel will be entirely due to its interaction with the particle.
Therein is the problem as this slowing of the wheel will need be about ΔE≈40KBT per bit to reliably eject bits.
To actually reliably erase all the bits, the wheel needs to eject them from their low energy wells, which thus requires ΔE≈40KBT per bit, because each bit had to be in a well with energy that much lower than the neighborhood. So to the extent your wheel works it’s just equivalent to the domino erasure mechanism (which could be having all the dominoes linked to axle rods and levers to a motor etc).
You could try to use the wheel to implement a temporary well, but that doesn’t work because it is not sufficient to simply lower the well as that doesn’t give the particle enough energy to move out of its location reliably.
You can move bits around ballistically for free (within some limits on not being able to aim them very precisely), but again moving bits around is not erasing them.
This still seem fatal, as it implies that any arbitrarily tiny transition energy will converge to the bit exiting the bit well, rather than staying put against noise until the erasure signal, which contradicts the model.
I’m not 100% sure what you’re trying to say here, so forgive me if this is a wrong interpretation. The point is that a given energy wall height gives you a certain length of time in which to do computations. The flow out of a state can be suppressed exponentially by energy wall height, so in practice this can be a really long time. Also, flow out of a state is compensated by flow back into that state from other states so that overall things converge to the Boltzmann distribution. This isn’t relevant to how long it takes a bit to thermalize, though.
Also, “erasure signals” aren’t a thing in my model, see below.
The difference is the domino resetting device (or any practical actual current CMOS computer, or bio neural network etc) erases/thermalizes bits, so it doesn’t have to continue keeping track of them.
My procedure also erases/thermalizes bits so that they no longer need to be tracked, that’s the entire point of it. I think I’m having a hard time understanding what you’re getting at here.
This interaction now just moves a bit around, and we now need a full model of the wheel to see where that bit went. Energy/information is conserved and can’t be destroyed. Any time you lose track of it in your model you have erased/thermalized it, so I can just keep asking where the ~1eV bit went.
The particle jumps around between the states because it has some coupling to the environment, and the environment is full of thermal noise / fluctuations. Because physics is reversible, we could in theory chase the bit into the environment: In principle you can always keep track of where the bit went (at least if you’re Laplace’s demon). But let’s say that once we’ve put the bit into the environment, that’s good enough.
But we still used some energy to do that. We drained some energy from our battery to accomplish this task (maybe it’s a conventional battery or capacitor, or maybe it’s something more exotic, like a spinning flywheel).
The next thing you might worry about is that I cheated at the bit-erasing task by allowing some information to escape to the battery instead of the environment. Obviously there’s some information going into the environment, since coupling to the environment is the entire reason the particle is jumping between states. But maybe the battery is picking up most of the information. That would be bad! But it seems like it could happen, since the amount of energy drawn by the device is random, and then that introduces randomness into the level of energy reserves left in the battery.
First, a meditation: Consider the double slit experiment. Momentum is conserved, so if the photon is refracted through the lower slit and heads back up to hit the detector, some downward momentum must have been transferred to the card with the slits. Likewise, if the photon goes through the upper slit, the card must have gained some upward momentum. Quantum mechanics is very sensitive to leaked information. If even a single bit of information (which slit the photon went though) were leaked to the environment, then the interference pattern would disappear. Why doesn’t the “which way” information encoded in the momentum of the card have this effect?
Anyways, think about erasing a lot of bits. By the central limit theorem, the ratio of variance in the amount of energy left in the battery relative to the number of bits erased goes to zero.
Or say we already have a lot of thermal uncertainty about the amount of energy stored in the battery. Say it’s a Gaussian distribution. This has entropy:
12(1+log2π+logσ2)
If performing 1 erasure costs a small quantity of energy with similarly small variance ϵ2, then the change in entropy of the battery is going to look like:
12(log(σ2+ϵ2)−logσ2)≈ϵ22σ2
The larger the uncertainty in battery energy, the less entropy a little additional information is going to carry.
In any case, note that Landauer’s double-well erase procedure also has an energy cost that varies randomly. If the bit happens to be a 1, then it draws ~1eV, if the bit happens to be a 0 then it’s free. Neither Landauer nor I are secretly depending on being able to shuffle information into the battery, though.
Your device also no longer makes sense to me—how does it erase a bit (or not) on demand from an incoming wire signal? As the wheel now controls the bit well and the erasure, and the wheel isn’t controlled by the input signal, the device no longer works (at least not without yet more complexity).
My model (obviously other models are possible) of a reversible computer looks like a reversible circuit with some small number of irreversible gates. Those gates produce bits that need to be erased on every clock tick (the clock can be synced with the spinning flywheel). In order to do long serial computations, the rest of the output bits are looped back around to the input of the circuit so that more computation can be done on them in the next clock tick. So the flywheel bit erasing device just needs to be able to erase the bits coming out of the circuit on each clock tick, and there’s always the same number of them. No need for an extra separate “erasure on demand” signal / feature.
You can move bits around ballistically for free (within some limits on not being able to aim them very precisely), but again moving bits around is not erasing them.
Yes, I also agree that moving bits around is not erasing them.
Also, “erasure signals” aren’t a thing in my model, see below.
You need an erasure signal to erase a bit.
Let’s step back for a second and more formally define “erasure” and “bit”.
I see several meanings of “bit”:
A True Bit—A bit in computer RAM/registers etc—read/write controlled by arbitrary signal bits on signal lines.
A signal line bit propagating on a wire
A temporary ‘bit’ which is not necessary for 1 or 2 above, and thus isn’t really an irreducible bit
I believe to the extent your spinning wheel thing works, it is only ‘erasing’ type 3 non-bits, which is irrelevant. You need to show erasure of at least type-2, and really type-1 bits.
A reversible computer can already (in simplified theory at least) avoid all type 2 and 3 erasures completely, so it’s irrelevant how much energy they use. You need to show reliable type 1 bit erasure, or you should change your post to add disclaimers that your claimed ‘erasure’ doesn’t actually work for bits in RAM, and can’t actually reduce energy use for a reversible computer.
The entire wheel apparatus in your scheme is just a complex way of reversible propagation of bits on signal lines. We could just simplify that down to a single particle propagating on the signal line.
Yes, I also agree that moving bits around is not erasing them.
Right, and your flywheel thing so far is just moving an (irreducible) bit.
Generally, I don’t see a problem with using my procedure to erase a register in a computer. Seems like it would work fine for that, just like Landauer’s double well procedure would. It would also work fine to erase data directly in RAM, though I personally don’t think anyone’s going to ever build a reversible computer that works that way. Anyways, what I’m saying is my procedure would suffice to erase a Cannellian Type-1 bit.
The point of the wheel example is that you claimed that: “manipulating the wells is just equivalent to moving particles out of wells”. The wheel device provides a counterexample, since it changes the energy levels of the various states just by spinning. (It’s also an example of a situation where an “erasure signal” is not necessary to erase a bit, since it erases a bit on every clock tick.)
But I’m in general totally fine with having an erasure signal. When I say it’s not in my model, I mean that the basic erasure procedure I describe is independent of that kind of external detail.
Right, and your flywheel thing so far is just moving an (irreducible) bit.
Where is it moving to in your opinion? I provided you an argument that the answer isn’t the wheel. What’s left other than the environment?
Just also replying to a chunk of your earlier comment:
To actually reliably erase all the bits, the wheel needs to eject them from their low energy wells, which thus requires ΔE≈40KBT per bit, because each bit had to be in a well with energy that much lower than the neighborhood. So to the extent your wheel works it’s just equivalent to the domino erasure mechanism (which could be having all the dominoes linked to axle rods and levers to a motor etc).
You could try to use the wheel to implement a temporary well, but that doesn’t work because it is not sufficient to simply lower the well as that doesn’t give the particle enough energy to move out of its location reliably.
After lowering the wall between the two states, I do then actually raise up one of the states high enough to kick the particle out of it with high reliability. The reason this doesn’t cost the full 40kT is that as the energy of the state gets higher, the probability of the particle occupying that state is already decreasing. I only pay any energy cost if the particle happens to be occupying the state I’m currently lifting. So you do an integral to get the expected energy cost of kicking this particle all the way out, and it comes out to way less than 40kT. In fact, it comes out to exactly kTlog2 if we’re moving so slowly that the particle is always distributed over states according to the Boltzmann distribution. But if you want to finish quickly, it comes out to a little bit more.
Generally, I don’t see a problem with using my procedure to erase a register in a computer. Seems like it would work fine for that, just like Landauer’s double well procedure would. It would also work fine to erase data directly in RAM,
You haven’t described any mechanism to do this yet.
Your flywheel thing (to the extent I now understand it), just seems to be equivalent to representing a signal bit moving down a wire, which could just be simplified to a single minimal particle. You haven’t described anything that is capable of true bit erasure.
True bit erasure would require having a control signal which then controls the wheel, or something like that.
You haven’t described any mechanism to do this yet.
However you’re imagining Landauer’s double well procedure raises the energy level of one of the wells conditional on a control signal, you should be able to imagine my procedure being implemented in a similar way. What obstacle do you run into when you try to do this?
Just to give an explicit example, though, you can imagine the control signal being used to determine the position of the particle that encodes the bit. You have some states close to the wheel, and some far away. Far away states aren’t affected by the spinning of the wheel and if the particle is in the far states rather than the near states, then the wheel isn’t slowed down and the bit isn’t erased.
Choosing whether the particle goes into the near states or the far states conditional on a control bit is a reversible process, of course, so that completes the implementation.
However you’re imagining Landauer’s double well procedure raises the energy level of one of the wells conditional on a control signal, you should be able to imagine my procedure being implemented in a similar way.
I do not imagine it this way, as trying to manipulate the barrier just punts the issue. It’s simpler to imagine static wells which the particle/bit moves between, as in dominoes.
Just to give an explicit example, though, you can imagine the control signal being used to determine the position of the particle that encodes the bit.
This is not a true memory bit storage mechanism unless the particle is in some sort of loop in a low energy potential well about 1eV lower than the background. The control signal could come at any time or never and the bit must be stable for very long periods of time.
“Determining the position of the particle” requires deflecting it into 1 of 2 paths with high reliability, which requires energy on order 1eV. If you can reliably alter the particle’s path—you no longer need the wheel, as one path can just exit the device or thermalize to erase. Any attempt to recover the energy of the erased particle is a dead end which just punts the problem to a new mechanism for erasure.
The gate which is formed from this process has 2 unique bit inputs (memory bit, control wire bit) and only 1 unique bit output (the control wire bit), as the other is erased. It is fundamentally irreversible—it doesn’t matter how many complex additional mechanisms (flywheels) you tack on, they are just distractions.
I do not imagine it this way, as trying to manipulate the barrier just punts the issue. It’s simpler to imagine static wells which the particle/bit moves between, as in dominoes.
A machine which turns a domino right side up is in fact raising the energy of the “domino tipped over” state. If the domino stayed tipped over, the mechanical arm pushing the domino up would at some point be intersecting with the domino, a state of very high energy indeed. Unless you’re imagining some other way for the domino resetter to function?
This is not a true memory bit storage mechanism unless the particle is in some sort of loop in a low energy potential well about 1eV lower than the background. [...] “Determining the position of the particle” requires deflecting it into 1 of 2 paths with high reliability, which requires energy on order 1eV.
Yes, you need to be 1eV below extraneous nearby states to be doing anything sensible at all. This is an energy difference and not an energy cost. You’re not dissipating any energy because the particle is not occupying those states. Determining the position of the particle based on a control bit is a reversible operation. If you want to argue that it must cost 1eV, you need to explain either why the operation is not actually reversible, or why it must have a thermodynamically unavoidable energy cost anyways, despite being reversible.
The control signal could come at any time or never and the bit must be stable for very long periods of time.
So the particle is in the far away states by default and the control signal kicks it into the nearby states when the bit has to be erased.
If you can reliably alter the particle’s path—you no longer need the wheel, as one path can just exit the device or thermalize to erase. Any attempt to recover the energy of the erased particle is a dead end which just punts the problem to a new mechanism for erasure.
I’m certainly not saying the wheel part is necessary, it’s just a particular example I gave. I do think it’s allowed by thermodynamics to reliably and costlessly alter the particle’s path in ways that are reversible. I’m not trying to recover the energy from the erased bit (I assume you meant “bit” here, as particles aren’t erased). I’m spending the kTlog2 (on average), and then that’s the end of it.
The gate which is formed from this process has 2 unique bit inputs (memory bit, control wire bit) and only 1 unique bit output (the control wire bit), as the other is erased. It is fundamentally irreversible—it doesn’t matter how many complex additional mechanisms (flywheels) you tack on, they are just distractions.
No, the whole point of controllable erasures is that sometimes the bit isn’t erased. So we need 2 outputs, one for the control wire as you say, and one for the original bit since sometimes the erasure signal is 0 and so the bit isn’t erased. The gate is still irreversible, of course, but it seems like your mental model of the situation here is quite different than mine, so I’m pointing out the difference in the hopes of some clarification.
Can you explain why an ideal reversible device avoiding erasure costs wouldn’t reduce the energy cost of reliable erasure?
The Mike Frank quote mentioned previously seems to limit itself to irreversible devices :
As long as it’s a reliable, irreversible device, it will have to dissipate at least on the order of 1 electron volt (about 40 kT) per bit-operation in a room-temperature envronment, full stop, end of story.
Erasure is not reversible so this is a non question. An irreversible computer is then one that uses irreversible logic and gates at all levels, so it’s erasing bits everywhere just to compute everything, even though that is not required in theory. So a reversible computer doesn’t save energy by reducing the cost of each bit erasure, it saves energy by reducing the large quantity of unnecessary bit erasures. (But that turns out to be very hard to do and comes at a price)
It may be possible to still use reversible computation to even save the amount of energy required per bit deletion. It will be possible to use reversible computation to transform an unreliable but energy efficient bit deletion device into a reliable and energy efficient bit deletion device. We first need to take the random garbage data and send it through the efficient but unreliable bit deletion process. For example, if we have 10^9 bits of random data, then after the bit deletion process, 90% of those bits will be 1′s and the rest will be 0′s. One can then send this data through a data compression algorithm, and after compression, one will have about 0.47*10^9 bits of random data.
But I do not know if this is the best way of getting the energy efficiency of deletion close to Landauer’s limit.
We first need to take the random garbage data and send it through the efficient but unreliable bit deletion process.
I don’t actually see a way of doing this. The problem is that storing a bit reliably requires that it is in a deep low energy potential well, lower by about 1eV than the local neighborhood.
So if you try to use only 0.1 eV to eject the bit, you only get a tiny probability of success, and you need to apply about 1eV for 50% success, > 1eV to eject it reliably, etc.
So the problem is that a reliable bit is—by requirement—one that requires large energy on order 1eV to move out of it’s stable low energy local minimum (as otherwise it wouldn’t persist reliably against noise).
I am a mathematician and not a physicist, so I am not confident in my ability to look for weaknesses in my own reasoning about physics.
It seems like we need to be able to move a bit from an irreversible low reliability high efficiency mode with a low barrier to a reversible mode with a high barrier where we can perform reliable reversible computation. It looks like we need a way of reversibly lowering the barrier when we need to perform the unreliable deletion process followed by reversibly raising the barrier when we need to perform the reversible operations. Is there a way to reversibly raise and lower the barrier from 0.1 eV to 1eV or higher?
I am pretty sure that it should not be too difficult to make a good enough simulation of this to verify that everything works out correctly and is reversible except for the bit deletion.
Lowering the barrier just punts the problem to a new system component. See the long comment exchange with DaemonicSignal, where he ends up using a flywheel mechanism which is only capable of erasing non-bits (ie it doesn’t implement actual bit erasure).
Yes. A flywheel seems like a reasonable idea for a mechanism for raising and lowering a potential barrier. We just need to make sure that the flywheel is completely reversible. I was thinking about having a flywheel that hooks up to cams and followers that can mechanically raise and lower a physical barrier. This is probably an engineering challenge that will be about as difficult as the problem of making reversible computing hardware in the first place. It therefore seems like there are at least two problems of reversible computation that need to be overcome:
The most obvious problem is the problem of doing energy efficient purely reversible calculations.
The other problem is the problem of deleting a large quantity of bits in a way that does not consume much more than k*T*ln(2) energy per bit deleted. This will likely include the problem of reversibly raising and lowering an energy barrier so that we have a high energy barrier for reversible operations and so that we have a low energy barrier for bit deletions.
It seems like the few people who are working on reversible computation are focused on (1) while I have not heard anything on (2). I am a mathematician and not a researcher in these kinds of mechanisms, so I should end this post by saying that more research on this topic is needed. I would like for there to be research backed up by simulations that show that k*T*ln(2) per bit deletion is possible. I would be satisfied if these simulations were classical, mechanical simulations but which are reversible (you can run the simulation in reverse) and they incorporate thermal noise and the laws of thermodynamics.
5/21/2023 I just checked the 1970 paper ‘Minimal Energy Dissipation in Logic’ by Keyes and Landauer, and that gives another way of getting the energy efficiency of computation close to k*T*ln(2). This paper also uses the raising and lowering of a potential barrier.
Yeah, that Frank quote is intriguing. I was previously suspecting that if I talked to an actual expert about this they’d be saying: “yeah yeah, we know all this rudimentary stuff already, stop wasting my time”. It would be exciting if this was a new result.
Yes, I’m indeed claiming to get high reliability erasures every time we do a bit erase operation. The error probabilities are 10−15, etc. The expectation is over energy cost, so the operation sometimes dissipates more energy and sometimes less, but the bit is always erased (unless you’re in one of the unlucky cases, but the chance of that is 10−15). If you look at the graph, you’ll see that the probability trace for successful erasure asymptotes to 1. (At the point where the graph ends, it’s reached 1−10−15.)
This isn’t obvious at all to me, so I think you’ll need to explain your objection here. Raising and lowering the energies of states isn’t associated with any extra information: It happens exactly the same way on every bit erase cycle. There’s no extra information produced that needs to be erased. If there were, then it would also prove Landauer’s analysis of the double well is incorrect, since Landauer needs to lift the energy of the 1 state so that the particle will diffuse over to the 0 state. If I looked at what the particle was doing before deciding how to move the wall, that would be a different story, but both Landauer and I are moving the state energies around in exactly the same way each time, so we don’t have to worry about creating an infinite recursive turtle stack of extra bits to erase.
My argument does apply in the classical case too. See here to cover moving a particle between states for a very low energy cost even in an environment with lots of thermal noise. To translate that into moving a bit, do the same thing for two states in parallel (with energy wall in between for high reliability).
Yes, but the analogy says that if I move the bit from one part of the system to the other, I have to give the associated energy cost to that part of the system. I don’t have to dissipate it to the environment. I only have to dissipate energy to the environment if I’m trying to send a bit to the environment. Hence why erasure is costly while bit movement between internal computer parts is not. (Speaking in terms of the fundamental thermodynamic limits, of course.)
(There’s a relatively minor technical point here, which is that parts of the computer are generally not assumed to be in thermal equilibrium, though the environment is. So the parts of the computer can contain unused negentropy inside them, and they can use that to accept a bit, rather forcing me to send them energy. It’s not a free lunch, of course, a resource is still used, namely the negentropy, so the importance of the point is relatively minor.)
I’ve looked over your math/code a bit and I don’t understand this in particular:
And looking at your steady state condition it looks like it converges to a transition probability of 1 if the energy levels are the same? Which doesn’t seem right, the convergence should be only to 0.5 - if we consider two possible locations/states the particle could be in, and they have the same energy, at equilibrium they have the same probability. Perhaps your connections are symmetric and normalization makes it equivalent, but that isn’t clear if so.
Regardless, the code comment above seems to indicate you are not allowing the particle to stay in its starting state, which seems probably fatal.
If there are two locations/states for the particle: A and B, then the probability distribution converges to the Boltzmann based on relative energy levels. If there is no energy gap between A and B, the probability is 50:50.
If we assume that both A and B are stable states whp then they must be lower potential energy favored states with a gap of ΔE vs nearby background states. Moving the particle up and out of one such well and into the other simply requires energy ΔE.
Any such potential energy wells are only created by yet other particles which themselves must also be in equally stable low energy configurations for the well to be stable, and so the argument applies recursively—manipulating the wells is just equivalent to moving particles out of wells.
Consider a simple minimal example of a computer built from dominoes. The starting up “0” state of a domino must have energy ΔE to be stable against noise so ΔE≈40KBT (imagine a continuous windstorm/earthquake). The down “1″ state is typically even more stable with energy ~2ΔE. A small force imparting on order ΔE to an input domino can then start a propagating flow of computation which results in perhaps half of the dominoes in the lowest energy 1 state.
The energy cost of one such cycle is very low as it’s just a constant on order ΔE, but only because it hasn’t yet erased any bits. In this system clearing the computational garbage by erasing all the 1 bits requires on order ~2ΔE per bit for moving each 1 bit back to the starting 0 state, and in general it requires at least ΔE to move a particle/bit out of some static low energy local minima (well) which must be ΔE lower than the background for stability.
Reversible computers avoid erasure costs by some combination of propagating bits ballistically through moving particles/waves and/or logically reversing time and uncomputing bits, but they don’t reduce the energy cost of reliable erasure.
The connection matrix is symmetric and has entries that are 0 or 1, and it represents a graph (you can put in entries that are fractions to represent a case where states are partially connected (i.e. connected but the maximum flow rate between them is lower than 1/τ)). Non-zero diagonal entries represent a state being connected to itself, which is kind of pointless since the flow is going to be 0 in any case.
For E1=E2, the steady state condition is:
p1p2=e−βE1e−βE2=1
The normalized distribution which satisfies this requirement is p1=p2=12.
It’s a continuous-time differential equation, so the outward flow of probability is continuous in the model. In a small timestep Δt, most particles are not going to change which state they’re in.
I ask again: If any manipulation of wells recursively creates another bit that we have to erase, then what’s the difference between my well manipulations and Landauer’s? Or for that matter, your domino resetting device? Why doesn’t you model imply that all 3 get mired in an eternal cycle of “create a bit to erase a bit”?
Our initial particle has an entropy associated with it, since it has two possible states, and these allow it to represent a bit. The other particles producing the energy wells do not need to have any entropy, they can be sitting in a single state at the bottom of their own well with high energy walls all around. Because those parts of the device require no information, they can operate ballistically. To take a concrete model, we can build a big wheel with charges glued to various points along its circumference. The wheel spins and charges move past the set of states where we’re keeping our particle, and depending on which charge is close, the energy of each states is raised and lowered. If we’ve designed a good bearing for the wheel, then the slowing of the wheel will be entirely due to its interaction with the particle.
This still seem fatal, as it implies that any arbitrarily tiny transition energy will converge to the bit exiting the bit well, which obviously is not physically correct (and contradicts the claim that the bit well was stable against noise). Once you include the required diagonals I think your mechanism no longer works.
The difference is the domino resetting device (or any practical actual current CMOS computer, or bio neural network etc) erases/thermalizes bits, so it doesn’t have to continue keeping track of them.
None of the published reversible computers designs I’ve seen claim to erase reliably for much less than 1eV btw. That’s not the focus at all, instead they save energy by eliminating unnecessary erasures.
Therein is the problem as this slowing of the wheel will need be about ΔE≈40KBT per bit to reliably eject bits.
To actually reliably erase all the bits, the wheel needs to eject them from their low energy wells, which thus requires ΔE≈40KBT per bit, because each bit had to be in a well with energy that much lower than the neighborhood. So to the extent your wheel works it’s just equivalent to the domino erasure mechanism (which could be having all the dominoes linked to axle rods and levers to a motor etc).
You could try to use the wheel to implement a temporary well, but that doesn’t work because it is not sufficient to simply lower the well as that doesn’t give the particle enough energy to move out of its location reliably.
You can move bits around ballistically for free (within some limits on not being able to aim them very precisely), but again moving bits around is not erasing them.
I’m not 100% sure what you’re trying to say here, so forgive me if this is a wrong interpretation. The point is that a given energy wall height gives you a certain length of time in which to do computations. The flow out of a state can be suppressed exponentially by energy wall height, so in practice this can be a really long time. Also, flow out of a state is compensated by flow back into that state from other states so that overall things converge to the Boltzmann distribution. This isn’t relevant to how long it takes a bit to thermalize, though.
Also, “erasure signals” aren’t a thing in my model, see below.
My procedure also erases/thermalizes bits so that they no longer need to be tracked, that’s the entire point of it. I think I’m having a hard time understanding what you’re getting at here.
The particle jumps around between the states because it has some coupling to the environment, and the environment is full of thermal noise / fluctuations. Because physics is reversible, we could in theory chase the bit into the environment: In principle you can always keep track of where the bit went (at least if you’re Laplace’s demon). But let’s say that once we’ve put the bit into the environment, that’s good enough.
But we still used some energy to do that. We drained some energy from our battery to accomplish this task (maybe it’s a conventional battery or capacitor, or maybe it’s something more exotic, like a spinning flywheel).
The next thing you might worry about is that I cheated at the bit-erasing task by allowing some information to escape to the battery instead of the environment. Obviously there’s some information going into the environment, since coupling to the environment is the entire reason the particle is jumping between states. But maybe the battery is picking up most of the information. That would be bad! But it seems like it could happen, since the amount of energy drawn by the device is random, and then that introduces randomness into the level of energy reserves left in the battery.
First, a meditation: Consider the double slit experiment. Momentum is conserved, so if the photon is refracted through the lower slit and heads back up to hit the detector, some downward momentum must have been transferred to the card with the slits. Likewise, if the photon goes through the upper slit, the card must have gained some upward momentum. Quantum mechanics is very sensitive to leaked information. If even a single bit of information (which slit the photon went though) were leaked to the environment, then the interference pattern would disappear. Why doesn’t the “which way” information encoded in the momentum of the card have this effect?
Anyways, think about erasing a lot of bits. By the central limit theorem, the ratio of variance in the amount of energy left in the battery relative to the number of bits erased goes to zero.
Or say we already have a lot of thermal uncertainty about the amount of energy stored in the battery. Say it’s a Gaussian distribution. This has entropy:
12(1+log2π+logσ2)
If performing 1 erasure costs a small quantity of energy with similarly small variance ϵ2, then the change in entropy of the battery is going to look like:
12(log(σ2+ϵ2)−logσ2)≈ϵ22σ2
The larger the uncertainty in battery energy, the less entropy a little additional information is going to carry.
In any case, note that Landauer’s double-well erase procedure also has an energy cost that varies randomly. If the bit happens to be a 1, then it draws ~1eV, if the bit happens to be a 0 then it’s free. Neither Landauer nor I are secretly depending on being able to shuffle information into the battery, though.
My model (obviously other models are possible) of a reversible computer looks like a reversible circuit with some small number of irreversible gates. Those gates produce bits that need to be erased on every clock tick (the clock can be synced with the spinning flywheel). In order to do long serial computations, the rest of the output bits are looped back around to the input of the circuit so that more computation can be done on them in the next clock tick. So the flywheel bit erasing device just needs to be able to erase the bits coming out of the circuit on each clock tick, and there’s always the same number of them. No need for an extra separate “erasure on demand” signal / feature.
Yes, I also agree that moving bits around is not erasing them.
You need an erasure signal to erase a bit.
Let’s step back for a second and more formally define “erasure” and “bit”.
I see several meanings of “bit”:
A True Bit—A bit in computer RAM/registers etc—read/write controlled by arbitrary signal bits on signal lines.
A signal line bit propagating on a wire
A temporary ‘bit’ which is not necessary for 1 or 2 above, and thus isn’t really an irreducible bit
I believe to the extent your spinning wheel thing works, it is only ‘erasing’ type 3 non-bits, which is irrelevant. You need to show erasure of at least type-2, and really type-1 bits.
A reversible computer can already (in simplified theory at least) avoid all type 2 and 3 erasures completely, so it’s irrelevant how much energy they use. You need to show reliable type 1 bit erasure, or you should change your post to add disclaimers that your claimed ‘erasure’ doesn’t actually work for bits in RAM, and can’t actually reduce energy use for a reversible computer.
The entire wheel apparatus in your scheme is just a complex way of reversible propagation of bits on signal lines. We could just simplify that down to a single particle propagating on the signal line.
Right, and your flywheel thing so far is just moving an (irreducible) bit.
Generally, I don’t see a problem with using my procedure to erase a register in a computer. Seems like it would work fine for that, just like Landauer’s double well procedure would. It would also work fine to erase data directly in RAM, though I personally don’t think anyone’s going to ever build a reversible computer that works that way. Anyways, what I’m saying is my procedure would suffice to erase a Cannellian Type-1 bit.
The point of the wheel example is that you claimed that: “manipulating the wells is just equivalent to moving particles out of wells”. The wheel device provides a counterexample, since it changes the energy levels of the various states just by spinning. (It’s also an example of a situation where an “erasure signal” is not necessary to erase a bit, since it erases a bit on every clock tick.)
But I’m in general totally fine with having an erasure signal. When I say it’s not in my model, I mean that the basic erasure procedure I describe is independent of that kind of external detail.
Where is it moving to in your opinion? I provided you an argument that the answer isn’t the wheel. What’s left other than the environment?
Just also replying to a chunk of your earlier comment:
After lowering the wall between the two states, I do then actually raise up one of the states high enough to kick the particle out of it with high reliability. The reason this doesn’t cost the full 40kT is that as the energy of the state gets higher, the probability of the particle occupying that state is already decreasing. I only pay any energy cost if the particle happens to be occupying the state I’m currently lifting. So you do an integral to get the expected energy cost of kicking this particle all the way out, and it comes out to way less than 40kT. In fact, it comes out to exactly kTlog2 if we’re moving so slowly that the particle is always distributed over states according to the Boltzmann distribution. But if you want to finish quickly, it comes out to a little bit more.
You haven’t described any mechanism to do this yet.
Your flywheel thing (to the extent I now understand it), just seems to be equivalent to representing a signal bit moving down a wire, which could just be simplified to a single minimal particle. You haven’t described anything that is capable of true bit erasure.
True bit erasure would require having a control signal which then controls the wheel, or something like that.
However you’re imagining Landauer’s double well procedure raises the energy level of one of the wells conditional on a control signal, you should be able to imagine my procedure being implemented in a similar way. What obstacle do you run into when you try to do this?
Just to give an explicit example, though, you can imagine the control signal being used to determine the position of the particle that encodes the bit. You have some states close to the wheel, and some far away. Far away states aren’t affected by the spinning of the wheel and if the particle is in the far states rather than the near states, then the wheel isn’t slowed down and the bit isn’t erased.
Choosing whether the particle goes into the near states or the far states conditional on a control bit is a reversible process, of course, so that completes the implementation.
I do not imagine it this way, as trying to manipulate the barrier just punts the issue. It’s simpler to imagine static wells which the particle/bit moves between, as in dominoes.
This is not a true memory bit storage mechanism unless the particle is in some sort of loop in a low energy potential well about 1eV lower than the background. The control signal could come at any time or never and the bit must be stable for very long periods of time.
“Determining the position of the particle” requires deflecting it into 1 of 2 paths with high reliability, which requires energy on order 1eV. If you can reliably alter the particle’s path—you no longer need the wheel, as one path can just exit the device or thermalize to erase. Any attempt to recover the energy of the erased particle is a dead end which just punts the problem to a new mechanism for erasure.
The gate which is formed from this process has 2 unique bit inputs (memory bit, control wire bit) and only 1 unique bit output (the control wire bit), as the other is erased. It is fundamentally irreversible—it doesn’t matter how many complex additional mechanisms (flywheels) you tack on, they are just distractions.
A machine which turns a domino right side up is in fact raising the energy of the “domino tipped over” state. If the domino stayed tipped over, the mechanical arm pushing the domino up would at some point be intersecting with the domino, a state of very high energy indeed. Unless you’re imagining some other way for the domino resetter to function?
Yes, you need to be 1eV below extraneous nearby states to be doing anything sensible at all. This is an energy difference and not an energy cost. You’re not dissipating any energy because the particle is not occupying those states. Determining the position of the particle based on a control bit is a reversible operation. If you want to argue that it must cost 1eV, you need to explain either why the operation is not actually reversible, or why it must have a thermodynamically unavoidable energy cost anyways, despite being reversible.
So the particle is in the far away states by default and the control signal kicks it into the nearby states when the bit has to be erased.
I’m certainly not saying the wheel part is necessary, it’s just a particular example I gave. I do think it’s allowed by thermodynamics to reliably and costlessly alter the particle’s path in ways that are reversible. I’m not trying to recover the energy from the erased bit (I assume you meant “bit” here, as particles aren’t erased). I’m spending the kTlog2 (on average), and then that’s the end of it.
No, the whole point of controllable erasures is that sometimes the bit isn’t erased. So we need 2 outputs, one for the control wire as you say, and one for the original bit since sometimes the erasure signal is 0 and so the bit isn’t erased. The gate is still irreversible, of course, but it seems like your mental model of the situation here is quite different than mine, so I’m pointing out the difference in the hopes of some clarification.
Can you explain why an ideal reversible device avoiding erasure costs wouldn’t reduce the energy cost of reliable erasure?
The Mike Frank quote mentioned previously seems to limit itself to irreversible devices :
Erasure is not reversible so this is a non question. An irreversible computer is then one that uses irreversible logic and gates at all levels, so it’s erasing bits everywhere just to compute everything, even though that is not required in theory. So a reversible computer doesn’t save energy by reducing the cost of each bit erasure, it saves energy by reducing the large quantity of unnecessary bit erasures. (But that turns out to be very hard to do and comes at a price)
It may be possible to still use reversible computation to even save the amount of energy required per bit deletion. It will be possible to use reversible computation to transform an unreliable but energy efficient bit deletion device into a reliable and energy efficient bit deletion device. We first need to take the random garbage data and send it through the efficient but unreliable bit deletion process. For example, if we have 10^9 bits of random data, then after the bit deletion process, 90% of those bits will be 1′s and the rest will be 0′s. One can then send this data through a data compression algorithm, and after compression, one will have about 0.47*10^9 bits of random data.
But I do not know if this is the best way of getting the energy efficiency of deletion close to Landauer’s limit.
I don’t actually see a way of doing this. The problem is that storing a bit reliably requires that it is in a deep low energy potential well, lower by about 1eV than the local neighborhood.
So if you try to use only 0.1 eV to eject the bit, you only get a tiny probability of success, and you need to apply about 1eV for 50% success, > 1eV to eject it reliably, etc.
So the problem is that a reliable bit is—by requirement—one that requires large energy on order 1eV to move out of it’s stable low energy local minimum (as otherwise it wouldn’t persist reliably against noise).
I am a mathematician and not a physicist, so I am not confident in my ability to look for weaknesses in my own reasoning about physics.
It seems like we need to be able to move a bit from an irreversible low reliability high efficiency mode with a low barrier to a reversible mode with a high barrier where we can perform reliable reversible computation. It looks like we need a way of reversibly lowering the barrier when we need to perform the unreliable deletion process followed by reversibly raising the barrier when we need to perform the reversible operations. Is there a way to reversibly raise and lower the barrier from 0.1 eV to 1eV or higher?
I am pretty sure that it should not be too difficult to make a good enough simulation of this to verify that everything works out correctly and is reversible except for the bit deletion.
Lowering the barrier just punts the problem to a new system component. See the long comment exchange with DaemonicSignal, where he ends up using a flywheel mechanism which is only capable of erasing non-bits (ie it doesn’t implement actual bit erasure).
Yes. A flywheel seems like a reasonable idea for a mechanism for raising and lowering a potential barrier. We just need to make sure that the flywheel is completely reversible. I was thinking about having a flywheel that hooks up to cams and followers that can mechanically raise and lower a physical barrier. This is probably an engineering challenge that will be about as difficult as the problem of making reversible computing hardware in the first place. It therefore seems like there are at least two problems of reversible computation that need to be overcome:
The most obvious problem is the problem of doing energy efficient purely reversible calculations.
The other problem is the problem of deleting a large quantity of bits in a way that does not consume much more than k*T*ln(2) energy per bit deleted. This will likely include the problem of reversibly raising and lowering an energy barrier so that we have a high energy barrier for reversible operations and so that we have a low energy barrier for bit deletions.
It seems like the few people who are working on reversible computation are focused on (1) while I have not heard anything on (2). I am a mathematician and not a researcher in these kinds of mechanisms, so I should end this post by saying that more research on this topic is needed. I would like for there to be research backed up by simulations that show that k*T*ln(2) per bit deletion is possible. I would be satisfied if these simulations were classical, mechanical simulations but which are reversible (you can run the simulation in reverse) and they incorporate thermal noise and the laws of thermodynamics.
5/21/2023 I just checked the 1970 paper ‘Minimal Energy Dissipation in Logic’ by Keyes and Landauer, and that gives another way of getting the energy efficiency of computation close to k*T*ln(2). This paper also uses the raising and lowering of a potential barrier.