Teorema de Solovay-Kitaev

---

En información y computación cuánticas, el teorema de Solovay-Kitaev dice, aproximadamente, que si un conjunto de puertas cuánticas de un solo qubit genera un subconjunto denso de SU(2) , entonces se garantiza que ese conjunto llenará SU(2) rápidamente, lo que significa que cualquier La puerta deseada se puede aproximar mediante una secuencia bastante corta de puertas del grupo electrógeno. Robert M. Solovay anunció inicialmente el resultado en una lista de correo electrónico en 1995, y Alexei Kitaev , de forma independiente, dio un resumen de su prueba en 1997. ^[1] Solovay también dio una charla sobre su resultado en MSRI en 2000, pero fue interrumpida por un incendio. alarma. ^[2] Christopher M. Dawson y Michael Nielsen llaman al teorema uno de los resultados fundamentales más importantes en el campo de la computación cuántica . ^[3]

Una consecuencia de este teorema es que un circuito cuántico de puertas de qubit constante puede aproximarse al error (en la norma del operador ) mediante un circuito cuántico de puertas de un conjunto de puertas universal finito deseado . ^[4] En comparación, el simple hecho de saber que un conjunto de puertas es universal solo implica que las puertas de qubit constante pueden aproximarse mediante un circuito finito del conjunto de puertas, sin límite en su longitud. Entonces, el teorema de Solovay-Kitaev muestra que esta aproximación puede ser sorprendentemente eficiente , lo que justifica que las computadoras cuánticas solo necesitan implementar un número finito de puertas para obtener todo el poder de la computación cuántica.${\ estilo de visualización m}$${\ estilo de visualización \ varepsilon}$${\displaystyle O(m\log ^{c}(m/\varepsilon))}$

Sea un conjunto finito de elementos en SU(2) que contenga sus propios inversos (lo que implica ) y tal que el grupo que generan sea denso en SU(2) . Considere algunos . Entonces hay una constante tal que para cualquier , hay una secuencia de puertas de longitud tal que . Es decir, se aproxima al error de la norma del operador. ^[3]${\displaystyle {\mathcal {G}}}$${\displaystyle g\in {\mathcal {G}}}$${\displaystyle g^{-1}\in {\mathcal {G}}}$${\displaystyle \langle {\mathcal {G}}\rangle }$${\ estilo de visualización \ varepsilon > 0}$${\ estilo de visualización c}$${\displaystyle U\en \mathrm {SU} (2)}$${\ estilo de visualización S}$${\displaystyle {\mathcal {G}}}$${\displaystyle O(\log ^{c}(1/\varepsilon))}$${\displaystyle \|SU\|\leq\varepsilon}$${\ estilo de visualización S}$${\ estilo de visualización U}$

---