0

Question:

Given controlled-SWAP (CSWAP) and Hadamard (H) gates, is it possible to exactly compile the Toffoli (CCX) gate?

Note that I'm not looking for an encoded Toffoli gate. The answer should implement Toffoli exactly on three physical qubits. The use of ancilla qubits is allowed and, in fact, necessary (see This question for proof).

Jonas Anderson
  • 671
  • 3
  • 8

1 Answers1

2

You can build a Toffoli out of five CSWAPS catalyzed by two plus states and a singlet state:

enter image description here

The middle CSWAP is just implementing a Z gate, so if you have an X or Z gate then the circuit can be simplified and the singlet state won't be needed.

The singlet state can be created using postselection:

x

Craig Gidney
  • 44,299
  • 1
  • 41
  • 116