Optimised T counts and active volume estimates for high- and low- level arithmetic subroutines

Título: Conteos de T y estimaciones de volumen activo optimizados para subrutinas aritméticas de alto y bajo nivel

Autor: Sam Heavey (Imperial College London)

Planteamiento del problema

Las computadoras cuánticas basadas en código de superficie son un candidato principal para la computación cuántica tolerante a fallos. Sin embargo, las arquitecturas "base" tradicionales, que dependen de arreglos 2-D de qubits con conectividad local, sufren ineficiencias significativas. Una gran parte del volumen espacio-temporal en estas computaciones es "ociosa", correspondiente a qubits lógicos que permanecen sin uso durante operaciones específicas. Este volumen ocioso aumenta el costo de recursos general (volumen espacio-temporal) sin contribuir a la computación lógica.

Aunque las arquitecturas de "volumen activo" (AV) buscan eliminar este volumen ocioso mediante la utilización de conectividad de largo alcance para paralelizar operaciones, existe una falta de un catálogo exhaustivo de subrutinas aritméticas optimizadas con estimaciones precisas de volumen activo. La literatura existente suele centrarse en la reducción del conteo de T en arquitecturas base sin considerar plenamente cómo la estructura del circuito impacta el volumen activo, particularmente cuando se trata de la inyección de estados y mediciones reactivas.

Metodología

El artículo propone una metodología para derivar y optimizar el volumen activo y los conteos de T para ambas subrutinas aritméticas de bajo nivel (p. ej., incremento, desplazamiento, suma) y de alto nivel (p. ej., raíz cuadrada, trigonometría, logaritmo).

1. Suposición de optimalidad: El trabajo opera bajo la suposición de que los diseños de circuitos que minimizan el conteo de T y el número de qubits en una arquitectura base también producirán el menor volumen activo. Esto permite al autor centrarse en minimizar los conteos de T (específicamente las compuertas Toffoli y AND temporales) en lugar de calcular volúmenes activos para cada posible variación de diseño.
2. Optimización del conjunto de compuertas: El autor utiliza la compuerta "AND temporal" (introducida por Gidney) para reducir a la mitad el conteo de T de ciertas operaciones. También opta por implementar compuertas Toffoli y AND temporales mediante estados CCZ en lugar de estados T, ya que la destilación de CCZ suele ser más económica en el modelo de volumen activo.
3. Cálculo del volumen activo mediante diagramas ZX orientados:
   • El autor convierte diagramas de circuitos estándar en diagramas ZX y luego en diagramas ZX orientados (OZX).
   • Los diagramas OZX incorporan conciencia espacial, mapeando los spiders a puertos específicos (U, D, N, S, E, W) de bloques espaciotemporales 3D.
   • Al aplicar las reglas de cálculo ZX (como la fusión de spiders) dentro de las restricciones de conectividad OZX, el autor simplifica los diagramas para contar el número mínimo de bloques lógicos (spiders) requeridos.
   • El volumen activo total se calcula sumando los conteos de bloques de los spiders y añadiendo los costos de destilación para cualquier estado mágico requerido (p. ej., estados CCZ).
4. Análisis de profundidad de reacción: El artículo tiene en cuenta la "profundidad de reacción", el tiempo requerido para el procesamiento clásico de los resultados de las mediciones para determinar las operaciones correctivas para compuertas no-Clifford. La profundidad de reacción total se calcula como la suma de las profundidades de los componentes secuenciales, proporcionando un límite superior en el tiempo de computación.

Contribuciones clave y resultados

1. Subrutinas aritméticas de bajo nivel
El artículo presenta circuitos optimizados para operaciones fundamentales, verificados mediante simulación en Qiskit:

• Incremento y Incremento controlado: Modificados para usar compuertas AND temporales, reduciendo el conteo de T a $7n - 14$ (para incremento) y $7n - 7$ (para incremento controlado).
• Desplazamientos (Shifts): Se demuestra que en arquitectes de volumen activo, los desplazamientos no controlados son "gratuitos" (costo de bloque lógico cero) mediante el renombre de etiquetas. Los desplazamientos controlados se optimizan usando fusiones de spiders de ZX, aunque la reducción en el conteo de bloques es marginal comparada con la versión no optimizada.
• Suma/Resta Controlada (CAS): Se diseña un nuevo sumador controlado al estilo de Gidney. Logra una reducción de $\approx 8\%$ en el volumen activo en comparación con una suma directa de costos, con un conteo de T de $7n - 7$.
• Multiplicación: Se propone un nuevo multiplicador que utiliza un arreglo Toffoli y sumadores de Desbordamiento Controlado de Gidney (COG), el cual logra una reducción del 62% en el factor principal del conteo de T respecto al diseño de vanguardia de Muñoz-Coreas & Thapliyal [21].
• Cuadrado: Optimizado mediante el intercambio de conteo de qubits por compuertas CNOT, reduciendo el requisito de qubits de $6n+2$ a $5n$ para la multiplicación, con ajustes específicos para el cuadrado.

2. Subrutinas aritméticas de alto nivel
El autor extiende estos componentes de bajo nivel a funciones complejas:

• Raíz Cuadrada: Se presenta un algoritmo de raíz cuadrada no restaurativa optimizado. Reduce el conteo de T significativamente en comparación con el diseño principal [19], aunque requiere ligeramente más qubits ($3n$ frente a $2n+1$).
• Trigonometría (Evaluación Polinómica por Partes - PPE): El artículo adapta el circuito PPE de Häner. Al reemplazar los sumadores y multiplicadores originales con las versiones optimizadas del autor (sumador OG, multiplicador COG) y un comparador nuevo, el conteo de T se reduce aproximadamente 2/3 en los términos principales en comparación con la implementación original [20].
• Trigonometría Inversa (Arcoseno): Se construye un circuito que combina la evaluación polinómica y la raíz cuadrada. El nuevo diseño logra una reducción de casi 6 veces en el término $n^2$ del conteo de T comparado con la implementación de Häner [20].
• Logaritmo: Se adapta una implementación del método qFBE de Wang et al. para computación de volumen activo. El artículo proporciona las primeras estimaciones de volumen activo y conteo de T para este método, señalando que es $O(n^3)$ en operaciones cuánticas.

3. Sensibilidad estructural del volumen activo
Un hallazgo crítico es que la estructura del circuito impacta el volumen activo independientemente de los conteos de compuertas. El autor demuestra que circuitos lógicamente equivalentes con idénticos conteos de compuertas pueden tener diferentes volúmenes activos debido a la disposición de los controles y objetivos. Específicamente, los diseños que maximizan las líneas ininterrumpidas de controles y objetivos permiten fusiones de spiders más eficientes en el cálculo ZX, reduciendo el conteo de bloques. Esto sugiere que optimizar solo para el conteo de compuertas es insuficiente para arquitecturas de volumen activo.

Significancia y Reivindicaciones

El artículo afirma proporcionar una "metodología simple" para estimar y optimizar volúmenes activos utilizando diagramas ZX orientados. Su principal significancia radica en:

• Reducción de recursos: Reducción significativa de los conteos de T y volúmenes activos para una amplia gama de subrutinas aritméticas, que son los bloques de construcción de algoritmos cuánticos mayores (p. ej., factorización, HHL).
• Conciencia Arquitectónica: Resaltar que la métrica de "volumen activo" es sensible a la topología del circuito, no solo a la complejidad de las compuertas. Esto requiere un cambio en la forma en que se diseñan los circuitos para arquitecturas con conectividad de largo alcance.
• Expansión del Catálogo: Proporcionar un recurso necesario de subrutinas optimizadas (incluyendo funciones de alto nivel como $\log x$ y $\arcsin x$) que carecían previamente de contexto en la computación de volumen activo.

El autor concluye que, si bien su trabajo se centra en los conteos de T y volúmenes activos, trabajos futuros también deberían considerar la optimización de compuertas Clifford y la inclusión de otras subrutinas de bajo nivel como sumadores de acarreo rápido (carry look-ahead) y circuitos de división. No pretenden haber resuelto todos los problemas de estimación de recursos, sino pretenden fomentar la investigación adicional en el diseño de circuitos conscientes del volumen activo (AV-aware).