Microsoft resuelve dos problemas de la computación cuántica presentes durante 20 años

La computación cuántica se ha convertido en uno de los proyectos más importantes y más prometedores del sector científico-tecnológico. No hay duda, abre un mundo de posibilidades, pero también plantea una serie de dificultades que, por sus propias particularidades, la convierten en un enorme desafío incluso para gigantes del calibre de Google y Microsoft.

Como sabrán muchos de nuestros lectores la computación cuántica parte de los principios del entrelazamiento cuántico y la superposición para lograr un rendimiento computacional muy superior al que ofrecen los ordenadores tradicionales basados en un esquema de bits. El algoritmo de Shor es un ejemplo común de esto, ya que puede producir aceleraciones exponenciales en una computadora cuántica escalada. Otro ejemplo que se cita con frecuencia es el algoritmo de Grover, que parte de una aceleración polinómica.

Microsoft es una de las compañías que más recursos está invirtiendo en la computación cuántica. Gracias a eso ha logrado avances interesantes, pero sin duda uno de los más importantes ha sido el que ha conseguido recientemente un equipo de investigadores dirigido por Robin Kothari, ya que resuelve dos problemas que han estado presentes en la computación cuántica durante 20 años.

Por un lado el equipo de Kothari profundizó sobre las implicaciones de un avance registrado en 2019 por Hao Huang en relación a la conjetura de sensibilidad, y demostró que el mejor método de aceleración cuántica para problemas no estructurados es el modelo cuártico (T frente a T ^ 4). Con esto han resuelto una cuestión que llevaba, como dijimos, 20 años vigente.

Por otro lado este equipo también descubrió que la misma técnica puede ser utilizada para resolver una conjetura antigua sobre aceleraciones cuánticas en problemas de gráficos que implican analizar conjuntos masivos de datos no estructurados, y encontrar conexiones y patrones subyacentes.

En 1999, Buhrman et al. mostró que cualquier algoritmo cuántico debe realizar consultas ? (?n) para decidir una propiedad de gráfico monótono. La respuesta conjeturada fue una complejidad lineal de tiempo con el peor de los casos siendo ? (n), que podría lograrse utilizando el algoritmo de Grover. Pues bien, el equipo de Kothari ha logrado demostrar de forma efectiva esta conjetura, todo un logro ya que la contraparte clásica de esta todavía no se ha demostrado.

Todo un logro por parte del equipo de Kothari. Podéis encontrar más información a través de este enlace.