Resource-Efficient Synthesis of Sparse Quantum States

Resumen Técnico: Síntesis Eficiente en Recursos de Estados Cuánticos Dispersos

Planteamiento del Problema
La preparación de estados cuánticos es una subrutina fundamental para numerosos algoritmos cuánticos, incluyendo la simulación de Hamiltonianos, resolvedores lineales y aprendizaje automático. Sin embargo, preparar un estado arbitrario de $n$ qubits generalmente requiere un tamaño de circuito de $\Omega(2^n)$, lo que resulta ineficiente en recursos para sistemas grandes. Aunque muchas aplicaciones prácticas requieren solo estados dispersos (vectores con pocas entradas no nulas), los métodos de síntesis existentes a menudo no logran optimizar métricas críticas para la computación cuántica tolerante a fallos (FTQC). Específicamente, en FTQC, las puertas no-Clifford (como las puertas T) son significativamente más costosas de implementar que las puertas Clifford. Los métodos actuales para la síntesis de estados dispersos suelen presentar conteos de no-Clifford elevados o una profundidad de circuito excesiva, y pocos enfoques han minimizado explícitamente los recursos no-Clifford manteniendo una profundidad lineal.

Metodología
Los autores proponen una metodología novedosa que descompone la síntesis de un estado de $n$ qubits y $s$-disperso en dos tareas distintas y optimizadas:

1. Generación de un Estado W Ponderado: El primer paso consiste en preparar un estado W generalizado, $|W(\vec{\alpha})\rangle = \sum \alpha_i |e_i\rangle$, el cual codifica las amplitudes del estado disperso. El artículo presenta dos estrategias de construcción:

   • Construcción basada en Árboles: Un método exacto, sin ancillas, basado en una definición inductiva mediante una estructura de árbol binario. Este enfoque utiliza puertas $RY(\theta)$ y logra un tamaño de $O(n)$ y una profundidad de $O(\log n)$. Los autores analizan las condiciones bajo las cuales estas rotaciones pueden ser compiladas al conjunto Clifford+T, observando que los estados W uniformes permiten reducciones significativas de puertas T.
   • Construcción de Estado Completo: Un enfoque alternativo que prepara un estado completo sobre $\lceil \log_2 n \rceil$ qubits y mapea los estados de la base al de la base del estado W. Este método aprovecha resultados óptimos recientes para la preparación de estados completos (Gosset et al.) para lograr mejores conteos de T en el régimen tolerante a fallos, aunque con mayores requisitos de ancillas.

2. Permutación mediante Circuitos Reversibles Clásicos: El segundo paso mapea los estados de la base $|e_i\rangle$ del estado W a los estados de la base específicos del vector disperso. Esto se modela como un problema de permutación sobre cadenas binarias.

   • Los autores reducen esto a la diagonalización de una matriz binaria $M_\chi$ utilizando operaciones elementales de fila correspondientes a puertas reversibles clásicas (X, CX, CCX).
   • Introducen una nueva variante de la eliminación de Gauss-Jordan que utiliza pasos de eliminación paralelos para minimizar la profundidad del circuito.
   • Una optimización clave consiste en el uso de circuitos Clifford adaptativos (que involucran mediciones y puertas controladas clásicamente) para reemplazar las costosas puertas Toffoli (CCX) cuando el qubit objetivo está garantizado como $|0\rangle$ tras la operación. Esto permite que el circuito de permutación se implemente con un conteo de T de $O(s)$ (o cero conteo de T con mediciones) y una profundidad de $O(s+n)$.

Contribuciones Clave y Resultados

• Eficiencia de Recursos: El algoritmo propuesto sintetiza estados dispersos con un conteo de no-Clifford lineal en la dispersión $s$ ($O(s)$) y una profundidad de circuito lineal tanto en la dispersión como en el número de qubits ($O(s+n)$). Esto mejora los métodos del estado del arte donde la profundidad suele ser $O(sn)$ o los conteos de no-Clifford son superlineales.
• Compilación Tolerante a Fallos: Al compilarse al conjunto de puertas Clifford+T, los autores proporcionan tres construcciones que ofrecen compensaciones entre el conteo de T, la profundidad y el conteo de ancillas.
  • La construcción más optimizada en T logra un conteo de T de $O(\sqrt{s \log_2(1/\epsilon)} + \log_2(1/\epsilon))$. Los autores señalan que esto coincide con los límites de optimalidad para la preparación de estados completos de Gosset et al., lo que sugiere que la construcción es probablemente óptima también para estados dispersos.
• Optimización de Casos Especiales: Para estados dispersos "T-uniformes" (donde las entradas no nulas están en el conjunto $\{e^{ik\pi/4}\}$), los autores demuestran una síntesis exacta utilizando solo $O(\sqrt{s})$ puertas T con una probabilidad de éxito $> 1/2$, utilizando ancillas sucias (dirty ancillae).
• Técnica de Diagonalización de Matrices: El artículo contribuye con un algoritmo específico para la diagonalización de matrices binarias utilizando operaciones paralelas CX y CCX, que sirve como el motor central para el circuito de permutación.

Significancia
El artículo reclama su importancia principalmente al abordar el cuello de botella de recursos de las puertas no-Clifford en la computación cuántica tolerante a fallos. Al desacoplar la preparación de la amplitud (estado W) de la permutación de la base, los autores logran un método de síntesis donde los recursos no-Clifford costosos escalan linealmente con la dispersión en lugar de con el número total de qubits. La profundidad del circuito también mejora al ser aditiva en $s$ y $n$, una mejora sustancial respecto a las dependencias multiplicativas de trabajos previos.

Los autores señalan modestamente que, si bien su método es altamente eficiente en conteo de T y profundidad, puede requerir un mayor número de qubits ancilla en comparación con algunos enfoques existentes (específicamente $\max(s, n) - n$). Identifican la optimización de las estructuras de árboles para maximizar las operaciones amigables con Clifford como un problema clásico NP-duro (relacionado con el problema de la partición) y sugieren que trabajos futuros podrían explorar la adaptación de la lógica del circuito reversible a restricciones de conectividad específicas de hardware o la generalización del enfoque a estados Dicke.