# Cheap Toffoli gates with phase errors

Here, a cheap verion of a Toffoli, up to a phase flip for $$|101\rangle$$, is given by

with $$A=R_y(\pi/4)$$. Are there similar versions of cheap implementation of general $$C^nNOT$$ gates?

I tried to just extend it the esay way, but found several unwanted off diagonal entries. My goal is a explicite $$C^5NOT$$.

So I came across this one for 4 qubits:

which I found here. Can anyone help me to build the circuit for 6 qubits out of the description?

And finally I found this approach: but the number of $$CNOT$$s feels like $$2^5$$ in my case, which is too high for my purpose.

• Maybe this helps: quantumcomputing.stackexchange.com/questions/9842/… Commented Apr 17, 2020 at 21:10
• @MartinVesely looks like the last approach I mentioned. So for a $C^5NOT$ with phase errors, I would expect 32 $CNOT$s and the angle of $R_y$ to be $\pi/32$ right? Commented Apr 17, 2020 at 21:22
• Exactly, I will soon post QASM code I am just constructing on IBM Q. Commented Apr 17, 2020 at 21:30
• I was wondering if there has been any new updates on this. I recently found a general circuit for Toffoli with phase errors that has polynomial complexity. Commented Jun 20, 2021 at 5:43
• @MinhPham Can you provide a reference? Commented Jun 25, 2021 at 7:21

## 1 Answer

Based on this thread, below is a code implementing $$C^5NOT$$ up to a phase for output states $$|q_0 q_1 q_2 q_3 q_4 1\rangle$$, $$q_i \in \{|0\rangle, |1\rangle\}$$ (with expection of state $$|111111\rangle$$). For these states the phase is $$\pi$$, so returned computational basis state is multiplied by -1.

Concerning number of CNOTs and $$R_y$$ gates, I think it is not possible to decrease its number and it rises exponentially with increasing number of qubits.

OPENQASM 2.0;
include "qelib1.inc";

qreg q[6];
creg c[6];

ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[2],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[1],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[2],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[0],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[2],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[1],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[2],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[3],q[5];
ry(pi/32) q[5];
cx q[4],q[5];
ry(-pi/32) q[5];
cx q[0],q[5];

• +1 thanks, but I'm still hoping for an improvement. At least for a while... Commented Apr 18, 2020 at 14:38
• ok, I checked the decomposition of the Hamilton operator of the corresponding unitary $U=\exp(-i\pi H)$ and found only product operator of the form $\sigma_y$ on the target- and $1$ or $\sigma_z$ on the control qubits, which is what I expect for an optimal decomposition. Interesting... Commented Apr 20, 2020 at 17:16
• I was wondering if there has been any new updates on this. I recently found a general circuit for Toffoli with phase errors that has polynomial complexity. Commented Jun 21, 2021 at 18:31