Quantum K-NN Algo


k-nearest neighbours (k-NN) is a supervised algorithm where test vectors are compared against labelled training vectors. Classification of a test vector is performed by taking a majority vote of the class for the k nearest training vectors. In the case of k=1, this algorithm reduces to an equivalent of nearest-centroid. k-NN algorithms lend themselves to applications such as handwriting recognition and useful approximations to the traveling salesman problem.


k-nearest-neighbor classifiers applied to the simulation data above. The broken purple curve in the background is the Bayes decision boundary.

k-NN has two subtleties. Firstly, for datasets where a particular class has the majority of the training data points, there is a bias towards classifying into this class. One solution is to weight each classification calculation by the distance of the test vector from the training vector, however this may still yield poor classifications for particularly under-represented classes. Secondly, the distance between each test vector and all training data must be calculated for each classification, which is resource intensive. The goal is to seek an algorithm with a favourable scaling in the number of training data vectors.

An extension of the nearest-centroid algorithm has been developed by Wiebe. First, the algorithm prepares a superposition of qubit states with the distance between each training vector and the input vector, using a suitable quantum sub-routine that encodes the distances in the qubit amplitudes. Rather than measuring the state, the amplitudes are transferred onto an ancilla register using coherent amplitude estimation. Grover’s search is then used to find the smallest valued register, corresponding to the training vector closest to the test vector. Therefore, the entire classification occurs within the quantum computer, and we can categorize the quantum k-NN as an L2 algorithm. The advantage over Lloyd’s algorithm is that the power of Grover’s search has been used to provide a speedup and it provides a full and clear recipe for implementation. The time scaling of the quantum k-NN algorithm is complex, however it scales as O ̃(√nlog(n)) to first order. The dependence on m no longer appears except at higher orders.

The quantum k-NN algorithm is not a panacea. There are clearly laid out conditions on the application of quantum k-NN, though, such as the dependence on the sparsity of the data. The classification is decided by majority rule with no weighting and, as such, it is unsuitable for biased datasets. K-NN works well with a small number of input variables (p), but struggles when the number of inputs is very large. Each input variable can be considered a dimension of a p-dimensional input space. For example, if you had two input variables x1 and x2, the input space would be 2-dimensional. As the number of dimensions increases the volume of the input space increases at an exponential rate. In high dimensions, points that may be similar may have very large distances. All points will be far away from each other and our intuition for distances in simple 2 and 3-dimensional spaces breaks down. This might feel unintuitive at first, but this general problem is called the “Curse of Dimensionality“.


Foucault, Noys, Grammar of Neoliberalism and the Bizarre Concessions to Market Resiliency

According to Foucault, the state intervention of neoliberalism is Kantian; it is designed to act on the conditions of the social to create the possibility of competition and enterprise. Neo-liberalism is opposed to the specter of the passive consumer just as much as various forms of leftism and anarchism. Second, the philosophical roots of neoliberal intervention can be traced back to the roots of German neoliberalism in the philosophy of Husserl. In this case, competition does not arise naturally but only as an essence that has to be constructed and formalized; neoliberalism is Husserlian. Foucault remarks that according to Marxism, there can be only one capitalism with one logic, contrasting this with the historical institutional argument that capitalism is a singularity with different possibilities. Neoliberals then try to invent a new logic for capitalism.


If we accept that we are not dealing with an essential capitalism deriving from the logic of capital, but rather with a singular capitalism formed by an economic-institutional ensemble, then we must be able to act on this ensemble and intervene in such a way as to invent a different capitalism.

For Benjamin Noys, the neoliberal government intervention is no less dense, active, frequent and continuous than in any other system. The difference is rather the point of application. It intervenes on society so that competitive mechanisms can play a regulative role at every moment and every point in society and by intervening in this way, its objective will become possible, that is to say a general regulation of the society by market. The necessity is to analyze how neoliberalism creates a new form of government in which state performs a different function, permeating society to subject it to the economic.

Despite the aggressive role the state plays, Noys tells us it misses the point to identify neoliberalism as another form of statism, rather the state subjects society to the economic. Now which “economic” would that be? The only “economic” Noys mentions are competition and the market. To this point in his 2010 paper, Noys has not even discussed capital the social relation itself. The single social relation that connects classical liberalism to fascism to neoliberalism is itself never discussed by Noys.

How the fuck does this happen?

Noys explains, “the state constantly intervenes to construct competition at all levels, so that the market economy is the ‘general index’ for all governmental action”, but Noys never explains that this construction is not ideology driven but aimed at the production of surplus value. What Noys never mentions is that the state itself is acting as the social capitalist and is imposing a capitalist regime on all of society. This is important for Noys to ignore because, despite his actual narrative that this is the action of the fascist state, the real problem identified by Noys is the market. It is not that the state is functioning as society’s capitalist, but that it is doing this by imposing the market on society.

Clever money versus the accelerationists reaches its crescendo here: The real poverty in Noys’ paper on grammar of neoliberalism is in his embarrassingly piss poor grasp of labor theory, and his obsession with the ideology of neoliberalism, rather than real relations of production. Icing on the cake happens with the #accelerate club seeming to be a variation of the post-humanist desire-assemblage forming among the 25-35 year old Caucasianistas that wants us to get our Übermensch on without giving up Xboxes and smartphones…..

Machine Learning via Quantum Nearest-Centroid Algorithm for k-Means Clustering

k-means clustering is a popular machine learning algorithm that structures an unlabelled dataset into k classes. k-means clustering is an NP-hard problem, but examining methods that reduce the average-case complexity is an open area of research. A popular way of classifying the input vectors is to compare the distance of a new vector with the centroid vector of each class (the latter being calculated from the mean of the vectors already in that class). The class with the shortest distance to the vector is the one to which the vector is classified. We refer to this form of classification sub-routine for k-means clustering, as the nearest-centroid algorithm.


Seth Lloyd and others have constructed a quantum nearest-centroid algorithm, only classifying vectors after the optimal clustering has been found. They show that the distance between an input vector, |u⟩, and the set of n reference vectors {|viC} of length m in class C, can be efficiently calculated to within error ε in O(ε−1 log nm) steps on a quantum computer. The algorithm works by constructing the state

|Ψ⟩ = 1/√2 (|u⟩|0⟩ + 1/√n Σnj=1 |vj|j⟩

and performing a swap test with the state

|Φ⟩ = 1/√Z (|u⟩||0⟩ + 1/√n Σnj=1 |vj|j⟩

where Z = |u|2 + (1/n) Σj |vj|2.

The distance between the input vector and the weighted average of the vectors in class C is then proportional to the probability of a successful swap test. The algorithm is repeated for each class until a desired confidence is reached, with the vector being classified into the class from which it has the shortest distance. The complexity arguments on the dependence of m were rigorously confirmed by Lloyd and others using the QPCA (Quantum principal component analysis) construction for a support vector machine (SVM) algorithm. This can roughly be thought of as a k-means clustering problem with k=2. A speedup is obtained due to the classical computation of the required inner products being O(nm)2.

The algorithm has some caveats, in particular it only classifies data without performing the harder task of clustering, and assumes access to a QRAM (Quantum random access memory). In the same paper, Lloyd and others develop a k-means algorithm, including clustering, for implementation on an adiabatic quantum computer. The potential of this algorithm is hard to judge, and is perhaps less promising due to the current focus of the quantum computing field on circuit-based architectures.

Machine learning data is usually (very) high dimensional, containing redundant or irrelevant information. Thus, machine learning benefits from pre-processing data through statistical procedures such as principal component analysis (PCA). PCA reduces the dimensionality by transforming the data to a new set of uncorrelated variables (the principal components) of which the first few retain most of the variation present in the original dataset. The standard way to calculate the principal components boils down to finding the eigenvalues of the data covariance matrix.


Lloyd and others suggested a quantum version of PCA (QPCA). The bulk of the algorithm consists of the ability to generate the exponent of an arbitrary density matrix ρ efficiently. More specifically, given n copies of ρ, Lloyd and others propose a way to apply the unitary operator e−iρt to any state σ with accuracy ε = O(t2/n). This is done using repeated infinitesimal applications of the swap operator on ρ ⊗ σ. Using phase estimation, the result is used to generate a state which can be sampled from to attain information on the eigenvectors and eigenvalues of the state ρ. The algorithm is most effective when ρ contains a few large eigenvalues and can be represented well by its principal components. In this case, the subspace spanned by the principal components ρ′ closely approximates ρ, such that ||ρ − P ρP || ≤ ε, where P is the projector onto ρ′. This method of QPCA allows construction of the eigenvectors and eigenvalues of the matrix ρ in time O(Rlog(d)), where d and R are the dimensions of the space spanned by the ρ and ρ′ respectively. For low-rank matrices, this is an improvement over the classical algorithm that requires O(d) time. In a machine learning context, if ρ is the covariance matrix of the data, this procedure performs PCA in the desired fashion.

The QPCA algorithm has a number of caveats that need to be covered before one can apply it to machine learning scenarios. For example, to gain a speedup, some of the eigenvalues of ρ need to be large (i.e. ρ needs to be well approximated by ρ′). For the case where all eigenvalues are equal and of size O(1/d), the algorithm reduces to scaling in time O(d) which offers no improvement over classical algorithms. Other aspects that need to be considered include the necessity of QRAM and the scaling of the algorithm with the allowed error ε. As of yet, it is unclear how these requirements affect the applicability of the algorithm to real scenarios.