IQC-QuICS Math and Computer Science Seminar
Universal efficient compilation: Solovay-Kitaev without inverses
Tudor Giurgica-Tiron, Stanford University
The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed.