2
$\begingroup$

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?

$\endgroup$
  • 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 Schuch Feb 17 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$ – bilanush Feb 18 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$ – bilanush Feb 18 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$ – bilanush Feb 19 at 13:37
  • $\begingroup$ Unlike the universality result, which is a random claim? $\endgroup$ – Norbert Schuch Feb 19 at 14:35
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – bilanush Feb 18 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$ – bilanush Feb 18 at 10:11
  • $\begingroup$ what do you understand by "two level matrices"? $\endgroup$ – DaftWullie Feb 18 at 11:47
  • $\begingroup$ One would have assumed that the OP would have checked that this is not used in the proof ... $\endgroup$ – Norbert Schuch Feb 18 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$ – DaftWullie Feb 19 at 13:59

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.