【論文出版】Graph Kernels Encoding Features of All Subgraphs by Quantum Superposition

修士課程のときの論文が IEEE JETCAS に出版されました。なお、 arXiv 版はこちら。

内容としては、量子計算を機械学習に使った論文で、分子などを表すグラフの特徴量を重ね合わせ状態に符号化してカーネルを計算するもの。

グラフは頂点数を \(n\) とすると、 \(2^n\) 個の部分グラフを持つ。一方、 \(n\) 量子ビットは \(2^n\) 個の状態を重ね合わせで保持できる。これは相性が良いのでは？というのが着眼点。

ただ、すべての部分グラフが一致しているかで判定するグラフカーネルは NP 困難であるという先行研究 [T. Gärtner et al., 2003] が存在しており、量子計算でもそのような計算量クラスは高速に解くことは難しいといわれるため、それは断念。したがって、本論文では、頂点数や辺の数などをそれぞれの部分グラフについて符号化する形にしており、それでも実験的に精度は十分出ることを示している。また、その際の計算量を古典で同じことをおこなう場合と理論的に比較し、優位性があることも示している。

でも、やっぱりグラフ同型問題を量子計算で多項式時間で解くような仕事ができたら本当は良かったなぁ・・・・・。