Context-Verified, Error-Budget-Aware Decomposition Selection for Toffoli Networks

Resumen Técnico: Selección de Descomposición Verificada por Contexto y Consciente del Presupuesto de Error para Redes Toffoli

1. Planteamiento del Problema

En el hardware cuántico de escala intermedia con ruido (NISQ), la falla de los circuitos está dominada por errores en puertas de dos cúbits, que son de uno a dos órdenes de magnitud peores que los errores de un solo cúbit. En consecuencia, la fidelidad efectiva de un circuito compilado está gobernada por el número y tipo de puertas de dos cúbits ejecutadas. La puerta Toffoli (CCX) es una primitiva fundamental para la aritmética cuántica y la lógica reversible, la cual admite diversas descomposiciones que intercambian ancillas, profundidad y conteo de puertas de dos cúbits.

El desafío central es que las descomposiciones conocidas más "baratas" —específicamente las Toffolis de fase relativa (que introducen una fase diagonal en un subconjunto de estados de la base) y las Toffolis aproximadas (que introducen un error acotado)— solo son correctas en contextos específicos. Sus fases residuales deben ser descomputadas posteriormente o sus errores deben permanecer dentro de la tolerancia en los estados específicos que la puerta realmente encuentra. Las herramientas existentes no logran cerrar la brecha entre:

• Optimizadores conscientes del contexto pero no verificados (p. ej., QContext, plantillas de Maslov): Estos seleccionan descomposiciones baratas y dependientes del contexto basadas en el conteo de puertas, pero carecen de modelos de fidelidad de hardware y, crucialmente, no verifican que la descomposición elegida sea válida en el contexto específico del circuito. Esto conduce a errores "silenciosos" donde las sustituciones por coincidencia de patrones corrompen el circuito.
• Optimizadores verificados pero ajenos al contexto (p. ej., VOQC, Quartz): Estos prueban que las reescrituras son correctas, pero solo como equivalencias incondicionales y ajenas al contexto, optimizando para el conteo de puertas en lugar de la infidelidad del hardware.

El resultado es un riesgo de seguridad: la sustitución agresiva y codiciosa de conteo de Toffolis de fase relativa puede ser silenciosamente incorrecta si el circuito circundante no cancela la fase residual.

2. Metodología

Los autores presentan un paso de compilador que selecciona las descomposiciones por cada Toffoli para minimizar un presupuesto de error de infidelidad de dos cúbits de hardware en lugar del conteo de puertas. El paso se construye sobre tres pilares:

1. Análisis de Contexto (Admisibilidad): Para cada puerta Toffoli $g$, el paso computa el conjunto de descomposiciones admisibles $A(g)$ basado en el circuito circundante:

   • Las descomposiciones exactas son siempre admisibles.
   • Las descomposiciones de fase relativa son admisibles si la fase diagonal residual $D$ es inobservable aguas abajo (por ejemplo, cancelada por una operación inversa subsecuente en un par de cómputo/descomputación).
   • Las descomposiciones aproximadas son admisibles si el error permanece dentro de la tolerancia $\epsilon$ en el subespacio alcanzable $R(g)$ —el span de los estados que realmente pueden alcanzar la puerta dado el circuito ascendente y los estados iniciales de las ancillas— en lugar de sobre todos los $2^n$ inputs.
   • El paso construye $R(g)$ mediante una propagación de conjuntos hacia adelante sólida sobre la base computacional, utilizando sobre-aproximaciones (super-cajas afines) cuando el conjunto de soporte se vuelve demasiado grande para asegurar la solidez.

2. Puerta de Verificación por Instancia: Ninguna regla estructural se confía implícitamente. Antes de comprometer una sustitución dependiente del contexto, el paso descarga una obligación de equivalencia condicionada al contexto:

   • Para la fase relativa, verifica que la CCX original y la descomposición candidata produzcan distribuciones de medición idénticas en los inputs alcanzables, considerando la cancelación aguas abajo.
   • Para la aproximada, verifica el límite de error en el subespacio alcanzable.
   • La verificación se realiza de forma exhaustiva (tabla de verdad/unitaria) para ventanas pequeñas o mediante backends de diagramas de decisión (MQT QCEC) o normalización ZX para ventanas más grandes. Si una comprobación falla, el paso retrocede a la alternativa más barata y certificada (usualmente una descomposición exacta).

3. Objetivo de Presupuesto de Error: El selector minimiza la infidelidad de dos cúbits sumada $B = \sum_g I(d_g)$, donde $I(d)$ es la suma de las infidelidades de las puertas de dos cúbits en la descomposición $d$. Este objetivo es específico del hardware, utilizando tasas de error calibradas para el dispositivo objetivo. La selección es codiciosa y óptima para casos separables; si el uso compartido de ancillas crea restricciones, se plantea como un Programa Lineal Entero (ILP).

3. Contribuciones Clave

El artículo realiza cuatro contribuciones primarias:

1. Primer Selector Impulsado por Presupuesto de Error: Un paso de compilador que optimiza para la infidelidad de dos cúbits de hardware en lugar del conteo de puertas, específicamente para la selección de Toffoli dependiente del contexto.
2. Capa de Verificación por Instancia: Un mecanismo que admite descomposiciones de fase relativa o de subespacio alcanzable solo después de descargar una obligación de equivalencia condicionada al contexto, haciendo que la selección agresiva sea sólida. Esto incluye un teorema de solidez (Teorema 1) y un corolario de composición de presupuesto de error acotado (Corolario 1).
3. Criterio de Admisibilidad de Subespacio Alcanzable: Un centro técnico que certifica las descomposiciones contra los estados realmente alcanzables en contexto, en lugar de sobre todos los inputs. Esto permite "controles exactos sobre lo alcanzable" (eliminando Toffolis con controles demostrablemente constantes) y admite más descomposiciones que la compilación aproximada de unidad completa.
4. Resultado de Seguridad: La demostración de que la sustitución por coincidencia de patrones de fase relativa es silenciosamente incorrecta en la práctica. Los autores muestran que un optimizador abierto desplegado contiene 66 reescrituras de librería no equivalentes, y un enfoque codicioso de conteo corrompe silenciosamente 6 de 12 circuitos de prueba, mientras que el paso con compuerta certifica 0 errores.

4. Resultados

La evaluación se realizó en dos suites: una suite de 12 circuitos (hasta 8 cúbits) para verificación exhaustiva y una suite de 20 circuitos (12–24 cúbits) para escalabilidad.

• Seguridad: El paso con compuerta elimina todos los errores silenciosos. Mientras que la sustitución codiciosa de conteo y el análisis de contexto sin verificación corrompieron 6 de 12 circuitos, el paso completo con compuerta introdujo 0 errores.
• Reducción del Presupuesto de Error:
  • En la suite de 12 circuitos (pesada en cómputo/descomputación), el paso con compuerta logró una reducción del 39.5% en puertas de dos cúbits y una reducción del 36.7% en la infidelidad estimada comparado con las líneas base de solo exactas.
  • Comparado con Qiskit opt-level-3 y tket, las reducciones fueron aproximadamente del 39% y 35% respectivamente.
  • En una suite más grande de 12–24 cúbits, la reducción agregada fue del 15.6% en puertas y del 11.7% en infidelidad.
  • La reducción es altamente dependiente de la carga de trabajo: los oráculos de escalera AND de Grover (completamente emparejados) vieron una reducción de ~49%, los sumadores de acarreo rápido (carry-lookahead) ~28%, los sumadores de acarreo (ripple) ~6%, y los multiplicadores de matriz 0% (ya que sus AND son "vivos" y no pueden simplificarse).
• Escalabilidad: El backend de verificación escala efectivamente. Para circuitos de hasta 24 cúbits, las comprobaciones de diagramas de decisión certificaron cada sustitución aceptada en menos de 0.025 segundos. El cruce de la verificación exhaustiva a la de diagramas de decisión ocurre alrededor de los 11–12 cúbits, proporcionando una aceleración de >3000x.
• Aplicación en el Mundo Real: En un circuito de reinicio de estado cuántico (palabra de sincronización), el paso eliminó el 48.8% de las puertas nativas de dos cúbits, con cada sustitución verificada, poniendo un experimento de sincronización limitado por presupuesto al alcance.
• Relevancia de Hardware: Con las tasas de error actuales para dispositivos superconductores (IBM, Google) y de iones atrapados (IonQ, Quantinuum), las sustituciones certificadas reducen la infidelidad estimada del circuito entre un 36–43%.

5. Significancia y Reclamaciones

El artículo afirma cerrar la brecha entre los optimizadores conscientes del contexto pero no verificados y los verificados pero ajenos al contexto. Su resultado central es una garantía de seguridad: la sustitución por coincidencia de patrones de fase relativa es inherentemente riesgosa sin verificación por instancia. Los autores afirman que su enfoque hace que la selección de Toffoli agresiva y dirigida a la fidelidad sea demostrablemente segura por instancia.

El trabajo no pretende resolver todos los problemas de optimización; señala explícitamente limitaciones:

• El régimen de aproximación acotada (admitiendo descomposiciones con $\epsilon > 0$) es actualmente inerte bajo la alcanzabilidad basada en conjuntos, ya que el método rastrea estados de la base, no amplitudes. Activar este compromiso requiere un front-end de alcanzabilidad consciente de la amplitud, lo cual se deja para trabajos futuros.
• La reducción en puertas e infidelidad es estrictamente una función de la estructura del circuito (la fracción de pares de Toffoli cancelables), no una constante universal para todos los circuitos.

Los autores concluyen que este marco proporciona una capa sólida y consciente del presupuesto de error que mejora la viabilidad de las ejecuciones de computación cuántica física limitadas por el presupuesto de error, con cada reducción certificada como sólida.