# Tag Info

## Hot answers tagged solovay-kitaev-algorithm

9

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

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

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

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

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

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

4

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

4

According to the paper The Solovay-Kitaev algorithm (pg. 7) a number of single qubits gates approximating unitary $U$ is $$l = O(\ln^{\ln5/\ln(3/2)}\frac{1}{\epsilon}),$$ where ${\ln5/\ln(3/2)} = 3.97$. So, in your case with accuracy $\epsilon = 0.125$, you have $\ln^{3.97}\frac{1}{0.125}=\ln^{3.97} 8 = 18.29$. For $\epsilon = 0.05$, you will get 77.93....

4

You might want a small set of gates, but it doesn't necessarily mean that you want the smallest set possible. When you talk about a fault-tolerant quantum computer, what you really want to do is minimise the number of $T$ gates (typically the thing that is hard to implement). Other gates from, for example, the Clifford group, are (relatively) easy to ...

2

The restricted gate set of, for example, $\{H,T\}$, is more relevant when you start talking about error corrected quantum computation. It may be that when you act on individual, physical, qubits, you can implement and arbitrary single-qubit rotation. However, when you encode in an error correcting code, and you want to implement a gate directly on the ...

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