I'm working my way through one of the quantum circuits sections in Nielsen and Chuang and I'm struggling to get a feel for the basics of circuit construction. For example, one of the exercises is as follows: enter image description here

This exercise seems really simple on the surface, however I'm struggling to figure out how to go from a question posed like this to implementation. I can obviously write down the action in terms of the computational basis, but after this I get stuck.

I'm not so much looking for a specific solution to this exercise but rather using this as an instance of how to get into the correct frame of mind / use the correct procedures to solve problems with circuits.


2 Answers 2


Here are three strategies for learning to make this kind of circuit. They all involve being initially loose with what is allowed and gradually tightening constraints until everything is accounted for.

A) Work up in stages from a classical circuit

Start by making a classical-ish circuit that prepares the correct output for each input without worrying about uncomputing the input. Then try to simplify that. Then, for each possible output, make sure you're uncomputing the input. Then try to simplify that. Then swap the uncomputed input for the computed output at the end of the circuit, making it a proper quantum circuit with some intermediate work qubits. Then try to simplify that and eliminate work qubits one by one.

B) Fix one state at a time, without breaking previous states

Pick the first input that is being sent to the wrong output. For example, $|001\rangle$ staying fixed instead of becoming $|010\rangle$. Apply a few operations that fix this without breaking any of the states you previously fixed. Repeat until all states are correct. Then look at the resulting circuit and start trying to make optimizations.

C) Recognize approximate patterns

The "each entry shifted down by one" pattern in the unitary matrix is what an increment looks like. So this matrix is applying an increment to the 1..7 subset of the state space while leaving 0 alone. This means that applying an increment operation (or learning how one is applied) is probably pretty close to the right answer, and from there you can try to fix up the differences.

  • $\begingroup$ Nice answer! My approach to solving the problem was more related to B) and slightly to C), but A) is also interesting. $\endgroup$ Jun 12, 2020 at 21:53
  • $\begingroup$ If I get it right option B) looks like Brut force searching you can find solution for 4x4 and 8x8 matrix but finding solution for matrix greater then that become very hard because I/O for 16x16 and 32x32 matrix will be 16 and 32 which is huge task. please share your thought on this @DavitKhachatryan $\endgroup$
    – zircon
    Sep 17, 2020 at 13:54
  • $\begingroup$ option A) sounds more promising for circuit construction but I didn't get it properly. If you don't mind Could you please explain it in more details and with example.Thanyou @CraigGidney $\endgroup$
    – zircon
    Sep 17, 2020 at 13:55
  • $\begingroup$ @quantum_boy, I am not sure that $N$ steps are required for a $N \times N$ matrix when we are using B) strategy. The complexity can be much worse. Also I don't see why $N$ (or even $N^2$) is a huge number (if it is then we should say compared to what or because of what criteria). $\endgroup$ Sep 19, 2020 at 6:33
  • $\begingroup$ @quantum_boy, but of course, you are right: B) as presented in this thread looks like a more manual strategy and might not work well for big problems. $\endgroup$ Sep 19, 2020 at 6:56

Here are the actions for the given transformation on the computational basis states:

$$|000\rangle \rightarrow |000\rangle \qquad |001\rangle \rightarrow |010\rangle \qquad |010\rangle \rightarrow |011\rangle \qquad |011\rangle \rightarrow |100\rangle \\ |100\rangle \rightarrow |101\rangle \qquad |101\rangle \rightarrow |110\rangle \qquad |110\rangle \rightarrow |111\rangle \qquad |111\rangle \rightarrow |001\rangle $$

Let's label the qubits in this format: $|q_2 q_1 q_0 \rangle$ (Qiskit's labeling). Here are some ideas. $|001\rangle \rightarrow |010\rangle$ and $ |010\rangle \rightarrow |011\rangle$ transformations can be done with CNOT(0, 1) and CNOT(1, 0) gates. $|011\rangle \rightarrow |100\rangle$ transformation can be done by adding Toffali(0, 1, 2) before the two CNOTs presented above and adding CNOT(2, 0) after the two CNOTs. $|110\rangle \rightarrow |111\rangle$ transformation can be done with Toffali(2, 1, 0). With this ideas we can construct the circuit (the ordering is important, but can be changed in some places):

For checking the correctness of the circuit we can try to give different inputs to the circuit and check the outputs or we can do matrix multiplications and see if the final matrix will be equal to the given matrix or we can use tools from Qiskit:

from qiskit import *
import qiskit.quantum_info as qi

circuit = QuantumCircuit(3)

circuit.ccx(0, 1, 2)
circuit.cx(0, 1)
circuit.cx(1, 0)
circuit.cx(2, 0)
circuit.ccx(2, 1, 0)

matrix = qi.Operator(circuit)

The output:

[[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]]

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.