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 2input 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?
Confusion about reversible/quantum computers
Moderators: phlip, Moderators General, Prelates

 Posts: 9
 Joined: Thu Aug 19, 2010 2:43 am UTC
 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."
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."

 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.
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.
"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
That wikipedia page also says:
"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 wellisolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known."
PS: http://xkcd.com/903/
"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 wellisolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known."
PS: http://xkcd.com/903/

 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.
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
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.
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"
Re: Confusion about reversible/quantum computers
Close, it's the Toffoli gate.
Another option is the Fredkin gate: a reversible 3bit gate that swaps the last two bits if the first bit is 1; a controlledswap operation.
Each of these gates is universal, i.e., any logic gate can be constructed from either of them.
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.
One possibility is the Toffoli gate, proposed in 1980 by Toffoli.[1]
This gate has 3bit inputs and outputs. If the first two bits are set, it flips the third bit.
[...]
The Toffoli gate can be realized by five twoqubit quantum gates.
Another option is the Fredkin gate: a reversible 3bit gate that swaps the last two bits if the first bit is 1; a controlledswap 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.
Who is online
Users browsing this forum: No registered users and 6 guests