Abstract:The Solovay-Kitaev theorem is a foundational result in quantum computing. It is crucial for quantum fault tolerance, it underpins quantum circuit compilation and thus shapes quantum algorithms, and it establishes gate-set independence for quantum complexity classes. The theorem says: Given a target element g in SU(d) and an arbitrary universal gate set A, there is a word w in A that ε-approximates g that has length polylog(1/ε); moreover, w can be computed in classical polynomial time. Given the general form of this result, the remaining question is to bound the polylog exponent α. Not long after the Solovay-Kitaev theorem was first proven, Kitaev, Shen, and Vyalyi established the exponent α = 3+δ for any δ > 0. For certain special gate sets such as Clifford+T, there are number-theoretic algorithms with α = 1, but the exponent for general gate sets remains in play. In this talk, I will discuss a new algorithm for general gate sets with polylog exponent α = log(2)/log(ϕ)+δ = 1.44042...+δ, where ϕ is the golden ratio.
Remote guests are invited via Zoom:Zoom link:
https://us06web.zoom.us/j/84248911743?pwd=ZsiAOQbRgYCm5IFsArOnb18Fj5IsZh.1Meeting ID: 842 4891 1743
Passcode: 394021
