Fetching the paper…
Reading the bibliography…
Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's algorithm for $k$-means.
On Tail Probabilities for Martingales
David A. Freedman · 1975
Earlier work this paper cites.
Algorithm AS 136: A k-means clustering algorithm
J. A. Hartigan and M. A. Wong · 1979
Earlier work this paper cites.
Least squares quantization in PCM
Stuart Lloyd · 1982
Earlier work this paper cites.
Algorithms for quantum computation: discrete logarithms and factoring
P.W. Shor · 1994
Earlier work this paper cites.
A quantum algorithm for finding the minimum
Christoph Dürr and Peter Høyer · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Quantum mechanics helps in searching for a needle in a haystack
Lov K. Grover · 1997
Earlier work this paper cites.
Genetic k k -means algorithm
K. Krishna and M. Narasimha Murty · 1999
Earlier work this paper cites.
The quantum query complexity of approximating the median and related statistics
Ashwin Nayak and Felix Wu · 1999
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Peter W. Shor · 1999
Earlier work this paper cites.
Quantum amplitude amplification and estimation
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp · 2002
Earlier work this paper cites.
A local search approximation algorithm for k-means clustering
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu · 2002
Earlier work this paper cites.
The global k k -means clustering algorithm
Aristidis Likas, Nikos Vlassis, and Jakob J. Verbeek · 2003
Earlier work this paper cites.
Quantum walk algorithm for element distinctness
Andris Ambainis · 2007
Earlier work this paper cites.
k-means++: the advantages of careful seeding
David Arthur and Sergei Vassilvitskii · 2007
Earlier work this paper cites.
The hardness of k k -means clustering
Sanjoy Dasgupta · 2008
Earlier work this paper cites.
Architectures for a quantum random access memory
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone · 2008
Earlier work this paper cites.
Quantum random access memory
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone · 2008
Earlier work this paper cites.
The hardness of k k -means clustering in the plane
Andrea Vattani · 2009
Cited alongside, same era.
Quantum search with variable times
Andris Ambainis · 2010
Cited alongside, same era.
Freedman’s inequality for matrix martingales
Joel Tropp · 2011
Cited alongside, same era.
Variable time amplitude amplification and quantum algorithms for linear algebra problems
Andris Ambainis · 2012
Cited alongside, same era.
The planar k k -means problem is NP-hard
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan · 2012
Cited alongside, same era.
Quantum speed-up for unsupervised learning
Esma Aïmeur, Gilles Brassard, and Sébastien Gambs · 2013
Cited alongside, same era.
A quantum-inspired classical algorithm for recommendation systems
Ewin Tang · 2019
Later among the works it cites.
Quantum algorithms for feedforward neural networks
Jonathan Allcock, Chang-Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang · 2020
Later among the works it cites.
On sampling based algorithms for k k -means
Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal, and Amit Kumar · 2020
Later among the works it cites.
Quantum gradient descent for linear systems and least squares
Iordanis Kerenidis and Anupam Prakash · 2020
Later among the works it cites.
A quantum interior point method for LPs and SDPs
Iordanis Kerenidis and Anupam Prakash · 2020
Later among the works it cites.
Practicality of Quantum Random Access Memory
Connor T. Hann · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost · 2013
Cited alongside, same era.
A simple D 2 {D}^{2} -sampling based PTAS for k k -means and other clustering problems
Ragesh Jaiswal, Amit Kumar, and Sandeep Sen · 2014
Cited alongside, same era.
Quantum principal component analysis
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost · 2014
Cited alongside, same era.
Quantum algorithms for linear algebra and machine learning
Anupam Prakash · 2014
Cited alongside, same era.
Simulating Hamiltonian dynamics with a truncated Taylor series
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma · 2015
Cited alongside, same era.
Better guarantees for k-means and euclidean k-median by primal-dual algorithms
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward · 2017
Cited alongside, same era.
Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
Ewin Tang · 2021
Later among the works it cites.
Near-optimal quantum algorithms for multivariate mean estimation
Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi · 2022
Later among the works it cites.
An improved quantum-inspired algorithm for linear regression
András Gilyén, Zhao Song, and Ewin Tang · 2022
Later among the works it cites.
Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints
Yanlin Chen and Ronald de Wolf · 2023
Closest in time.
A quantum approximation scheme for k k -means
Ragesh Jaiswal · 2023
Closest in time.
Samuel Jaques and Arthur G. Rattew · 2023
Closest in time.
Quantum random access memory for dummies
Koustubh Phalak, Avimita Chatterjee, and Swaroop Ghosh · 2023
Closest in time.
Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, and Miklos Santha · 2024
Closest in time.
Provably faster randomized and quantum algorithms for k k -means clustering via uniform sampling, 2025
Tyler Chen, Archan Ray, Akshay Seshadri, Dylan Herman, Bao Bach, Pranav Deshpande, Abhishek Som, Niraj Kumar, and Marco Pistoia · 2025
Closest in time.
Des-q: a quantum algorithm to provably speedup retraining of decision trees
Niraj Kumar, Romina Yalovetzky, Changhao Li, Pierre Minssen, and Marco Pistoia · 2025
Closest in time.
Quantum (inspired) D 2 {D}^{2} -sampling with applications
Poojan Chetan Shah and Ragesh Jaiswal · 2025
Closest in time.