En el mundo de la información, proteger los datos de la corrupción es una cuestión de supervivencia. Ya sea enviando un mensaje a través de un canal de radio con ruido o almacenando un archivo en un disco duro, los ingenieros utilizan códigos de corrección de errores. Estos son estructuras matemáticas que añaden redundancia a los datos, lo que permite a un receptor detectar y corregir errores sin pedir una retransmisión. Durante décadas, los científicos han sabido que encontrar la versión más robusta de estos códigos es un rompecabezas increíblemente difícil. En el mundo clásico, donde los datos están hechos de bits simples que son cero o uno, se ha demostrado que calcular la fuerza exacta de un código es una tarea tan compleja que ningún algoritmo de computadora eficiente puede resolverla para todos los casos.

El reino cuántico, sin embargo, opera bajo reglas diferentes. En lugar de bits, las computadoras cuánticas utilizan qubits, que pueden existir en delicadas superposiciones de estados. Para proteger esta información frágil, los físicos utilizan códigos de corrección de errores cuánticos, que son mucho más intrincados que sus primos clásicos. Una medida clave de la fuerza de un código cuántico es su "distancia", un número que nos indica cuántos errores puede soportar el código antes de que la información se pierda. Si la distancia es pequeña, el código es frágil; si es grande, el código es robusto. Durante mucho tiempo, los investigadores creyeron que, si bien encontrar esta distancia era difícil, quizás no lo era tanto como la versión clásica. Algunos estudios recientes sugirieron que la dificultad podría estancarse en un cierto punto, creando una barrera donde el problema se vuelve más fácil de aproximar de lo que se pensaba anteriormente. Esta idea insinuaba que los códigos cuánticos podrían tener una simplicidad oculta de la que carecen los códigos clásicos.

Un nuevo estudio de Upendra Kapshikar, de la Universidad de Ottawa, desafía esta noción directamente. El investigador ha demostrado que la dificultad de aproximar la distancia de un código cuántico es tan severa como la versión clásica, llegando hasta los límites mismos de lo que las computadoras pueden hacer, siempre que se cumplan ciertas hipótesis fundamentales de complejidad. Al construir un puente específico entre problemas clásicos y cuánticos, Kapshikar demuestra que no hay un atajo para encontrar la fuerza de estos códigos cuánticos. El trabajo demuestra que intentar adivinar la distancia dentro de un margen de error razonable es una tarea que sigue siendo computacionalmente imposible para cualquier algoritmo eficiente, a menos que las hipótesis ampliamente aceptadas sobre la naturaleza de la computación colapsen. Esto cierra efectivamente la puerta a la idea de que los códigos cuánticos poseen una propiedad especial y más fácil de resolver.

Para entender la importancia de este resultado, primero hay que comprender la naturaleza del problema. En una computadora cuántica, los errores pueden filtrarse desde el entorno, cambiando el estado de un qubit o desplazando su fase. Un código cuántico está diseñado para detectar estos errores. La "distancia" del código es el número mínimo de qubits que deben verse afectados por un error antes de que el código no pueda detectarlo. Si un código tiene una distancia de diez, puede detectar cualquier error que afecte a nueve o menos qubits. El desafío para los científicos de la computación es que, dada la descripción de un código, calcular este número exacto es una pesadilla. En el mundo clásico, se demostró hace años que ni siquiera se puede acercar rápidamente a la respuesta correcta; el problema es "NP-duro", lo que significa que a medida que el código se hace más grande, el tiempo requerido para resolverlo crece explosivamente.

Para los códigos cuánticos, la situación parecía más turbia. Investigaciones anteriores habían logrado demostrar que el problema era difícil, pero solo hasta cierto punto. Esas pruebas anteriores podían mostrar que encontrar la distancia era difícil si se quería una respuesta dentro de una brecha que crecía con la raíz cuadrada del tamaño del código. Sin embargo, no podían demostrar que fuera difícil encontrar una respuesta dentro de una brecha que creciera linealmente con el tamaño. Imagine un código con mil qubits. Una brecha de raíz cuadrada podría permitir una respuesta con un error de treinta, mientras que una brecha lineal permitiría una respuesta con un error de cien. Los resultados previos dejaban abierta la posibilidad de que los códigos cuánticos pudieran ser fáciles de aproximar si se aceptaba un margen de error mayor. El trabajo de Kapshikar elimina esta incertidumbre.

El investigador logró esto construyendo un nuevo tipo de código llamado código "estabilizado por palabra de clave" (codeword-stabilized). Esta construcción actúa como un traductor, tomando un problema clásico difícil y convirtiéndolo en uno cuántico. El proceso involucra dos ingredientes principales: un código clásico y un grafo, que es una red de puntos conectados por líneas. El grafo determina cómo interactúan los qubits, mientras que el código clásico proporciona la estructura subyacente. La innovación clave estuvo en cómo se eligió el grafo. Los métodos anteriores dependían de grafos con conexiones muy específicas y dispersas, lo que limitaba la fuerza de la prueba. Kapshikar se dio cuenta de que, al utilizar un grafo aleatorio —una red donde las conexiones se eligen al azar—, se podía lograr un resultado mucho más fuerte.

En un grafo aleatorio, las conexiones son densas e impredecibles. El estudio muestra que para casi cualquier grafo aleatorio elegido, el código cuántico resultante tendrá una distancia que está estrechamente ligada a la distancia del código clásico original. Si el código clásico es fuerte, el código cuántico es fuerte. Si el código clásico es débil, el código cuántico es débil. Este vínculo es tan estrecho que, si se pudiera aproximar fácilmente la distancia del código cuántico, también se podría aproximar fácilmente la distancia del código clásico. Dado que sabemos que el problema clásico es imposible de resolver eficientemente, el problema cuántico también debe serlo, asumiendo que las hipótesis estándar de complejidad como la Hipótesis del Tiempo Exponencial (SETH) y la Hipótesis del Tiempo Exponencial de Brecha (Gap-ETH) se mantienen. La prueba establece que ninguna computadora puede aproximar la distancia cuántica dentro de una brecha lineal a menos que estas hipótesis fundamentales sobre la naturaleza de la computación colapsen.

El estudio va más allá, observando el problema a través de la lente de la complejidad "fina" (fine-grained). Este enfoque no solo pregunta si un problema es difícil, sino qué tan difícil es exactamente. Considera el tiempo que toma resolver el problema a medida que aumenta el tamaño de la entrada. La investigación muestra que, incluso si se permite que un algoritmo se ejecute durante mucho tiempo —más de un tiempo polinómico pero menos que una búsqueda exponencial completa—, aun así no puede resolver el problema, siempre que las hipótesis SETH y Gap-ETH sean ciertas. Específicamente, el artículo demuestra que ningún algoritmo puede resolver el problema en un tiempo significativamente menor al tiempo que tomaría verificar cada patrón de error posible. Esto es válido para computadoras teóricas poderosas, siempre que operen dentro de las reglas estándar de la lógica y la probabilidad y las hipótesis mencionadas sigan siendo válidas.

Uno de los aspectos más notables del hallazgo es su robustez. El resultado se mantiene incluso cuando el código cuántico se restringe a un tipo específico y popular conocido como código CSS. Estos códigos se utilizan ampliamente en diseños prácticos de computación cuántica porque son más fáciles de implementar. El investigador demostró que la dificultad también se aplica a ellos, lo que significa que la dificultad no es un artefacto de un diseño de código extraño o exótico, sino una propiedad fundamental de la propia corrección de errores cuánticos. La prueba también aborda el tema de la "degeneración", una característica única de los códigos cuánticos donde algunos errores son inofensivos porque actúan trivialmente sobre la información. El estudio tiene esto en cuenta cuidadosamente, mostrando que incluso con este detalle cuántico, el problema sigue siendo intratable.

Las implicaciones de este trabajo son profundas para el futuro de la computación cuántica. Confirma que la barrera para diseñar y analizar códigos cuánticos no es un obstáculo temporal que se superará con mejores algoritmos. En cambio, la dificultad es intrínseca a las matemáticas del problema, asumiendo las conjeturas estándar de complejidad. Esto significa que los ingenieros que diseñan computadoras cuánticas no pueden confiar en un cálculo rápido para verificar la fuerza de sus códigos. Deben aceptar que encontrar la distancia exacta es computacionalmente prohibitivo para sistemas grandes o confiar en construcciones específicas donde la distancia es conocida por diseño. El estudio traza efectivamente una línea en la arena, mostrando que la búsqueda de comprender los límites de la corrección de errores cuánticos debe proceder con el entendimiento de que la matemática subyacente es tan obstinada como puede ser.

El artículo también aborda la naturaleza de la aleatoriedad en la computación. La prueba se basa en la idea de que una elección aleatoria de grafo es suficiente para crear una instancia difícil. Aunque la prueba inicial utiliza un proceso aleatorio, el investigador también muestra cómo eliminar esta aleatoriedad bajo una hipótesis ampliamente aceptada sobre el poder de los circuitos de computación. Esto significa que la dificultad no es solo un accidente estadístico del azar, sino una realidad determinante. Existen códigos cuánticos específicos y fijos que garantizan ser difíciles de analizar, y estos códigos pueden ser generados por una computadora sin necesidad de lanzar dados. Esto fortalece la conclusión, moviéndola de una declaración probabilística a una garantía firme sobre los límites de la computación.

Al final, esta investigación cierra una brecha que había estado abierta durante algún tiempo. Toma la dificultad conocida de los códigos clásicos y la extiende plenamente al reino cuántico, eliminando la barrera de la raíz cuadrada que los estudios anteriores habían encontrado. El resultado es una imagen clara del panorama computacional: el problema de encontrar la distancia de un código cuántico es tan difícil como los problemas más difíciles de las ciencias de la computación, siempre que las hipótesis estándar de complejidad se mantengan. Para el observador curioso, esto significa que el mundo cuántico, aunque lleno de fenómenos extraños y maravillosos, no ofrece un escape de los límites fundamentales de la lógica. La complejidad de proteger la información cuántica es real, profunda y, por ahora, inalterable.