Experimental Multi-Photon Quantum Walk on a Directed Graph

Quantum walks are of crucial importance in the development of quantum information processing algorithms. Recently, another potential application has been proposed, where one could efficiently perform network analysis with quantum walks, especially on vertex centrality ranking. However, it is challenging to rank the centrality of a directed network via quantum walks, since it corresponds to a non-Hermitian Hamiltonian, which leads to non-unitary dynamics and thus cannot be simulated by conventional quantum walks. In this presentation, we solve the non-unitary challenge by introducing pseudo-Hermitian evolutions. We report the first experimental realization of centrality ranking of a directed graph on a photonic platform with multi-photon parity-time-symmetric quantum walks. The experimental results agree well with theoretical predictions.