9
$\begingroup$

I'm working my way through the book "Quantum computation and quantum information" by Nielsen and Chuang. (EDIT: the 10th anniversary edition).

On chapter 3 (talking about reversibility of the computation) exercise 3.32, it is possible to see that the minimum number of Toffoli gates required to simulate Fredkin gate is 4. See Andrew Landahl's notes for more details.

By the end of Chapter 3, it is also stated:

From the point of view of quantum computation and quantum information, reversible computation is enormously important. To harness the full power of quantum computation, any classical subroutines in a quantum computation must be performed reversibly and without the production of garbage bits depending on the classical input.

On chapter 4 exercise 4.25, we construct the Fredkin gate using only 3 Toffoli gates.

The question is: what's the difference between simulation and construction of Fredkin gate using Toffoli gates?

Improve this question
$\endgroup$
2
  • $\begingroup$ Great question, the only improvement I can recommend is that if you're going to cite a particular exercise (such as 4.25, like you have done), then it would be useful to also say which version of N&C you're referring to. $\endgroup$
    – user1271772 No more free time
    Commented Oct 15, 2018 at 13:00
  • $\begingroup$ I haven't had a chance to look at the original text of N&C and Andrew Landahl because it's first thing in the morning and I have to go to work, but based on what you said it looks like construct and simulate mean the same thing, and it is interesting that in chapter 3 they say you need a minimum of 4 gates and in chapter 4 they say you need a minimum of 3 gates. What are the gate sets used for each case? {CNOT,H,T} in both cases? Or does the situation requiring only 3 gates have access to more types of gates? Sorry I wasn't able to read the N&C text yet and won't have time until Thursday. $\endgroup$
    – user1271772 No more free time
    Commented Oct 15, 2018 at 13:05

2 Answers 2

Reset to default
6
$\begingroup$

I don't think there is a difference between the meanings of "construct" and "simulate" in this case. Exercise 3.32 of Nielsen and Chuang doesn't actually tell you that you need 4 Toffoli gates to simulate a Fredkin one, and you can in fact do it using just 3 gates, similar to the construction of SWAP gate using 3 CNOT gates:

CCNOT(control1, control2, target)
CCNOT(control1, target, control2)
CCNOT(control1, control2, target)

The circuit given in Andrew Landahl's notes with 4 gates doesn't seem to perform a Fredkin gate on the three given qubits. Based on the notes on the circuit provided in the notes, the middle qubit (the z input) ends up in $y \oplus z$ state, not in $x(y \oplus z) \oplus z$ state as the Fredkin gate requires (the fifth qubit, which started in $|0\rangle$, ends in this state instead).

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Davide_sd, I do not see how Neil de Beaudrap's answer has answered your question. But I think Marria's answer (this one) is perfect. $\endgroup$
    – user1271772 No more free time
    Commented Oct 15, 2018 at 19:00
  • $\begingroup$ @NieldeBeaudrap: My understanding was that in this particular context "simulate" and "construct" meant the same thing (while in general your answer would be correct). The confusing thing for the OP was that when they used the word "simulate", the OP thought that the minimum # of gates was 4, and when the word "construct" was used, the OP thought the minimum # of gates was 3, and Mariia seems to have clarified that. I was just surprised your answer got accepted and hers had not even a single upvote, but of course you answered 4 hours ago so it makes sense. Don't you think her answer was good? $\endgroup$
    – user1271772 No more free time
    Commented Oct 15, 2018 at 19:44
  • $\begingroup$ Yes, I now see that in my haste, I missed the OP's central confusion. I've edited my answer to try to clarify my own post to indicate that I'm only addressing the terminology. Thanks for pointing out the particular way in which you considered my post not to adequately answer the OP. $\endgroup$
    – Niel de Beaudrap
    Commented Oct 15, 2018 at 19:59
  • $\begingroup$ Part 1. @Mariia Mykhailova thanks for showing me that I missed the fact that the output of Andrew Landahl's procedure is not a proper Fredkin representation (given the input/output map). I'm marking your answer as correct, even though I still have doubts. After reading section 3.2.5 again, I realized I did not fully comprehend the concept of uncomputation, which may be used in Andrew Landahl's procedure. This idea, togheter with the reversible-conservative assumptions (@Niel de Beaudrap) of section 3.2.5, may be the keys to understand the difference between simulation and construction. $\endgroup$
    – Davide_sd
    Commented Oct 15, 2018 at 21:28
  • $\begingroup$ Part 2. Looking at Fredkin map $F(x,y,z)\rightarrow(x, y \oplus x(z \oplus y), z \oplus x(z \oplus y)$, if we are allowed to use ancilla states and 4 Toffoli gates, we are actually capable to reconstruct the circuit starting from the result moving towards the inputs. As far as I can see, it is not possible to do that using only 3 Toffoli gates and no ancilla states. What do you think about it? $\endgroup$
    – Davide_sd
    Commented Oct 15, 2018 at 21:28
4
$\begingroup$

The words "construct" and "generate" are in practice synonyms when it comes to transformations, but suggest different ways in which we consider what's going on.

  • "Construct" suggests thinking of a FREDKIN gate as a subroutine, which you realise as a composition of more primitive operations.

  • "Simulate" suggests the idea that there is some model (eg. conservative reversible computation) for which FREDKIN is a primitive, and which you are realising by other operations in some other model (eg. quantum computation, or reversible but not necessarily conservative computation) in which it is not a primitive.

The second viewpoint is particularly useful when you consider operations which are being realised using a protocol which succeeds only under certain circumstances, or using a protocol which is only realises an operation up to some probability of error or up to some precision.

Improve this answer
$\endgroup$
0

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.