Prove that, if \(U\in\mathbb{C}^{n\times n}\) is a unitary matrix, then \(\|Ux\|_2=\|x\|_2\) for all \(x\in\mathbb{C}^n\) where \(\|x\|_2=\sqrt{\sum_{i=1}^n|x_i|^2}\text{.}\)
The Kronecker Product of two matrices \(A = [a_{i,j}]_{\substack{1\leq i\leq n\\ 1\leq j\leq k}}\in \mathbb{C}^{n\times k}\) and \(B=[b_{i,j}]_{\substack{1\leq i\leq m\\ 1\leq j\leq \ell}}\in\mathbb{C}^{m\times \ell}\) is the \(nm\times k\ell\) matrix \(A\otimes B\) where, for any \(1\leq i\leq n\text{,}\)\(1\leq j\leq k\text{,}\)\(1\leq i'\leq m\) and \(1\leq j'\leq \ell\text{,}\) the entry on row \((i-1)n + i'\) and column \((i'-1)k + j'\) is equal to \(a_{i,j}b_{i',j'}\text{.}\) For example, if \(A=\begin{bmatrix}a \amp b\\c\amp d\end{bmatrix}\) and \(B=\begin{bmatrix}e \amp f\\g\amp h\end{bmatrix}\text{,}\) then
\begin{equation*}
A\otimes B = \begin{bmatrix}ae \amp af \amp be \amp bf\\ ag \amp ah \amp bg \amp bh\\ce \amp cf \amp de \amp df\\ cg \amp ch \amp dg \amp dh\end{bmatrix}.
\end{equation*}
Let \(A\) be an \(n\times n\) matrix and \(B\) be an \(m\times m\) matrix. Prove that \((A\otimes B)^T=A^T\otimes B^T\text{.}\)
Let \(A\) be an \(n\times n\) matrix and \(B\) be an \(m\times m\) matrix. Prove that \((A\otimes B)^*=A^*\otimes B^*\text{.}\)
Let \(A\) and \(C\) be \(n\times n\) matrices and \(B\) and \(D\) be \(m\times m\) matrices. Prove that \((A\otimes B)(C\otimes D) = (AC)\otimes (BD)\text{.}\)
Prove that if \(A\) is a unitary matrix and \(B\) is a unitary matrix, then \(A\otimes B\) is a unitary matrix.
Let \(N=2^n\) for some integer \(n\geq1\) and denote the the elements of an orthonormal basis of \(\mathbb{C}^n\) by \(\left|0\right\rangle,\dots,\left|N-1\right\rangle\text{.}\) Use the matrix \(H_1\) from Example 9.1.2 and the Kronecker product to prove that there exists a unitary matrix \(H_n\in\mathbb{C}^{N\times N}\) such that \(H_n\left|0\right\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\left|x\right\rangle\) and \(H_n^2=I\text{.}\)
Prove that \(\begin{bmatrix}1-\frac{4}{N}\amp -\frac{2}{\sqrt{N}}\\ \frac{2}{\sqrt{N}}\amp 1\end{bmatrix}=MJM^{-1}\) where \(M\) and \(J\) are defined as in Section 9.1.
Let \(n=2\) (and so \(N=4\)). Show that, for any \(\omega\in\{0,1,2,3\}\text{,}\) running Grover’s algorithm for \(r=1\) step always yields the state \(\left|\omega\right\rangle\text{.}\) Conclude that Grover’s Algorithm yields the correct output with probability one in this case.
Let \(N=4\) and suppose that the \(N\) pure states of a quantum system are \(\left|00\right\rangle\text{,}\)\(\left|01\right\rangle\text{,}\)\(\left|10\right\rangle\) and \(\left|11\right\rangle\text{.}\) Come up with quantum gates (i.e. \(4\times 4\) unitary matrices) that perform the following operations:
Negate the first bit. That is, \(\left|0x\right\rangle\) maps to \(\left|1x\right\rangle\) and \(\left|1x\right\rangle\) maps to \(\left|0x\right\rangle\) for each \(x\in\{0,1\}\text{.}\)
Negate the first bit if the second bit is \(1\text{;}\) otherwise, keep the first bit the same.
Apply the Hadamard gate to the first bit if the second bit is \(1\text{;}\) otherwise, keep the first bit the same. That is, \(\left|01\right\rangle\) maps to \(\frac{1}{\sqrt{2}}\left|01\right\rangle + \frac{1}{\sqrt{2}}\left|11\right\rangle\) but, \(\left|00\right\rangle\) maps to itself, for example.
