(Almost) quadruply optimal unitary designs in 1D

Resumen Técnico: Diseños Unitarios (Casi) Cuádruplemente Óptimos en 1D

Planteamiento del Problema
La construcción de diseños unitarios $k$-aproximados es una tarea fundamental en la información cuántica, que sirve como un sustituto eficiente en recursos de las unitarias de medida de Haar para tareas que van desde el aprendizaje cuántico hasta la caracterización de dispositivos. Mientras que generar unitarias verdaderamente aleatorias de Haar requiere una profundidad de circuito exponencial, los diseños unitarios $k$ imitan la medida de Haar hasta el $k$-ésimo momento. Un desafío central ha sido minimizar la profundidad de circuito requerida para generar estos diseños, particularmente en arquitecturas de 1D con vecinos cercanos, las cuales representan la configuración experimentalmente más accesible.

Las construcciones existentes se han enfrentado a compensaciones (trade-offs). Los primeros análisis de brecha espectral arrojaron límites de profundidad polinómicos, que luego se refinaron a $O(nk \log^7 k)$ y posteriormente a $O(nk)$. Avances recientes utilizando "lemmas de pegado" (gluing lemmas) y circuitos aumentados con magia lograron límites de profundidad de $\tilde{O}(k) \log(n/\epsilon)$ o $O(\log(n/\epsilon) + 2^{O(k \log k)})$ en regímenes específicos. Sin embargo, persistía una brecha: ninguna construcción lograba simultáneamente la escala óptima en el tamaño del sistema $n$, el orden del diseño $k$ y el error $\epsilon$, manteniendo el desacoplamiento entre $n$ y $k$ en la escala de profundidad, todo esto sin cúbits ancilla. Además, el costo de recursos respecto a las compuertas no-Clifford "mágicas" (específicamente las compuertas $T$) no se había optimizado para coincidir con los límites teóricos inferiores.

Metodología
Los autores proponen una construcción que combina y refina dos marcos teóricos existentes: la arquitectura de circuito aumentada con magia (Zhang et al., Ref. [1]) y el conjunto generador de brecha espectral constante para el grupo unitario (Chen et al., Ref. [2]). La estrategia central consiste en una arquitectura de bloques de ladrillo (block-brickwork) de dos capas que actúa sobre una cadena 1D de $n$ cúbits, particionada en parches de tamaño $\xi$.

1. Optimización de Circuitos Aumentados con Magia:
   La construcción utiliza un bloque "aumentado con magia" que consiste en una operación de Clifford aleatoria sándwich entre dos capas de diseños unitarios $k$-aproximados de localidad $\ell$. Un parámetro crítico es la localidad $\ell$ requerida para que las unitarias aleatorias rompan las simetrías adicionales del grupo de Clifford (específicamente, los elementos del conmutante de permutación de Clifford).

   • Refinamiento: Los autores realizan un análisis refinado del conmutante de Clifford bajo simetría de permutación. Al enfocarse en los elementos más cercanos a la identidad, demuestran que la localidad $\ell$ requerida puede reducirse de los $O(k \log k)$ conocidos anteriormente a $O(\log k)$. Esta reducción es crucial para comprimir tanto la profundidad del circuito como el número de compuertas mágicas requeridas.

2. Generadores de Profundidad Constante en 1D:
   Para implementar eficientemente las unitarias aleatorias de $\ell$-cúbits, los autores construyen un conjunto generador para el grupo unitario de $\ell$-cúbits (específicamente el ensamble CPZPC) que posee una brecha espectral constante y es implementable en profundidad constante en una geometría 1D.

   • Grupo de Permutación: Demuestran que los generadores de Kassabov para el grupo de permutación pueden sintetizarse en profundidad constante en un sistema 1D genérico con fronteras abiertas mediante la introducción de una disposición de "cúbit plegado" (folded-qubit layout). Esta disposición asegura que los vecinos cíclicos en la definición del generador se conviertan en vecinos de distancia constante en la cadena física 1D.
   • Grupo de Clifford: Construyen un conjunto generador de tamaño constante y local en 1D para el grupo de Clifford con una constante de Kazhdan $\Omega(1)$. Esto se logra elevando los generadores desde el grupo simpléctico binario (vía el grupo lineal especial) y extendiéndolos al grupo de Clifford completo mediante la extensión de Pauli y generadores de fase. Especifican el tamaño de este conjunto generador a 451 elementos.

3. Pegado (Gluing):
   El diseño final se ensambla utilizando el gluing lemma (Ref. [23]), que permite formar un diseño de $n$-cúbits concatenando bloques más pequeños, siempre que el tamaño del bloque local $\xi$ satisfaga $\xi = \Omega(\log(n/\epsilon) + k)$.

Resultados Clave
El artículo establece el siguiente teorema principal respecto a la construcción de diseños unitarios $k$-aproximados:

• Profundidad de Circuito: Para un sistema de $n$ cúbits y orden de diseño $k = O(n)$, se puede construir un diseño unitario $k$-aproximado con error relativo $\epsilon$ utilizando compuertas locales de 1D sin ancillas. La profundidad del circuito es:
  $$O\left(\log\left(\frac{n}{\epsilon}\right) + k \log k\right)$$
  Esto coincide con el límite inferior conocido $\Omega(\log(n/\epsilon) + k)$ salvo por un único factor $\log k$ en la dirección del orden del diseño.

• Conteo de Compuertas Mágicas: La construcción requiere $O(nk \log k)$ compuertas $T$ (compuertas mágicas). Esto es independiente del parámetro de error $\epsilon$ y mejora los límites superiores previos de $O(\log^2 k (nk + \log(1/\epsilon)))$. Se aproxima al límite inferior de $\Omega(nk / (\log n \log k + \log^2 k))$.

• Régimen: La construcción es válida para órdenes de diseño de hasta $k = \Theta(n)$, extendiendo el régimen factible de diseños de alto orden eficientes más allá del límite previo de $k = O(\sqrt{n})$.

• Contribución Auxiliar: El artículo proporciona un conjunto generador de tamaño constante (451 elementos), local en 1D, para el grupo de Clifford con una brecha espectral constante, un resultado de interés independiente para tareas como el benchmarking aleatorizado.

Significado y Reivindicaciones
Los autores afirman que su construcción logra una "casi optimalidad simultánea en todos los parámetros" (profundidad de circuito, conteo de cúbits, error y recursos mágicos) para arquitecturas 1D. Al reducir la localidad del bloque mágico de $O(k \log k)$ a $O(\log k)$ y proporcionar generadores de profundidad constante en 1D para los elementos de grupo necesarios, casi cierran la brecha entre los límites superiores existentes y los límites fundamentales inferiores.

El artículo señala modestamente que queda un residuo de sobrecarga logarítmica ($\log k$) en la escala del orden del diseño. Sugieren que eliminar esto requeriría reducir la localidad $\ell$ a $O(1)$, lo cual implica analizar la función de Weingarten en un régimen singular. Adicionalmente, aunque el conteo de compuertas mágicas es casi óptimo, permanece una brecha de $O(\log n \log^2 k + \log^3 k)$ entre su límite superior y el límite inferior teórico, lo cual los autores atribuyen a posibles ineficiencias en su construcción o a la pérdida de precisión en la derivación del límite inferior.

El trabajo establece una nueva base para la generación de diseños unitarios eficientes en recursos en sistemas 1D, desacoplando el tamaño del sistema $n$ del orden del diseño $k$ en la escala de profundidad, minimizando simultáneamente los costosos recursos no-Clifford requeridos para la computación cuántica tolerante a fallos.