Teorema de Solováy-Kitáev

Teorema de la teoría de la información cuántica

En información y computación cuántica, el teorema de Solovay-Kitaev dice que si un conjunto de puertas cuánticas de un solo qubit genera un subgrupo denso de SU(2) , entonces ese conjunto se puede utilizar para aproximar cualquier puerta cuántica deseada con una secuencia corta de puertas. que también se puede encontrar de manera eficiente. Este teorema se considera uno de los resultados más significativos en el campo de la computación cuántica y fue anunciado por primera vez por Robert M. Solovay en 1995 y probado de forma independiente por Alexei Kitaev en 1997. ^{[1] [2]} Michael Nielsen y Christopher M. Dawson han destacó su importancia en el campo. ^[3]

Una consecuencia de este teorema es que un circuito cuántico de puertas de qubit constantes puede aproximarse al error (en 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 constantes 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 hacerse sorprendentemente eficiente , justificando así 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. ${\displaystyle m}$ ${\displaystyle \varepsilon }$ ${\displaystyle O(m\log ^{c}(m/\varepsilon ))}$

Declaración

Sea un conjunto finito de elementos en SU(2) que contiene sus propios inversos (así 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 longitud tal que . Es decir, se aproxima al error normativo del operador. ^[3] Además, existe un algoritmo eficiente para encontrar dicha secuencia. De manera más general, el teorema también se cumple en SU(d) para cualquier d fijo. ${\displaystyle {\mathcal {G}}}$ ${\displaystyle g\in {\mathcal {G}}}$ ${\displaystyle g^{-1}\in {\mathcal {G}}}$ ${\displaystyle \langle {\mathcal {G}}\rangle }$ ${\displaystyle \varepsilon >0}$ ${\displaystyle c}$ ${\displaystyle U\in \mathrm {SU} (2)}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle O(\log ^{c}(1/\varepsilon ))}$ ${\displaystyle \|S-U\|\leq \varepsilon }$ ${\displaystyle S}$ ${\displaystyle U}$

Este teorema también se cumple sin el supuesto de que contiene sus propios inversos, aunque actualmente con un valor mayor de que también aumenta con la dimensión . ^[5] ${\displaystyle {\mathcal {G}}}$ ${\displaystyle c}$ ${\displaystyle d}$

Límites cuantitativos

Se puede hacer que la constante sea para cualquier fijo . ^[6] Sin embargo, existen conjuntos de puertas particulares para los cuales podemos tomar , lo que hace que la longitud de la secuencia de puertas sea óptima hasta un factor constante. ^[7] ${\displaystyle c}$ ${\displaystyle \log _{(1+{\sqrt {5}})/2}2+\delta =1.44042\ldots +\delta }$ ${\displaystyle \delta >0}$ ${\displaystyle c=1}$

idea de prueba

Cada prueba conocida del teorema completamente general de Solovay-Kitaev procede construyendo recursivamente una secuencia de puertas que proporciona aproximaciones cada vez mejores a . ^[3] Supongamos que tenemos una aproximación tal que . Nuestro objetivo es encontrar una secuencia de puertas que se aproxime al error, por . Al concatenar esta secuencia de puertas con , obtenemos una secuencia de puertas tal que . ${\displaystyle U\in \operatorname {SU} (2)}$ ${\displaystyle U_{n-1}\in \operatorname {SU} (2)}$ ${\displaystyle \|U-U_{n-1}\|\leq \varepsilon _{n-1}}$ ${\displaystyle UU_{n-1}^{-1}}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \varepsilon _{n}<\varepsilon _{n-1}}$ ${\displaystyle U_{n-1}}$ ${\displaystyle U_{n}}$ ${\displaystyle \|U-U_{n}\|\leq \varepsilon _{n}}$

La idea principal del argumento original de Solovay y Kitaev es que los conmutadores de elementos cercanos a la identidad pueden aproximarse "mejor de lo esperado". Específicamente, para satisfacer y y aproximaciones que satisfacen y , entonces ${\displaystyle V,W\in \operatorname {SU} (2)}$ ${\displaystyle \|V-I\|\leq \delta _{1}}$ ${\displaystyle \|W-I\|\leq \delta _{1}}$ ${\displaystyle {\tilde {V}},{\tilde {W}}\in \operatorname {SU} (2)}$ ${\displaystyle \|V-{\tilde {V}}\|\leq \delta _{2}}$ ${\displaystyle \|W-{\tilde {W}}\|\leq \delta _{2}}$

${\displaystyle \|VWV^{-1}W^{-1}-{\tilde {V}}{\tilde {W}}{\tilde {V}}^{-1}{\tilde {W}}^{-1}\|\leq O(\delta _{1}\delta _{2}),}$

donde la notación O grande oculta términos de orden superior. Se puede vincular ingenuamente la expresión anterior a , pero la estructura del conmutador de grupo crea una cancelación sustancial de errores. ${\displaystyle O(\delta _{2})}$

Podemos utilizar esta observación para aproximarnos como un conmutador de grupo . Esto se puede hacer de manera que ambos y estén cerca de la identidad (desde ). Entonces, si calculamos recursivamente secuencias de puertas que se aproximan a y hasta el error, obtenemos una secuencia de puertas que se aproxima a la mejor precisión deseada con . Podemos obtener una aproximación del caso base con constante con una búsqueda exhaustiva de secuencias de puertas de longitud limitada. ${\displaystyle UU_{n-1}^{-1}}$ ${\displaystyle V_{n-1}W_{n-1}V_{n-1}^{-1}W_{n-1}^{-1}}$ ${\displaystyle V_{n-1}}$ ${\displaystyle W_{n-1}}$ ${\displaystyle \|UU_{n-1}^{-1}-I\|\leq \varepsilon _{n-1}}$ ${\displaystyle V_{n-1}}$ ${\displaystyle W_{n-1}}$ ${\displaystyle \varepsilon _{n-1}}$ ${\displaystyle UU_{n-1}^{-1}}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \varepsilon _{0}}$

Prueba del teorema de Solovay-Kitaev

Elijamos el valor inicial para que < para poder aplicar el lema de "reducción" iterado. Además queremos <1 para asegurarnos de que disminuya a medida que aumentamos . Además, también nos aseguramos de que sea lo suficientemente pequeño como para que < . ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \varepsilon '}$ ${\displaystyle s\varepsilon _{0}}$ ${\displaystyle \varepsilon _{k}}$ ${\displaystyle k}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \varepsilon _{k}^{2}}$ ${\displaystyle \varepsilon _{k+1}}$

Dado que es denso en SU(2), podemos elegir lo suficientemente grande ^[8] para que sea un -net para SU(2) (y por lo tanto también para S) sin importar cuán pequeño sea. Por lo tanto, dado cualquiera , podemos elegir tal que − < . Sea Δ := la “diferencia” de y . Entonces ${\displaystyle <G>}$ ${\displaystyle l_{0}}$ ${\displaystyle G^{l_{0}}}$ ${\displaystyle \varepsilon _{0}^{2}}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle U\in \operatorname {SU} (2)}$ ${\displaystyle U_{0}\in \operatorname {G^{l_{0}}} }$ ${\displaystyle ||U}$ ${\displaystyle U_{0}||}$ ${\displaystyle \varepsilon _{0}^{2}}$ ${\displaystyle UU_{0}^{+}}$ ${\displaystyle U}$ ${\displaystyle U_{0}}$

${\displaystyle \|\Delta _{1}-I\|=\|(U-U_{0})U_{0}^{+}\|=\|U-U_{0}\|<\varepsilon _{0}^{2}<\varepsilon _{1}.}$

Por eso, . Al invocar el lema de "reducción" iterado con , existe tal que ${\displaystyle \Delta _{1}\in \operatorname {S_{\varepsilon _{1}}} }$ ${\displaystyle k=1}$ ${\displaystyle U_{1}\in \operatorname {G^{l_{1}}} }$ ${\displaystyle \|\Delta _{1}-U_{1}\|=\|UU_{0}^{+}-U_{1}\|=\|U-U_{1}U_{0}\|<\varepsilon _{1}^{2}.}$

De manera similar, dejemos . Entonces ${\displaystyle \Delta _{2}:=\Delta _{1}U_{1}^{+}=UU_{0}^{+}U_{1}^{+}}$

${\displaystyle \|\Delta _{2}-I\|=\|(U-U_{1}U_{0})U_{0}^{+}U_{1}^{+}\|=\|U-U_{1}U_{0}\|<\varepsilon _{1}^{2}<\varepsilon _{2}.}$

Por lo tanto, podemos invocar el lema de "reducción" iterado (con este tiempo) para obtener tal que ${\displaystyle \Delta _{2}\in \operatorname {S_{\varepsilon _{2}}} }$ ${\displaystyle k=2}$ ${\displaystyle U_{2}\in \operatorname {G^{l_{2}}} }$ ${\displaystyle \|\Delta _{2}-U_{2}\|=\|UU_{0}^{+}U_{1}^{+}-U_{2}\|=\|U-U_{2}U_{1}U_{0}\|<\varepsilon _{2}^{2}.}$

Si continuamos de esta manera, después de k pasos obtenemos tal que ${\displaystyle U_{k}\in \operatorname {G^{l_{k}}} }$

${\displaystyle \|U-U_{k}U_{k-1}...U_{0}\|<\varepsilon _{k}^{2}.}$

Así, hemos obtenido una secuencia de

${\displaystyle L=\sum _{m=0}^{k}l_{m}=\sum _{m=0}^{k}5^{m}l_{0}={\frac {5^{k+1}-1}{4}}l_{0}<{\frac {5}{4}}5^{k}l_{0}}$

puertas que se aproximan a la precisión . Para determinar el valor de , establecemos y resolvemos para k: ${\displaystyle U}$ ${\displaystyle \varepsilon _{k}^{2}}$ ${\displaystyle k}$ ${\displaystyle \varepsilon _{k}^{2}=((s\varepsilon _{0})^{(3/2)^{k}}/s)^{2}=\varepsilon }$

${\displaystyle ({\frac {3}{2}})^{k}={\frac {{\text{log}}(1/s^{2}\varepsilon )}{2{\text{log}}(1/s\varepsilon _{0})}}.}$

Ahora siempre podemos elegir un poco más pequeño para que el valor obtenido de sea un número entero. ^[9] Dejemos que . Entonces ${\displaystyle \varepsilon _{0}}$ ${\displaystyle k}$ ${\displaystyle c={\text{log}}5/{\text{log}}(3/2)\approx 3.97}$ ${\displaystyle 5^{k}=({\frac {3}{2}})^{kc}}$

${\displaystyle L<{\frac {5}{4}}5^{k}l_{0}={\frac {5}{4}}({\frac {3}{2}})^{kc}l_{0}={\frac {5}{4}}({\frac {{\text{log}}(1/s^{2}\varepsilon )}{2{\text{log}}(1/s\varepsilon _{0})}})^{c}l_{0}}$

Por lo tanto, para cualquiera existe una secuencia de puertas que se aproxima a la precisión . ${\displaystyle U\in \operatorname {SU} (2)}$ ${\displaystyle L=O({\text{log}}^{c}(1/\varepsilon ))}$ ${\displaystyle U}$ ${\displaystyle \varepsilon }$

Algoritmo Solovay-Kitaev para qubits

Aquí se han presentado las ideas principales que se utilizan en el algoritmo SK. El algoritmo SK puede expresarse en nueve líneas de pseudocódigo. Cada una de estas líneas se explica en detalle a continuación, pero se presenta aquí en su totalidad para referencia del lector y para enfatizar la simplicidad conceptual del algoritmo:

función Solovay-Kitaev(Puerta , profundidad ) ${\displaystyle U}$ ${\displaystyle n}$

si ( == 0) ${\displaystyle n}$

Regresar Aproximación Básica a ${\displaystyle U}$

demás

Conjunto = Solováy-Kitaev( , ) ${\displaystyle U_{n-1}}$ ${\displaystyle U}$ ${\displaystyle n-1}$

Establecer = GC-Descomponer ( ) ${\displaystyle V,W}$ ${\displaystyle UU_{n-1}^{+}}$

Conjunto = Solováy-Kitaev( ) ${\displaystyle V_{n-1}}$ ${\displaystyle V,n-1}$

Conjunto = Solováy-Kitaev( ) ${\displaystyle W_{n-1}}$ ${\displaystyle W,n-1}$

Devolver ${\displaystyle U_{n}=V_{n-1}W_{n-1}V_{n-1}^{+}W_{n-1}^{+}U_{n-1}}$ ;

Examinemos cada una de estas líneas en detalle. La primera línea:

función Solovay-Kitaev(Puerta , profundidad ) ${\displaystyle U}$ ${\displaystyle n}$

indica que el algoritmo es una función con dos entradas: una puerta cuántica arbitraria de un solo qubit, que deseamos aproximar, y un número entero no negativo, que controla la precisión de la aproximación. La función devuelve una secuencia de instrucciones que se aproxima a una precisión , donde es una función decreciente de , de modo que a medida que aumenta, la precisión mejora, con → 0 como → ∞. se describe en detalle a continuación. ${\displaystyle U}$ ${\displaystyle n}$ ${\displaystyle U}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle n}$ ${\displaystyle \varepsilon _{n}}$

La función Solovay-Kitaev es recursiva, de modo que para obtener una aproximación a , se llamará a sí misma para obtener aproximaciones a ciertos unitarios. La recursividad termina en , más allá del cual no se realizan más llamadas recursivas: ${\displaystyle \varepsilon _{n}}$ ${\displaystyle U}$ ${\displaystyle \varepsilon _{n-1}}$ ${\displaystyle n=0}$

si ( == 0) ${\displaystyle n}$

Regresar Aproximación Básica a ${\displaystyle U}$

Para implementar este paso se supone que se ha completado una etapa de preprocesamiento que permite encontrar una aproximación básica a arbitraria . Dado que es una constante, en principio esta etapa de preprocesamiento se puede lograr simplemente enumerando y almacenando una gran cantidad de secuencias de instrucciones desde , digamos hasta una longitud suficientemente grande (pero fija) , y luego proporcionando una rutina de búsqueda que, dada , devuelve el secuencia más cercana. ${\displaystyle \varepsilon _{0}}$ ${\displaystyle U\in \operatorname {SU} (2)}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle G}$ ${\displaystyle l_{0}}$ ${\displaystyle U}$

En niveles más altos de recursividad, para encontrar una aproximación a , se comienza por encontrar una aproximación a : ${\displaystyle \varepsilon _{n}}$ ${\displaystyle U}$ ${\displaystyle \varepsilon _{n-1}}$ ${\displaystyle U}$

demás

Conjunto = Solováy-Kitaev( , ) ${\displaystyle U_{n-1}}$ ${\displaystyle U}$ ${\displaystyle n-1}$

${\displaystyle U_{n-1}}$se utiliza como un paso hacia la búsqueda de una aproximación mejorada a . Al definir ≡ , los siguientes tres pasos del algoritmo tienen como objetivo encontrar una aproximación a , donde hay un nivel mejorado de precisión, es decir, . Encontrar dicha aproximación también nos permite obtener una aproximación a , simplemente concatenando la secuencia exacta de instrucciones para con la secuencia aproximada de . ${\displaystyle U}$ ${\displaystyle \Delta }$ ${\displaystyle UU_{n-1}^{+}}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \Delta }$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \varepsilon _{n}<\varepsilon _{n-1}}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle U}$ ${\displaystyle U_{n-1}}$ ${\displaystyle \varepsilon _{n}}$ ${\displaystyle \Delta }$

¿Cómo encontramos tal aproximación a ? Primero, observe que está a una distancia de la identidad. Esto se desprende de la definición de y del hecho de que se encuentra a una distancia de . ${\displaystyle \Delta }$ ${\displaystyle \varepsilon _{n-1}}$ ${\displaystyle \Delta }$ ${\displaystyle U_{n-1}}$ ${\displaystyle \varepsilon _{n-1}}$ ${\displaystyle U}$

En segundo lugar, descompóngalo como un conmutador de grupo de puertas unitarias y . Para cualquiera resulta que esto no es obvio y que siempre hay un conjunto infinito de opciones para y tal que . Para nuestros propósitos es importante que encontremos y tal que para alguna constante . A esta descomposición la llamamos conmutador de grupo equilibrado . ${\displaystyle \Delta }$ ${\displaystyle \Delta =VWV^{+}W^{+}}$ ${\displaystyle V}$ ${\displaystyle W}$ ${\displaystyle \Delta }$ ${\displaystyle V}$ ${\displaystyle W}$ ${\displaystyle \Delta =VWV^{+}W^{+}}$ ${\displaystyle V}$ ${\displaystyle W}$ ${\displaystyle d(I,V),d(I,W)<c_{gc}{\sqrt {\varepsilon _{n-1}}}}$ ${\displaystyle c_{gc}}$

Establecer = GC-Descomponer ( ) ${\displaystyle V,W}$ ${\displaystyle UU_{n-1}^{+}}$

Para implementaciones prácticas veremos a continuación que es útil tener el menor tamaño posible. ${\displaystyle c_{gc}}$

El siguiente paso es encontrar secuencias de instrucciones que sean aproximaciones a y : ${\displaystyle \varepsilon _{n-1}}$ ${\displaystyle V}$ ${\displaystyle W}$

Conjunto = Solováy-Kitaev( ) ${\displaystyle V_{n-1}}$ ${\displaystyle V,n-1}$

Conjunto = Solováy-Kitaev( ) ${\displaystyle W_{n-1}}$ ${\displaystyle W,n-1}$

El conmutador de grupo de y resulta ser una aproximación ≡ a , para alguna constante pequeña . Siempre que veamos eso , y este procedimiento, por lo tanto, proporciona una aproximación mejorada a y, por lo tanto, a . ${\displaystyle V_{n-1}}$ ${\displaystyle W_{n}}$ ${\displaystyle \varepsilon _{n-1}}$ ${\displaystyle c_{\text{approx}}\varepsilon _{n-1}^{3/2}}$ ${\displaystyle \Delta }$ ${\displaystyle c_{\text{approx}}}$ ${\displaystyle \varepsilon _{n-1}<1/c_{\text{approx}}^{2}}$ ${\displaystyle \varepsilon _{n}<\varepsilon _{n-1}}$ ${\displaystyle \Delta }$ ${\displaystyle U}$

La constante es importante ya que determina la precisión requerida de las aproximaciones iniciales. En particular, vemos que para que esta construcción garantice que debemos tener . ${\displaystyle c_{\text{approx}}}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \varepsilon _{0}>\varepsilon _{1}>...}$ ${\displaystyle \varepsilon _{0}<1/c_{\text{approx}}^{2}}$

El algoritmo concluye devolviendo las secuencias que se aproximan al conmutador de grupo, así como : ${\displaystyle U_{n-1}}$

Devolver ${\displaystyle U_{n}=V_{n-1}W_{n-1}V_{n-1}^{+}W_{n-1}^{+}U_{n-1}}$ ;

En resumen, la función Solovay-Kitaev(U, n) devuelve una secuencia que proporciona una aproximación al unitario deseado . Los cinco componentes de esta secuencia se obtienen llamando a la función en el nivel ésimo de recursividad. ^[10] ${\displaystyle \varepsilon _{n}=c_{\text{approx}}\varepsilon _{n-1}^{3/2}}$ ${\displaystyle U}$ ${\displaystyle n-1}$

Referencias

1. 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. Código Bib : 1997RuMaS..52.1191K. doi :10.1070/rm1997v052n06abeh002155. ISSN  0036-0279. S2CID  250816585.
2. Kitaev, Alexei Yu.; Shen, Alejandro; 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.
3. Dawson, Christopher M.; Nielsen, Michael (1 de enero de 2006). "El algoritmo de Solovay-Kitaev". Información y computación cuánticas . 6 : 81–95. arXiv : quant-ph/0505030 . doi :10.26421/QIC6.1-6.
4. 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 .
5. Bouland, Adán; Giurgica-Tiron, Tudor (3 de diciembre de 2021), Compilación cuántica universal eficiente: un algoritmo de Solovay-Kitaev libre inverso , arXiv : 2112.02040
6. Kuperberg, Greg (22 de junio de 2023), "Rompiendo la barrera cúbica en el algoritmo de Solovay-Kitaev", arXiv : 2306.13158 [quant-ph]
7. Ross, Neil J.; Selinger, Pedro. "Aproximación óptima de rotaciones z de Clifford + T sin ancillas". Información y computación cuánticas . 16 (11–12): 901–953. arXiv : 1403.2975 . doi :10.26421/QIC16.11-12-1.
8. Kitaev, Yu. "Cálculos cuánticos: algoritmos y corrección de errores".
9. Nielsen, Chuang, MA, IL "Computación cuántica e información cuántica (Cambridge University Press, 2000), Apéndice 3, págs. 617 {624". {{cite web}}: Falta o está vacío |url=( ayuda )CS1 maint: multiple names: authors list (link)
10. CHRISTOPHER M. DAWSON, MICHAEL A. NIELSEN. "EL ALGORITMO DE SOLOVAY-KITAEV".