3
$\begingroup$

We know that {$H,T$} is universal. However, I don't understand how we can generate any rotational matrix from this set. For example, how can I build

\begin{bmatrix} cos(\pi/8) & sin(\pi/8)\\ -sin(\pi/8) & cos(\pi/8) \end{bmatrix}

Where does the $\pi/8$ come from? To me it seems like we can only build rotational matrices involving multiples of $\pi/4$ from this universal gate set

$\endgroup$
3
  • 2
    $\begingroup$ As a general rule, it's highly non-trivial and cannot be done exactly. You need to use a synthesis algorithm to find a high accuracy sequence that achieves the unitary that you want. (Side note: H and T and not universal. They are single-qubit universal. You need to add a two-qubit gate such as cNOT to make them universal) $\endgroup$
    – DaftWullie
    Apr 18, 2023 at 15:55
  • $\begingroup$ @DaftWullie So the "universal" set is actually not universal? $\endgroup$
    – Irene
    Apr 18, 2023 at 16:34
  • 1
    $\begingroup$ Universal means that any gate can be approximated to arbitrary precision, not decomposed exactly. And what DaftWullie means is that $\{H, T\}$ is only universal for single qubit operations; you'll need to add, say, $CNOT$ to make the set universal for an arbitrary number of qubits. $\endgroup$
    – Cody Wang
    Apr 18, 2023 at 18:11

2 Answers 2

3
$\begingroup$

There are (asymptotically) far more efficient ways of performing the calculation than using the Solovay-Kitaev algorithm. I like the package provided here, assuming your rotation can easily be related to a Z rotation (your example can).

Let's take your example of $e^{i Y \pi/8}$. First, I'm going to change basis to make this into a $Z$ rotation, $$ e^{i Y \pi/8}=\sqrt{X}e^{i Z \pi/8}\sqrt{X}^\dagger=HSH e^{i Z \pi/8}HS^\dagger H $$ (where $S=T^2$ and $S^\dagger=T^6$). Now we can run the gridsynth program to approximate a $\pi/4$ Z rotation:

gridsynth pi/4

and it gives the output

SHTSHTHTSHTSHTSHTHTSHTSHTSHTSHTHTHTHTSHTHTHTSHTHTSHTHTHTSHTSHTHTHTHTHTHTHTSHTSHTHTHTHTHTHTSHTHTHTHTSHTSHTHTSHTHTHTHTSHTHTHTSHTHTSHTHTHTSHTHTSHTSHTHTSHTSHTHTSHTHTSHTHTHTSHTHTSHTSHTHTSHTSHTSHTSHTHTHTHTHTSHTSHTHTHTSHTHTHTHTSHTHTHTSHTHTHTSHTSHTSHTHTSHTSHTSHTSHTHTHTHTSHTSHTHTSHTHTSHTSHTHTHTHTHTSHTSHTSHTSHTSHTHTSHTHTSHTHTSHX

which we insert in place of the $e^{iZ\pi/8}$, and should be accurate to $10^{-10}$.

$\endgroup$
2
$\begingroup$

For single-qubit gates this can be done with the (indeed rather complex) Solovay-Kitaev algorithm. A solid pedagogical review is here. I put a working implementation here (it took me forever to get that to work ;-)

Note that for this algorithm to work, the rotations must be part of $SU(2)$ and have a determinant of 1. This means I had to convert the H, T gates via something like this:

def to_su2(u):
  return np.sqrt(1 / np.linalg.det(u)) * u

base = [to_su2(ops.Hadamard()), to_su2(ops.Tgate())]

So the algorithm is not strictly using H and T.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.