Reversible Computation: Feasible?

[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):

There are some processes that are effectively reversible: no energy is dissipated, and entropy remains constant, or almost so. Chemical reactions are reversible if run sufficiently slowly; they can dissipate arbitrarily small amounts of energy per step. Coherent quantum-mechanical processes such as tunnelling and superconductivity are reversible and can operate without dissipation. And so can computation, in principal.

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.

But then Charles Bennett and independently, Ed Fredkin realized that most logically irreversible operations can be embedded in slightly more complicated reversible operations. As a consequence, computation can in principal be implemented using reversible physical processes ... The one logically irreversible process that connot be embedded in a more complicated reversible process is erasure: when you erase the last copy of a bit from your computer, entropy must increase elsewhere.

Also:

Quantum computers are the closest thing we have to devices that carry out computation in a logically and physically reversible fashion.

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.

What about death? Must computation, like all physical processes, grind to a close? In fact, as long as the expansion of the universe keeps supplying free energy and environment into which to reject errors, the known laws of physics apparently allow a computer to compute for ever. Just what might an eternal computer compute? The answer will have to wait.

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.)

 

[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

 

[Q_Goest]

... if a computation is reversible, there's inherently no information loss,

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?

 

[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."

 

[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.

 

[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.

 

[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.