Un equipo de investigadores ha logrado rebajar la complejidad cuántica del problema de colisión en grafos, un reto clásico de la informática cuántica en el que, dado un grafo conocido de n vértices y acceso por consulta a los bits que marcan los vértices, hay que decidir si existe una arista con ambos extremos marcados. El trabajo refuta la conjetura de que cualquier algoritmo cuántico con error acotado necesitaría Ω(n²ᐟ³) consultas, y presenta en su lugar un algoritmo que resuelve el problema con Õ(n⁹²ᐟ¹³⁹) consultas.

El avance se consolida después con una versión refinada del método que reduce aún más el número de consultas hasta Õ(n¹¹ᐟ¹⁷). Además, los autores extienden el resultado a todas las funciones booleanas (parciales) de salida con complejidad de certificado positivo como máximo 2 y alfabeto de tamaño q, obteniendo una cota de Õ((nq)¹¹ᐟ¹⁷). Esto contrasta con la cota inferior conocida de Ω(n²ᐟ³) para problemas de este tipo cuando el alfabeto es grande, lo que sugiere que la barrera previa no era alcanzable en el régimen cuántico.

El trabajo se complementa con una nueva cota inferior cuántica de Ω(√(n log n)) consultas para el problema de colisión en grafos. Este límite es notable porque supera la barrera de la complejidad de certificado positivo, O(√n), que el método del adversario positivo no puede rebasar por construcción. La cota inferior, por tanto, sitúa el problema en una zona intermedia entre lo que prometían las técnicas estándar y lo que permiten los algoritmos aquí propuestos.

Los resultados abren varias líneas de trabajo. Queda por ver si la cota superior Õ(n¹¹ᐟ¹⁷) puede acercarse aún más a la nueva cota inferior, o si existe una barrera intrínseca que impida cerrar la brecha. También queda explorar hasta qué punto las técnicas desarrolladas pueden aplicarse a otros problemas de consulta con certificados pequeños, un terreno donde las herramientas cuánticas estándar han encontrado hasta ahora límites claros.