El teorema de Solovay-Kitaev nos permite definir una clase de complejidad BQP (y otras clases) para estudiar lo que se puede hacer con el cálculo cuántico con buenas propiedades y en términos de solo unas pocas puertas.
Aquí está el trasfondo: cualquier cálculo cuántico puede considerarse como una transformación unitaria en qubits. (De la misma manera que un cálculo clásico puede considerarse como una función arbitraria de entradas a salidas). Sin embargo, necesitamos una forma de hablar sobre la eficacia con la que se puede realizar un cálculo cuántico.
Para hacer esto, queremos hablar construyendo una transformación unitaria cuántica a partir de puertas cuánticas. Un conjunto de puertas cuánticas es universal si se pueden combinar para aproximar cualquier transformación unitaria. Uno de estos conjuntos universales es {CCNOT, Hadamard}.
- ¿La computación cuántica facilitará la biología computacional?
- ¿Cuál es el significado físico de la trama de 2 convoluciones?
- ¿Cuáles son algunos recursos de mecánica cuántica que enfatizan el uso efectivo de las computadoras?
- ¿Cuáles son buenos temas sobre computación cuántica?
- ¿Qué hubiera pasado si Einstein fuera un programador o un informático en lugar de la física?
(Un ejemplo más familiar de universalidad podría ser el conjunto {AND, NOT}, que es universal para la computación clásica; es decir, cualquier función clásica se puede hacer componiendo compuertas AND y NOT).
Como solemos hacer en la teoría de la complejidad, nuestra línea de base para que algo sea “eficiente”. Entonces, digamos que BQP es el conjunto de problemas que se pueden resolver mediante una operación unitaria que se puede aproximar mediante un número polinómico de puertas.
Lo que dice el teorema de Solovay-Kitaev es básicamente que podemos amplificar estas aproximaciones. En particular, dice que el número de puertas necesarias para aproximar un unitario dado dentro de [math] \ varepsilon [/ math] escalas con [math] \ log ^ 2 (1 / \ varepsilon) [/ math]. Esto permite una “composición” adecuada de los cálculos cuánticos, y nos permite considerar las “subrutinas” de la computación cuántica. (La forma del teórico de la complejidad de decir esto sería que [math] \ mathsf {BQP} ^ \ mathsf {BQP} = \ mathsf {BQP} [/ math].) El problema es que si tenemos un montón de buenas aproximaciones a transformaciones unitarias, podríamos obtener una aproximación horrible cuando las combinamos todas juntas. Pero Solovay-Kitaev nos permite tomar esas buenas aproximaciones y, sin demasiadas puertas, obtener aproximaciones increíbles . Combinarlos dará una buena aproximación a lo que queramos.
Otra implicación importante de Solovay-Kitaev es que no importa qué conjunto universal de puertas elijas, ¡todos los conjuntos de puertas universales darán la misma clase! Esto significa que si nos limitamos a {CCNOT, Hadamard}, por ejemplo, no tenemos que preocuparnos de que nos estemos perdiendo ningún cálculo cuántico potencialmente eficiente. Esto también tendría una gran implicación práctica si la computación cuántica universal con el modelo de compuerta alguna vez se convierta en una realidad y realmente necesitemos fabricar compuertas.
También tenga en cuenta que EQP (el equivalente de BQP sin permitir aproximaciones) no tiene esta bondad, y su definición básicamente requiere que especifique qué conjunto universal está utilizando junto con sus soluciones. Es por eso que generalmente solo hablamos de BQP y solo requerimos que nuestros cálculos cuánticos sean correctos con una probabilidad (por ejemplo) mayor que 2/3.
