SciPost Submission Page
On the quantum simulation of complex networks
by Duarte Magano, João Moutinho, Bruno Coutinho
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Duarte Magano |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/2212.06126v3 (pdf) |
| Date accepted: | 2023-07-20 |
| Date submitted: | 2023-06-27 09:37 |
| Submitted by: | Magano, Duarte |
| Submitted to: | SciPost Physics |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approaches: | Theoretical, Computational |
Abstract
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.
List of changes
1) We removed an unwanted repetition of "in the i-th row of A"
2) We corrected the typo “Schödinger” -> “Schrödinger”
Published as SciPost Phys. Core 6, 058 (2023)