Researchers at Chongqing University of Posts and Telecommunications and University of Otago develop two quantum granular-ball generation methods—iterative splitting and fixed-split—to accelerate KNN classification. They map classical data into qubit rotation angles, compute fidelities with swap tests and QADC, and leverage quantum minimum search to cluster samples into granular-balls, achieving significant time complexity reductions over classical approaches.
Key points
Iterative splitting algorithm encodes dataset and center points into qubit rotation angles using QRAM and CRY gates for efficient data preparation.
Fidelities between samples and centers are computed via swap test and abs-QADC with phase estimation to embed distance information in digital registers.
Quantum minimum search assigns each data point to its nearest granular-ball center, achieving O((log^2 N) N^1/4) depth for the fixed-split method.
Why it matters:
This quantum granular-ball method reduces KNN clustering complexity, paving the way for scalable, high-speed quantum machine learning on large datasets.
Q&A
What is a granular-ball?
How does the swap test measure similarity between points?
What role does quantum analog-to-digital conversion play?
Why is the fixed-split method faster than classical approaches?
Read full article
Academy
Quantum Machine Learning
Quantum Machine Learning is an emerging field at the intersection of quantum computing and artificial intelligence, aiming to exploit quantum mechanical phenomena to accelerate or enhance classical machine learning tasks. By leveraging qubits, superposition, and entanglement, quantum algorithms can process and analyze data in fundamentally new ways.
In classical computing, data is encoded in bits that are either 0 or 1. In quantum computing, qubits can exist in a superposition of 0 and 1 simultaneously, enabling quantum systems to represent an exponentially large amount of information with relatively few qubits. Entanglement between qubits allows correlated operations across distant elements of a quantum register, which classical computers cannot mimic efficiently.
Key Components
- Data Encoding: Classical data must be mapped to quantum states. Common approaches include amplitude encoding (storing data in the amplitudes of a quantum state) and angle encoding (using rotation angles of single-qubit gates such as RY and RX).
- QRAM (Quantum Random Access Memory): A theoretical model for storing and retrieving data in superposition. QRAM architectures like bucket-brigade allow accessing large datasets in logarithmic time, essential for scalable quantum data preparation.
- Swap Test: A quantum circuit used to measure the fidelity (inner product) between two quantum states. It forms the basis for quantum distance or similarity calculations, which replace Classical distance metrics in algorithms such as quantum KNN.
- Quantum Phase Estimation (QPE): A subroutine that extracts the phase (analog information) of an eigenstate of a unitary operator into a digital register. QPE underlies many quantum algorithms, including quantum Fourier transform and analog-to-digital conversion routines (QADC).
- Quantum Minimum Search: A search algorithm that finds the minimum value among encoded quantum data points more efficiently than classical scanning, using amplitude amplification techniques.
Quantum KNN Classification
Quantum K-Nearest Neighbors (QKNN) uses the swap test and amplitude-based search to identify the k closest training examples to a new test point. Recent advances propose quantum granular-ball generation, which groups training data into overlapping “balls” that capture overall data structure. Quantum algorithms generate these granular-balls in parallel, significantly reducing time complexity compared to classical splitting methods.
Applications and Outlook
Quantum machine learning holds promise in areas where large-scale data analysis is critical, such as drug discovery, materials science, and genomics. In longevity research, quantum algorithms could accelerate the classification of complex biochemical data, enhance biomarker discovery, and optimize predictive models for aging interventions. As hardware matures, accessible quantum ML frameworks will enable broader adoption in both academic and industrial longevity science.
