Clustering on NISQ hardware is constrained by data loading and limited qubits. We present qc-kmeans, a hybrid compressive $k$-means that summarizes a dataset with a constant-size Fourier-feature sketch and selects centroids by solving small per-group QUBOs with shallow QAOA circuits. The QFF sketch estimator is unbiased with mean-squared error $O\left(\varepsilon^{2}\right)$ for $B, S=\Theta\left(\varepsilon^{-2}\right)$, and the peak-qubit requirement $q_{\text {peak }}=\max \left\{D,\left\lceil\log _{2} B\right\rceil+1\right\}$ does not scale with the number of samples. A refinement step with elitist retention ensures non-increasing surrogate cost. In Qiskit Aer simulations (depth $p=1$), the method ran with $\leq 9$ qubits on low-dimensional synthetic benchmarks and achieved competitive sum-of-squared errors relative to quantum baselines; runtimes are not directly comparable. On nine real datasets (up to $4.3 \times 10^{5}$ points), the pipeline maintained constant peak-qubit usage in simulation. Under IBM noise models, accuracy was similar to the idealized setting. Overall, qc-kmeans offers a NISQ-oriented formulation with shallow, bounded-width circuits and competitive clustering quality in simulation.