16026d60ff9b54410b3435b403afd226-AuthorFeedback.pdf

The classical time for a single iteration ofk-means isO(kNd), we will add this to the4 mainpaper. The first step ofq-means indeed assigns points to the closest cluster using methods similar to [WKS14].16 The introduction ofδ-k-means is necessary to have a rigorous classical analogue of our quantum19 algorithm. Despite this,q-means is still useful for machine learning purposes. Note also, that we42 could apply our quantum algorithm oneach one ofthese processors and reduce thecomplexity toO(kdlog(N/p)).43