# Partial Cyclic Permuation with only Toffoli and CNOT gates?

I have been trying to solve this puzzle of constructing this transformation from CNOT and Toffoli gates as mentioned in NC page 193 (Ex 4.27)

Here is what I have done:

1. First observation is it has 8 rows and columns, so it is showing the table for 3 qubits.
2. Whenever it is not $$|000\rangle$$ and $$|111\rangle$$ it always add 1. $$|001\rangle$$ becomes $$|010\rangle$$ etc.
3. I ignored the complicated part just tried to implement the easy always add 1 part.
4. One observation for $$|001\rangle$$ to $$|110\rangle$$ is the LSB qubit is always flipped.
5. At this point I realized I would keep one line for $$|1\rangle$$ and it would help me always flip a state. (let's call it qubit 4)
6. Then I realize when would qubit 2 and qubit 1 change. Qubit 2 changes when qubit 3 and 4 both are 1. Qubit 1 change when qubit 2,3,4 are 1.

1. Then I ran the rest of the two cases and checked what output they generated and brute forced to correct it using Toffoli gates.

Is it possible to verify if this is how the puzzle is intended to be solved or did I miss something?

(Also CCCNOT gate is a feasible gate right? or am I making things up?)

Looking at the book, I'm not sure whether the exercise allows to allocate extra qubits in the $$|1\rangle$$ state to enable implementing the X gate using the CNOT gate (if the allocated qubits start in the $$|0\rangle$$ state, you'd need an X gate to flip them to $$|1\rangle$$ to use them as controls, which seems a chicken-and-egg problem). If not, the last gate in the circuit can be problematic, since it's controlled on zero state of the qubits, and requires X gates to implement it from the Toffoli gate.

If X gates are fair game (on their own or using an extra $$|1\rangle$$ qubit), this would work.

Here's a trick I used to validate this (applying the gates to 8 basis states separately by hand seems like a lot of work and can be error-prone): implement the circuit in Q# and use DumpOperation to print its matrix.

open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Diagnostics;

operation PartialPermutation (qs : Qubit[]) : Unit is Adj+Ctl {
// reverse the order of qubits to get matrix with big endian indices
let qsBE = Reversed(qs);
Controlled X(qsBE[1 .. 2], qsBE[0]);
Controlled X([qsBE[2]], qsBE[1]);
X(qsBE[2]);
ControlledOnInt(0, X)(qsBE[0 .. 1], qsBE[2]);
}

operation RunDumpOperation () : Unit {
DumpOperation(3, PartialPermutation);
}


Update: the circuit implemented by the operation (without qubit order reversal, so that it looks more like the circuit in the question):

• Thanks for the answer. Though I get first part of your answer the second part is not clear. I searched in the document to get more idea regarding controlled a parameter list but I couldn’t find one. Same for controlled on int. Is there anyway we can see the circuit? Feb 21 at 6:36
• I added the circuit (conveniently produced from the same Q# code using %trace command), without the qubit order reversal so that the qubit order matches your original one. There is no 4th qubit, since I'm assuming X gate is available; if it's not, we might not have the 4th qubit in the |1⟩ state, so the solution might not work. Feb 21 at 8:07
• Thanks. I will try to understand the circuit first. Feb 21 at 9:48
• This is exactly the circuit I designed but you have removed the extra line and gave a pauli-X based representation of Toffoli but this is actually still a toffoli. 1. What is the meaning of $X'$ ? 2. In the text it was mentioned that I can use CNOT and Toffoli only. Can you make Pauli X gate without using anything other than this two? I guess no Feb 21 at 13:10
• Yes, this is the same circuit. 1. Adjoint of X, which is X itself. 2. That's what I wrote about in the first part of the answer. If you cannot use X on its own, you might not have access to extra qubits in the |1⟩ state and to the zero-controlled variant of Toffoli. If you are granted access to extra qubits in arbitrary state without having to prepare them using gates, you can assume X gate as given via CNOT. Feb 21 at 18:24

I think... I just guessed a circuit.

This figure is generated by Qiskit. Only circuits between the gray dashed barriers are relevant! This is due to different convention of Qiskit's and Nielsen and Chuang's multi-qubit state-vector. Qiskit's convention is $$|q_2 q_1 q_0\rangle$$, while Nielsen and Chuang's is $$|q_0 q_1 q_2\rangle$$. That's the reason of adding that two swap gates.

That was really guessed! (T.T) Currently I have no references for this result.

To generate this circuit, following Qiskit code could be utilized:

import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator

circ1 = QuantumCircuit(3)
circ1.swap(0, 2)
circ1.barrier()
circ1.toffoli(1, 2, 0)
circ1.cnot(2, 1)
circ1.cnot(1, 2)
circ1.cnot(0, 1)
circ1.toffoli(0, 1, 2)
circ1.cnot(0, 1)
circ1.barrier()
circ1.swap(0, 2)
circ1.draw()


The Matrix representation of this circuit is then

>>> np.array(Operator(circ1).data, dtype=int)
array([[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0]])


The answer from Mariia Mykhailova, and also the question itself, are substantially clearer and easy to comprehensive to me. The circuit could also be verified:

circ2 = QuantumCircuit(3)
circ2.swap(0, 2)
circ2.barrier()
circ2.toffoli(1, 2, 0)
circ2.cnot(2, 1)
circ2.x(0); circ2.x(1); circ2.x(2)
circ2.toffoli(0, 1, 2)
circ2.x(0); circ2.x(1)
circ2.barrier()
circ2.swap(0, 2)
circ2.draw()


>>> np.allclose(Operator(circ1), Operator(circ2))
True


So the circuit below should be exactly the same compared to the circuit above.

• I'm really a newcomer (QλQ) I'm not sure if there's any existed gate identities, that could prove that those two circuits are the same. Aug 10 at 10:09
• Also, since this solution was guessed, so I hope that if anyone could rationalize how this circuit could be derived by some rules or comprehensible ideas. The original answer actually gives really clear ideas how his result was derived, but I can't do that currently. Aug 10 at 10:10