# Understanding function controlled NOT gate

              _________
|         |
|x> ---->|   f     | -----> |x>
|_________|
|
v
|f(x)>
|
___v_____
|         |
|y> ---->| CNOT    | -----> |y XOR f(x)>
|_________|


I am trying to figure out how quantum computers work. Diagram above is what I "think" f-CNOT gate should look like.

Given a description of a function f it is trivial to design classical circuit to calculate it using multiplexers, logic gates etc.

1. How can I design quantum circuit for f? e.g.
 x      f(x)

0 0 0     0
0 0 1     0
0 1 0     1
0 1 1     1
1 0 0     0
1 0 1     1
1 1 0     0
1 1 1     1

1. What is quantum analog of multiplexers?
2. What does the matrix of f-CNOT gate look like?
3. How can I design quantum circuit for any boolean function?
• I don't think this is research level. Reading the first few chapters of any textbook on quantum computation answers these questions. – Robin Kothari Feb 8 '11 at 4:40
• I was wondering about that, but since I'm not a quantum expert I wasn't sure. good to see the experts weigh in . – Suresh Venkat Feb 8 '11 at 5:47
• @Robin You first implement any circuit using classical NAND gates and replace all those NAND gates by Toffoli gate with target bit set to 1. Is this how it is done? It is not in "Kaye, Laflamme, Mosca" book. – Pratik Deoghare Feb 9 '11 at 5:25
• Yes, that works. I don't have a copy of KLM at hand at the moment, but I'm quite sure it is explained there somewhere. Most probably in the first chapter. – Robin Kothari Feb 9 '11 at 18:04

For a somewhat naïve but general solution, you can, e.g., use the Toffoli gate to simulate an AND-gate by using an extra bit initialized to 0 as the target line: $(A,B,0) \mapsto (A,B,AB)$. Similar embeddings allow you to simulate all the classical logic gates, for a (admittedly wasteful) reversible circuit simulation of a boolean function $f$.
The result line then holds $f(x)$ which is used as control line for a Feynman gate (controlled-not) targeting $y$. Following that, clear the extra (ancillary) bits by applying the inverse circuit for $f$.