log in  |  register  |  feedback?  |  help  |  web accessibility
Universal efficient compilation: Solovay-Kitaev without inverses
Tudor Giurgica-Tiron - Stanford University
Virtual Via Zoom: https://uwaterloo.zoom.us/j/93303967968?pwd=bm9VWjkwRGZTUjVOTkptekhleHdsZz09
Thursday, April 21, 2022, 2:00-3:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

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. Arxiv: 2112.02040.

This talk is organized by Andrea F. Svejda