# Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28)

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.

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 is not possible. We can consider the simpler case of constructing $$C^3(U)$$ using only $$\tt{CNOT}$$, Toffoli, $$U$$, $$V$$, $$C(U)$$, $$C^2(U)$$ and $$C(V)$$ where $$V^2=1$$.

We consider the determinant of the matrix representation of the gates over only the first 3 qubits (so the outcome of the determinant is an operator on the last qubit), and we have:

$$C^3(U) = \left.\begin{array}{ccc}- & \bullet & - \\ & | & \\- & \bullet & - \\ & | & \\- & \bullet & - \\ & | & \\- & U & -\end{array}\right. = \left(\begin{array}{cccccccc}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 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right) \Rightarrow \det C^3(U) = U$$

$$C^2(U) = \begin{array}{ccc}- & - & - \\ & & \\- & \bullet & - \\ & | & \\- & \bullet & - \\ & | & \\- & U & -\end{array} = \left(\begin{array}{cccccccc}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 & U & 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 & U\end{array}\right) \Rightarrow \det C^2(U) = U^2$$

$$C(U) = \left.\begin{array}{ccc}- & - & - \\ & & \\- & - & - \\ & & \\- & \bullet & - \\ & | & \\- & U & -\end{array}\right. = \left(\begin{array}{cccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & U & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & U & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right) \Rightarrow \det C(U) = U^4$$

$$U = \begin{array}{ccc}- & - & - \\ & & \\- & - & - \\ & & \\- & - & - \\ & & \\- & U & -\end{array} = \left(\begin{array}{cccccccc}U & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & U & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & U & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & U & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & U & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & U & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right) \Rightarrow \det U = U^8$$

Similarly, we can prove $$\det V = V^8 = U^4$$ and $$\det C(V) = V^4 = U^2$$.

The determinant of $$\tt{CNOT}$$ and Toffoli do not involve factors of $$U$$ so they will not affect the analysis below.

Now suppose $$C^3(U)$$ can be constructed by the combinations $$C^3(U) = G_1 G_2 \cdots$$, where each $$G_i$$ is among the gates stated above, then we must have: $$\det C^3(U) = \prod_i \det G_i \Rightarrow \prod_i \det G_i = U$$

This identity is however impossible to satisfy using the gates above because the determinants of $$U$$, $$V$$, $$C(U)$$, $$C^2(U)$$ and $$C(V)$$ all give even powers of $$U$$.

The only possible way out is to include $$C(\sqrt{V})$$ because $$\det C(\sqrt{V})=\sqrt{V}^4= U$$. But $$C(\sqrt{V})$$ can be used to construct $$C^2(V)$$. If we can use $$C^2(V)$$, then the solution to (4.28) is rather obvious and we get the solution given by Bram.

The proof for more qubits is similar.

I am a physicist, not specialized in quantum computing. Question 4.28 was indeed frustrating. Up until that question, the underlying principle of the chapter was the construction of more complicated gates using more elementary gates. Had I known the authors wanted us to use $$C^2(V)$$ (which would require $$C(\sqrt{V})$$ gate, which may or may not exist, not previously constructed nor alluded to in the question), I would have solved the question in less than a minute. Perhaps proving once and for all there is no solution (the way most readers would interpret the question) will save others from the frustration.

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

Look in arXiv0708.3274 for details

• 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. Commented Aug 31, 2017 at 17:16