Growing Random Graphs with Quantum Rules

Hamza Jnane
(Télécom Paris, LTCI, 19 Place Marguerite Perey, 91120 Palaiseau, France)
Giuseppe Di Molfetta
(Université publique, CNRS, LIS, Marseille, France & Quantum Computing Center, Keio University)
Filippo M. Miatto
(Télécom Paris, LTCI, 19 Place Marguerite Perey, 91120 Palaiseau, France)

Random graphs are a central element of the study of complex dynamical networks such as the internet, the brain, or socioeconomic phenomena. New methods to generate random graphs can spawn new applications and give insights into more established techniques. We propose two variations of a model to grow random graphs and trees, based on continuous-time quantum walks on the graphs. After a random characteristic time, the position of the walker(s) is measured and new nodes are attached to the nodes where the walkers collapsed. Such dynamical systems are reminiscent of the class of spontaneous collapse theories in quantum mechanics. We investigate several rates of this spontaneous collapse for an individual quantum walker and for two non-interacting walkers. We conjecture (and report some numerical evidence) that the models are scale-free.

In Giuseppe Di Molfetta, Vivien Kendon and Yutaka Shikano: Proceedings 9th International Conference on Quantum Simulation and Quantum Walks (QSQW 2020), Marseille, France, 20-24/01/2020, Electronic Proceedings in Theoretical Computer Science 315, pp. 38–47.
Published: 3rd April 2020.

ArXived at: http://dx.doi.org/10.4204/EPTCS.315.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org