# Reversible Computation: Feasible?

1. Jun 3, 2005

### Q_Goest

This regards an article found in the journal of Nature, 26 Aug. '04. I thought it might be interesting, not so much for the physics it presents (although they are certainly fascinating) but because of the implications. I think a discussion around the questions provided at the end of this essay might be interesting.

From the journal of Nature, 26 Aug. '04 (By Seth Lloyd, Dept of Mechanical Engineering, MIT):

The article then goes on to discuss "logically reversible operations" such as NOT and "logically irreversible operations" such as ERASE which requires physical irreversibility implying increasing entropy.

Also:

They discuss quantum computers but I gather that still, erasing or generation of errors in the data results in an increase in entropy.

The last paragraph seems to beg one's imagination, so perhaps some discussion about what the implications are would be of interest.

So... is it possible that computations can be performed forever? Does this imply anything about physical reality?

(I can email the article to anyone interested in reading it if you PM me, but it is too large to upload.)

2. Jun 4, 2005

### James Jackson

Define 'forever'...

Anyway, all quantum gates are reversible, this is a fundamental property. We then introduce Landauer's Principle: If a computer erases a single bit (i.e. in a classical irreversable gate such as a NAND gate), the amount of energy dissipated into the environment is at least $k_B \ln{2}$.

This can be restated in terms of entropy: If a computer erases a single bit of information, the entropy of the environment increases by at least $k_B \ln{2}$.

Notice these set a lower bound on the energy dissipation / entropy gain.

So, if a computation is reversible, there's inherently no information loss, therefore there is no lower bound on entropy increases.

Further reading: R. Landauer. Irreversibility and heat generation in the computing process. IBM J. Res. Dev., 5:183, 1961

3. Jun 6, 2005

### Q_Goest

What does information loss mean? I assume it can't be the same loss of information as described by Hawking for something falling into a black hole for example, since he's claiming there is no information loss in that case.

How is information in a computer different from information which is created as matter in the universe interacts?

4. Jun 6, 2005

### James Jackson

Consider a classical NOT gate:

in out
______
0 1
1 0

I put one bit in and I get one bit out. I can always reconstruct the input given the output. However, if I have a classical ZOR gate:

x y output
___________
0 0 0
0 1 1
1 0 1
1 1 0

I put two bits in and I get one bit out. You can't reconstruct the input given the output - I have lost one bit of information.

I quote from the Preskill lecture notes on Quantum Information theory (http://www.theory.preskill.caltech.edu/~preskill/ph229):

"Information, after all, is something that is encoded in the state of a physical system; a computation is something that can be arried out on an actual physically realizable device. So the study of information and computation should be linked to the study of the underlying physical processes."

Last edited: Jun 6, 2005
5. Jun 8, 2005

### slyboy

Read Charlie Bennett's article "Reversible Computation" for a good discussion of all this.

The point about reversible computation is that we can do computation in principle without any entropy increase, i.e. there is no intrinsic "physical" cost associated with a computation.

Of course, like any other reversible process, in practice this is a limit that can never be achieved. For example, we are always working at a finite temperature, so there is always a cost associated with initializing bits or qubits into definite states.

6. Jun 8, 2005

### Baggio

You have to keep in mind decoherence as well. These gate operations aren't exactly perfect all the time, you will get coupling to the environment which is where error codes come in.

7. Jun 10, 2005

### Q_Goest

Thanks for the responces. This concept of information flow is still bothering me though.

It seems I've often heard that, in principal, the past can be determined from the present state of the universe. The past it would seem, is calculable from the present. Hawking even went so far as to suggest that information that falls into a black hole isn't actually lost, you can reconstruct it from what comes out of the black hole.

On the other hand, the recent experiment regarding the "Delayed Choice Quantum Eraser" seems to suggest that there is a method of destroying information. And James Jackson above points out that a ZOR gate (whatever that is) will result in the loss of information.

Certainly I'd agree with Slyboy, that in practice there is a limit to what can be achieved (ie: how much information can ACTUALLY be retrieved) and being a mechanical engineer, I have no doubt there are irreversible processes and entropy increases. But it seems to me an irreversible process, and increasing entropy does not imply a loss of information in the sense that the past can't be reconstructed, in principal, from the present. Perhaps there's two different concepts here regarding information that someone can help differentiate.