💻 computer science

Multi-class quantum k-nearest-neighbour classification in a single quantum circuit

Este artículo presenta un novedoso circuito cuántico, totalmente implementable, para la clasificación de k-vecinos más cercanos multiclase que elimina la dependencia de primitivas hipotéticas como la memoria RAM cuántica o los oráculos mediante el uso de superposición, una red de mariposa de compuertas SWAP controladas y un análisis de fidelidad geométrica para lograr comparaciones precisas de ejecución única con costos operativos explícitamente declarados.

Autores originales: Razieh Abdolahi, M. Reza Soleymani, Walaa Hamouda

Publicado 2026-10-08

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Razieh Abdolahi, M. Reza Soleymani, Walaa Hamouda

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el mundo de la informática, algunos problemas son sencillos de plantear pero increíblemente difíciles de resolver cuando la cantidad de datos crece. Uno de esos desafíos es encontrar la coincidencia más cercana en una vasta biblioteca de información. Imagine a un bibliotecario que debe encontrar el libro más similar a una nueva solicitud comparándolo con cada uno de los volúmenes en los estantes. En una computadora clásica, este proceso requiere revisar cada elemento uno por uno, una tarea que se vuelve dolorosamente lenta a medida que la biblioteca se expande. Este es el núcleo del problema de los "k-vecinos más cercanos", una herramienta fundamental utilizada en todo, desde el diagnóstico médico hasta la recomendación de películas. Durante décadas, los científicos han esperado que las computadoras cuánticas, que pueden procesar la información de una manera fundamentalmente distinta, pudieran resolver este problema de búsqueda de forma instantánea. Sin embargo, los intentos previos de construir una versión cuántica de esta herramienta de búsqueda se han basado en atajos teóricos que aún no existen en el mundo real, o se han limitado a resolver solo problemas muy simples de dos opciones.

Un equipo de investigadores de la Universidad de Concordia ha demostrado ahora una nueva forma de realizar esta búsqueda que funciona sin esos atajos imposibles. Han diseñado un circuito cuántico que puede comparar una única consulta con una vasta colección de datos de entrenamiento, incluyendo muchas categorías diferentes, todo dentro de una sola ejecución de la máquina. Su trabajo demuestra que es posible construir un clasificador cuántico que maneje múltiples clases de datos simultáneamente, sin necesidad de dispositivos de memoria hipotéticos que puedan acceder instantáneamente a cualquier pieza de datos. En lugar de depender de la magia o de tecnología no probada, construyeron un sistema utilizando operaciones físicas estándar que pueden ejecutarse en hardware cuántico real. El resultado es una máquina que, en simulación, iguala la precisión de los mejores métodos clásicos mientras ofrece un nuevo camino arquitectónico que no requiere que todo el conjunto de entrenamiento se cargue en un banco de memoria separado y masivo.

Los investigadores comenzaron abordando el problema de cómo traducir los datos ordinarios a un lenguaje que una computadora cuántica pueda entender. Las máquinas cuánticas operan sobre estados que deben tener un tamaño matemático específico, de forma muy parecida a un globo que debe inflarse a un volumen preciso para mantener su forma. Si simplemente se reduce un objeto grande para que quepa, se pierde información sobre su tamaño original. El equipo utilizó una técnica matemática llamada proyección estereográfica inversa para mapear sus datos sobre una esfera. Este proceso es ingenioso porque preserva el tamaño y la forma originales de los puntos de datos mientras los ajusta al formato cuántico requerido. Al hacer esto, aseguraron que la distancia entre dos puntos en los datos originales se refleje fielmente en la distancia entre sus representaciones cuánticas. Este paso fue crucial; sin él, la computadora cuántica estaría comparando sombras distorsionadas en lugar de los objetos reales, lo que conduciría a respuestas incorrectas.

Una vez que los datos fueron correctamente codificados, el equipo construyó un circuito que actúa como un gigantesco motor de comparación. En un enfoque tradicional, una computadora compararía la nueva consulta con el primer punto de entrenamiento, luego con el segundo, luego con el tercero, y así sucesivamente, uno por uno. El circuito cuántico descrito en este artículo hace algo más radical: coloca todos los datos de entrenamiento en un estado de superposición, donde existen en una combinación de todos los estados posibles a la vez. El circuito utiliza entonces una red de intercambios controlados (controlled swaps), que pueden pensarse como un sofisticado mecanismo de clasificación, para enrutar los datos. Esta red permite que la computadora cuántica compare la consulta contra cada uno de los puntos de entrenamiento de cada una de las clases simultáneamente. La máquina no necesita revisarlos secuencialmente; evalúa la biblioteca entera de un solo golpe.

El corazón del proceso de medición se basa en una técnica conocida como la prueba SWAP (SWAP test). Este es un procedimiento que comprueba qué tan similares son dos estados cuánticos. Si dos estados son idénticos, la prueba produce un resultado; si son diferentes, produce otro. Los investigadores diseñaron su circuito de modo que la probabilidad de obtener un resultado de medición específico esté directamente vinculada a qué tan cerca está un punto de entrenamiento de la consulta. Al ejecutar el circuito muchas veces y contar los resultados, la máquina construye una imagen estadística de cuáles puntos de entrenamiento son las coincidencias más cercanas. Crucialmente, el circuito también realiza un seguimiento de a qué clase pertenece cada vecino más cercano. Esto permite que el sistema realice una votación por mayoría, decidiendo la etiqueta final basándose en los vecinos más cercanos, tal como lo haría un humano si consultara a un grupo de expertos para obtener su opinión.

El equipo probó su diseño utilizando un banco de pruebas que involucraba cuatro categorías diferentes de datos, con miles de comparaciones simuladas. Encontraron que el circuito cuántico reproducía exactamente las reglas de decisión del método clásico. En el límite de mediciones infinitas, el sistema cuántico y el sistema clásico coincidieron en cada uno de los casos de prueba. Incluso con un número realista de mediciones, el clasificador cuántico igualó la precisión clásica con un margen muy pequeño, diferenciándose en menos del uno por ciento en los escenarios más difíciles. Este nivel de rendimiento es significativo porque demuestra que el enfoque cuántico no sacrifica la precisión por la velocidad o la complejidad. El sistema identificó con éxito los vecinos correctos y asignó las etiquetas correctas, demostiendo que la lógica subyacente se sostiene bajo escrutinio.

Una gran fortaleza de este trabajo es que evita la necesidad de una Memoria de Acceso Aleatorio Cuántico, o QRAM. Muchas propuestas anteriores de aprendizaje automático cuántico asumían la existencia de esta tecnología, la cual permitiría a una computadora cuántica recuperar instantáneamente cualquier pieza de datos de un enorme banco de almacenamiento. Sin embargo, la QRAM sigue siendo un concepto teórico que no ha sido construido y que puede ser físicamente imposible de construir a escala. El nuevo diseño no utiliza QRAM. En su lugar, carga los datos directamente en los registros del circuito. Aunque este proceso de carga toma tiempo proporcional al tamaño de los datos, es un paso práctico e implementable que no depende de hardware hipotético. Los investigadores fueron transparentes sobre este costo, señalando que el tiempo dedicado a cargar los datos es actualmente el principal cuello de botella, pero demostraron que la parte de la comparación es altamente eficiente y no requiere que los datos se almacenen en una memoria separada e inaccesible.

Los investigadores también compararon su método con otros enfoques cuánticos que se han propuesto en años recientes. Encontraron que los métodos que dependen de diferentes tipos de codificación de datos a menudo perdían información importante sobre el tamaño de los puntos de datos, lo que conducía a una menor precisión. Su enfoque, que preserva la geometría completa de los datos, funcionó tan bien como los mejores métodos clásicos y mejor que otras propuestas cuánticas que dependían de codificaciones menos completas. Además, cuando contaron el número total de componentes físicos requeridos, incluyendo la memoria necesaria para contener los datos, su diseño resultó más eficiente que los métodos basados en QRAM para conjuntos de datos de cierto tamaño. Esto sugiere que su arquitectura no es solo una curiosidad teórica, sino un camino viable para el hardware futuro.

El estudio concluye que es posible construir un clasificador cuántico multiclasificación que funcione en un solo circuito sin depender de tecnología no probada. El sistema traduce con éxito los datos clásicos a estados cuánticos, compara una consulta contra un conjunto completo de datos simultáneamente y lee los resultados con alta precisión. Si bien la velocidad actual del sistema está limitada por el tiempo que toma cargar los datos, la arquitectura en sí es sólida y modular. Esto significa que, a medida que los científicos desarrollen mejores formas de cargar datos en las computadoras cuánticas, este diseño de circuito específico puede beneficiarse de inmediato de esas mejoras sin necesidad de ser rediseñado. El trabajo proporciona una demostración clara y concreta de cómo se puede aprovechar la interferencia cuántica para resolver un problema de búsqueda clásico, acercando el campo un paso más hacia aplicaciones prácticas donde las máquinas cuánticas puedan asistir genuinamente en el análisis de datos complejos.

Resumen Técnico: Clasificación de k-Vecinos Más Cercanos Cuánticos Multiclase en un Único Circuito Cuántico

1. Planteamiento del Problema

El artículo aborda el desafío de implementar un clasificador de k-vecinos más cercanos (kNN) multiclase en hardware cuántico sin depender de primitivas hipotéticas. Las propuestas de kNN cuánticos (qkNN) existentes suelen depender de:

Memoria de Acceso Aleatorio Cuántico (QRAM) o acceso por oráculo para la carga de datos, los cuales aún no se han materializado físamente a escala.
Métricas de distancia restrictivas (por ejemplo, métricas de Hamming o polares) que requieren discretización o pierden información de magnitud.
Limitaciones de clase binaria o arquitecturas que requieren procesamiento post-clásico para determinar las etiquetas de clase.
Evaluación por pares, donde se ejecutan circuitos separados para cada punto de entrenamiento, lo que genera una alta sobrecarga de recursos.

Los autores buscan diseñar una arquitectura de un solo circuito que compare una consulta contra todos los miembros de todas las clases simultáneamente, utilice la métrica euclidiana (la más aplicable ampliamente) y devuelva etiquetas de clase directamente desde las estadísticas de medición, todo ello evitando las suposiciones de QRAM y de oráculo.

2. Metodología

2.1 Preprocesamiento: Proyección Estereográfica Inversa (ISP)

Para mapear datos euclidianos clásicos ( $\mathbb{R}^d$ ) en el espacio de estados cuánticos (hiperesfera unitaria $S^d \subset \mathbb{R}^{d+1}$ ), los autores emplean la Proyección Estereográfica Inversa (ISP).

Mapeo: Un vector $z$ se mapea mediante $\Phi(z) = \frac{1}{1+\|z\|^2}(2z_1, \dots, 2z_d, 1-\|z\|^2)$ .
Preservación de la Norma: A diferencia de la normalización estándar ( $z \to z/\|z\|$ ), la ISP preserva la magnitud del vector de entrada en la coordenada final, evitando la pérdida de información.
Transformación de Distancia: El artículo deriva una expresión en forma cerrada para la distancia cordal en la esfera. Demuestra que, si bien el mapeo es no lineal, el orden de los k-vecinos más cercanos se preserva con un factor de distorsión acotado $\sqrt{\alpha}$ (donde $\alpha = 1+R^2$ y $R$ es el límite de amplitud de los datos).
Selección de Escala: Los autores seleccionan una escala de datos de $R=1$ (entradas escaladas a $\|z\| \in [0,1]$ ). Esto equilibra la fidelidad del ordenamiento (minimizando la distorsión) frente a la capacidad de resolución estadística del test SWAP (asegurando una separación angular suficiente para la medición).

2.2 Codificación Cuántica

Codificación de Ángulo Densa: Las coordenadas proyectadas se codifican en cúbits mediante codificación de ángulo densa. Los pares de coordenadas $(a_k, b_k)$ se mapean a un estado de cúbit único $|q_k\rangle = \cos(\theta_k/2)|0\rangle + e^{i\phi_k}\sin(\theta_k/2)|1\rangle$ .
Eficiencia de Cúbits: Cada punto de datos ocupa $n_q = \lceil(d+1)/2\rceil$ cúbits, aproximadamente la mitad del ancho requerido por la codificación estándar de una coordenada por cúbit.

2.3 Arquitectura de Circuito: Comparación Multiclase de un Solo Circuito

La innovación central es una "codificación de superposición de clases" y una red de mariposa de puertas controladas-SWAP (CSWAP).

Estado de Superposición de Clases: Para cada clase $k$ , los miembros de entrenamiento se cargan en un registro dedicado en superposición: $|C_k\rangle = \frac{1}{\sqrt{2^m}}\sum_{j=0}^{2^m-1} |\phi^{(k)}_j\rangle|j\rangle$ , donde $|j\rangle$ es el índice del miembro.
Red de Mariposa: Una red de $\lceil \log_2 l \rceil$ etapas de CSWAP (donde $l$ es el número de clases) enruta los registros de clase. En una única ejecución, la consulta se compara contra todos los $l \times 2^m$ puntos de entrenamiento simultáneamente.
Test SWAP: Un test SWAP final entre el registro de clase enrutado y el registro de la consulta estima la fidelidad (similitud).
Medición y Lectura: El circuito mide los cúbits ancila y los cúbits de índice de miembro. La probabilidad de medir un resultado específico $(j, k)$ con la ancila final en el estado $|1\rangle$ es inversamente proporcional a la fidelidad entre la consulta y el $j$ -ésimo miembro de la clase $k$ .
Clasificación: Se seleccionan los $K$ resultados con las probabilidades más bajas (mayor fidelidad). La etiqueta predicha se determina mediante el voto mayoritario de los índices de clase en estos $K$ resultados. No se requiere procesamiento clásico de los índices para identificar la clase; la clase está codificada en las estadísticas de medición.

3. Contribuciones Clave

Codificación de Superposición de Clases: Un método para cargar los miembros de cada clase en superposición, permitiendo que una única ejecución de circuito compare una consulta contra todos los datos de entrenamiento a través de todas las clases. La identidad de la clase se lee directamente de las estadísticas de medición.
Fundamento Analítico: Una expresión en forma cerrada para las probabilidades de medición post-seleccionadas del circuito. Los autores demuestran que el circuito implementa exactamente la regla de decisión prevista en el límite de infinitos disparos (infinite-shot limit).
Análisis Geométrico: Un análisis riguroso de la ISP que muestra cómo preserva los órdenes de k-vecinos más cercanos euclidianos con un límite de distorsión agudo ( $\sqrt{2}$ en $R=1$ ). Esto establece que la proyección no degrada la precisión de la clasificación.
Arquitectura de Recursos Eficientes: Un diseño que no requiere QRAM ni oráculos. El ancho del circuito es lineal en el número de clases y logarítmico en el número de miembros por clase. La profundidad es lineal en el número de clases.
Benchmarking Exhaustivo: Una comparación justa de múltiples reglas de decisión de kNN cuántico sobre un benchmark gaussiano común, aislando el impacto de la codificación y las métricas de distancia del ruido de hardware y del ruido de disparo (shot noise).

4. Resultados

Preservación de la Precisión: Las simulaciones en benchmarks gaussianos de cuatro clases ( $d=3$ , variando la dispersión de los grupos) muestran que el ordenamiento de fidelidad basado en ISP coincide con la precisión del kNN euclidiano clásico dentro de 1 punto porcentual en todos los niveles de separabilidad.
Corrección del Circuito: En el límite de infinitos disparos, el circuito de 29 cúbits produce predicciones idénticas a la regla de decisión teórica (320/320 puntos de prueba coincidieron).
Rendimiento de Disparos Finitos: Con un presupuesto realista de disparos ( $2.62 \times 10^5$ ), el circuito sigue la línea base clásica con una diferencia de 5 de 80 muestras de prueba (aprox. 6.25%), con discrepancias atribuidas al ruido de disparo en casos marginales.
Comparación con Trabajos Previos:
- Codificación de Amplitud: Los métodos que dependen de la fidelidad de amplitud (por ejemplo, Basheer et al.) tuvieron un rendimiento inferior por 5–12 puntos porcentuales en datos informativos de norma debido a que la codificación de amplitud estándar descarta la información de magnitud.
- Suposiciones de QRAM: Al contar la memoria física necesaria para almacenar los datos, el método de los autores (29 cúbits para el benchmark) requiere menos recursos que los métodos basados en QRAM para conjuntos de entrenamiento mayores a 32 puntos, ya que los métodos de QRAM requieren implícitamente $\Theta(N)$ celdas de memoria no contabilizadas en sus estimaciones de "cúbits".
- Binario vs. Multiclase: El método propuesto maneja con éxito problemas multiclase, mientras que algunos métodos previos basados en interferencia son inherentemente binarios.

5. Significado y Reivindicaciones

El artículo reclama un avance estructural más que una aceleración asintótica. La significancia radica en:

Eliminación de Primitivas Hipotéticas: Demuestra un clasificador kNN multiclase que funciona sin QRAM ni oráculos, utilizando únicamente puertas implementables (Hadamard y CSWAP).
Eficiencia de un Solo Circuito: Reemplaza $N$ comparaciones por pares separadas con un único circuito más ancho, exponiendo todas las clases de vecinos en una sola medición.
Paridad de Precisión: Logra una precisión comparable al kNN euclidiano clásico, demostrando que las transformaciones geométricas necesarias (ISP) y las codificaciones cuánticas no degradan intrínsecamente el rendimiento.
Transparencia en el Costo: Los autores declaran explícitamente que el cuello de botella sigue siendo la preparación del estado (carga de datos), que es $\Omega(N)$ por ejecución sin QRAM. Argumentan que su arquitectura es modular; cualquier mejora futura en la preparación de estados (por ejemplo, cargadores variacionales) puede integrarse para reducir el costo dominante sin alterar la red de comparación.

Los autores concluyen que la arquitectura hace avanzar el campo al proporcionar un marco práctico y libre de QRAM para la clasificación multiclase que iguala la precisión clásica, siendo los desafíos restantes aquellos de la preparación eficiente de estados comunes a todos los clasificadores cuánticos.