Talk:Toffoli gate

Untitled

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)

GH: In discreet electronics, the gate first refer to as CCNOT is (to my mind) a 'NAND' Gate: If both Ins are high, output is low (Invert of an AND Gate), If not high. You can take a feed off any of the inputs by just connecting to them. So:

An AND: Any Low on any input (two to n inputs) = Low Out a NAND: Inverter on the OUTPUT. Ie if the above have a low out, this would give a high out.

An OR: Any High (on any input be it a one or two or n input Or Gate) = A High out. A NOR: Same as the above but with inverter on output.

AN XOR: (Two Input). Difference between one & other = High out, else low.

A 'NOT' (or invert). High in = Low Out, Low in = High out.

I'm sure you all know this but just for reference sake and an easy way to remember it. Gavin Hampshire. — Preceding unsigned comment added by 82.44.215.132 (talk) 09:46, 5 January 2014 (UTC)

Wiki Education Foundation-supported course assignment

This article was the subject of a Wiki Education Foundation-supported course assignment, between 10 March 2020 and 30 April 2020. Further details are available on the course page. Student editor(s): Pbellys.

Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT (talk) 11:27, 17 January 2022 (UTC)

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)

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)

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

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)

Image

The logic image is unclear. What do the dots, lines, and circle represent? Zylstra (talk) 20:24, 27 February 2018 (UTC)

Quantum cost

I removed the text ", thus its quantum cost is five." following the sentence regarding how the Toffoli gate can be implemented with 5 two-bit gates. First of all, there is no agreed on measurement for "quantum cost". You would only care about the number 5 rather than say 17 if you were actually implementing things, and then you would be measuring cost in terms of your implementation, in which it may be the case that not all two-bit gates are created equal.

Additionally, it is not proven that the Toffoli cannot be implemented with fewer than 5 quantum gates. —Preceding unsigned comment added by Phrenophobia (talk • contribs) 06:58, 30 July 2008 (UTC)

Create Reversible Gate Entry

The information in Background is very helpful to understanding the confusing, multidisciplinary aspects of quantum computing. I recommend creating an entry for Reversible Gates and expanding on the information presented in the background. I am aware of the entry Reversible Computing, but I believe it lacks a tangible nature that was clarified here. --*elAndres (talk) 18:28, 30 March 2011 (UTC)

Weird sentence

At the end of the article, there is a sentence I can't understand : "However, the Toffoli gate can not be used for universal quantum computation, though it does mean that a quantum computer can implement all possible classical computations." Can someone explain or make it clear ? Thanks, Zandr4^[Kupopo ?] 07:54, 16 January 2014 (UTC)

non-trivial gate

In the article there is : "the only non-trivial gate is the controlled NOT gate". What make it non-trivial is not clear (if I add to guess I would say it's would be the use of a logical function like XOR). It's not clear either if being non-trivial is an important property and why. — Preceding unsigned comment added by Astyan42 (talk • contribs) 01:53, 3 February 2017 (UTC)

Citations needed for Background section

The section mentions the relationship between Toffoli gates and thermodynamics, and the following source may provide the relevant information necessary for a citation: R. Landauer, "Irreversibility and heat generation in the computing process," IBM Journal of Research and Development, vol. 5, pp. 183-191, 1961. --Beaker Bytes (talk) 14:52, 16 January 2019 (UTC)

Deutsch gate

The article references the Deutsch gate in the Related logic gates section. The Deutsch gate has an angle associated with it that when chosen to be pi/2 yields the Toffoli gate. I think this may be worth mentioning. Pbellys (talk) 02:01, 14 April 2020 (UTC)