|         |
    |x> ---->|   f     | -----> |x>
             |         |
    |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?
  • 5
    $\begingroup$ I don't think this is research level. Reading the first few chapters of any textbook on quantum computation answers these questions. $\endgroup$ Feb 8, 2011 at 4:40
  • 2
    $\begingroup$ I was wondering about that, but since I'm not a quantum expert I wasn't sure. good to see the experts weigh in . $\endgroup$ Feb 8, 2011 at 5:47
  • $\begingroup$ @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. $\endgroup$ Feb 9, 2011 at 5:25
  • $\begingroup$ 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. $\endgroup$ Feb 9, 2011 at 18:04

2 Answers 2


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.


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

  • $\begingroup$ What I want is to "see" that circuit implemented for some function. :-) $\endgroup$ Feb 7, 2011 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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