<p>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$.</p>

<p>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$. </p>

<p>I'm not sure I would call this question research-level, though.</p>

CC BY-SA 2.5
2011-02-07T21:35:03.393Z
2011-02-07T21:35:03.393Z
funkstar
<p>If my understanding is correct, the <a href="http://en.wikipedia.org/wiki/Toffoli_gate" rel="nofollow">Toffoli gate</a> is universal for classical computations, and thus a circuit consisting of Toffoli gates answers your question (3). </p>

CC BY-SA 2.5
2011-02-07T19:45:56.450Z
What I want is to "see" that circuit implemented for some function. :-)
Pratik Deoghare
CC BY-SA 2.5
2011-02-07T19:27:40.503Z
2011-02-07T19:27:40.503Z
Suresh Venkat
<pre><code>              _________
             |         |
    |x&gt; ----&gt;|   f     | -----&gt; |x&gt;
             |_________|
                 |
                 v
                |f(x)&gt;
                 |
              ___v_____
             |         |
    |y&gt; ----&gt;| CNOT    | -----&gt; |y XOR f(x)&gt;
             |_________|
</code></pre>

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

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

<ol>
<li>How can I design quantum circuit for <code>f</code>?
e.g. </li>
</ol>

<blockquote>
<pre><code> 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
</code></pre>
</blockquote>

<ol>
<li>What is quantum analog of multiplexers? </li>
<li>What does the matrix of f-CNOT gate look like?</li>
<li>How can I design quantum circuit for any boolean function? </li>
</ol>

CC BY-SA 2.5
2011-02-08T04:40:37.197Z
I don't think this is research level. Reading the first few chapters of any textbook on quantum computation answers these questions.
Robin Kothari
CC BY-SA 2.5
2011-02-08T05:47:37.060Z
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
CC BY-SA 2.5
2011-02-09T05:25:53.647Z
@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
CC BY-SA 2.5
2011-02-09T18:04:09.907Z
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
<reference-request><quantum-computing>
Understanding function controlled NOT gate
Pratik Deoghare
# Understanding function controlled NOT gate

(Asked by: username_0 on 2011-02-07)

_________
             |         |
    |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.

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



What is quantum analog of multiplexers? 
What does the matrix of f-CNOT gate look like?
How can I design quantum circuit for any boolean function?

**Tags:** reference-request, quantum-computing
> **Comments:**
> **username_1**: I don't think this is research level. Reading the first few chapters of any textbook on quantum computation answers these questions.  
> **username_2**: I was wondering about that, but since I'm not a quantum expert I wasn't sure. good to see the experts weigh in .  
> **username_0**: @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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2011-02-07. Score: 1 | Accepted answer

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$.

I'm not sure I would call this question research-level, though.


---

### Answer by username_2 on 2011-02-07. Score: 3

If my understanding is correct, the [Toffoli gate](http://en.wikipedia.org/wiki/Toffoli_gate) is universal for classical computations, and thus a circuit consisting of Toffoli gates answers your question (3).

> **Comments:**
> **username_0**: What I want is to "see" that circuit implemented for some function. :-)  

---

