One of the major challenges for me (and I expect for many as a beginning students with only general maths skills) in studying quantum computation is that while the background and calculations required are fairly elementary, the tools themselves come from a diverse range of often neglected, and at best long forgotten or under-exercised, toolkits (complex arithmetic, including roots of $-1$, modular arithmetic, linear algebra, matrix representations, summation, etc.)

For example, in a typical calculation, as part of the analysis of Simon's algorithm, we are given* $$ U_{f}=\sum_{y,z}\big(\left|z\right>\!\!\left<z\right|\otimes\left|y\oplus f(z)\right>\!\!\left<y\right|\big)$$ and $$ \left|\psi\right>=(H^{\otimes^n}\otimes I_n)\left|0^n\right>\!\!\left|0^n\right>= \frac{1}{\sqrt{2^n}}\sum_{x}\left|x\right>\!\!\left|0^n\right>$$ where the summations are over all $x,y,z \in \{0,1\}^n$, and need to produce an expression for $U_{f}\left|\psi\right>$.

Accomplishing this is much more challenging for me that it feels like it ought to be, and I've no confidence at all in how I've gone about it.

Setting up the expression is straightforward enough

$$U_{f}\left|\psi\right> = \frac{1}{\sqrt{2^n}}U_{f}\sum_{x}\left|x\right>\!\!\left|0^n\right>= \frac{1}{\sqrt{2^n}}\sum_{x}U_{f}\left|x\right>\!\!\left|0^n\right>$$ and expanding $U_{f}$ at this point to $$= \frac{1}{\sqrt{2^n}}\sum_{x}\bigg[\bigg[\sum_{y,z}\big(\left|z\right>\!\!\left<z\right|\otimes\left|y\oplus f(z)\right>\!\!\left<y\right|\big)\bigg]\left|x\right>\!\!\left|0^n\right>\bigg]$$

allows application of the definition of $\otimes$ for linear operators to give $$= \frac{1}{\sqrt{2^n}}\sum_{x}\sum_{y,z}\big(\left|z\right>\left<z|x\right>\otimes\left|y\oplus f(z)\right>\left<y|0^n\right>\big)$$

Then, recognizing that $\left<z|x\right> = [z=x]$ (using an Iverson bracket, for brevity) allows eliminating of the summation over $z$ by substituting $x$ for $z$

$$= \frac{1}{\sqrt{2^n}}\sum_{x}\sum_{y,z}\big([z=x]\left|z\right>\otimes\left|y\oplus f(z)\right>\left<y|0^n\right>\big)$$

$$= \frac{1}{\sqrt{2^n}}\sum_{x}\sum_{y}\big(\left|x\right>\otimes\left|y\oplus f(x)\right>\left<y|0^n\right>\big)$$

and similarly, recognizing that $\left<y|0^n\right> = [y=0]$ allows eliminating of the summation over $y$ by substituting $0^n$ for $y$

$$= \frac{1}{\sqrt{2^n}}\sum_{x}\sum_{y}\big(\left|x\right>\otimes [y=0]\left|y\oplus f(x)\right>\big)$$

$$= \frac{1}{\sqrt{2^n}}\sum_{x}\big(\left|x\right>\otimes \left|0\oplus f(x)\right>\big)$$

The result then follows from the definition of $\oplus$:

$$= \frac{1}{\sqrt{2^n}}\sum_{x}\left|x\right> \left|f(x)\right>$$

Does this approach make any sense at all? Have I missed something or failed to apply some idiom in a way that obscures what's going on. Are there errors or assumptions I've made that I shouldn't have?

*In Eq. 9 of the reference we're actually given $ U_{f}=\sum_{y,x}\big(\left|x\right>\!\!\left<x\right|\otimes\left|y\oplus f(x)\right>\!\!\left<y\right|\big)$, that is, with $x$ instead of $z$; but this seems misleading and invites confusion when used as above. Is my substitution of a distinct $z$ for the "already used" $x$ correct?



You must log in to answer this question.