  In the NISQ-era of quantum computing, we should not expect to see quantum
devices that provide an exponential improvement in runtime for practical
problems, due to the lack of error correction and small number of qubits
available. Nevertheless, these devices should be able to provide other
performance improvements, particularly when combined with existing classical
machines. In this article, we develop several hybrid quantum-classical
clustering algorithms that can be employed as subroutines on small, NISQ-era
devices. These new hybrid algorithms require a number of qubits that is at most
logarithmic in the size of the data, provide performance improvement and/or
runtime improvement over their classical counterparts, and do not require a
black-box oracle. Consequently, we are able to provide a promising near-term
application of NISQ-era devices.
