Table of Contents
- Introduction
- Classical k-Nearest Neighbors (k-NN) Overview
- Motivation for Quantum k-NN (QkNN)
- Quantum State Similarity Measures
- Encoding Classical Data into Quantum States
- Distance Metrics in Quantum Space
- Quantum Fidelity and Inner Products
- Amplitude Encoding for Input Vectors
- Variational k-NN Quantum Models
- Quantum Kernel k-NN Approaches
- Oracle-Based Quantum Nearest Neighbor Search
- Quantum k-NN via Grover’s Search
- QkNN for Classification Tasks
- QkNN for Anomaly and Outlier Detection
- Experimental Results and Toy Datasets
- QkNN with Hybrid Classical-Quantum Pipelines
- Implementation in Qiskit and PennyLane
- Strengths and Limitations
- Future Directions
- Conclusion
1. Introduction
Quantum nearest-neighbor (QkNN) models are adaptations of the classical k-nearest neighbor algorithm, reformulated for quantum computing. They leverage quantum metrics such as fidelity and kernel-based distance to classify or cluster data based on similarity in quantum Hilbert space.
2. Classical k-Nearest Neighbors (k-NN) Overview
- Lazy, non-parametric algorithm
- Classifies based on majority vote of nearest neighbors in feature space
- Sensitive to distance metric and data dimensionality
3. Motivation for Quantum k-NN (QkNN)
- High-dimensional vector spaces naturally map to quantum states
- Inner products (e.g., fidelity) computed efficiently on quantum hardware
- Speedups in similarity search via amplitude estimation and Grover-like methods
4. Quantum State Similarity Measures
- Fidelity: \( F(\psi, \phi) = |\langle \psi | \phi
angle|^2 \) - Bures Distance, Trace Distance
- Inner product as proxy for Euclidean similarity
5. Encoding Classical Data into Quantum States
- Normalize data vectors to unit length
- Use amplitude or angle encoding
- Each data point corresponds to a quantum state
6. Distance Metrics in Quantum Space
- Define proximity using:
- State overlap (inner product)
- Fidelity-based measures
- Distance between feature embeddings
7. Quantum Fidelity and Inner Products
- Estimable via Swap Test:
\[
F(\psi, \phi) = ext{Tr}[
ho_\psi
ho_\phi]
\] - Implemented using quantum circuits to compare states
8. Amplitude Encoding for Input Vectors
- Map \( x = (x_1, …, x_n)
ightarrow \sum_i x_i |i
angle \) - Efficient encoding critical for QkNN practicality
9. Variational k-NN Quantum Models
- Use VQC to generate quantum embeddings
- Compute fidelity between embedded query and training examples
10. Quantum Kernel k-NN Approaches
- Compute kernel matrix using quantum circuits
- Apply classical k-NN using quantum-enhanced distances
11. Oracle-Based Quantum Nearest Neighbor Search
- Quantum RAM (qRAM) enables loading training data
- Use Grover-based search to identify closest matches
12. Quantum k-NN via Grover’s Search
- Use amplitude amplification to find nearest neighbor with high probability
- Provides quadratic speedup over classical search
13. QkNN for Classification Tasks
- Apply on encoded datasets (e.g., MNIST patches, synthetic parity)
- Label predicted by majority class of top-k nearest quantum states
14. QkNN for Anomaly and Outlier Detection
- Use quantum metrics to detect low-density regions
- Estimate anomaly score based on inverse fidelity
15. Experimental Results and Toy Datasets
- Iris dataset, XOR, circle vs square classification
- Small quantum circuits for proof-of-concept studies
16. QkNN with Hybrid Classical-Quantum Pipelines
- Classical preprocessing → quantum distance evaluation
- Useful in resource-constrained NISQ setups
17. Implementation in Qiskit and PennyLane
- Qiskit:
Statevector
,SwapTestCircuit
- PennyLane:
qml.state_fidelity
, variational embeddings
18. Strengths and Limitations
Strengths:
- Conceptually simple
- Quantum advantage in similarity evaluation
Limitations:
- Encoding overhead
- Fidelity computation requires repeated measurements
- Limited by qRAM availability
19. Future Directions
- Hardware-efficient encoding schemes
- Fault-tolerant QkNN at scale
- Application in graph-based QML
20. Conclusion
Quantum nearest-neighbor models offer an intuitive and potentially powerful extension of classical k-NN by utilizing quantum state similarity. While still in early development, they show promise for tasks involving classification, clustering, and anomaly detection in quantum-enhanced learning systems.