The Solovay-Kitaev algorithm claims that any $n$-qubit unitary gate can be decomposed to $O(\log^c(1/\epsilon))$ gates in any given universal gate set, e.g. Clifford+T.

However, the number of qubits $n$ does not appear in the equation. Is the scaling independent of $n$? If so it seems to be a super efficient algorithm. As far as I know, in quantum computing for quantum chemistry, people apply the unitary evolution of Hamiltonian $e^{-iHt}$ with $H=\sum_i h_i$ by sequentially applying $e^{-i h_i \Delta t}$ via Trotterization, which has roughly $O(n^4)$ cost since $H$ typically has $O(n^4)$ terms.

Clearly, the $O(\log^c(1/\epsilon))$ circuit length is much better, so I think I must be wrong somewhere. If the answer is that the Solovay-Kitaev algorithm actually has an exponential scaling with $n$, where does the dependence come from?

I read the proofs but didn't find it. Or maybe the answer is that Solovay-Kitaev algorithm requires $O(\exp(n))$ classical cost so is not practical for large unitary matrices? Also, what is the current best result of decomposing $n$-qubit unitary to Clifford+T (or other universal gate set) up to error $\epsilon$?


1 Answer 1


Your statement of the theorem is slightly inaccurate. However, this inaccuracy is actually very important, and perhaps this is what creates confusion.

Briefly, the Solovay-Kitaev (SK) theorem and proof tell us how to approximate a unitary of dimensions $d \times d$ in terms of other unitary gates of dimension $d \times d$, and it will take $O(\log^c(1/\epsilon))$ of such gates if we want accuracy $\epsilon$. The theorem does not state that we can approximate a $d \times d$ unitary with say $4 \times 4$ or $2 \times 2$ gates.

The correct statement of the theorem is: enter image description here Source: THE SOLOVAY-KITAEV ALGORITHM by M. A. Nielsen and C. M. Dawson

Let's break down the key points.

  1. $\mathcal{G}$ is the instruction set, and it is assumed that all $g \in \mathcal{G}$ are in $SU(d)$ (see the referenced paper).
  2. There exists a finite sequence $S$ of gates from $\mathcal{G}$ of length $O(\log^c(1/\epsilon))$.

Now, let's carefully think about the points above. Do we at any point see that we can approximate a unitary matrix in $SU(d)$ in terms of any given universal gate set? The answer is no. The theorem states that we can approximate a unitary matrix in $SU(d)$ in terms of gates from $\mathcal{G} \subset SU(d)$, and it takes $O(\log^c{1/\epsilon})$ of such gates. This means the sequence of approximating gates must be comprised of $d \times d$ unitaries in $SU(d)$.

I also want to point out that $\mathcal{G}$ is not required to be a universal gate set! This might sound surprising. But again, read the theorem carefully; it never states that $\mathcal{G}$ is a universal gate set. Let me expand on this below.

For example, let our gate set be $\mathcal{G}=\{X, Y, Z , H, T\}$, then SK does not tell us and can't be used for approximating a $d \times d$ unitary $U$ with the sequences from $\mathcal{G}$. However, it doesn't mean we can't do that. We first need to decompose a $d \times d$ unitary $U$ into a sequence of CNOTs and arbitrary one-qubit gates. The decomposition is exact; no approximations are made. Only then we run SK to approximate the single-qubit gates with sequences from $\mathcal{G}$. The final approximating circuit will be comprised of gates from $\mathcal{G}$ and CNOTs. So, if we wanted to talk about universal gate sets, it would be $\mathcal{G} + CNOT$, which is essentially Clifford + T in its colloquial meaning. However, our $\mathcal{G}$ is clearly not a universal gate set on its own, yet we use it to get a circuit comprising single- and two-qubit Clifford gates and one non-Clifford single-qubit T gate.

One also must realize why the word "instruction" is used in the theorem. This word emphasizes that the primary purpose of the SK algorithm is to break down a unitary matrix into instructions that a quantum computer can actually execute. This is pretty much the main purpose of the algorithm. It is an important result that essentially tells us that quantum computers with limited instruction sets can run any unitary operations up to some accuracy.

  • $\begingroup$ I understand that you are talking about a more generalized version (which is also what the original SK algorithm states), i.e. approximating any $d\times d$ unitary matrix, and the universal gate set is a special case. I believe I'm talking about a different problem, i.e., is the length of the sequence $S$ independent of $d=2^n$? As said in the original question, if the answer is Yes it looks like some currently popular algorithms are unnecessary, while if the answer is no I don't find any place that $d$ appears in the proof. $\endgroup$
    – SUSY
    Commented Apr 15 at 21:10
  • $\begingroup$ As I stated in my answer the length of a sequence that approximates U is log of the inverse of the error. The gates in that sequence of the same dimension as U. So why the dimension should matter when using SK? Don't let your confusion make false statements about necessity of SK. The SK theorem is widely regarded as one of the important results in the theory of QC. $\endgroup$
    – MonteNero
    Commented Apr 15 at 22:00

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.