Breaking the cubic barrier in the Solovay-Kitaev algorithm
Greg Kuperberg (UC Davis)
我们改进了Solovay-Kitaev定理和算法,用于在qudit上作用的一般有限,反向闭合的生成集。 该算法的先前版本有效地找到一个长度 O(n^3+δ) 的单词,以近似任意的目标门到 n 位的精度。 使用两个新想法,每个想法分别减少指数,我们对单词长度的新绑定是O(n^1.44042...+δ)。 我们的结果更普遍地适用于任何密集生成任何连接的、半简单的实列组的有限集,在非紧凑的情况下有一个额外的长度,以到达远离身份的组元素。
We improve the Solovay–Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm efficiently find a word of length O(n^3+δ) to approximate an arbitrary target gate to n bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is O(n^1.44042…+δ). Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, w...