From the Qiskit textbook I read about Simon's algorithm. There are two n-wide quantum registers, so the general state is given by


where x and y are the $2^n-1$ binary representations. A function from the n-subspace into n-subspace id defined by

$$f: |x\rangle\mapsto|f(x)\rangle$$

Now, the "query function" is given by the operation

$$|x\rangle|a\rangle \rightarrow |x\rangle |a \oplus f(x)\rangle$$

All building blocks in quantum computation shall be unitary transformations, so this mapping is unitary too - but how can I prove that this is really the case?

Is it enough to show, that norm is conserved like this:


$$U|x\rangle|a\rangle = |x\rangle |a \oplus f(x)\rangle$$

I would have

$$\langle x| \langle a|U^\dagger = \langle x| \langle a \oplus f(x)|$$

so $$\langle x| \langle a|U^\dagger U |x\rangle |a\rangle= \langle x|x\rangle \langle a \oplus f(x)|a \oplus f(x)\rangle = 1 \cdot 1 = 1$$

But this appears a bit too trivial to be a prove...


The easiest way to prove this is to apply the operator twice $$ |x\rangle|a\rangle\mapsto |x\rangle|a\oplus f(x)\rangle\mapsto |x\rangle|a\oplus f(x)\oplus f(x)\rangle=|x\rangle|a\rangle. $$ So, two applications of the function is the identity operation. Thus, the function is its own inverse, $U=U^{-1}$. Moreover, the eigenvalues must all be $\pm 1$, which shows that, for example, $U=U^\dagger$, and hence $UU^\dagger=I$, the standard relation for a unitary.

Incidentally, for what you tried to prove, is it clear that because, in a certain basis, all the lengths of those basis states are preserved, that the lengths of all possible superpositions of those states are also preserved?

  • 1
    $\begingroup$ Those two conditions combined clearly gives $U U^\dagger=I$. The first, $U=U^{-1}$ is clear. But why eigenvalues of this operation are $\pm 1$ from which one follows $U=U^\dagger$? $\endgroup$
    – MichaelW
    Oct 25 at 11:01
  • 3
    $\begingroup$ Oh yes, of course: $U^2|\psi\rangle = \lambda^2 |\Psi\rangle$. From this I get trivially $\lambda = \pm 1$. $\endgroup$
    – MichaelW
    Oct 25 at 11:15
  • $\begingroup$ Why is my original approach wrong? When the norm is conserved in one orthogonal base, I thought, by insertion of the unit-operator, this is true in any base. The property "unitary" cannot depend on the base I use - where am I wrong? $\endgroup$
    – MichaelW
    Oct 25 at 19:45
  • 1
    $\begingroup$ Consider the operator $P=\sqrt{2}|+\rangle\langle +|$. This has $P|0\rangle=|+\rangle$ and $P|1\rangle=|+\rangle$. For both computational basis states of a qubit, the length is preserved. But for other states, such as $|+\rangle$, it is not. It should be sufficient to additionally prove that orthogonality of your outputs is preserved. $\endgroup$
    – DaftWullie
    Oct 26 at 6:39
  • 1
    $\begingroup$ It's true I skipped over that (it wasn't obvious to me from the question what the appropriate level of detail was). It might be easiest to take a look at quantumcomputing.stackexchange.com/questions/5779/… $\endgroup$
    – DaftWullie
    Oct 27 at 9:48

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.