7
$\begingroup$

The Solvay Kitaev algorithm was discovered long before the Group Leaders Optimization algorithm and it has some nice theoretical properties. As far as I understand, both have exactly the same goals: given a finite dimensional unitary operator, they decompose the operator into basic quantum gates. I couldn't find any theoretical results about the time complexity or convergence time or error bounds for the GLOA as such. Does the latter (GLOA) have any practical advantage over the former at all, in terms of convergence time or anything?

P.S: For a detailed description of the GLOA, see: Understanding the Group Leaders Optimization Algorithm

$\endgroup$
  • $\begingroup$ I don’t know anything about GLOA, but nowadays there are better algorithms than Solovay-Kitaev $\endgroup$ – DaftWullie Oct 22 '18 at 5:46
  • $\begingroup$ As a side question, do you have any link to resources about these algorithms? Or at least their name? @DaftWullie $\endgroup$ – Adrien Suau Oct 22 '18 at 6:53
  • $\begingroup$ @Nelimee Sure, I just had to be on a decent computer to find the link I had. Try this one: arxiv.org/abs/1212.6253 $\endgroup$ – DaftWullie Oct 22 '18 at 8:50
  • 2
    $\begingroup$ Thanks! But even if the algorithm is better in terms of complexity, it does not replace the SK algorithm. I though you were speaking of an algorithm as general as SK. $\endgroup$ – Adrien Suau Oct 22 '18 at 9:32
  • $\begingroup$ @Nelimee the Ross-Selinger algorithm is not just better in terms of complexity than the Solvay-Kitaev algorithm, it has been implemented in practice and is very fast (were talking seconds to achieve errors in the $10^{-3}$ range and is the standard tool for doing approximate circuit synthesis on Clifford+T gate sets. In what way does it not replace the SK algorithm? $\endgroup$ – Condo Jul 7 '20 at 19:01
1
$\begingroup$

It sounds like GLOA algorithms are a type of genetic algorithm. Genetic algorithms are heuristic algorithms which often do not have any specified time complexity nor accuracy (which is likely why you couldn't find anything). So why do we even use these algorithms you might ask? The answer is that often they work and if they do so in a reasonable amount of time, then why not use them. Often they are easy to program and can be applied to problems where one might have no idea how to find an optimal solution.

On the other hand the SK algorithm is an exact or deterministic algorithm with polynomial complexity in $O(\log(1/\epsilon))$ where $\epsilon$ is the desired accuracy of the quantum gate. The SK algorithm (unlike heuristic algorithms) takes advantage of the fact that quantum gates are elements of the unitary group $U(d)$, which is a Lie group and therefore a smooth manifold in which one can make conclusions about the geometry and distance between points.

GLOA's may have advantages when engineering quantum circuits as it may be possible to incorporate other desired aspects of circuit design into the optimization. However, they will not be as efficient nor optimal as the SK algorithm (or the more powerful number theoretic approximation algorithms for $U(d)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.