2
$\begingroup$

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

enter image description here

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:

enter image description here

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: enter image description here but the number of $CNOT$s feels like $2^5$ in my case, which is too high for my purpose.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Maybe this helps: quantumcomputing.stackexchange.com/questions/9842/… $\endgroup$
    – Martin Vesely
    Apr 17, 2020 at 21:10
  • $\begingroup$ @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? $\endgroup$
    – draks ...
    Apr 17, 2020 at 21:22
  • $\begingroup$ Exactly, I will soon post QASM code I am just constructing on IBM Q. $\endgroup$
    – Martin Vesely
    Apr 17, 2020 at 21:30
  • $\begingroup$ 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. $\endgroup$
    – Minh Pham
    Jun 20, 2021 at 5:43
  • $\begingroup$ @MinhPham Can you provide a reference? $\endgroup$
    – draks ...
    Jun 25, 2021 at 7:21

1 Answer 1

Reset to default
1
$\begingroup$

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];
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ +1 thanks, but I'm still hoping for an improvement. At least for a while... $\endgroup$
    – draks ...
    Apr 18, 2020 at 14:38
  • 1
    $\begingroup$ 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... $\endgroup$
    – draks ...
    Apr 20, 2020 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – Minh Pham
    Jun 21, 2021 at 18:31

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.