Science of Machine Learning

Quantum search over huge network for hidden structures

- High-speed search over hypergraphs via quantum walk -

Abstract

The goal of this research is to devise fast algorithms that search a huge input hypergraph for a substructure (i.e., sub-hypergraph) satisfying prespecified conditions, if it exists. Such algorithms are expected to discover new laws or principles that have been hidden in massive data, such as web access logs and sensor data. Presented here is a novel search algorithm that takes advantages of state-of-the-art techniques regarding quantum walk. This quantum algorithm runs much faster than any possible classical (i.e., non-quantum) algorithms, and also than the celebrated quantum search algorithm invented by Grover. The proposed algorithm is thus much more likely to find a specific substructure hidden in so huge a input hypergraph that classical algorithms fail or require unallowably long time to deal with.

Photos

Poster


Please click the thumbnail image to open the full-size PDF file.

Presenters

Seiichiro Tani
Seiichiro Tani
Media Information Laboratory
Yasuhito Kawano
Yasuhito Kawano
Media Information Laboratory
Yasuhiro Takahashi
Yasuhiro Takahashi
Media Information Laboratory
Go Kato
Go Kato
Media Information Laboratory