Quantum computers use qubits, which are like regular bits except that they can be in a superposition of quantum states $\vert 0\rangle$ and $\vert 1\rangle$: $$ \vert \psi\rangle = \alpha \vert 0\rangle + \beta \vert 1\rangle. $$ This suggests the following scheme for breaking an $n$-bit lock with a quantum computer: take $n$ qubits and put each into an even superposition, $$ \vert +\rangle = \frac{1}{\sqrt{2}} (\vert 0\rangle + \vert 1\rangle). $$ The total state of the system will be an even superposition over every $n$-bit string $\mathbf{x} \in \{0, 1\}^n$: $$ \begin{align*} \vert \psi\rangle & = \vert +\rangle \otimes \vert +\rangle \otimes \cdots\otimes \vert +\rangle \\ & = \vert +\rangle^{\otimes n} \\ & = \frac{1}{\sqrt{2^n}} \sum_{\mathbf{x} \in \{0, 1\}^n} \vert \mathbf{x}\rangle,\label{eq:had0} \tag{1} \end{align*} $$ where $\otimes$ indicates the tensor product. Note that when we take tensor products of basis states, we will usually omit the tensor product symbol, so for instance $\vert 0\rangle \otimes \vert 1\rangle = \vert 01\rangle$. If we could somehow test this state on our lock, then we will test the correct answer at the same time as everything else, and open the lock on the first go! It appears that we have turned an exponentially hard classical task into something we can perform in a single shot on a quantum computer. --- ***Exercise A.1.1.*** Prove Eq. $(\ref{eq:had0})$ by showing that the tensor product $\vert +\cdots + \rangle$ does indeed give the uniform superposition.

Hint.

Consider expanding a product of polynomials in ordinary algebra.

Solution.

It's a bit like ordinary algebra, where expanding a product $$ (a + b)(x + y) = ax + ay + bx + by $$ gives us all products of terms in the first factor with terms in the second. Similarly, $$ (\vert 0\rangle + \vert 1\rangle)\otimes (\vert 0\rangle + \vert 1\rangle) = \vert 00\rangle + \vert 01\rangle + \vert 10\rangle + \vert 11\rangle $$ gives us all tensor products of things in the first factor with things in the second. We can extend this to additional factors: $$ \begin{align*} (\vert 0\rangle + \vert 1\rangle) \otimes(\vert 0\rangle + \vert 1\rangle)\otimes(\vert 0\rangle + \vert 1\rangle) & = (\vert 00\rangle + \vert 01\rangle + \vert 10\rangle + \vert 11\rangle)\otimes(\vert 0\rangle + \vert 1\rangle) \\ & = \vert 000\rangle + \vert 001\rangle + \vert 010\rangle + \vert 011\rangle + \vert 100\rangle + \vert 101\rangle + \vert 110\rangle + \vert 111\rangle. \end{align*} $$ We can continue on in this way for $n$ factors, and generate an even superposition of all $n$-bit strings, labelled by $\mathbf{x} \in \{0, 1\}^n$. The factors of $1/\sqrt{2}$ come along for the ride. Thus, $$ \frac{1}{\sqrt{2}}(\vert 0\rangle + \vert 1\rangle) \otimes \frac{1}{\sqrt{2}}(\vert 0\rangle + \vert 1\rangle) \otimes \cdots \otimes \frac{1}{\sqrt{2}}(\vert 0\rangle + \vert 1\rangle) = \frac{1}{\sqrt{2^n}} \sum_{\mathbf{x} \in \{0, 1\}^n} \vert \mathbf{x}\rangle, $$ as required. ▢

Codercise A.1.1 — Create a uniform superposition

Breaking a lock classically

The uniform superposition

A quantum method?