Re: the end of fermi's paradox?

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