In Nielsen and Chuang, there's the following paragraph:

The Toffoli gate can be used to simulate NAND gates and can also be used to do FANOUT. With these two operations, it becomes possible to simulate all other elements in a classical circuit, and thus an arbitrary classical circuit can be simulated by an equivalent reversible circuit.

I'm confused about why FANIN isn't required to be able to simulate all other elements in a classical circuit, while FANOUT is required?

Also, a side note/question, I originally posted this question on the Electrical Engineering SE, but it was suggested to be migrated to this SE as it seems to them that "fan-in" and "fan-out" from a EE perspective is very different from FANOUT and FANIN in the context of Toffoli Gates. I learned "fan-in" and "fan-out" from EE perspective and just assumed the FANOUT discussed in Nielsen and Chuang is the exact same thing. Am I mistaken and "fan-in" and "fan-out" in QC is different from that in EE?

  • 1
    $\begingroup$ Isn't it an error in a classical logic circuit for two outputs to drive one input? What's a FANIN gate, exactly? $\endgroup$ Aug 23 at 16:40
  • $\begingroup$ @CraigGidney I learned Fan-In as the number of inputs of a gate that it can handle w/o impairing its normal function. So eg, a NAND has a fan-in number of 2 $\endgroup$
    – Alexia.
    Aug 24 at 3:43

A NAND gate is a universal classical gate. All boolean logic can be implemented using only NAND gates. This is clear because SOP/POS implementation needs only AND/OR/NOT and NAND can make all three of those gates as shown bellow.

enter image description here

Quantum Computing however has the constraint/feature of requiring all operations to be reversible, and the NAND gate itself (like AND and OR) is not reversible. For instance if I tell you NAND$(X,Y)$ $=1$ you have no way of reversing that operation to tell me what $X$ or $Y$ is.

But with a Toffoli gate operating on $3$ qubits $|ab1 \rangle$ you would get the output $|abc \rangle$ where $c=$NAND($a,b$).

Which means we have successfully done a NAND operation on two qubits $a$ and $b$. However this gate doesn't only output the bit $c$ it also outputs $a$ and $b$ which are fanout bits.

Therefore we can say that the Toffoli can act as a NAND gate that also fans out the two input bits. But the fanout doesn't even matter for universality since we showed up above just having the NAND operation gets the job done for us. The fanout bits simply exist because of the conditions imposed on quantum operations.

  • $\begingroup$ Thank you for the reply! Just to make sure: The fan out here isn't the same as the one in classical digital circuit, which I learned to be the maximum # of digital inputs that the output of a single logic gate can feed & the gates must be from the same logic family? $\endgroup$
    – Alexia.
    Aug 24 at 3:57
  • $\begingroup$ @Alexia. It sort of is; in digital circuits the fanout is the number of signals you can draw from the output of a gate, out the output of our Toffoli gate we have a qubit $|a \rangle$ and a qubit $|b \rangle$ which you can draw. This is a single Fanout. Again it doesn't matter for universality or the simulation of classical circuits since Fanout isn't a "logical" thing. $\endgroup$ Aug 24 at 20:29
  • $\begingroup$ @Alexia. What N+C is trying to say is that we can make NAND gates, but we're gonna have some leftover bits; I will admit they could have clearer words, but the central point of a Quantum NAND gate is there. $\endgroup$ Aug 24 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.