El modelo de circuito cuántico de caja negra

Cuando comentábamos los algoritmos cuánticos y su estructura necesaria, veíamos que el caso ideal es que un algoritmo cuántico tenga un ventaja exponencial o, en el peor de los casos, cuadrática respecto al algoritmo clásico. Si hay una ventaja exponencial, el algoritmo cuántico es capaz de resolver el problema en un cantidad de recursos polinómicos mientras el clásico necesita una cantidad que crece exponencialmente con el tamaño de la entrada n.

¿Cuál es el tipo de recurso que queremos minimizar? Un posible caso es el número de puertas de uno o dos qubits que usamos en el circuito. El caso ideal es resolver un problema con un número de puertas que crece de manera polinómica con el tamaño de la entrada (e.g. 4n).

Sin embargo, en teoría de complejidad clásica y cuántica es muy complicado probar limites inferiores a la cantidad de puertas necesarias para resolver un problema. Cuando se resuelve un problema con un número determinado de puertas, e.g un número exponencial, es casi imposible probar que no existe un circuito con un número polinómico de puertas que lo pueda resolver.

Esto nos lleva a usar otro tipo de recurso para estudiar la complejidad de un circuito cuántico. Es el modelo de complejidad de caja negra. El recurso a minimizar es el número de consultas o queries a una caja negra que computa una función f.

Este modelo, que se ve en la figura siguiente, se tiene que implementar con una puerta o matriz que sea unitaria. Por eso no se aplica directamente la función a la entrada y se aplica el elemento x también a la entrada.

La función hay que implementarla para que dada una entrada te de una salida y la única información que el circuito puede obtener de la función es consultándola con una entrada, que puede ser una superposición de estados.

Este modelo nos permite probar límites inferiores y superiores al número de consultas necesarias que debe hacer un algoritmo o circuito para resolver un problema.

Por ejemplo, en el algoritmo de Grover, clásicamente tendríamos que llamar a la función para todo el dominio de la entrada {0,1,…,N-1}, mientras que el algoritmo cuántico solo debe hacer √N consultas a la entrada.

Por lo tanto, el modelo de caja negra, que evalúa como crece el número de consultas a la función con el tamaño de la entrada, es un modelo muy útil en computación y algoritmos cuánticos.