An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group

Planteamiento del problema

El artículo aborda el desafío computacional de preparar estados cuánticos correspondientes a las columnas de la tabla de caracteres del grupo simétrico $S_n$. Específicamente, para un tipo de ciclo $\nu$ dado (una partición de $n$), el objetivo es preparar el estado de columna de carácter:
$$|\chi_\nu\rangle := \frac{1}{\sqrt{z_\nu}} \sum_{\lambda \vdash n} \chi_\lambda(\nu) |\lambda\rangle$$
donde $\chi_\lambda(\nu)$ es el carácter de la representación irreducible (irrep) $\lambda$ evaluado en la clase de conjugación $\nu$, y $z_\nu$ es el factor de normalización.

Si bien se sabe que la evaluación de entradas individuales de caracteres es $\#P$-dura en el peor de los casos, se ha propuesto que el muestreo de la distribución de probabilidad $P_\nu(\lambda) = |\langle \lambda | \chi_\nu \rangle|^2$ es un candidato para la ventaja cuántica. Un trabajo previo por Bravyi et al. [1] demostró que dicho muestreo podría lograrse mediante la Transformada de Fourier Cuántica (QFT) sobre $S_n$, pero la mejor implementación conocida de esta QFT requiere $\tilde{O}(n^3)$ puertas y $\tilde{O}(n^{3/2})$ cúbits. Los autores buscan un método más eficiente y directo que evite la QFT completa, particularmente uno adecuado para hardware de corto plazo con cúbits reconfigurables.

Metodología

Los autores proponen un algoritmo basado en el Hamiltoniano que evita la QFT implementando directamente el mecanismo de transferencia requerido para generar los estados de carácter.

1. Codificación fermiónica y mecanismo de transferencia:
El algoritmo se basa en la codificación fermiónica de los caracteres de $S_n$ establecida por Crichigno y Prakash [11] y Bravyi et al. [1]. En esta codificación, el estado semilla $|1^n 0^n\rangle$ corresponde a la partición vacía, y la aplicación de una secuencia de operadores de corriente $J_\nu = J_{\nu_1} \dots J_{\nu_\ell}$ genera el carácter de columna no normalizado.
Dado que $J_s$ (el operador de corriente para la longitud de ciclo $s$) no es unitario, los autores introducen un mecanismo de transferencia utilizando un único cúbit ancilla. Definen un Hamiltoniano:
$$H_s = |1\rangle\langle 0|_a \otimes J_s + |0\rangle\langle 1|_a \otimes J_s^\dagger$$
Al evolucionar bajo $H_s$ durante un tiempo preciso $t_{s,j} = \pi / (2\sqrt{\zeta})$, donde $\zeta$ es un autovalor de $J_s^\dagger J_s$, el sistema realiza una rotación de Rabi exacta que mapea $|0\rangle_a |\phi\rangle \to |0\rangle_a (J_s |\phi\rangle / \sqrt{\zeta})$.

2. La propiedad de escalera (Ladder Property):
Un insight crítico es la propiedad de escalera de los operadores de corriente. Los autores demuestran que los estados visitados por el algoritmo son autovectores de $J_s^\dagger J_s$ con autovalores enteros conocidos ($s \cdot j$ para la $j$-ésima transferencia de longitud $s$). Esto permite que los tiempos de evolución se fijen a priori, permitiendo la preparación de estados determinista sin post-selección.

3. Dos estrategias de implementación:
El artículo presenta dos métodos distintos para simular la evolución del Hamiltoniano $e^{-iH_s t}$:

• Descomposición de Trotter con cúbits reconfigurables:

  • El Hamiltoniano $H_s$ se descompone en términos de vecinos más cercanos mediante el reordenamiento de los modos fermiónicos a través de una permutación $P_s$ que agrupa los sitios por residuo módulo $s$.
  • Utilizando el protocolo de permutación fermiónica rápida para cúbits reconfigurables (por ejemplo, arreglos de átomos neutros) de Maskara et al. [16], la permutación $P_s$ se implementa con $O(n)$ puertas en profundidad constante.
  • La evolución se simula mediante la trotterización de primer orden. Los autores realizan un análisis de error dependiente del estado, mostrando que los errores de conmutador son significativamente menores en los estados específicos visitados por el algoritmo de lo que sugieren las cotas de norma de operador del peor de los casos.

• Transformada de Valor Singular Cuántica (QSVT):

  • Para proporcionar un límite riguroso del peor de los casos, los autores construyen un codificación de bloque (block-encoding) de $H_s$ utilizando cadenas de Pauli.
  • Aplican QSVT para simular la evolución con una dependencia logarítmica de la inversa del error $1/\delta$.
  • Este enfoque se extiende a la Transformada de Carácter Cuántica (QCT), que mapea coherentemente superposiciones de tipos de ciclo a superposiciones de estados de carácter. La QCT implica "borrar" los registros de tipo de ciclo después de los pasos de transferencia usando estimación de fase en el operador $N_s = J_s J_s^\dagger / s$, amplificado mediante amplificación de valor singular para reducir los costos de puertas.

Contribuciones clave y resultados

1. Mejora en la complejidad de puertas:

• CSP basada en QSVT: Los autores demuestran que la Preparación de Estados de Carácter (CSP) para cualquier tipo de ciclo puede lograrse con $\tilde{O}(n^{5/2})$ puertas y $O(n)$ cúbits. Esto mejora el conteo de puertas $\tilde{O}(n^3)$ del enfoque basado en QFT.
• Transformada de Carácter Cuántica (QCT): Proporcionan la primera cota polinómica explícita de puertas para la QCT completa sobre $S_n$ general, que también escala como $\tilde{O}(n^{5/2})$ con $O(n)$ cúbits.

2. Cotas de Trotter dependientes del estado:

• Para tipos de ciclos uniformes $\nu = (s^m)$, los autores derivan una cota de error de Trotter de orden principal dependiente del estado.
• En el régimen propuesto para la ventaja cuántica ($m = \Theta(\sqrt{n}/\log n)$), el conteo de puertas suficiente estimado es $\tilde{O}(n^{7/4}/\delta)$.
• Las simulaciones numéricas hasta $n=48$ sugieren que los conteos de puertas reales requeridos son incluso menores que estas cotas analíticas, escalando aproximadamente como $n^{1.2}$ a $n^{1.5}$ para varios tipos de ciclos, lo que indica que las cotas analíticas son conservadoras.

3. Análisis de complejidad clásica:

• El artículo desafía la suposición de que todos los tipos de ciclos en el "régimen de granularidad" (donde Bravyi et al. argumentan para la ventaja cuántica) son clásicamente difíciles.
• Presentan algoritmos de muestreo clásicos exactos para ciclos uniformes ($\nu = (s^m)$) y ciclos casi uniformes (perturbaciones de ciclos uniformes por un número constante de ciclos excepcionales).
• Estos muestreadores clásicos corren en tiempo esperado $\tilde{O}(n^2)$ para ciclos uniformes y $n^{4b+O(1)}$ para ciclos casi uniformes con $b$ ciclos excepcionales. Esto implica que la ventaja cuántica en este régimen requiere tipos de ciclos donde el número de ciclos excepcionales crezca con $n$.

4. Aplicación a CFTs:

• La QCT inversa se aplica para estimar la entropía de defecto en las Teorías de Campo Conforme (CFT) de orbifold simétrico. Al medir la salida de la QCT inversa, uno puede muestrear tipos de ciclo $\nu$ con una probabilidad proporcional a los pesos en la fórmula de la entropía de defecto. Los autores muestran que esto permite una estimación eficiente de la entropía con un error aditivo de $O(\sqrt{n})$, que se convierte en un error relativo evanescente para representaciones irreducibles genéricas donde la entropía escala como $\Theta(n)$.

Significado y afirmaciones

El artículo afirma proporcionar una alternativa más simple y eficiente al enfoque basado en QFT para acceder a los caracteres del grupo simétrico. Al aprovechar la evolución del Hamiltoniano y la estructura algebraica específica de los operadores de corriente (la propiedad de escalera), los autores logran una reducción demostrable en la complejidad de puertas de $\tilde{O}(n^3)$ a $\tilde{O}(n^{5/2})$.

La importancia es doble:

1. Teórica: Establece la primera cota polinómica explícita para la QCT sobre $S_n$ general y refina la comprensión del panorama de dureza clásica, mostrando que los ciclos uniformes (un candidato clave) son clásicamente tratables.
2. Práctica: La implementación basada en Trotter está diseñada explícitamente para arquitecturas de cúbits reconfigurables (como arreglos de átomos neutros), utilizando puertas de vecinos más cercanos y permutaciones rápidas. Los puntos de referencia numéricos sugieren que este enfoque es un candidato viable para realizar la ventaja cuántica de corto plazo, siempre que los tipos de ciclos elegidos involucren un número creciente de ciclos excepcionales para asegurar la dureza clásica.

Los autores se mantienen modestos respecto a las cotas de Trotter, señalando que sus cotas rigurosas del peor de los casos son probablemente sobreestimaciones laxas en comparación con el rendimiento empírico observado en las simulaciones, y que el análisis de error completo más allá del orden principal sigue siendo una cuestión abierta.