In the book by Chuang and Nielsen they prove that controlled U operations can be made out of CNOTs and single qubit gates. But then they go on to prove that they are universal by showing that every n by n matrix can be decomposed into two level matrices and then to CNOTs and single qubit gates. But if so, then why can't we prove this way that controlled U can be too, decomposed to them. Since a controlled U is after all an n by n matrix. Why is there a separate proof for them?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ Because it might be more insightful? These gates might be more relevant? Because the construction you get is simpler? Or just for educational purposes? This is a bit like asking why a math textbook first proves Cauchy-Schwarz and then later Hölder's inequality, given that the former is a special case. $\endgroup$– Norbert SchuchCommented Feb 17, 2019 at 21:15
-
$\begingroup$ But is this indeed the case here? They give a pretty lengthy and complicated proof for this . What's the point if later it can be proven by the universality. Why do they have to show controlled U and not other special cases? $\endgroup$– bilanushCommented Feb 18, 2019 at 9:50
-
1$\begingroup$ I thought, but I am not sure. Maybe their universality proof which is based on factorization of unitary into two level matrices doesn't hold for controlled U just like it doesn't hold for CNOT $\endgroup$– bilanushCommented Feb 18, 2019 at 9:53
-
$\begingroup$ I don't think the comparison to Cauchy Schwar is valid. As it's a theorem. But here what's the point $\endgroup$– bilanushCommented Feb 19, 2019 at 13:37
-
$\begingroup$ Unlike the universality result, which is a random claim? $\endgroup$– Norbert SchuchCommented Feb 19, 2019 at 14:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
Constructing controlled-U out of single qubit rotations and cNOT is part of the proof of universality of single qubit rotations and cNOT.
The bit of Nielsen & Chuang that you're referring to decomposes an arbitrary unitary in terms of gates such as controlled-controlled-....-controlled-U. See, for example, Fig 4.16 (P. 193 of 2002 printing). But that gate is built out of controlled-U. See, for example, Fig. 4.10 (P. 184). (although Exercise 4.28 gives you a different construction without work qubits). So, you need to construction of controlled-U for the whole thing to work.
answered Feb 18, 2019 at 7:41
-
$\begingroup$ Not sure what you mean by figure 4.16 and 4.10. In which pages? I don't find them. According to what I see their proof is based on decomposition to two level matrices and then , each of them they decompose to single qubit matrices and CNOTs. $\endgroup$– bilanushCommented Feb 18, 2019 at 10:10
-
$\begingroup$ I thought, but I am not sure. Maybe their universality proof which is based on factorization of unitary into two level matrices doesn't hold for controlled U just like it doesn't hold for CNOT $\endgroup$– bilanushCommented Feb 18, 2019 at 10:11
-
$\begingroup$ what do you understand by "two level matrices"? $\endgroup$ Commented Feb 18, 2019 at 11:47
-
$\begingroup$ One would have assumed that the OP would have checked that this is not used in the proof ... $\endgroup$ Commented Feb 18, 2019 at 16:13
-
1$\begingroup$ @bilanush So, according to you, how do N&C go from having a two-level matrix to decomposing it in terms of cNOT and single qubit unitaries? $\endgroup$ Commented Feb 19, 2019 at 13:59