Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

Resumen Técnico: Síntesis Eficiente de Puertas Toffoli Multicontroladas con Puertas Ternarias Clifford+P9

Planteamiento del Problema
Las puertas Toffoli multicontroladas (MCT) son primitivas fundamentales en el diseño de circuitos cuánticos, esenciales para la aritmética reversible, la construcción de oráculos y la amplificación de amplitud. Sin embargo, su descomposición se vuelve cada vez más costosa en términos de recursos a medida que aumenta el número de cúbits de control. En arquitecturas tolerantes a fallos, las operaciones no Clifford (como las puertas Toffoli) requieren la preparación e inyección de estados de recursos costosos. Los enfoques convencionales basados únicamente en sistemas binarios suelen descomponer las MCT en puertas Toffoli más pequeñas y luego en conjuntos de Clifford+T, lo que incurre en un compromiso entre el coste de las puertas T, los requisitos de cúbits auxiliares y la profundidad del circuito. Aunque construcciones binarias recientes utilizando ancillas condicionalmente limpias logran una profundidad logarítmica, dependen de la descomputación asistida por medición y de la retroalimentación clásica, lo que introduce sobrecostes relacionados con la latencia de medición y la programación coherente. Alternativamente, existen métodos de síntesis aproximada, pero no proporcionan construcciones exactas. El artículo aborda la necesidad de una síntesis de MCT exacta y eficiente en recursos que evite la sobrecarga de medición mientras mejora la profundidad y los requisitos de ancillas en un entorno tolerante a fallos.

Metodología
Los autores proponen una descomposición exacta de las puertas MCT con entradas y salidas de subespacio binario utilizando el marco ternario Clifford+P9. Este enfoque aprovecha la ocupación temporal del nivel de trutrit no computacional $|2\rangle$ como espacio de trabajo, manteniendo los estados lógicos codificados en el subespacio binario $H_{bin} = \text{span}\{|0\rangle, |1\rangle\}$.

La metodología central consiste en una descomposición de árbol jerárquico:

1. Primitivas: La construcción utiliza tres operaciones elementales: la puerta SUM ternaria (Clifford), un incremento controlado selectivo de estado $C_2(\text{INC})$ (no Clifford) y un toggle estricto controlado de la target binaria $C_2(X_{01})$ (no Clifford). El coste de recursos se mide por el número de inyecciones lógicas de P9 requeridas para implementar las puertas no Clifford.
2. Estructura de Árbol: En lugar de una extensión recursiva secuencial, los controles se evalúan mediante un árbol equilibrado.
   • Bloques de Hoja (Leaf Blocks): Grupos de tres controles binarios se evalúan en paralelo. Un bloque de hoja utiliza una puerta SUM y un $C_2(\text{INC})$ para marcar temporalmente un trutrit de control con el estado $|2\rangle$ si y solo si los tres inputs son $|1\rangle$.
   • Bloques de Fusión (Merge Blocks): Los nodos internos combinan los resultados de dos subárboles hijos y un control adicional. Esto utiliza un trutrit auxiliar limpio (inicializado en $|0\rangle$) y tres puertas $C_2(\text{INC})$. Si ambos marcadores de los hijos son $|2\rangle$ y el control intermedio es $|1\rangle$, el auxiliar alcanza el estado $|2\rangle$, lo que a su vez dispara al control intermedio para alcanzar el estado $|2\rangle$.
   • Operación Raíz (Root Operation): Una vez que el marcador raíz alcanza $|2\rangle$ (indicando que todos los controles están activos), un único toggle estricto $C_2(X_{01})$ invierte el cúbit target.
   • Descomputación (Uncomputation): El circuito se invierte para restaurar todos los marcadores temporales y los trutrits auxiliares a $|0\rangle$.

Contribuciones Clave y Resultados
El artículo proporciona un análisis de recursos exacto para anchuras de control equilibradas $n = 2^h - 1$ y extiende la construcción a anchuras arbitrarias.

• Eficiencia de Recursos para Anchuras Equilibradas ($n = 2^h - 1$):

  • Recuento de P9: La construcción requiere $6n + 3$ inyecciones lógicas de P9. Esto coincide con el recuento exacto de P9 de la línea base de vanguardia sin ancillas de extensión recursiva (Baseline B) derivada de Bocharov et al. [16].
  • Cúbits Auxiliares (Trutrits): La construcción requiere $\frac{n-3}{4}$ trutrits auxiliares limpios. Esto es asintóticamente una cuarta parte de los $n-2$ auxiliares requeridos por la Baseline B.
  • Profundidad del Circuito: Al evaluar subárboles independientes en paralelo, la profundidad se reduce de lineal $\Theta(n)$ a logarítmica $\Theta(\log n)$.

• Frontera de Compromiso (Trade-off Frontier):
  El artículo identifica un compromiso constructivo entre el espacio de trabajo auxiliar y el coste no Clifford. Al reutilizar los trutrits auxiliares (reduciendo el número de auxiliares vivos simultáneamente $A$), el recuento de P9 aumenta. Específicamente, utilizar un solo auxiliar reutilizado ($A=1$) resulta en un recuento de P9 de $9n - 18$ y una profundidad de $\Theta(n)$, mientras que retener $I(n)$ auxiliares minimiza el recuento de P9 a $6n+3$.

• Anchuras de Control Arbitrarias:
  Para un $n$ arbitrario, los autores extienden la construcción seleccionando un núcleo equilibrado de anchura $m = 2^h - 1 \leq n$ y añadiendo secuencialmente los $n-m$ controles restantes. Esto preserva el recuento de $6n+3$ de P9 pero resulta en una profundidad de $O(\log m + n - m)$. En el peor de los casos (por ejemplo, $n = 2^{h+1}-2$), la profundidad escala linealmente con $n$.

Significancia y Reivindicaciones
El artículo afirma que la descomposición propuesta proporciona un bloque de construcción práctico para el diseño y la compilación de algoritmos cuánticos más eficientes en recursos en el régimen tolerante a fallos. Su principal significancia radica en:

1. Reducción de Profundidad: Reemplazar la profundidad lineal de las bases ternarias recursivas por una profundidad logarítmica para inputs equilibrados sin depender de la medición o la retroalimentación.
2. Reducción de Ancillas: Reducir el requisito asintótico de trutrits auxiliares limpios por un factor de cuatro en comparación con las mejores líneas base recursivas exactas existentes, manteniendo el mismo coste no Clifford (P9).
3. Síntesis Exacta: Ofrecer una estrategia de construcción exacta que integra información binaria en sistemas multinivel, distinta de los regímenes de síntesis aproximada.

Los autores señalan que, si bien el caso equilibrado ofrece una profundidad logarítmica, la profundidad del peor caso para anchuras arbitrarias sigue siendo lineal. Sugieren que trabajos futuros podrían explorar modelos de coste de tolerancia a fallos más detallados (incluyendo la destilación de estados mágicos y el enrutamiento), configuraciones alternativas de trutrits intermedios y la integración en subrutinas reversibles más grandes como circuitos aritméticos.