Skip to content

Lesson 32: Quantum k-Means Clustering and the Swap Test

32.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Recall Lloyd's algorithm for classical k-means and its complexity.
  2. Derive the swap test and use it to estimate state overlap.
  3. Convert an overlap into a Euclidean distance and know exactly when this is valid.
  4. Describe the quantum k-means (Lloyd–Mohseni–Rebentrost) algorithm and its claimed speed-up.
  5. Assess the caveats honestly and describe the NISQ-friendly variants.

32.2 Classical k-Means

Lloyd's algorithm

1. Initialise k centroids (k-means++ recommended)
2. repeat until assignments stop changing:
     ASSIGN:  each point x_i -> nearest centroid c_j    (M*k distance computations)
     UPDATE:  c_j <- mean of the points assigned to it
3. return the centroids and the assignment

Objective (within-cluster sum of squares):

\[ J = \sum_{j=1}^{k}\sum_{\vec x_i \in C_j}\big\|\vec x_i - \vec c_j\big\|^{2} \]

Lloyd's algorithm monotonically decreases \(J\) and therefore converges — but only to a local minimum, which is why initialisation (k-means++) matters.

Complexity

\[ O\big(M\,k\,d\,T\big) \]

for \(M\) points, \(k\) clusters, \(d\) dimensions, \(T\) iterations. The bottleneck is the assignment step: \(Mk\) distance computations, each costing \(O(d)\).

32.3 The Swap Test

The primitive that makes quantum distance estimation possible.

Circuit

ancilla |0>  --[H]--------*--------[H]--[M]
                          |
reg A  |phi>  ------------x-----------
                          |
reg B  |psi>  ------------x-----------

   (the two x's joined by | form a controlled-SWAP = Fredkin gate)

Derivation

Initial state. \(|0\rangle|\phi\rangle|\psi\rangle\).

After \(H\) on the ancilla.

\[ \frac{1}{\sqrt2}\big(|0\rangle + |1\rangle\big)|\phi\rangle|\psi\rangle \]

After the controlled-SWAP (swaps registers A and B only when the ancilla is \(|1\rangle\)):

\[ \frac{1}{\sqrt2}\Big(|0\rangle|\phi\rangle|\psi\rangle + |1\rangle|\psi\rangle|\phi\rangle\Big) \]

After the second \(H\). Substitute \(|0\rangle\to\frac{|0\rangle+|1\rangle}{\sqrt2}\) and \(|1\rangle\to\frac{|0\rangle-|1\rangle}{\sqrt2}\):

\[ \frac12\Big[|0\rangle\big(|\phi\rangle|\psi\rangle + |\psi\rangle|\phi\rangle\big) + |1\rangle\big(|\phi\rangle|\psi\rangle - |\psi\rangle|\phi\rangle\big)\Big] \]

Probability of measuring \(0\). The \(|0\rangle\) branch has squared norm

\[ \frac14\Big(\langle\phi|\langle\psi| + \langle\psi|\langle\phi|\Big) \Big(|\phi\rangle|\psi\rangle + |\psi\rangle|\phi\rangle\Big) = \frac14\Big(1 + |\langle\phi|\psi\rangle|^{2} + |\langle\psi|\phi\rangle|^{2} + 1\Big) \]
\[ \boxed{\ \Pr[0] = \frac{1 + \big|\langle\phi|\psi\rangle\big|^{2}}{2}\ } \]
\[ \boxed{\ \big|\langle\phi|\psi\rangle\big|^{2} = 2\Pr[0] - 1\ } \qquad\blacksquare \]

Reading the result

\(\lvert\langle\phi\rvert\psi\rangle\rvert^2\) \(\Pr[0]\) Meaning
\(1\) \(1\) identical states — the ancilla never reads 1
\(0.5\) \(0.75\) partially overlapping
\(0\) \(0.5\) orthogonal — ancilla is a fair coin

Resources. 1 ancilla + \(2n\) data qubits; \(n\) Fredkin gates (each ≈ 2 Toffolis, so ≈ 14 \(T\) gates).

Shot cost. Estimating \(\Pr[0]\) to precision \(\epsilon\) needs \(O(1/\epsilon^2)\) shots — and the error on \(|\langle\phi|\psi\rangle|^2\) is twice that on \(\Pr[0]\).

The Hadamard test — when you need the sign

The swap test returns only \(|\langle\phi|\psi\rangle|^2\), losing the sign and phase. To get \(\mathrm{Re}\langle\phi|\psi\rangle\), use the Hadamard test: prepare \(|0\rangle|\phi\rangle\), apply \(H\), apply a controlled-\(U\) that maps \(|\phi\rangle\to|\psi\rangle\), apply \(H\), and measure:

\[ \Pr[0] = \frac{1 + \mathrm{Re}\langle\phi|\psi\rangle}{2} \]

Inserting an \(S^\dagger\) on the ancilla gives the imaginary part instead.

32.4 Distance from Overlap

The identity

For normalised states,

\[ \big\||\phi\rangle - |\psi\rangle\big\|^{2} = \langle\phi|\phi\rangle + \langle\psi|\psi\rangle - 2\,\mathrm{Re}\langle\phi|\psi\rangle = 2 - 2\,\mathrm{Re}\langle\phi|\psi\rangle \]

For real, non-negative amplitudes (the usual case in amplitude encoding of non-negative data), \(\langle\phi|\psi\rangle\) is real and non-negative, so

\[ \boxed{\ d^{2} = 2 - 2\sqrt{2\Pr[0]-1}\ } \]

The normalisation trap — and its fix

Amplitude encoding normalises, so \(|\phi\rangle\) carries only the direction of \(\vec x\). Two points at very different magnitudes but the same direction have overlap 1 and apparent distance 0, even though their Euclidean distance is large.

Fix: the norm-augmented encoding. Append the magnitude information explicitly. Define

\[ |\phi\rangle = \frac{1}{\sqrt Z}\Big(\|\vec x\|\,|0\rangle|\hat x\rangle + \|\vec c\|\,|1\rangle|\hat c\rangle\Big), \qquad |\psi\rangle = \frac{1}{\sqrt2}\Big(|0\rangle - |1\rangle\Big), \]

with \(Z = \|\vec x\|^{2}+\|\vec c\|^{2}\). Then

\[ \big|\langle\phi|\psi\rangle\big|^{2} = \frac{\big\|\vec x - \vec c\big\|^{2}}{2Z} \]

giving the true Euclidean distance. This is the construction used in Lloyd, Mohseni and Rebentrost (2013), and it is why their algorithm needs one extra ancilla qubit.

Simpler alternative used in practice: standardise all data to unit norm before encoding, so that \(\|\vec x - \vec c\|^2 = 2 - 2\cos\vartheta\) is a legitimate distance on the unit sphere (a cosine distance). Valid when direction is what matters — text embeddings, spectra, normalised images.

32.5 Quantum k-Means

The algorithm

1. Encode all M data points and k centroids as quantum states  (amplitude encoding)
2. repeat until convergence:
     ASSIGN: for each point i and centroid j:
                 run the swap test  ->  estimate d(x_i, c_j)
                 assign i to argmin_j d
             (optionally: use Grover / minimum-finding to get sqrt(k) speed-up here)
     UPDATE: recompute centroids  (classically, or with a quantum mean-estimation subroutine)
3. return assignments

The claimed complexity

Step Classical Quantum
One distance \(O(d)\) \(O(\log d)\) (swap test on \(\log d\) qubits)
Find the nearest of \(k\) \(O(k)\) \(O(\sqrt k)\) (Dürr–Høyer minimum finding)
One assignment round \(O(Mkd)\) \(O(M\sqrt k\log d)\)
\[ \boxed{\ \text{Total: } O(Mkd) \ \longrightarrow\ O\!\left(M\sqrt{k}\log d\right)\ } \]

— exponential in \(d\), quadratic in \(k\).

The caveats — the same four, again

  1. State preparation. Encoding \(M\) points of dimension \(d\) costs \(O(Md)\) unless qRAM exists — which already matches the classical read cost. This is the binding constraint.
  2. Precision. Each distance needs \(O(1/\epsilon^2)\) shots. To distinguish two nearly-equidistant centroids you need small \(\epsilon\), and near cluster boundaries this becomes expensive.
  3. Re-preparation. Centroids change every iteration, so the states must be re-prepared each round — a cost the complexity table quietly omits.
  4. Dequantisation. Tang (2019) gave a classical algorithm with \(\mathrm{polylog}\) scaling under the same \(\ell^2\)-sampling access assumption. The exponential-in-\(d\) claim does not survive a fair comparison.

What survives

Claim Verdict
Exponential in \(d\) ✗ dequantised for low-rank data; state preparation dominates otherwise
Quadratic in \(k\) (Grover minimum finding) ✓ genuine — Grover's speed-up is unconditional
Useful on quantum-native data ✓ yes — no encoding bottleneck

Honest position for students: quantum k-means is an excellent vehicle for teaching the swap test, amplitude encoding and quantum subroutine composition. Its practical advantage on classical data is not established.

NISQ-friendly variants

  • q-means (Kerenidis et al., 2019): a robust version with proven convergence to a \(\delta\)-approximate solution, requiring only \(\epsilon\)-accurate distances.
  • Quantum-assisted clustering: use the quantum computer only for distance estimation on a subset (coresets), doing the rest classically.
  • QAOA-based clustering: formulate clustering as MaxCut on a similarity graph and solve with QAOA (L34) — currently the most practical NISQ route.

32.6 Solved Problems

Problem 1 — Swap test on two specific states

Compute \(\Pr[0]\) for the swap test on (a) \(|\phi\rangle = |0\rangle\), \(|\psi\rangle = |0\rangle\); (b) \(|0\rangle\) and \(|1\rangle\); (c) \(|0\rangle\) and \(|+\rangle\); (d) \(|+\rangle\) and \(\frac{1}{\sqrt5}(1,2)^T\).

Solution.

\[ \Pr[0] = \frac{1+|\langle\phi|\psi\rangle|^{2}}{2} \]

(a) \(\langle0|0\rangle = 1\): \(\Pr[0] = \frac{1+1}{2} = \mathbf{1}\). The ancilla never reads 1 — a single shot that returns 1 proves the states differ.

(b) \(\langle0|1\rangle = 0\): \(\Pr[0] = \frac{1+0}{2} = \mathbf{0.5}\). Maximally distinguishable, and the ancilla is a fair coin.

(c) \(\langle0|+\rangle = \frac{1}{\sqrt2}\), so \(|\cdot|^2 = 0.5\):

\[ \Pr[0] = \frac{1+0.5}{2} = \mathbf{0.75} \]

(d) \(\langle +|\psi\rangle = \frac{1}{\sqrt2}\cdot\frac{1+2}{\sqrt5} = \frac{3}{\sqrt{10}} = 0.94868\):

\[ |\langle+|\psi\rangle|^{2} = \frac{9}{10} = 0.9, \qquad \Pr[0] = \frac{1.9}{2} = \mathbf{0.95} \]

Note the sensitivity. \(\Pr[0]\) ranges only over \([0.5, 1]\) — a compressed dynamic range. This is why the swap test needs many shots: distinguishing \(|\langle\phi|\psi\rangle|^2 = 0.90\) from \(0.92\) means distinguishing \(\Pr[0] = 0.950\) from \(0.960\), a difference of only 0.01.

Problem 2 — Estimating a distance with a shot budget

Two normalised data points give a swap test with \(\Pr[0] = 0.92\) over 4096 shots. Compute the overlap, the distance, and the uncertainty in the distance.

Solution.

Overlap.

\[ |\langle\phi|\psi\rangle|^{2} = 2(0.92) - 1 = \mathbf{0.84} \]
\[ |\langle\phi|\psi\rangle| = \sqrt{0.84} = 0.91652 \]

Distance (assuming real non-negative amplitudes):

\[ d^{2} = 2 - 2(0.91652) = 0.16696 \ \Longrightarrow\ d = \mathbf{0.4086} \]

Uncertainty propagation.

Shot noise on \(\Pr[0]\):

\[ \sigma_{p} = \sqrt{\frac{0.92\times0.08}{4096}} = \sqrt{\frac{0.0736}{4096}} = \sqrt{1.797\times10^{-5}} = 4.239\times10^{-3} \]

On the squared overlap \(F = 2p-1\):

\[ \sigma_F = 2\sigma_p = 8.478\times10^{-3} \]

On \(\sqrt F\): \(\sigma_{\sqrt F} = \frac{\sigma_F}{2\sqrt F} = \frac{8.478\times10^{-3}}{2(0.91652)} = 4.625\times10^{-3}\).

On \(d^2 = 2 - 2\sqrt F\): \(\sigma_{d^2} = 2\sigma_{\sqrt F} = 9.25\times10^{-3}\).

On \(d\): \(\sigma_d = \frac{\sigma_{d^2}}{2d} = \frac{9.25\times10^{-3}}{2(0.4086)} = \mathbf{1.13\times10^{-2}}\).

\[ \boxed{\ d = 0.409 \pm 0.011 \quad (2.8\%\ \text{relative})\ } \]

Design implication. To halve the uncertainty you need 4× the shots (\(1/\sqrt S\) scaling). And notice the error amplification: a 0.46 % relative error in \(\Pr[0]\) became a 2.8 % error in \(d\) — a factor of 6, because of the square-root and the compressed dynamic range.

Problem 3 — Full quantum k-means iteration by hand

Cluster \(\vec x_1 = (1,0)\), \(\vec x_2 = (0,1)\), \(\vec x_3 = (1,1)\) into \(k=2\) clusters with initial centroids \(\vec c_1 = (1,0)\), \(\vec c_2 = (0,1)\). Use normalised (cosine) distance and give the swap test probability for each pair.

Solution.

Normalise everything (amplitude encoding requires it).

\[ |x_1\rangle = (1,0)^{T},\quad |x_2\rangle = (0,1)^{T},\quad |x_3\rangle = \tfrac{1}{\sqrt2}(1,1)^{T} \]
\[ |c_1\rangle = (1,0)^{T},\quad |c_2\rangle = (0,1)^{T} \]

Assignment step — all six overlaps.

Pair \(\langle x\rvert c\rangle\) \(\lvert\cdot\rvert^2\) \(\Pr[0]\) \(d^2 = 2-2\lvert\cdot\rvert\)
\(x_1, c_1\) \(1\) 1.0 1.00 0
\(x_1, c_2\) \(0\) 0.0 0.50 2
\(x_2, c_1\) \(0\) 0.0 0.50 2
\(x_2, c_2\) \(1\) 1.0 1.00 0
\(x_3, c_1\) \(1/\sqrt2\) 0.5 0.75 0.586
\(x_3, c_2\) \(1/\sqrt2\) 0.5 0.75 0.586

Assignments.

  • \(x_1 \to C_1\) (distance 0 versus 2)
  • \(x_2 \to C_2\) (distance 0 versus 2)
  • \(x_3\) is exactly equidistant (\(0.586\) from both). Tie — break arbitrarily; say \(x_3\to C_1\).

Update step.

\[ \vec c_1 = \frac{\vec x_1 + \vec x_3}{2} = \frac{(1,0)+(1,1)}{2} = (1,\ 0.5) \]
\[ \vec c_2 = \vec x_2 = (0,1) \]

Normalised for the next round:

\[ |c_1\rangle = \frac{(1, 0.5)}{\sqrt{1.25}} = (0.8944,\ 0.4472)^{T}, \qquad |c_2\rangle = (0,1)^{T} \]

Second assignment round — new overlaps with \(c_1\).

\[ \langle x_1|c_1\rangle = 0.8944 \Rightarrow \Pr[0] = \frac{1+0.8}{2} = 0.90 \]
\[ \langle x_3|c_1\rangle = \tfrac{1}{\sqrt2}(0.8944+0.4472) = 0.9487 \Rightarrow \Pr[0] = 0.95 \]
\[ \langle x_2|c_1\rangle = 0.4472 \Rightarrow \Pr[0] = \frac{1+0.2}{2} = 0.60 \]

Assignments are unchanged (\(x_2\) still prefers \(c_2\) with \(\Pr[0] = 1\)), so the algorithm has converged in 2 iterations.

Shot cost. 6 swap tests per round × 2 rounds × 1024 shots = 12 288 shots — to cluster three 2-D points, a task a classical computer completes in nanoseconds. This concretely illustrates the constant-factor problem in quantum ML.

Problem 4 — Grover speed-up in the assignment step

With \(k = 256\) clusters, compare classical linear scan and Dürr–Høyer quantum minimum finding for the nearest-centroid search, including the constant factor.

Solution.

Classical. Compare all \(k\) distances: \(k = \mathbf{256}\) distance evaluations.

Quantum (Dürr–Høyer). The algorithm repeatedly runs Grover search for an element smaller than a current threshold, halving the candidate set:

\[ \text{expected queries} \approx \frac{22.5\sqrt{k}}{2} + \ldots \approx 22.5\sqrt{k} \ \text{in the original bound, though } \approx 3\sqrt k \text{ is typical in practice.} \]

Using the practical estimate:

\[ 3\sqrt{256} = 3\times16 = \mathbf{48} \ \text{oracle calls} \]

Speed-up factor: \(256/48 \approx \mathbf{5.3\times}\).

But each "oracle call" is expensive. It requires a full coherent distance computation — a swap test embedded inside a Grover oracle, meaning the distance must be computed reversibly into a register rather than measured. With \(\epsilon\)-precision distances this costs \(O(1/\epsilon)\) repetitions (via amplitude estimation) per oracle call.

Revised comparison with \(\epsilon = 0.01\):

\[ \text{quantum} = 48 \times O(100) = 4800 \ \text{circuit executions} \]
\[ \text{classical} = 256 \ \text{floating-point operations} \]

The classical version wins by a factor of \(\sim10^{6}\) in wall-clock time, because each classical "operation" is a nanosecond and each quantum circuit execution is a millisecond.

\[ \boxed{\ \text{The } \sqrt k \text{ speed-up is real asymptotically but does not pay for itself at } k = 256.\ } \]

Break-even requires \(k\) large enough that \(\sqrt k \cdot(\text{quantum constant}) < k\cdot(\text{classical constant})\), i.e. \(\sqrt k > 10^{6}\), so \(k > 10^{12}\) clusters — not a realistic clustering problem.

Problem 5 — When quantum clustering genuinely helps

Identify a realistic scenario where quantum clustering is the right tool, and design the pipeline.

Solution.

Scenario: clustering quantum states from a quantum experiment.

A quantum simulator prepares ground states \(|\psi(\vec g)\rangle\) of a many-body Hamiltonian at many parameter settings \(\vec g\). The goal is to cluster the parameter settings by phase of matter, without knowing the phase diagram in advance.

Why classical methods fail.

  • Each state lives in \(\mathbb{C}^{2^{n}}\); to cluster them classically you would first need tomography, costing \(O(4^{n})\) measurements per state. For \(n = 20\) that is \(10^{12}\) measurements per data point.
  • Classical shadows reduce this but still need \(O(\log)\)-many measurements per observable and require knowing which observables matter — precisely what is unknown.

Why quantum clustering works here.

  • No encoding bottleneck. The states are already quantum — the simulator hands them over directly. Amplitude encoding costs nothing.
  • The swap test is the natural similarity measure. \(|\langle\psi(\vec g)|\psi(\vec g')\rangle|^2\) is the fidelity, which is exactly the physically meaningful notion of "same phase": fidelity drops sharply across a phase boundary (the fidelity susceptibility diverges there).

Pipeline.

1. For each pair (g, g'), prepare |psi(g)> and |psi(g')> on 2n+1 qubits
2. Run the swap test -> fidelity F(g,g')
3. Build the similarity matrix S with S_ij = F(g_i, g_j)
4. Convert to a distance:  D_ij = sqrt(2 - 2*sqrt(S_ij))
5. Run classical spectral clustering or k-medoids on D
6. Cluster boundaries in parameter space = PHASE BOUNDARIES

Cost. \(\binom{P}{2}\) swap tests for \(P\) parameter settings, each \(O(1/\epsilon^2)\) shots. For \(P = 50\) and \(\epsilon = 0.01\): \(1225\times10^{4} = 1.2\times10^{7}\) shots — about 20 minutes at 10 kHz. Entirely feasible.

Why this is the honest use case.

Requirement Satisfied?
Data is quantum-native ✓ no state-preparation cost
Classical alternative is exponentially hard ✓ tomography is \(O(4^n)\)
Similarity measure is physically meaningful ✓ fidelity ↔ phase
Output is small (a clustering) ✓ no exponential readout

This is the same lesson as L30's quantum phase recognition: the credible applications of QML are in the QQ quadrant, where the data is quantum, the classical alternative is exponentially expensive, and the answer is small. On classical tabular data, the constant factors and the encoding bottleneck defeat every proposed advantage.

32.7 Practice Problems

  1. Swap test on \(|+\rangle\) and \(|-\rangle\): what is \(\Pr[0]\)? [Ans: 0.5]
  2. \(\Pr[0] = 0.85\): find the overlap and the distance. [Ans: \(F = 0.7\), \(d = 0.572\)]
  3. Derive \(\Pr[0] = \frac{1+|\langle\phi|\psi\rangle|^2}{2}\) from scratch.
  4. Shots for \(\pm0.01\) accuracy in \(F\) when \(\Pr[0] = 0.9\)? [Ans: \(\approx3600\)]
  5. Why does amplitude encoding lose magnitude information, and how is it recovered?
  6. Compute the classical complexity of k-means with \(M=10^{6}\), \(k=100\), \(d=50\), \(T=20\). [Ans: \(10^{11}\) operations]
  7. Explain why quantum k-means on a CSV file gives no advantage.

32.8 Summary

  • Lloyd's algorithm costs \(O(Mkd)\) per iteration; the assignment step dominates.
  • The swap test gives \(\Pr[0] = \frac{1 + |\langle\phi|\psi\rangle|^2}{2}\) using 1 ancilla, \(2n\) data qubits and \(n\) Fredkin gates. The Hadamard test recovers the sign/phase.
  • Distance from overlap: \(d^2 = 2 - 2\,\mathrm{Re}\langle\phi|\psi\rangle\). Amplitude encoding normalises, so magnitude must be restored via a norm-augmented encoding — or you must accept cosine distance.
  • Quantum k-means claims \(O(Mkd) \to O(M\sqrt k\log d)\), combining the \(\log d\) swap test with \(\sqrt k\) Dürr–Høyer minimum finding.
  • Caveats: state preparation costs \(O(Md)\) without qRAM; centroids must be re-prepared each round; precision costs \(O(1/\epsilon^2)\); and Tang dequantised the low-rank case. Only the \(\sqrt k\) factor is unconditionally real, and it does not pay for itself at realistic \(k\).
  • The honest application is quantum-native data: clustering many-body states by fidelity to map a phase diagram — where tomography is \(O(4^n)\) and fidelity is the physically correct similarity measure.

Next lesson: L33 — Quantum Boltzmann machines.

Practise now: unit3-qml-lab.html → Swap Test Lab: build two states, run the swap test with a chosen shot count, and see the estimated overlap converge to the exact value with error bars.