We propose a distance-based quantum supervised learning protocol that implements a kernel based on the quantum state fidelity between training and test data. In principle, a swap-test with the test datum and an entangled state, that encodes training and label data in a specific form, followed by measuring an expectation value of a two-qubit observable, which takes the combined class label and state-overlap into account, completes the classification. The quantum kernel can be tailored systematically with a quantum circuit to raise the kernel to an arbitrary power and to assign arbitrary weights to each training data. As an interesting finding we document a connection between the proposed classifier and the famous Helstrom measurement for the optimal quantum state discrimination. Finally, we verify our method via classical simulations with a realistic noise model and proof-of-principle experiments using the IBM quantum cloud platform.