Approximating unitary matrices

Question

I currently have 2 unitary matrices that I want to approximate to a good precision with the fewer quantum gates possible.

In my case the two matrices are:

• The square root of NOT gate (up to a global phase) $$G = \frac{-1}{\sqrt{2}}\begin{pmatrix} i & 1 \\ 1 & i \end{pmatrix} = e^{-\frac{3}{4}\pi} \sqrt{X}$$
• $$W = \begin{pmatrix} 1&0&0&0\\ 0&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\\ 0&\frac{1}{\sqrt{2}}&\frac{-1}{\sqrt{2}}&0\\ 0&0&0&1 \\ \end{pmatrix}$$

My question is the following:

How can I approximate these specific matrices with the fewer quantum gates possible and a good precision?

What I want to have an can afford to have it:

1. I can afford to use several days/weeks of CPU time and a lot of RAM.
2. I can afford to spend 1 or 2 human days searching for mathematical tricks (in last resort, that is why I ask here first). This time does not include the time I would need to implement the hypothetical algorithms used for the first point.
3. I want the decomposition to be nearly exact. I don't have a target precision at the moment, but the 2 gates above are used extensively by my circuit and I don't want errors to accumulate too much.
4. I want the decomposition to use the fewest quantum gates possible. This point is secondary for the moment.
5. A good method would let me choose the trade-off I want between the number of quantum gates and the precision of the approximation. If this is not possible, an accuracy of at least $10^{-6}$ (in terms of trace norm) is probably (as said before, I do not have estimates so I am not sure of this threshold) required.
6. The gate set is: $$ \left\{ H, X, Y, Z, R_\phi, S, T, R_x, R_y, R_z, \text{CX}, \text{SWAP}, \text{iSWAP}, \sqrt{\text{SWAP}} \right\} $$ with $R_\phi, \text{SWAP}, \sqrt{\text{SWAP}}$ as described in Wikipédia, $R_A$ the rotation with respect to the axe $A$ ($A$ is either $X$, $Y$ or $Z$) and $$\text{iSWAP} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & i & 0 \\ 0 & i & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$$.

The methods I know about:

1. The Solovay-Kitaev algorithm. I have an implementation of this algorithm and already tested it on several unitary matrices. The algorithm generates sequences that are quite long and the trade-off [number of quantum gates] VS [precision of the approximation] is not enough parametrisable. Nevertheless, I will execute the algorithm on these gates and edit this question with the results I obtained.
2. Two papers on 1-qubit gate approximation and n-qubit gate approximation. I also need to test these algorithms.

EDIT: edited the question to make "square root of not" more apparent.

Answer 1

You have picked two particularly simple matrices to implement.

The first operation (G) is just the square root of X gate (up to global phase):

In your gate set, this is $R_X(\pi/2)$.

The second operation (W) is a Hadamard matrix in the middle 2x2 block of an otherwise-identity matrix. Anytime you see this 2x2-in-the-middle pattern you should think "controlled operation conjugated by CNOTs". And that's exactly what works here (note: you may need to swap the lines; depends on your endianness convention):

So the only real trouble is how to implement a controlled Hadamard operation. A Hadamard is a 180 degree rotation around the X+Z axis. You can use a 45 degree rotation around the Y axis to move the X+Z axis to the X axis, then do a CNOT in place the CH, then move the axis back:

Where $Y^{1/4} \equiv R_Y(\pi/4)$.

Answer 2

When a two qubit gate $W$ can be expressed (up to a global phase) in the computational basis by a matrix with entirely real entries, i.e., $W \in O(4)$, then there is general construction of implementing the gate with $CNOTs$ and single qubit gates, please see Vatan and Williams.

The construction is optimal in the sense that it requires two CNOT gates and at most 12 single qubit gates (for the most general case of a real two qubit gate). The construction is based on the homomorphism:

$$SO(4) \approx SU(2) \times SU(2),$$ which asserts that any two-qubit gate $W$ with real entries can be expressed as: $$W = M U M^{\dagger}$$ with $U\in SU(2) \otimes SU(2)$ , i.e., can be implemented by two single qubit gates.

A matrix $M$ inducing this homomorphism is named by Makhlin the magic matrix, one possible solution is given on the bottom of page 2 in Vatan and Williams work, another possibility is given in equation (10) by Fujii. Vatan and Williams gave a construction with one CNOT for $M$

Using this construction, the full gate implementation given by Vatan and Williams is:

with $S_1 = S_z(\frac{\pi}{2})$ and $R_1 = S_y(\frac{\pi}{2})$

Using this construction, it should be a quite an easy exercise to compute the one-qubit gates $A$ and $B$, for your case.

Answer 3

Neither of these gates require approximate sequences. You can implement them exactly with your specified gate sets with no great effort.

Up to a global phase (which should be irrelevant), G is simply $HSH$.

The second, $W$, is a little more complicated. The way that I constructed this was to think of it as a controlled-Hadamard where I then required a basis change which is created by a controlled-not. One therefore has the circuit

where $U=\cos\frac{\pi}{8}\mathbb{I}-i\sin\frac{\pi}{8}Y$. I always get factors of 2 wrong in these angles, but this is of the form $R_Y(\theta)$. I've taken no particular effort to optimise this gate sequence, but this is probably fairly good.