Quantum Clustering (QC) is a class of data-clustering algorithms that use conceptual and mathematical tools from quantum mechanics. QC belongs to the family of density-based clustering algorithms, where clusters are defined by regions of higher density of data points. QC was first developed by David Horn and Assaf Gottlieb in 2001.
Original Quantum Clustering Algorithm Given a set of points in an n-dimensional data space, QC represents each point with a multidimensional Gaussian distribution, with width (standard deviation) sigma, centered at each point's location in the space. These Gaussians are then added together to create a single distribution for the entire data set. (This step is a particular example of kernel density estimation, often referred to as a Parzen-Rosenblatt window estimator.) This distribution is considered to be the quantum-mechanical wave function for the data set. Loosely speaking, the wave function is a generalized description of where there are likely to be data points in the space. QC next introduces the idea of a quantum potential; using the time-independent Schrödinger equation, a potential surface is constructed which has the data set's wave function as a stable solution. Details in the potential surface are more robust to changes in sigma (the width of the Gaussians) than the corresponding details in the wave function; this advantage is one of the initial motivations for the development of QC. The potential surface is considered to be the 'landscape' of the data set, where 'low' points in the landscape correspond to regions of high data density. QC then uses gradient descent to move each data point 'downhill' in the landscape, causing points to gather together in nearby minima, thus revealing clusters within the data set. QC has a single main hyperparameter, which is the width sigma of the Gaussian distribution around each data point. For sufficiently small sigma, every data point will define its own depression in the landscape, and no points will move, thus creating no clusters. For sufficiently large sigma, the landscape becomes a single smooth bowl, and every data point will cluster together at the single global minimum in the landscape. Exploring the range of sigma values between these extremes yields information about the inherent structure of the data set, including hierarchy of structure; smaller sigma values reveal more fine-grained local structure, and larger sigma values reveal overall global structure. The QC algorithm does not specify a preferred or 'correct' value of sigma.
Dynamic Quantum Clustering Developed by Marvin Weinstein and David Horn in 2009, Dynamic Quantum Clustering (DQC) extends the basic QC algorithm in several ways.
Quantum evolution, non-local gradient descent, and tunneling DQC uses the same potential landscape as QC, but it replaces classical gradient descent with quantum evolution. To do this, each data point is again represented by its individual wave function (a multidimensional Gaussian distribution with width sigma). The time-dependent Schrödinger equation is then used to compute each wave function's evolution over time in the given quantum potential. More precisely, a small time-step value is introduced, and the evolution of the wave function is calculated repeatedly at each time step, with a new expected location for the data point calculated after each step. This process builds a trajectory through the data space for each point; the evolution continues until all points have stopped moving. Importantly, the Ehrenfest theorem from quantum mechanics states that this quantum evolution does, in fact, equate to the point moving downhill in the potential landscape, in expectation. The "in expectation" part is important because, unlike in classical physics, the point's motion is not influenced only by the gradient of the potential at the point's location; instead, the point's wave function extends over the entire landscape (with the Gaussian centered at the point's location), and a complex interaction between the wave function and the potential determines the point's motion. As a loose analogy: regions of the landscape that are below the point's current location 'attract' the point—the more so the lower the region is, but the less so the farther away from the point it is. In the same way, higher regions of the landscape 'repel' the point. Thus, quantum evolution for each point acts as a form of non-local gradient descent in the potential. This non-locality creates the possibility of tunneling, where a point will seem to ignore or pass through a potential barrier on its way toward some lower minimum. The biggest problem in non-convex gradient descent is often the existence of many small and uninteresting local minima where points can get stuck as they descend. (This problem tends to get worse as the number of dimensions increases, which is part of the curse of dimensionality.) DQC's use of non-local gradient descent and tunneling presents a solution to this problem. DQC introduces two new hyperparameters: the time step, and the mass of each data point (which controls the degree of tunneling behavior). Whereas tuning of sigma is integral to understanding any new data set, both time step and mass can usually be left at reasonable default values and still produce useful results. An important downside of the quantum-evolution approach is that the time complexity of the evolution is now O ( n 3 ) {\displaystyle O(n^{3})} in the number of data points, since interacting with the entire potential landscape is O ( n 2 ) {\displaystyle O(n^{2})} for each point. For large data sets, the computation time would quickly become intractable. When needed, DQC addresses this problem by selecting a limited number of points from the data set to act as a basis (see next section).
… excerpt ends here. Continue reading the full article.
