TY  - JOUR
PB  - SciPost Foundation
DO  - 10.21468/SciPostPhysCore.6.3.058
TI  - On the quantum simulation of complex networks
PY  - 2023/08/24
UR  - https://www.scipost.org/SciPostPhysCore.6.3.058
JF  - SciPost Physics Core
JA  - SciPost Phys. Core
VL  - 6
IS  - 3
SP  - 058
A1  - Magano, Duarte
AU  - Moutinho, João
AU  - Coutinho, Bruno
AB  - Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.
ER  -

@Article{10.21468/SciPostPhysCore.6.3.058,
	title={{On the quantum simulation of complex networks}},
	author={Duarte Magano and João Moutinho and Bruno Coutinho},
	journal={SciPost Phys. Core},
	volume={6},
	pages={058},
	year={2023},
	publisher={SciPost},
	doi={10.21468/SciPostPhysCore.6.3.058},
	url={https://scipost.org/10.21468/SciPostPhysCore.6.3.058},
}