8

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 "...


8

Throughout this answer, the norm of a matrix $A$, $\left\lVert A\right\rVert$ will be taken to be the spectral norm of $A$ (that is, the largest singular value of $A$). The solovay-Kitaev theorem states that approximating a gate to within an error $\epsilon$ requires $$\mathcal O\left(\log^c\frac 1\epsilon\right)$$ gates, for $c<4$ in any fixed number of ...


6

The Solovay-Kitaev algorithm is not practical. It is very useful theoretically because it proves that once you have a "dense" set of quantum gates (i.e. a set with which you can approximate any other quantum gate) you can approximate up to an arbitrary precision and quickly any quantum gate. In practice, the Solovay-Kitaev works as follow: Fill the space ...


5

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 ...


4

For Qiskit, there are two tools you can check out. The two qubit kak tool does exactly what you want for 2 qubits. If you give it a two qubit unitary, it gives you a list of gates to realize this, using the standard gate set used in Qiskit. This tool uses Vatan and Williams optimal two-qubit circuit. The decomposition algorithm used is explained in Drury ...


4

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 ...


3

I don't pretend that this is optimal in the sense of minimal number of applications, but here's one method that comes from the universality proof... The unitary that you want to implement can be parametrised by $U=\cos\gamma\mathbb{I}-i\sin\gamma\ \underline{m}\cdot\underline{\sigma}$ where $\underline\sigma$ is the vector of Pauli matrices $X$, $Y$, $Z$. ...


2

Here's a silly method that works if you know $y$, you know the probability of measuring $y$, and you can efficiently generate arbitrary-size superpositions of the form $$\frac{1}{\sqrt{N}}\sum_{b < N}\vert b\rangle.$$ To do this, use a Grover-like search: You need two circuits $U_y$ and $U_0$, with the following action: $$U_y\vert x\rangle \vert \psi\...


1

Note that Solovay-Kitaev theorem holds for unitaries on qu$d$it (section 5 in DN05), then we can set $d=2^n$ for $n$-qubit unitary. Following the same analysis, we obtain length of gate sequences $l_{\epsilon} = O(\ln^{\ln 5/\ln(3/2)} (1/\epsilon))$, time complexity $t_{\epsilon} = O(\ln^{\ln 3/\ln(3/2)}(1/\epsilon))$. Now the issue is the accuracy ...


1

The full scaling will be $O(4^n\text{poly}\left(\log\frac{1}{\epsilon}\right))$, so you do indeed get exponential scaling in the number of qubits.


Only top voted, non community-wiki answers of a minimum length are eligible