Quantum Computing 2.4 -- Quantum code golf

The optimal sequence of the operators $H$ and $T$ must obey the following rules

• The sequence must begin and end with the Hadamard gate $H$
• Each Hadamard gate $H$ is followed by a phase gate $T$

We can justify the first rule by the fact, that the phase shift does not alter the probability amplitudes of the state. If the sequece ends with the operation $T$ , we can delete this last operation without altering the measurement results. In particular, the phase shift does not alter the initial state ( $T|0\rangle = |0\rangle$ ).

The second rule follows from the fact, that the Hadamard gate is self-adjoint so that $H \cdot H = I$ . If in the sequence somewhere the $H$ operator appears twice in direct succession, then you can simply omit both operators without changing anything.

Considering these rules, we get a sequence of possible "programs" for our quantum computer: $H, HTH, HTTH, HTTTH, HTHTH, \dots$ The first nontrivial seqeunces have the form $H T^k H$ . In this case, the probability $P_{|0\rangle} = |\langle 0 | \psi \rangle|^2$ for the measurement result $|0\rangle$ yields $\begin{aligned} P_{|0 \rangle} = |\langle 0| H T^k H |0\rangle|^2 &= \left|\frac{1}{2} \left(\begin{array}{cc} 1 & 0 \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & e^{i k \frac{\pi}{4}} \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array} \right) \left(\begin{array}{c} 1 \\ 0 \end{array} \right) \right|^2 \\ &= \left|\frac{1}{2} \left(\begin{array}{cc} 1 & 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & e^{i k \frac{\pi}{4}} \end{array} \right) \left(\begin{array}{c} 1 \\ 1 \end{array} \right) \right|^2 \\ &= \left|\frac{1 + e^{i k \frac{\pi}{4}}}{2} \right|^2 \\ &= \frac{1 + \cos \frac{k \pi}{4} }{2} \\ &= 1, \frac{1}{2} + \frac{1}{\sqrt 8}, \frac{1}{2}, \frac{1}{2} - \frac{1}{\sqrt 8}, 0 \end{aligned}$ Note, that the wanted result $P_{|0 \rangle} = 3/4$ does not appear in this list.

Now we consider the next sequence $HTHTH$ : $\begin{aligned} P_{|0\rangle} = |\langle 0| HTHTH |0\rangle|^2 &= \left|\frac{1}{\sqrt{8}} \left(\begin{array}{cc} 1 & 0 \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & e^{i \frac{\pi}{4}} \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & e^{i \frac{\pi}{4}} \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array} \right) \left(\begin{array}{c} 1 \\ 0 \end{array} \right) \right|^2 \\ &= \frac{1}{8} \left| \left(\begin{array}{cc} 1 & 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & e^{i \frac{\pi}{4}} \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & e^{i \frac{\pi}{4}} \end{array} \right) \left(\begin{array}{c} 1 \\ 1 \end{array} \right) \right|^2 \\ &= \frac{1}{8} \left| \left(\begin{array}{cc} 1 & e^{i \frac{\pi}{4}} \end{array} \right) \left( \begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array} \right) \left(\begin{array}{c} 1 \\ e^{i \frac{\pi}{4}} \end{array} \right) \right|^2 \\ &= \frac{1}{8} \left| \left(\begin{array}{cc} 1 & e^{i \frac{\pi}{4}} \end{array} \right) \left(\begin{array}{c} 1 + e^{i \frac{\pi}{4}}\\ 1 - e^{i \frac{\pi}{4}} \end{array} \right) \right|^2 \\ &= \frac{1}{8} \left|1 + 2 e^{i \frac{\pi}{4}} - e^{i \frac{\pi}{2}} \right|^2 \\ &= \frac{1}{8} \left|(\sqrt{2} + 1) + (\sqrt{2} - 1) i \right|^2 \\ &= \frac{1}{8} \left((\sqrt{2} + 1)^2 + (\sqrt{2} - 1)^2 \right) \\ &= \frac{1}{8} \left(2 + 1 + 2 \sqrt 2 + 2 + 1 - 2 \sqrt 2 \right) \\ &= \frac{3}{4} \end{aligned}$ Thus, we get the wanted probability of 75%. Futhermore, we have proved, that the sequence $HTHTH$ with the length $n = 5$ is the shortest sequence with this property.

Alternatively, you can visualize these operations on the Bloch sphere. In this representation, the operator $H$ corresponds to a rotation about the angle $\pi$ around the axis $\hat x + \hat z$ and $T$ rotates the state vector by the angle $\pi / 4$ around the axis $\hat z$ . We start at the point $\vec r = \hat z$ (north pole of the Bloch sphere). The goal is to get to a point at the circle $z = \cos (\theta) = 2 \cos ^ 2 (\theta / 2) - 1 = 1/2$ using only this two rotation operations. The two rotation matrices read $\begin{aligned} \mathcal{H} &= \left( \begin{array}{ccc} 0 & 0 & 1 \\ 0 & -1 & 0 \\ 1 & 0 & 0 \end{array} \right) \\ \mathcal{T} &= \left( \begin{array}{ccc} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \end{array} \right) \end{aligned}$ The final state of the operation $HTHTH$ results (without displaying all the calculations) $\mathcal{H} \cdot \mathcal{T} \cdot \mathcal{H} \cdot \mathcal{T} \cdot \mathcal{H} \cdot \hat z = \left( \begin{array}{c} 1/ \sqrt{2} \\ 1/2 \\ 1/2 \end{array} \right)$ Finally, we can visualize these operations: