Hay un resultado matemático que es bastante importante para el cálculo cuántico práctico. De hecho, sin ella nos resultaría imposible implementar computadoras cuánticas tolerantes a fallas “completas” (en el sentido de que podemos implementar cualquier compuerta cuántica) mientras mantenemos la velocidad que los algoritmos cuánticos nos prometen. Se llama el teorema de Solovay-Kitaev .
El problema es fácil de entender. Tienes un montón de puertas que podrías usar en un algoritmo cuántico dado. El algoritmo (que es una colección secuencial de puertas lógicas con estados de entrada específicos correspondientes a qubits) debe “compilarse” en una colección de puertas tolerantes a fallas que, en cierto sentido, actúen como un “conjunto de instrucciones” para una computadora cuántica . Además, esta compilación debe ser eficiente ; si no, perdemos completamente la mejora de la velocidad de nuestros algoritmos cuánticos.
Resulta que puede hacer esto compilando aproximando los circuitos originales con secuencias de compuertas desde el conjunto de instrucciones a una precisión arbitraria en tiempo poligarrítmico ([math] \ mathcal {O} (\ log ^ {2.71} (1 / \ epsilon) [/ math] para ser exactos, donde [math] \ epsilon [/ math] es la precisión deseada. La complejidad del espacio también es poliligarítmica, lo que significa que el número de compuertas en el conjunto de instrucciones utilizado para la aproximación crece lentamente (el real la figura es [math] \ mathcal {O} (\ log ^ {3.97} (1 / \ epsilon) [/ math]). Es importante tener en cuenta que ambos resultados son igualmente impresionantes e importantes.
- ¿Qué hace que las computadoras cuánticas sean tan rápidas en algunos problemas, pero fantásticamente lentas en otros?
- ¿Es posible que no haya 'nada' que ni siquiera incluya campos cuánticos?
- ¿Cuál es la diferencia entre las computadoras cuánticas y el autómata finito no determinista?
- ¿Qué es un número cuántico?
- ¿Cuánto han cambiado tu vida las computadoras?
Desafortunadamente, nunca pude encontrar la referencia original (probablemente esté escrita en ruso, desde los días anteriores a la llegada de Kitaev a Caltech), pero aquí hay un documento general del algoritmo y algo de historia de Dawson y Nielsen: [quant- ph / 0505030] El algoritmo Solovay-Kitaev. También puede encontrar una explicación en el libro de Nielsen y Chuang sobre computación cuántica e información.
Otro es el enlace Holevo , que establece que no puede extraer más bits de un cálculo que la cantidad de qubits que tiene. Es un poco extraño porque el espacio de cálculo es dos veces mayor que la cantidad de qubits, pero es la razón por la que tenemos que usar un montón de trucos para obtener respuestas significativas.
Agregaré más pronto.
