Quantumly controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms

Resumen Técnico: Medición Controlada Cuánticamente, Conjugación Hermítica y Normalización en Algoritmos de Manipulación de Matrices

Planteamiento del Problema
El artículo aborda tres limitaciones críticas en los algoritmos cuánticos existentes para la manipulación de matrices (específicamente aquellos basados en la codificación de los elementos de la matriz en las amplitudes de probabilidad de un estado de superposición pura, como se propone en las Refs. [33–35]):

1. Ineficiencia de la Post-selección: Los algoritmos actuales dependen de la medición de un ancilla de un solo qubit para filtrar los estados de "basura" (garbage states) y seleccionar el resultado deseado. Este proceso sufre de una baja probabilidad de éxito que disminuye de forma polinómica o exponencial con la dimensión de la matriz. En consecuencia, el algoritmo requiere múltiples ejecuciones para lograr el resultado deseado, reduciendo severamente la eficiencia.
2. Incapacidad para Manejar la Conjugación Hermítica: Aunque estos algoritmos generalmente manejan matrices complejas, operaciones específicas como la conjugación hermítica no pueden realizarse dentro del marco de codificación estándar, lo que restringe la variedad de las manipulaciones algebraicas.
3. Restricciones Estrictas de Normalización: La codificación de los elementos de la matriz en un estado cuántico puro impone una condición de normalización estricta ($\sum |a_{jk}|^2 = 1$). Esto limita el módulo de los elementos de la matriz, requiriendo un escalado específico que puede no ser óptimo para todas las aplicaciones.

Metodología
Los autores proponen tres extensiones distintas al marco de manipulación de matrices:

1. Medición Controlada Cuánticamente (QCM - Quantumly Controlled Measurement):

   • En lugar de una medición proyectiva estándar sobre un único qubit ancilla ($B_1$), los autores introducen un sistema ancilla de dos qubits ($B_1$ y $B_2$).
   • El estado del primer qubit ($B_1$) actúa como un control para un operador de medición aplicado al segundo qubit ($B_2$).
   • Específicamente, si el sistema se encuentra en una superposición donde el término "útil" está entrelazado con $|1\rangle_{B_1}$ y la "basura" con $|0\rangle_{B_1}$, una puerta C-NOT entrelaza $B_1$ con $B_2$. Se aplica entonces un operador de medición controlado $W^{(3)}_{B_1B_2} = |1\rangle_{B_1}\langle 1| \otimes M_{B_2} + |0\rangle_{B_1}\langle 0| \otimes I_{B_2}$.
   • Este mecanismo asegura que, si el componente útil existe ($\alpha \neq 0$), la medición en $B_2$ se activa de manera determinista, colapsando el sistema al estado deseado sin el fallo probabilístico asociado con la post-selección estándar.

2. Codificación Separada de las Partes Real e Imaginaria:

   • Para permitir la conjugación hermítica, los autores proponen codificar las partes real e imaginaria de los elementos de la matriz compleja en dos subespacios ortogonales utilizando un subsistema adicional de un qubit ($M$).
   • El estado $|0\rangle_M$ etiqueta la parte real y el estado $|1\rangle_M$ etiqueta la parte imaginaria.
   • La conjugación hermítica se realiza entonces mediante una operación SWAP en los registros de filas/columnas combinada con una operación $\sigma_z$ en el registro $M$, realizando efectivamente la transposición y la conjugación compleja.

3. Debilitamiento de la Restricción de Normalización:

   • Los autores introducen un qubit auxiliar adicional ($K$) al esquema de codificación.
   • El estado inicial se modifica para incluir un término extra con amplitud $b$ asociado al estado $|0\rangle_K$, mientras que los elementos de la matriz se asocian con $|1\rangle_K$.
   • Esto cambia la condición de normalización de una igualdad ($\sum |a_{jk}|^2 = 1$) a una desigualdad ($\sum |a_{jk}|^2 \leq 1$), permitiendo una mayor flexibilidad en la magnitud de los elementos de la matriz.

Contribuciones Clave y Resultados

• Implementación en Multiplicación de Matrices: Los autores integran QCM y las dos extensiones de codificación en un algoritmo de multiplicación de matrices. Demuestran que el algoritmo puede realizar la multiplicación estándar así como operaciones que involucran conjugados hermíticos (por ejemplo, $A^\dagger B$, $A B^\dagger$).
• Construcción de Circuitos: Se presentan circuitos cuánticos detallados para:
  • La subrutina QCM.
  • El operador de conjugación hermítica.
  • El algoritmo de multiplicación de matrices modificado incorporando las tres extensiones.
• Análisis de Complejidad:
  • Espacio: Las modificaciones requieren solo un número constante de qubits adicionales (específicamente, cuatro qubits adicionales para las extensiones de codificación y uno para el ancilla de QCM en el contexto de la multiplicación). La complejidad de espacio permanece en $O(n)$, donde $N=2^n$ es la dimensión de la matriz.
  • Profundidad: La profundidad del circuito permanece en $O(n)$. Los autores señalan que, si bien el tiempo de ejecución total de algoritmos previos era efectivamente $O(2^n n)$ debido a la necesidad de múltiples ejecuciones para superar las bajas probabilidades de éxito, el algoritmo basado en QCM logra el resultado en una sola ejecución, manteniendo la característica de profundidad $O(n)$ del propio circuito.
• Recuperación de la Normalización: Los autores reconocen que QCM elimina la información probabilística respecto a la constante de normalización $G$ (que anteriormente se derivaba de la probabilidad de éxito de la medición). Proponen un método para medir $G$ probabilísticamente ejecutando el algoritmo múltiples veces para medir la probabilidad del estado auxiliar $|0\rangle_K$, aunque esto requiere ejecuciones separadas de la generación de resultados de disparo único (single-shot).

Significancia y Reivindicaciones
El artículo afirma que la introducción de la Medición Controlada Cuánticamente (QCM) resuelve fundamentalmente el "problema de la post-selección" inherente a los algoritmos de manipulación de matrices basados en la medición. Al reemplazar el filtrado probabilístico de los estados de basura por un proceso controlado cuánticamente determinista, el algoritmo elimina la sobrecarga exponencial asociada con las ejecuciones repetidas.

Los autores enfatizan que QCM no es meramente una técnica de amplificación de amplitud (como el algoritmo de Grover), sino un operador distinto que combina el control cuántico con la medición clásica, ofreciendo potencialmente un nuevo tipo de "control cuántico-clásico".

Además, las extensiones relativas a la conjugación hermítica y las restricciones de normalización relajadas amplían la aplicabilidad de los algoritmos de manipulación de matrices a una clase más amplia de matrices complejas y escenarios de codificación de datos. Los autores afirman que estas modificaciones pueden aplicarse no solo a la multiplicación de matrices, sino también a otros algoritmos discutidos en las Refs. [34, 35], incluyendo la suma de matrices, el cálculo de determinantes, la inversión y los resolvedores de sistemas lineales, así como otros algoritmos cuánticos basados en la medición.