4
$\begingroup$

I wrote a circuit that makes use of Toffoli gates, but it is too inefficient for my purpose.

In my circuit the states of control qubits are fixed to $|+\rangle$ state. So I wanted to know if there is an efficient way to realize a Toffoli for that fixed case.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

If one of your controls is in the plus state, or your target is in the zero state, you can decompose inline using four T gates instead of seven T gates. For example, this circuit outputs the same thing as applying a Toffoli:

enter image description here

(Of course if you input a state other than $|+\rangle$ for that second qubit, the result won't be correct.)

I don't think it's possible to further reduce the cost of the circuit, even by specifying more individual inputs (other than of course the trivial ones like doing nothing because a control is known to be off or switching to a better gate set). The reason I don't think it's possible is because you can create a magic state by acting on the state where both controls are $|+\rangle$ and the target is $|0\rangle$. You can use this magic state to apply a Toffoli to an arbitrary state via gate teleportation. So any improvement in the special case is actually an improvement in the general case. Also there are results around needing some minimum number of T states to produce a Toffoli state (e.g. Table 1 of https://arxiv.org/abs/1904.01124 says that the Tof-from-T conversion rate is somewhere between 3.63 and 4).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks a lot for your answer, it is really helpful! Is there any paper where I can find the proof of such an equivalence? $\endgroup$
    – Daniele Cuomo
    Dec 1, 2020 at 12:25
  • $\begingroup$ You can pretty easily verify it with any simulator. $\endgroup$
    – Craig Gidney
    Dec 1, 2020 at 16:44
  • $\begingroup$ A simulator would only show intuitively the convergence to an equivalent process matrix. But I can't consider this being a proof. $\endgroup$
    – Daniele Cuomo
    Dec 1, 2020 at 17:18
  • $\begingroup$ What? The simulator will tell you it outputs the same state as the desired gate for every computation basis state input. That's a proof it's equivalent. $\endgroup$
    – Craig Gidney
    Dec 1, 2020 at 17:54
  • 1
    $\begingroup$ Use a simulator that can tell you the full statevector of the output, then use the state channel duality to verify equivalence. E.g. this Quirk circuit outputting zero verifies the equivalence. $\endgroup$
    – Craig Gidney
    Dec 1, 2020 at 22:51

Your Answer

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

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