Talk:Toffoli gate

From Wikipedia, the free encyclopedia

In normal logic, XOR is NOT reversible. It is not possible to tell which input did what given only the output. If this isn't what you meant, the ststement needs clarification Graham 03:57, 17 Mar 2004 (UTC)

I meant the gate with two outputs, one equal to the first input and the other being the XOR. That's reversible. But now I see that it's confusing that I talk about 2-output version of XOR, then about 1-output AND. So, let the sentence about XOR stay deleted. Andris 04:37, 17 Mar 2004 (UTC)

Contents 1 Universality and Toffoli gate 2 Use of the word "invented" 3 3-bit Adder Diagram 4 Link to Universal

[edit] Universality and Toffoli gate

"Toffoli gate is universal. This means that for any Boolean function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli gates which takes x1, x2, ..., xm and some extra bits to 0 and outputs x1, x2, ..., xm, f(x1, x2, ..., xm). Essentially, this means that Toffoli gate is sufficient for any computation." I don't think that's right. For example, show me a function that consists of Toffoli gates and outputs 1 independent of input, like, f(x1, x2, ... xm)=1 . AFAIK, you need at least some bits to 1, not 0.

That's a bit of a quibble. Typically you assume that inputs of gates can be tied to a variables (one of the x1, x2, ..., xm) or to a constant (0, or 1). This is not an unreasonable assumption in an actual hardware implementation. With this assumption the 3 input Toffoli gate is universal. The 2 input version is still not universal, even with this assumption. --David Battle 20:24, 17 August 2005 (UTC)

Yes, "tied to a variable or to a constant (0 or 1)". However, the article claims it needs to be possible to tie it only to variables and zeroes, which I think is wrong.

OK, a network of Fredkin gates (since it can't change the number of zeros or ones) needs *both* "0" and "1" constants to be able to implement "NOT" and other important functions. However, a network of Toffoli gates only needs "1" constants to implement "NOT" and any other arbitrary function, right? Toffoli networks don't absolutely need "0" constants, because we can can synthesize a "0" constant by feeding "1" constants into a Toffoli gate, right? (I agree that in an actual hardware implementation, it will probably be simpler to just hard-wire "0" constants rather than synthesize them from "1" constants). --DavidCary 23:38, 22 December 2005 (UTC)

[edit] Use of the word "invented"

Great article. It's refreshing to see an article on quantum computing without pedantic descriptions of orthogonality, Hamiltonians... I do have a problem with the intro. Generally, scientists don't "invent" abstract concepts, only the methods used to describe them. So Einstein described/discovered special relativity but Feynman invented Feynman diagrams (used to describe particle-antiparticle interactions). Anybody else agree that the wording needs to be changed? Zyxoas (talk to me - I'll listen) 20:03, 26 May 2006 (UTC)

[edit] 3-bit Adder Diagram

I tested out different combinations of A, B and C inputs for the 3-bit adder diagram. From what I understand, this is supposed to just add the three bits, so if all are 0, Xor = 0 and Carry = 0. If one bit is 1, then Xor = 1 and Carry = 0, if two bits are 1, then Xor = 0 and Carry = 1, and if all three are 1, then Xor = 1 and Carry = 1.

This is true for all cases, except for the case where A = 1, B = 0 and C = 1. This should give Xor = 0 and Carry = 1, but instead it gives Xor = 0 and Carry = 0. Am I calculating this right??? -Jeff Marks

I did the calculations and reached the same conclusion. Either we made the same mistake, or that diagram is in error. -L. M.

I came up with a solution to correctly calculate the carry value. Gate 1 Inputs: C C B Gate 2 Inputs: B B A Gate 3 Inputs: Gate1 Gate2 B The Carry is the output of Gate 3 - Jeff Marks

[edit] Link to Universal

The introduction had linked the word universal to Universality (philosophy) which is clearly wrong - universal as used here is a mathematical/computer science term. A closer link would be Turing completeness but I'm not sure whether the definition of universal here is quite the same as in that article (one seems to be about boolean functions, the other about natural numbers, for example). At least for now I just unlinked "universal". The relevant definition of "universal" is given further down in the article. Kingdon 21:04, 19 January 2007 (UTC)