From: Larry (entropy@farviolet.com)
Date: Fri Jan 05 2007 - 11:58:53 MST
On Fri, 5 Jan 2007, Philip Goetz wrote:
> On 1/5/07, Larry <entropy@farviolet.com> wrote:
>>
>> Interestingly some useful problems can be stated in a fashion that doesn't
>> require discarding of bits, and theoritically can harness this should
>> we manage to build decent quantum computers.
>
> Say you have a computer with n bits, and they all have some value.
> You want to compute a result of m < n bits.
> We know this value isn't present in the n bits at the start (because
> otherwise you wouldn't need to compute it).
> It must be present in the n bits at the end of computation.
> How can you put those m bits into the set of n bits without erasing m of
> them?
The trick is reversible logic gates, three bits in, three bits out, and
self inverse. One example is a controlled exchange of two bits, passing
through the control bit.
C is the control bit, A & B get exchanged
A B C | A' B' C'
0 0 0 | 0 0 0
0 0 1 | 0 0 1
0 1 0 | 0 1 0
0 1 1 | 1 0 1
1 0 0 | 1 0 0
1 0 1 | 0 1 1
1 1 0 | 1 1 0
1 1 1 | 1 1 1
You can compute something, then unwind it back to the original by
reversing all the operations. You've not had to discard any information.
Any one state completely defines both the next and the previous state.
All algorithms can be implemented with these gates, as this gate can
be used to make any of the standard logic gates. However most useful
algorithms as normally implemented will have a requirement for
bits that grows without bounds. In a normal computer you dump these
surplus bits over board ultimately through the heat sink and into
the cosmic /dev/null, as a result a normal computer cannot be run
backward, the information has been discarded.
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:57 MDT