Understanding function controlled NOT gate

Question

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

Answer 1

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 2

If my understanding is correct, the Toffoli gate is universal for classical computations, and thus a circuit consisting of Toffoli gates answers your question (3).