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. It has been a longstanding open question if efficient algorithmic compilation is possible without this condition. In this work, we provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality, answering this problem in the affirmative, and providing an efficient compilation algorithm in the absence of inverses for both the special unitary, and the special linear groups in arbitrary dimension. The algorithm works by showing that approximate gate implementations of the generalized Pauli group can self-correct their errors. The contents of the talk are based on Efficient Universal Quantum Compilation: An Inverse-free Solovay Kitaev Algorithm.
Join the seminar on Zoom
Meeting link: IQC-QuICS Math and Computer Science Seminar
Add event to calendar
Apple Google Office 365 Outlook Outlook.com Yahoo
This virtual seminar is jointly sponsored by the Institute for Quantum Computing and the Joint Center for Quantum Information and Computer Science.
If you are interested in presenting at a future seminar, please email either Daniel Grier (daniel.grier@uwaterloo.ca) or Adam Bene Watts (adam.benewatts1@uwaterloo.ca).