En información y computación cuántica, 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 esbozo de su prueba en 1997. [1] Christopher M. Dawson y Michael Nielsen llaman al teorema uno de los resultados fundamentales más importantes en el campo de Computación cuántica . [2]
Una consecuencia de este teorema es que un circuito cuántico de Las puertas de qubit constantes se pueden aproximar a error (en la norma del operador ) por un circuito cuántico depuertas de un conjunto de puertas universal finito deseado . [3] En comparación, el simple hecho de saber que un conjunto de puertas es universal solo implica que las puertas de qubit constantes pueden aproximarse mediante un circuito finito a partir del conjunto de puertas, sin límite en su longitud. Entonces, el teorema de Solovay-Kitaev muestra que esta aproximación se puede hacer sorprendentemente eficiente , lo que justifica que las computadoras cuánticas solo necesitan implementar un número finito de puertas para obtener la potencia total de la computación cuántica.
Declaración
Dejar ser un conjunto finito de elementos en SU (2) que contiene sus propios inversos (por lo que implica ) y tal que el grupo que generan es denso en SU (2) . Considere algunos. Entonces hay una constante tal que para cualquier , hay una secuencia de puertas de de longitud tal que . Es decir, aproxima al error de la norma del operador. [2]
Límites cuantitativos
El constante se puede hacer para ser para cualquier fijo . [4] Sin embargo, existen conjuntos de puertas particulares para los que podemos tomar, lo que hace que la longitud de la secuencia de la puerta se ajuste a un factor constante. [5]
Prueba de idea
La demostración del teorema de Solovay-Kitaev procede mediante la construcción recursiva de una secuencia de puertas que da cada vez más buenas aproximaciones a . [2] Supongamos que tenemos una aproximación tal que . Nuestro objetivo es encontrar una secuencia de puertas que se aproxime a error, por . Concatenando esta secuencia de puertas con, obtenemos una secuencia de puertas tal que .
La idea clave es que los conmutadores de elementos cercanos a la identidad pueden aproximarse "mejor de lo esperado". Especificamente para satisfactorio y y aproximaciones satisfactorio y , luego
donde la notación O grande oculta términos de orden superior. Uno puede vincular ingenuamente la expresión anterior a ser, pero la estructura del conmutador de grupo crea una cancelación sustancial de errores.
Usamos esta observación reescribiendo la expresión que deseamos aproximar como un conmutador de grupo . Esto se puede hacer de manera que tanto y están cerca de la identidad (ya que ). Entonces, si calculamos recursivamente secuencias de puertas que se aproximan y a error, obtenemos una secuencia de puerta que se aproxima a la mejor precisión deseada con . Podemos obtener una aproximación del caso base con constante mediante el cálculo de fuerza bruta de todas las secuencias de puertas suficientemente largas.
Referencias
- ↑ Kitaev, A Yu (31 de diciembre de 1997). "Cálculos cuánticos: algoritmos y corrección de errores" . Encuestas matemáticas rusas . 52 (6): 1191-1249. doi : 10.1070 / rm1997v052n06abeh002155 . ISSN 0036-0279 .
- ^ a b c Dawson, Christopher M .; Nielsen, Michael (1 de enero de 2006). "El algoritmo Solovay-Kitaev" . Computación e información cuántica . 6 : 81–95. arXiv : quant-ph / 0505030 . doi : 10.26421 / QIC6.1-6 .
- ^ Nielsen, Michael A .; Chuang, Isaac L. (2010). El teorema de Solovay-Kitaev . Computación cuántica e información cuántica: Edición del décimo aniversario . págs. 617–624. doi : 10.1017 / cbo9780511976667.019 . ISBN 9780511976667. Consultado el 20 de mayo de 2020 .
- ^ Kitaev, Alexei Yu .; Shen, Alexander; Vyalyi, Mikhail N. (2002). Computación clásica y cuántica . Providence, Rhode Island: Sociedad Matemática Estadounidense. ISBN 0-8218-2161-X. OCLC 48965167 .
- ^ Harrow, Aram W .; Recht, Benjamin; Chuang, Isaac L. (20 de agosto de 2002). "Aproximaciones discretas eficientes de puertas cuánticas" . Revista de Física Matemática . 43 (9): 4445–4451. arXiv : quant-ph / 0111031 . doi : 10.1063 / 1.1495899 . ISSN 0022-2488 . S2CID 119043335 .