• Open Access

Community Detection in Quantum Complex Networks

Mauro Faccin, Piotr Migdał, Tomi H. Johnson, Ville Bergholm, and Jacob D. Biamonte
Phys. Rev. X 4, 041012 – Published 21 October 2014
PDFHTMLExport Citation

Abstract

Determining community structure is a central topic in the study of complex networks, be it technological, social, biological or chemical, static or in interacting systems. In this paper, we extend the concept of community detection from classical to quantum systems—a crucial missing component of a theory of complex networks based on quantum mechanics. We demonstrate that certain quantum mechanical effects cannot be captured using current classical complex network tools and provide new methods that overcome these problems. Our approaches are based on defining closeness measures between nodes, and then maximizing modularity with hierarchical clustering. Our closeness functions are based on quantum transport probability and state fidelity, two important quantities in quantum information theory. To illustrate the effectiveness of our approach in detecting community structure in quantum systems, we provide several examples, including a naturally occurring light-harvesting complex, LHCII. The prediction of our simplest algorithm, semiclassical in nature, mostly agrees with a proposed partitioning for the LHCII found in quantum chemistry literature, whereas our fully quantum treatment of the problem uncovers a new, consistent, and appropriately quantum community structure.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 6 May 2014

DOI:https://doi.org/10.1103/PhysRevX.4.041012

This article is available under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Authors & Affiliations

Mauro Faccin1,*, Piotr Migdał2,1, Tomi H. Johnson3,4,5,1, Ville Bergholm1, and Jacob D. Biamonte1

  • 1ISI Foundation, Via Alassio 11/c, 10126 Torino, Italy
  • 2ICFO–Institut de Ciències Fotòniques, 08860 Castelldefels (Barcelona), Spain
  • 3Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117543, Singapore
  • 4Clarendon Laboratory, University of Oxford, Parks Road, Oxford OX1 3PU, United Kingdom
  • 5Keble College, University of Oxford, Parks Road, Oxford OX1 3PG, United Kingdom

  • *mauro.faccin@isi.it

Popular Summary

Real-life networks such as groups of animals and biochemical assemblies exhibit complex relationships that can benefit from systematic study. The macroscopic properties of a network cannot be easily deduced from knowledge of its microscopic properties. Such a deduction is aided by the identification of strongly connected subnetworks, called communities. For traditional networked systems, the problem of community detection has, accordingly, received a significant amount of attention, and a multitude of techniques are employed for this task, often based on dynamical processes within the network. No methods are currently known for community detection in quantum networks, despite a growing interest in large networks in quantum biology, transport, and communication. We extend the concept of community detection from classical to quantum systems, providing a crucial missing tool for analyzing quantum systems with a network structure.

We argue that breaking down a quantum system into strongly correlated parts, i.e., a form of community partitioning, is an essential precursor for any simulation that aims to use this partitioning to reduce computational costs. We adapt traditional community detection methods that, as their starting point, use a measure of “closeness” of any two basic network components, denoted “nodes.” The computational costs of simulations scale exponentially with the number of nodes. We investigate quantum systems that are generally smaller than the classical systems typically studied, and we naturally ensure that the closeness measure captures relevant quantum effects, which can therefore lead to partitionings that are significantly different than those expected based on classical analyses. We partition nodes into communities using a quantum-walk process, which is akin to partitioning Hilbert space into orthogonal subspaces, illustrating our analyses on a light-harvesting complex.

We anticipate that our results will be useful for conducting numerical analyses of these systems.

Key Image

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand
Issue

Vol. 4, Iss. 4 — October - December 2014

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 3.0 License. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×