2
$\begingroup$

I am reading Quantum Computation and Quantum Information by Chuang and Nielsen and they claim that it is easy to show that transformation $U_f: \left| x, y \right\rangle \to \left| x, y \oplus f(x) \right\rangle$ is unitary.

My first instinct is to use the condition $U^\dagger U = I$, but I can’t figure out how to construct the matrix $U_f$. Is there another way?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
4
$\begingroup$

As it happens, this $U_f$ is its own inverse. So to show that it is unitary, you need to show that

  1. $U_fU_f=I$

  2. $U_f^\dagger = U_f$

(that is, $U_f$ is its own inverse).

Both of these are straightforward (1. ist just arithmetics, for 2. you can use a change of variables).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Just question, the second condition means that the matrix is Hermitian. To be a unitary, it does not have to be self-inverse, take for example rotational gates. Right? $\endgroup$
    – Martin Vesely
    Commented Jun 30 at 13:13
  • $\begingroup$ @MartinVesely I'm not sure I understand the question correctly, so (a) unitaries don't have to be hermitian, and (b) the unitary in the question is hermitian (i.e. self-inverse), which is proven by checking the two conditions given. (There are other ways to prove unitarity, like the one in the other answer, but the way given in my answer is just as good of a proof for the unitary in the question, which is what the question is about. Note that for the other answer, it is not sufficient to check that it maps any computational basis state to a computational basis state, ... $\endgroup$
    – Norbert Schuch
    Commented Jun 30 at 16:47
  • $\begingroup$ (which is easy), but also that this is a permutation, which e.g. can be done by constructing an inverse map -- so it also requires checking two conditions (the way the answer is written might make this sound easier than it actually is)). $\endgroup$
    – Norbert Schuch
    Commented Jun 30 at 16:50
  • $\begingroup$ (As a side note, I tend to ask this in oral exams, and either of the two answers is a valid answer.) $\endgroup$
    – Norbert Schuch
    Commented Jun 30 at 16:52
  • $\begingroup$ I see now, thanks for detailed explanation. $\endgroup$
    – Martin Vesely
    Commented Jun 30 at 21:26
2
$\begingroup$

First notice that a transformation is unitary if and only if it sends an orthonormal basis to an orthonormal basis. Then conclude that every transformation which permutes the computational basis, such as $U_f$, is unitary.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Of course, one has to make sure it is really a permutation: Just mapping any computational basis state to a computational basis state (which can be read off directly of the form of the map) is not enough. $\endgroup$
    – Norbert Schuch
    Commented Jun 30 at 16:54
  • $\begingroup$ Of course. But clearly, it is a permutation (proof: apply it twice). $\endgroup$
    – Adam Zalcman
    Commented Jul 1 at 7:59
  • 1
    $\begingroup$ True, but it is as clear as the point you make in your answer. Point is, one has to check two things in both cases (which it seems wasn't clear to a commenter below my answer, thus my comment here). $\endgroup$
    – Norbert Schuch
    Commented Jul 10 at 14:34
  • $\begingroup$ This is a fair point. I see that you made this explicit in your answer. +1 $\endgroup$
    – Adam Zalcman
    Commented Jul 11 at 3:29

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