  Graph kernels are often used in bioinformatics and network applications to
measure the similarity between graphs; therefore, they may be used to construct
efficient graph classifiers. Many graph kernels have been developed thus far,
but to the best of our knowledge there is no existing graph kernel that
considers all subgraphs to measure similarity. We propose a novel graph kernel
that applies a quantum computer to measure the graph similarity taking all
subgraphs into account by fully exploiting the power of quantum superposition
to encode every subgraph into a feature. For the construction of the quantum
kernel, we develop an efficient protocol that removes the index information of
subgraphs encoded in the quantum state. We also prove that the quantum computer
requires less query complexity to construct the feature vector than the
classical sampler used to approximate the same vector. A detailed numerical
simulation of a bioinformatics problem is presented to demonstrate that, in
many cases, the proposed quantum kernel achieves better classification accuracy
than existing graph kernels.
