On Friday 2005-03-04 06:27, David Hobby wrote: > Trent Shipley wrote: > > What the ???? I can't find any context for this. > But see comments, below. > > ---David
1) You might have seen this on brin-l aztechlist or [EMAIL PROTECTED] I did not recognize this as a simple pigeonhole problem of 2n choose n, so I cross posted to lists where I thought I might get help and would not be accused of an off topic post. David Hobby, do you live in the Phoenix area? ========== As for context: Well all the chatter about things quantum on brin-l made me think of quantum computers and computation. Thinking about quantum computing reminded me that I know virtually nothing about the topic, but that ever since taking introductory digital circuit design I have known that flip-flops (the basis of memory circuits) can be put into an indeterminate state called "metastable". Metastability is usually regarded by EEs as A Bad Thing. My immediate reaction was "that looks like a QM effect at a macro scale". When I read about metastability in my text book my first idea was that one could use the phenomenon to build a random number generator or coin tosser. (It turns out that there are references on the web to patents for random generators based on metastability.) Then I thought, "if you can use metastability to make random generators, then MAYBE (if you can find a way to entangle more states) you could use metastability to make a quantum computer with off the shelf parts ... in a garage on your vacation. Shure, there is at best a 0.05% chance of success, but IF it worked it would rank as more important than the integrated circuit and less important than the solid-state transistor. I even wrote to ask about inducing metastability. See: http://www.sigcon.com/Pubs/news/4_4.htm Most of Dr. Howard Johnson's objections to inducing metastability can either be answered or are generically a problem for ANY quantum-ALU (QLU) design one might consider. "The metastable window on a flip-flop is extremely narrow, perhaps only a few picoseconds wide." This is a design issue. Since EEs do not want metastability screwing up their designs, they minimize the window where metastability can occur. Working from scratch, one could MAXIMIZE a flip-flop's metastable window. "Furthermore, it [the metastable window] drifts with time, temperature, power supply voltage, and other factors." For quantum computation you need to be able to (more or less) reliably induce metastability. The latch is touchy about initial conditions, so if you want to build a quantum computer around one you need to carefully control those initial conditions. "Once you set the potentiometer to create a lot of metastable events, drift in the flip-flop's metastable window will soon cause the circuit to fall off the metastable cusp, and the circuit will return to normal operation. You have to keep chasing the metastable window around if you want to observe events over a long period of time." Using a latch (or any other basis for a QC) throws the basis out of its initial state. Any engine (including a latch) will have a refractory period before it returns to an initial or 'ground' state and is again ready to perform another operation. These refractory periods are likely to be best described with probability curves. One can partly overcome this problem by having multiple QPUs in a series so that a fresh QPU in ground state is always waiting to take the output from the last QPU that performed an operation. ============== Now with an ordinary latch we have an input control lead (it sets the latch to remember current state or receive a new state) an data input lead (if the control is T, then the data lead sets the latch to either T or F), and an output lead that just tells you whether the latch is remembering T or F. More literally the latch has TWO output leads, but if one is T the other must be F, so we gain no data from the second one. I had my Digital Design textbook stolen partway through the semester, but as i remember it a latch was mathematically: A[out] -> B[in], Output B[out] -> A[in] So, if we have a latch with two output leads we should be able to get it to act as the brain of a trivial qpu: it will perform the not so interesting operation of "ADD 1". Unfortunately if we have two latches we do not get either a 2 or a 4 q-bit computer. We just have two weak little 1 q-bit qpu's. They cannot be quantum entangled. I conjecture that a three component latch (3-latch) will not be stable, but have a tendency to "ring". (Note this is a K-3 graph.) A[o] -> B[i],C[i], Out B[o] -> A[i],C[i], Out C[o] -> A[i],C[i], Out A 4-latch, however, should be stable. Like a 2-latch I conjecture it should only output bits so that the number of Fs equals the number of Ts. A[o] -> B[i], C[i], D[i], Out B[o] -> A[i], C[i], D[i], Out C[o] -> A[i], B[i], D[i], Out D[o] -> A[i], B[i], C[i], Out That is 4 pick 2. The conjecture is that THIS 4-latch can be built and used in a QPU (designed by someone more clever than my self). It will have 6 states. Unfortunately, mapping these states to numbers is not as straightforward as in a determinate ALU, but counting to 3 should be straight forward. Indeed, if one can build a 4-latch QPU then one should, in theory, be able to use the same solid-state technology to build a QPU of arbitrary size with an even number of output leads. ====================== Abstraction: ====================== For the moment, forget about stupid real-world things like latches and quantum computers. Those are toys for experimental physicists at best and dirty engineers at worst. Let's do some mathematical computer science, albeit inspired by the forgoing speculation. Imagine we have a device that must produce output in pairs so that for every F there is a T. It cannot produce an odd number of outputs. How many symbols can be represented by such a machine's output (how big is the output's alphabet) for any output block size 2N that implicitly includes N F's and N T's. Now aren't you sorry you asked? > ... > > > 2th item: 4 places: 0011 > > 0101 > > 0110 > > 1001 > > 1010 > > 1100 > > > > 6 parity combinations, > > sum of each row is 2 > > 2^4 possible (16) > > 4: 6 :8:16 > > This is C(4,2) = 4!/(2! * 2!) = 6. You are picking > 2 places out of 4 possible ones to place the 1s. > > > 3th item: 6 places: 000111 > > 001011 > > ... > > 110100 > > > 111000 > > > > 20 parity combinations (if my spreadsheet is > > right) > > And this is C(6,3) = 6!/(3! * 3!). > > > 4th item: 8 places: 00001111 > > 00010111 > > . > > . > > 11101000 > > 11110000 > > > > 70 parity combinations (if spreadsheet right) > > And C(8,4), etc. > > ... > > > NOTE each binary number (or representation of state) has an equal number > > of 'zeroes' and 'ones'. > > > > Because of the parity of zeroes and ones we are only interested in binary > > numbers with an even number of places. > > > > The idea that the sum of symbols for each number equals the rank of the > > item in the sequence is not proven, but is evident. > > > > --------------- > > > > Question: > > > > For a given item n in the sequence N, how many parity number combinations > > will occur in the resulting set of all modulo 2^(2n) binary > > representations? (How many parity combinations for a given item N?) > > > > Is number of binary parities bounded underneath by 2^(2[n-1]) for all N? > > I don't understand the question completely. But if > these are just C(2n,n), you can use Sterling's formula > to approximate the factorials, and get a very accurate > estimate. > > _______________________________________________ > http://www.mccmedia.com/mailman/listinfo/brin-l _______________________________________________ http://www.mccmedia.com/mailman/listinfo/brin-l