# Techniques: Big data applications on small quantum computers

## What the paper contributes (one paragraph)
The paper applies the coreset method, a classical data-reduction technique, so that large machine-learning datasets can be tackled on small quantum computers. A large dataset is replaced by a much smaller weighted dataset whose solution stays competitive with the original. The authors take three well-studied clustering problems, divisive clustering, 3-means clustering, and Gaussian mixture model clustering, and give a Hamiltonian formulation of each so that the ground state encodes the clustering solution and the qubit count scales with the coreset size. The 3-means cost is recast as a weighted MaxCut on a complete graph partitioned into three sets, with a two-qubit-per-vertex labelling. They then run the variational quantum eigensolver (VQE) on these Hamiltonians and compare against classical solvers, performing exact noiseless simulations on instances up to 25 qubits using CUDA Quantum, finding performance comparable to classical methods.

## Techniques offered
- **Coreset-based dataset compression for small quantum computers** - replaces a large classical dataset with a small weighted coreset that approximates every task cost to relative error epsilon, so a big-data clustering instance fits on a small device.
  - guarantee: statistical bound; the coreset cost is within a multiplicative epsilon of the full-dataset cost for all candidate models.
  - quote: "This technique allows a large collection of data $X$ to be replaced (to within an error $\epsilon$) by a weighted data set $(X',w)$ with a significantly reduced size."
- **Ising or QUBO Hamiltonian encoding of clustering cost functions** - maps the divisive, 3-means, and Gaussian mixture clustering cost functions onto interacting-qubit Hamiltonians whose ground state is the optimal clustering, with qubit count scaling with the coreset size.
  - guarantee: none beyond exact correspondence between the Hamiltonian ground state and the clustering optimum; the number of Hamiltonian terms scales polynomially with coreset size.
  - quote: "For this reason, we introduced three novel Hamiltonians to solve the aforementioned problems."
- **Weighted MaxCut reduction for 3-means clustering** - restates weighted 3-means as a weighted MaxCut on a complete graph partitioned into three sets, encoded with a two-qubit-per-vertex labelling into a Pauli Hamiltonian.
  - guarantee: none; the reduction is exact under the equal-cluster-weight assumption but the resulting Hamiltonian carries up to four-qubit terms and uses twice the coreset-size in qubits.
  - quote: "We show that the 3-means clustering problem can be restated as a weighted MaxCut instance on a complete graph where the vertices are partitioned into three distinct sets."

## Where it could apply
- Target primitive(s): VQE; QAOA (noted as limited for the 3-means Hamiltonian by its four-qubit terms)
- Target application group(s): quantum_ml; optimization
- Code family / hardware assumptions: NISQ gate-model devices, hardware-efficient ansatz, noiseless statevector simulation (CUDA Quantum); qutrit encoding suggested as an alternative for 3-means; no error correction or fault-tolerance assumed

## Caveats
This is a NISQ machine-learning applications paper; the contributions are problem encodings and an empirical demonstration rather than a certificate, decoder, or bound that an external result could consume. The Hamiltonian encodings are reusable, but they carry no performance guarantee for VQE itself (the variational algorithms are heuristics with no strong theoretical guarantees), and solving the coreset optimally need not recover the full-dataset optimum. Results are noiseless simulations up to 25 qubits only, with no demonstration on real hardware or under noise. Do not use the em dash character.