My question is related to the exercise 4.28 in the book of Nielsen and Chuang (Quantum Computation and Quantum Information). Here is the exercise

For $U=V^2$ with $V$ unitary, construct a $C^5(U)$ gate analogous to that in Figure 4.10, but using no work qubits. You may use controlled-$V$ and controlled-$V^{\dagger}$ gates.

enter image description here

I think the exercise in the current form is not possible to solved. Since any usage of a controlled-$V$ or $V^{\dagger}$ gate gives even 4 cases (with case I mean a combination of qubits) where $V$ or $V^{\dagger}$ is applied. So we can increase the number of applied $V$ gates with any usage of a controlled-$V$ or decrease the number of applied $V^{\dagger}$ gates with any usage of a controlled-$V^{\dagger}$ by 4. But to obtain the controlled-$U$ gate, we may only have $2$ usages of a $V$ gate. Thus any way we apply the controlled-$V$ or $V^{\dagger}$ gates, in the end we will always have more than 2 cases where a $V$ or $V^{\dagger}$ is applied (with applying I mean that it does not contract with another controlled gate, so it will really be applied at the end).

Note that this problem does not occur for controlled-X gate since an addition can be though as an addition modulo 2, therefore we can decrease the numbers of cases where a qubit is switched.

Since I think that this chapter is heavily influenced by the paper https://arxiv.org/abs/quant-ph/9503016.pdf which constructs a $C^3(U)$ with controlled-$V$ gates where $V^4=U$, I think it should be $V^16=U$ in the exercise. However I am not certain if there really does not exist a solution, maybe one using maybe gates creating a superposition like the Hadamard gate. So my question is, if someone has a solution for this exercise or a proof that it is impossible to do.


It can be done in the same way as the $$C^3(U)$$ circuit with 4 controls. circuit

Look in arXiv0708.3274 for details

  • $\begingroup$ This construction is also in the paper I posted in my question (Lemma 7.5), but I thought, in the exercise by "controlled-V" gate a gate with only one control qubit is meant, however the term is vague and could mean your solution and probably does. It is just a bit unsatisfying, because to construct the controlled-U gate you need another controlled-V gate with one less control bit, which is in general also not easy to construct; thus the construction seems to be not very useful. $\endgroup$ – Alex Go Aug 31 '17 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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