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)

enter image description here

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.

enter image description here

  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.

enter image description here

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?)


3 Answers 3


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]);
    ControlledOnInt(0, X)(qsBE[0 .. 1], qsBE[2]);

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

Permutation matrix screenshot

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

Circuit implemented by the Q# code

  • $\begingroup$ 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? $\endgroup$
    – user27286
    Feb 21, 2021 at 6:36
  • $\begingroup$ 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. $\endgroup$ Feb 21, 2021 at 8:07
  • $\begingroup$ Thanks. I will try to understand the circuit first. $\endgroup$
    – user27286
    Feb 21, 2021 at 9:48
  • $\begingroup$ 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 $\endgroup$
    – user27286
    Feb 21, 2021 at 13:10
  • $\begingroup$ 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. $\endgroup$ Feb 21, 2021 at 18:24

$\newcommand{\ket}[1]{\left|{#1}\right\rangle}\newcommand{\+}{\oplus}$Let us call this matrix as $U$. Since this is a permutation matrix, for any $x,y,z\in\{0,1\}$, $U\ket{xyz}$ equals $\ket{XYZ}$ for some $X,Y,Z\in\{0,1\}$. Then, we see that the mapping $(x,y,z)\mapsto X$ is a boolean function, and can be written in terms of $x,y,z$ using AND and XOR. Similarly, $Y$ and $Z$ are boolean functions of $x,y,z$.

The matrix $U$ can be written in the standard basis as $$ \begin{align*} U\ket{000}&=\ket{000}\\ U\ket{001}&=\ket{010}\\ U\ket{010}&=\ket{011}\\ U\ket{011}&=\ket{100}\\ U\ket{100}&=\ket{101}\\ U\ket{101}&=\ket{110}\\ U\ket{110}&=\ket{111}\\ U\ket{111}&=\ket{001} \end{align*} $$ This 'table' can be written as the following boolean formula: $$ \begin{aligned} U\ket{xyz}&=(1\+x)(1\+y)(1\+z)&\ket{000}\\ &+(1\+x)(1\+y)z&\ket{010}\\ &+(1\+x)y(1\+z)&\ket{011}\\ &+(1\+x)yz&\ket{100}\\ &+x(1\+y)(1\+z)&\ket{101}\\ &+x(1\+y)z&\ket{110}\\ &+xy(1\+z)&\ket{111}\\ &+xyz&\ket{001} \end{aligned} $$ For example, $U\ket{011}=\ket{100}$, and $\ket{xyz}=\ket{011}$ iff $(1\+x)yz=1$, so we have the term $(1\+x)yz\ket{100}$ in the above equation.

Now, we can compute $X, Y, Z$ in terms of $x,y,z$: for example, $X=1$ for $\ket{100},\ket{101},\ket{110},\ket{111}$, and the amplitudes for these are $(1\+x)yz$, $x(1\+y)(1\+z)$, $x(1\+y)z$, $xy(1\+z)$. Since they must be all exclusive ($U$ is permutation), we can XOR them together: $$ \begin{aligned} X&=(1\+x)yz\+x(1\+y)(1\+z)\+x(1\+y)z\+xy(1\+z)\\ &=yz\+xyz\+x\+xy\+xz\+xyz\+xz\+xyz\+xy\+xyz\\ &=x\+yz. \end{aligned} $$ Similarly we can compute $Y, Z$, and get $Y=y\+z$, $Z=x\+y\+xy\+yz\+zx$.

Hence, $U\ket{xyz}=\ket{x\+yz}\ket{y\+z}\ket{x\+y\+xy\+yz\+zx}$.

In our attempt to implement $U$, we can see that at least implementing $x\+yz$ and $y\+z$ is easy:

enter image description here

So the problem is: given $a=x\+yz$, $b=y\+z$, $c=z$, implement $x\+y\+xy\+yz\+zx$.

Then, we have $z=c$, $y=b\+c$, $x=a\+yz=a\+(b\+c)c$. So,


But this is easy to implement:

enter image description here

Combining the two circuits, we obtain

enter image description here


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 the different conventions 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 for adding those two swap gates.

Qiskit Route of this answer

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

To generate this circuit, the 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.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.swap(0, 2)

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.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.swap(0, 2)

Qiskit Route of previous answer

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

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

  • $\begingroup$ 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. $\endgroup$
    – ajz34
    Aug 10, 2021 at 10:09
  • $\begingroup$ 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. $\endgroup$
    – ajz34
    Aug 10, 2021 at 10:10
  • $\begingroup$ The problem is equivalent to one in in combinatorial group theory: The target circuit and the 9 available gates (three Toffoli and six CNOT gates on three qubits) each act as permutations on the 8 states in the computational 3-qubit basis. (7 if you note that these gates do nothing to |000>.) If we think of the nine gates as our 'letters', then we want to represent the target circuit as a word in this alphabet. This can be solved, e.g., in SageMath (see math.stackexchange.com/a/2833182/137524 for instance), but as yet i have no insight into the underlying algorithm. $\endgroup$ Oct 21, 2021 at 0:54

Your Answer

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

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