9

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?

Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
Davide_sd
  • 305
  • 1
  • 7

2 Answers2

6

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

Mariia Mykhailova
  • 9,285
  • 1
  • 13
  • 40
4

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.

Niel de Beaudrap
  • 12,522
  • 1
  • 33
  • 73