Sparse quantum state preparation with improved Toffoli cost

Resumen Técnico: Preparación de Estados Cuánticos Dispersos con Coste de Toffoli Mejorado

Planteamiento del Problema
La preparación de estados cuánticos es un primitivo fundamental en la computación cuántica, esencial para aplicaciones que van desde resolvedores de sistemas lineales y aprendizaje automático cuántico hasta simulación cuántica. Mientras que la preparación de estados genéricos ha sido ampliamente estudiada, los estados cuánticos dispersos (o sparse) —estados en $n$ qubits que contienen solo $s \ll 2^n$ estados de la base computacional con coeficientes no nulos— requieren algoritmos especializados y eficientes.

En la computación cuántica tolerante a fallos, la métrica de recurso principal suele ser el número de puertas Toffoli (y puertas T), ya que estas operaciones no-Clifford son significativamente más costosas de implementar que las puertas Clifford debido a la sobrecarga de la destilación de estados mágicos. Los enfoques existentes para la preparación de estados dispersos generalmente caen en dos categorías:

1. Construcción iterativa: Construir el estado en $s$ pasos, preparando cada paso un único estado de la base. Esto típicamente incurre en un coste de Toffoli superior a $s \lceil \log(s) \rceil$.
2. Enfoque de dos pasos (Preparación Densa + Isometría): Primero preparar un estado denso en un subregistro de $\lceil \log(s) \rceil$ qubits, y luego mapearlo al estado disperso objetivo mediante una isometría. La preparación de estados densos está bien optimizada (por ejemplo, mediante algoritmos de Grover-Rudolph), pero el paso de la isometría ha sido histómente el cuello de botella. El arte previo, como el método de Malvetti et al., requiere un coste de Toffoli en el peor de los casos de $s(\lceil \log(s) \rceil - 1)$ para la isometría, lo que domina el coste total del algoritmo.

Metodología
Los autores proponen un marco refinado de dos pasos (ilustrado en la Figura 1) que optimiza el paso de la isometría y lo integra con la preparación de estados densos:

1. Construcción de Isometría por Lotes (Batched):
   La innovación central es un nuevo algoritmo clásico para construir el circuito de isometría. En lugar de aplicar puertas multi-controladas-X individuales para anular los qubits fuera del subespacio para cada uno de los $s$ estados (como hace Malvetti et al.), el algoritmo agrupa los estados en lotes (batches) de tamaño $m$, donde $m$ es la mayor potencia de dos que cabe en el registro disponible fuera del subespacio ($m \le n - \lceil \log(s) \rceil$).

   • Para cada lote, el algoritmo transforma los estados en una forma donde el registro fuera del subespacio contiene un único $|1\rangle$ en posiciones distintas (por ejemplo, $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$).
   • Se aplica entonces un circuito de Iteración Unaria Parcial (PUI) para anular simultáneamente los registros fuera del subespacio para todo el lote.

2. Circuitos de Iteración Unaria Parcial (PUI):
   Los autores introducen dos variantes de circuitos PUI, que iteran sobre un intervalo específico $[l, r]$ de un registro de dirección en lugar del espacio completo:

   • PUI Restringida: Garantiza que las unitarias se apliquen solo a los estados dentro del intervalo objetivo $[l, r]$.
   • PUI No Restringida: Permite que el circuito aplique unitarias no triviales a estados con valores de dirección superiores a $r$. Esta relajación reduce significativamente el recuento de Toffolis. Los efectos "no deseados" en los valores de dirección superiores se rastrean clásicamente y se corrigen en pasos o lotes posteriores.

3. Optimización Conjunta con la Preparación de Estados Densos:
   Los autores analizan la compensación (trade-off) entre el coste de la isometría y el coste de la preparación del estado denso. Proponen "externalizar" ciertas subtareas de la preparación densa al circuito de isometría:

   • Correcciones de Signo: En lugar de descomputar el registro de ángulos tras la preparación densa (lo que requiere Toffolis adicionales para la corrección de signo), la información de signo se codifica directamente en la isometría mediante PUIs restringidas.
   • Estados Reales: Para estados objetivo con coeficientes puramente reales, el paso de codificación de fase de la preparación densa se elimina por completo y se gestiona dentro de la isometría, lo que potencialmente reduce el coste de Toffoli de la preparación densa en un factor de hasta tres.

Contribuciones Clave

• Algoritmo de Isometría Mejorado: Un nuevo algoritmo clásico (Algoritmo 1) que construye circuitos de isometría con un coste de Toffoli en el peor de los casos acotado por:
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  donde $\tilde{s} = 2^{\lceil \log(s) \rceil}$. Esto representa una mejora de aproximadamente $\log(s)/2$ respecto al método de vanguardia de Malvetti et al.
• Variantes de PUI: La definición y el análisis de coste de los circuitos de iteración unaria parcial restringidos y no restringidos. La versión no restringida logra recuentos de Toffoli más bajos al permitir la "fuga" de operaciones hacia valores de dirección superiores, lo cual es manejable en el contexto de la construcción de isometría por lotes.
• Análisis de Compensación de Recursos: Un análisis exhaustivo (Tabla 1) de los costes combinados de Toffoli y qubits para la preparación de estados dispersos, demostrando cómo la optimización de la isometría permite una mejor utilización de los qubits auxiliares (ancilla) para reducir el coste de la preparación densa, particularmente para estados de valor real.
• Implementación: Los circuitos se implementan en el marco Qualtran, con el algoritmo clásico de búsqueda de isometrías optimizado mediante código Rust acelerado por SIMD.

Resultados

• Límites Teóricos: El coste de Toffoli en el peor de los casos para la isometría se reduce de $O(s \log s)$ a aproximadamente $O(s)$ para valores de $n$ suficientemente grandes. Específicamente, el coste se aproxima a $s$ en comparativas numéricas en estados aleatorios, frente al anterior mejor de aproximadamente $s \log s$.
• Comparativas Numéricas:
  • Para estados aleatorios $s$-dispersos, el número de Toffolis por $s$ se aproxima a 1 a medida que $n$ aumenta (Figura 2, derecha).
  • Para estados puramente reales, la optimización conjunta reduce significativamente el recuento total de Toffolis en comparación con los estados complejos genéricos (Figura 9).
  • El algoritmo clásico se ejecuta de manera eficiente, encontrando isometrías para $s=10^7$ estados en aproximadamente 10–20 minutos en hardware de CPU estándar.
• Comparación: El método propuesto supera a la literatura existente (por ejemplo, [4, 14, 20, 21]) en términos de recuento de Toffoli manteniendo un exceso de qubits comparable o incluso inferior.

Significado y Reivindicaciones
El artículo afirma presentar los circuitos de preparación de estados dispersos más eficientes de la literatura en términos de recuento de Toffoli y de qubits. La significancia reside en:

1. Eliminación del Cuello de Botella: Al reducir el coste de la isometría de ser el factor dominante a un nivel comparable con la preparación densa, el algoritmo general se vuelve más eficiente.
2. Escalabilidad: El enfoque escala favorablemente con el número de qubits $n$, lo que lo hace adecuado para algoritmos cuánticos de gran escala donde $s$ es grande pero $s \ll 2^n$.
3. Practicidad: El método es compatible con los marcos de estimación de recursos para computación tolerante a fallos existentes (centrados en el recuento de Toffoli) y está implementado en un marco de software modular (Qualtran).

Los autores mantienen la modestia respecto a las implicaciones futuras, señalando que, si bien el recuento de Toffoli es la métrica estándar actual, los avances en la generación de estados mágicos (cultivo/destilación) podrían desplazar el enfoque hacia métricas de tiempo de ejecución en el futuro. También dejan abierta la cuestión de si es posible lograr costes de Toffoli sublineales en $s$ con recursos de ancilla limitados.