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


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