REVIEW 4 cited by
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning
read the original abstract
We present several quantum algorithms for performing nearest-neighbor learning. At the core of our algorithms are fast and coherent quantum methods for computing distance metrics such as the inner product and Euclidean distance. We prove upper bounds on the number of queries to the input data required to compute these metrics. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to the corresponding classical algorithm. In certain cases, we show exponential or even super-exponential reductions over the classical analog. We study the performance of our quantum nearest-neighbor algorithms on several real-world binary classification tasks and find that the classification accuracy is competitive with classical methods.
Forward citations
Cited by 4 Pith papers
-
GHZ is All You Need: Quantum Sensing with VISTA
VISTA achieves near-Heisenberg scaling in moderately noisy quantum magnetometry by passively evolving a probe, comparing it via swap test to a physics-informed quantum twin circuit, and optimizing only physical parame...
-
Quantum Data Fitting Algorithm for Non-sparse Matrices
Quantum data fitting algorithm for non-sparse N x N Hermitian matrices achieves O(κ² √N polylog(N) / (ε log κ)) runtime via QSVE, eigenvalue sign recovery, and regularization.
-
Quantum-Enhanced Similarity Measures for Polarimetric Materials Classification
A quantum-classical hybrid uses SWAP-test fidelity on 32D embeddings from polarimetric data to classify 23 materials with competitive accuracy versus classical optimal transport, suggesting viability for NISQ devices.
-
A Quantum Algorithm for Finding $k$-Minima
Quantum algorithm for k-minima with O(sqrt(k N)) query complexity via threshold search and generalized amplitude amplification.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.