  Quantum computing opens exciting opportunities for kernel-based machine
learning methods, which have broad applications in data analysis. Recent works
show that quantum computers can efficiently construct a model of a classifier
by engineering the quantum interference effect to carry out the kernel
evaluation in parallel. For practical applications of these quantum machine
learning methods, an important issue is to minimize the size of quantum
circuits. We present the simplest quantum circuit for constructing a
kernel-based binary classifier. This is achieved by generalizing the
interference circuit to encode data labels in the relative phases of the
quantum state and by introducing compact amplitude encoding, which encodes two
training data vectors into one quantum register. When compared to the simplest
known quantum binary classifier, the number of qubits is reduced by two and the
number of steps is reduced linearly with respect to the number of training
data. The two-qubit measurement with post-selection required in the previous
method is simplified to single-qubit measurement. Furthermore, the final
quantum state has a smaller amount of entanglement than that of the previous
method, which advocates the cost-effectiveness of our method. Our design also
provides a straightforward way to handle an imbalanced data set, which is often
encountered in many machine learning problems.
