Block Encoding of Sparse Matrices via Coherent Permutation

1. El Problema

La codificación en bloque (block encoding) es una primitiva fundamental en algoritmos cuánticos modernos, como la Transformación de Valores Singulares Cuánticos (QSVT), la simulación de Hamiltonianos y los solucionadores de sistemas lineales cuánticos (HHL). Consiste en incrustar una matriz $A$ (posiblemente no unitaria) dentro de un operador unitario más grande $U_A$.

Aunque existen formulaciones teóricas basadas en oráculos "caja negra" para matrices dispersas, su realización explícita a nivel de puertas lógicas sigue siendo un desafío mayor debido a:

• Sobrecarga de puertas MCX: La necesidad de puertas de múltiples controles (Multi-Controlled X) genera circuitos profundos y complejos.
• Reordenamiento de amplitudes: La gestión de cómo se asignan los datos a los estados base requiere operaciones costosas.
• Conectividad del hardware: La mayoría de los procesadores cuánticos actuales (como los de iones atrapados o qubits superconductores) tienen restricciones de conectividad de vecinos más cercanos. Las interacciones a larga distancia aumentan el ruido y la profundidad del circuito.
• Factor de subnormalización: El factor $\alpha$ afecta directamente la eficiencia de los algoritmos; construcciones ineficientes pueden inflar este factor.

2. Metodología

El autor propone un marco unificado que conecta la codificación en bloque con la optimización combinatoria y la permutación coherente. La metodología se divide en los siguientes pasos clave:

A. Preprocesamiento y Oráculos

Se define una matriz dispersa $A$ extrayendo sus elementos únicos a lo largo de las diagonales. Se construyen dos vectores:

1. Vector de datos ($v_{data}$): Contiene las magnitudes de los elementos no nulos.
2. Vector de signos ($v_{sign}$): Contiene las fases (signos reales o imaginarios).

Se utilizan oráculos de preparación de estado (PREP/UNPREP) para codificar estos vectores en las amplitudes de un estado cuántico.

B. Oráculos de Mapeo de Índices

Para colocar los datos en las posiciones correctas de la matriz (filas $i$ y columnas $j$), se utilizan dos oráculos:

• Desplazamiento ($O_{shift}$): Mueve los elementos desde la diagonal principal a la diagonal objetivo $d = i - j$.
• Eliminación ($O_{del}$): Elimina elementos que caen en filas no deseadas para esa diagonal específica.

C. Compresión de Puertas MCX (Teorema 2)

El núcleo de la optimización reside en analizar composiciones de puertas MCX. El artículo demuestra que si un conjunto de estados de control $S_2$ comparte un subconjunto fijo de índices $F$ y las variaciones en los índices restantes cubren todas las combinaciones binarias posibles, la composición de $2^n$ puertas MCX puede comprimirse en una sola puerta MCX con menos controles.

D. Permutación Coherente y Optimización Combinatoria (Teorema 3)

Cuando el conjunto de estados de control no cumple naturalmente las condiciones para la compresión, el marco propone:

1. Permutar amplitudes: Utilizar operaciones unitarias reversibles (basadas en MCX) para reordenar las amplitudes de los estados base.
2. Optimización Combinatoria: Formular la asignación de estados de control a una estructura comprimible como un problema de asignación lineal (resuelto mediante el algoritmo húngaro).
3. Objetivo: Minimizar la distancia de Hamming total entre los estados originales y los estados objetivo, asegurando que los controles de las puertas MCX se puedan implementar en qubits adyacentes (conectividad de vecinos más cercanos).

3. Contribuciones Clave

• Marco Unificado de Implementación: Transita de las formulaciones teóricas abstractas a implementaciones explícitas a nivel de puertas, manejando matrices complejas y dispersas.
• Compresión de MCX: Proporciona un método sistemático para reducir la complejidad de los controles en las puertas MCX mediante la identificación de patrones estructurales en los estados de control.
• Permutación Coherente: Introduce operadores unitarios ($A\_PERMUTE$) que reordenan amplitudes sin colapsar el estado cuántico, permitiendo adaptar el circuito a las restricciones de hardware.
• Optimización para Hardware: El enfoque integra técnicas de optimización clásica para mapear qubits de control en qubits físicos adyacentes, reduciendo significativamente la profundidad del circuito y el ruido en arquitecturas de vecinos más cercanos.
• Estrategias de Inserción/Eliminación: Desarrolla operadores eficientes para insertar o eliminar datos en filas específicas sin necesidad de operaciones exponenciales, utilizando la propiedad de que eliminar en todas las filas y luego insertar en la deseada es más eficiente.

4. Resultados y Validación

El autor demuestra la eficacia del marco en dos casos de estudio:

1. Matriz Tridiagonal Compleja: Se muestra cómo codificar una matriz tridiagonal compleja, comprimiendo los estados de control de las puertas de desplazamiento y eliminación. El circuito resultante es compacto y adecuado para hardware real.
2. Matriz Estructurada Real (32x32): Se aplica el método a una matriz dispersa con una estructura específica.
   • Se identificaron múltiples estrategias para manejar elementos en la misma diagonal (modificando los valores de datos para minimizar el factor de subnormalización $\alpha$).
   • Se optimizaron los mapeos de índices utilizando el algoritmo de asignación lineal para encontrar la mejor permutación de amplitudes.
   • Se generaron circuitos completos que combinan desplazamiento, eliminación, inserción y permutación, validando la escalabilidad del enfoque.

5. Significancia

Este trabajo es significativo porque cierra la brecha entre la teoría de la codificación en bloque y la implementación práctica en hardware cuántico actual.

• Eficiencia de Recursos: Al reducir la profundidad del circuito y el número de puertas MCX, disminuye la probabilidad de error y el tiempo de coherencia requerido.
• Compatibilidad con Hardware: Al priorizar la conectividad de vecinos más cercanos mediante permutación coherente, el método es directamente aplicable a las arquitecturas de qubits superconductores más comunes hoy en día.
• Habilitador de Algoritmos: Facilita la ejecución eficiente de algoritmos críticos como QSVT y HHL, que dependen de una codificación en bloque de alta calidad y bajo costo.
• Perspectiva Futura: Establece que el diseño de permutaciones no es solo un paso de compilación, sino un recurso de optimización que puede ser tratado mediante técnicas de optimización clásica para mejorar el rendimiento cuántico.

En resumen, el artículo ofrece una ruta concreta y optimizada para construir circuitos cuánticos que codifiquen matrices dispersas, abordando directamente los cuellos de botella de la conectividad y la complejidad de los controles.