Generators for Certain Alternating Groups with Applications to Cryptography

The proof of universality of G1 is a simple reduction to a set of gates shown universal by Kitaev.

“Our proof of universality of G 1 is a simple reduction to a set of gates, which was shown to be universal by Kitaev[39].”

Kitaev and Solovay showed that universality of a set G guarantees that any quantum computation can be approximated by a circuit using G with only polylogarithmic cost.

“Kitaev[39] and Solovay[66] showed, by a beautiful proof which uses Lie algebra and Lie groups, that universality of a set G guarantees that any quantum computation can be approximated by a circuit which uses G with only polylogarithmic cost.”

The threshold result was independently described by Knill, Laflamme and Zurek, and by Kitaev.

“The threshold result was independently described also by Knill, Laflamme and Zurek[42], and by Kitaev[40, 39].”

Theorem 6 (Kitaev, Solovay): For a universal set of gates G over U(m), there exists a polynomial p_m such that any element of U(m) can be approximated up to ε by a word from G not longer than p_m(log(1/ε)), and this word can be found efficiently by a classical Turing machine.

“Theorem 6. Kitaev, Solovay,: Consider a universal set of gates G over U ( m ) , for some integer m . Then there exists a polynomial p m such that any element of U ( m ) can be approximated up to ǫ by a word from G which is not longer than p m ( log (1 /ǫ )) , and this word can be found efficiently (in time which is p m ( log (1 /ǫ )) ) by a classical Turing machine.”