A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Dash_Riprock
Posts: 9
Joined: Thu Aug 19, 2010 2:43 am UTC

My knowledge of these subjects comes largely from wikipedia, and I have what seems to be a contradiction

I do not understand how one can have in theory a computer which is physically reversible but conventional i.e. not quantum. In order to have a conventional computer, each logic operation must result in a definite output state, 1 or 0. In order for this to happen the logic components must be sufficiently macroscopic such that the wave functions of the information carriers (electrons) fully decohere, obviously an irreversible process. It seems that in order to have the a physically reversible process, an therefore a reversible computer, decoherence must be avoided and the stochastic nature of quantum mechanics must be preserved until the algorithm completes, i.e. a quantum computer.

Wikipedia, however does not seem to think this and talks about how a physically reversible computer must start with logically reversible binary gates, which seems to me to already be flawed. While logically reversible gates would indeed avoid the loss of that one piece of information (one bit for a 2-input AND gate for instance), that would surely be negligible in comparison to the irreversible information loss associated with a macroscopic measurement necessary for a deterministic binary logic gate. Did I miss something?

dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Re: Confusion about reversible/quantum computers

Can you link to the Wikipedia page where it says the stuff you have a problem with?

On the page about reversible computing:
http://en.wikipedia.org/wiki/Reversible ... _computing
It talks about how you can't actually get a perfectly physically reversible computer, and goes on to say that we can get pretty close however, and might "someday build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally."

Dash_Riprock
Posts: 9
Joined: Thu Aug 19, 2010 2:43 am UTC

### Re: Confusion about reversible/quantum computers

My problem isn't with Wikipedia per se, I was just giving a disclaimer that my expertise in this is limited to what is on Wikipedia.

"someday build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally."

This is where I am confused. It seems to me that in order to have the a conventional (not quantum) computer, each logic gate must be sufficiently macroscopic so as to completely decohere the wavefunctions of the information carriers such that the gate output becomes in a definite state. My expertise is too limited to try to calculate a lower bound on exactly how much entropy increase that process would cause, but I would imagine it must be larger than one bit.

I do not understand how a binary logic gate, whose output must be definite, can be compatible with the underlying mechanisms of QM in a way that does not require a "quantum measurement" at each gate, i.e. an irreversible process.

dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

### Re: Confusion about reversible/quantum computers

"Although in practice no nonstationary physical process can be exactly physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well-isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known."

PS: http://xkcd.com/903/

Dash_Riprock
Posts: 9
Joined: Thu Aug 19, 2010 2:43 am UTC

### Re: Confusion about reversible/quantum computers

Yes, I understand that and I do not doubt that statement. However, an isolated, isentropic process will evolve stochastically in accordance with the laws of QM. This is good, indeed necessary, if one is making a quantum computer. However, a conventional binary computer works by each logic gate outputting a definite 1 or 0 value. What I am saying is that I do not understand how one can make a conventional (albeit logically reversible) logic gate in such a way that does not require irreversible quantum decorerence in order to suppress the inherently stochastic nature of QM.

elasto
Posts: 3611
Joined: Mon May 10, 2010 1:53 am UTC

### Re: Confusion about reversible/quantum computers

I assume it's saying there will always be irreversible quantum decoherence during a conventional calculation - but that the amount of information lost when that happens can be rendered arbitrarily small.

Posts: 51
Joined: Mon Nov 12, 2012 11:15 pm UTC

### Re: Confusion about reversible/quantum computers

Dash_Riprock wrote:Yes, I understand that and I do not doubt that statement. However, an isolated, isentropic process will evolve stochastically in accordance with the laws of QM. This is good, indeed necessary, if one is making a quantum computer. However, a conventional binary computer works by each logic gate outputting a definite 1 or 0 value. What I am saying is that I do not understand how one can make a conventional (albeit logically reversible) logic gate in such a way that does not require irreversible quantum decorerence in order to suppress the inherently stochastic nature of QM.

I don't understand that statement ... particularly the first part.

Entropy and QM are not unrelated, but you're conflating the two - adiabatic processes are reversible, they can be macroscopic or microscopic.

There's some nice work from Don Eigler and Andreas Heinrich at IBM where they show some model systems that could be used for this sort of computation.

-O

MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

### Re: Confusion about reversible/quantum computers

You are only examining an edge case of computation: Multiple input, single output gates.

If you have a gate that implements a function from ordered triples of bits to ordered triples of bits, you can have the Troffoli(?) gate:

Given inputs A, B, C and outputs A', B', C': C' = C, If C then B' = A and A' = B, else A' = A and B' = B.

This one suffices to build every logic gate. The cool things happen when you then use the outputs of the gate for other gates, then the computation can randomly roll back and forth and requires only a very marginal energy to roll forward more probably than backwards.
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

PM 2Ring
Posts: 3664
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: Confusion about reversible/quantum computers

Close, it's the Toffoli gate.
One possibility is the Toffoli gate, proposed in 1980 by Toffoli.[1]
This gate has 3-bit inputs and outputs. If the first two bits are set, it flips the third bit.
[...]
The Toffoli gate can be realized by five two-qubit quantum gates.

Another option is the Fredkin gate: a reversible 3-bit gate that swaps the last two bits if the first bit is 1; a controlled-swap operation.

Each of these gates is universal, i.e., any logic gate can be constructed from either of them.

Reversible gates have been studied since the 1960s. The original motivation was that reversible gates dissipate less heat (or, in principle, no heat). In a normal gate, input states are lost, since less information is present in the output than was present at the input. This loss of information loses energy to the surrounding area as heat, because of thermodynamic entropy. Another way to understand this is that charges on a circuit are grounded and thus flow away, taking a small quantity of energy with them when they change state. A reversible gate only moves the states around, and since no information is lost, energy is conserved.

More recent motivation comes from quantum computing. Quantum mechanics requires the transformations to be reversible but allows more general states of the computation (superpositions). Thus, the reversible gates form a subset of gates allowed by quantum mechanics and, if we can compute something reversibly, we can also compute it on a quantum computer.

Because these gates don't create or destroy states, they only move states around, they could be useful in other situations where it's desirable to conserve states, eg logic circuits that use trained animals to represent bits.