Quantum Theory and Complex Networks

By correctly studying information as an entity fundamentally governed by the laws of physics, development of an emerging common language is already binding certain ideas and mapping some techniques between the fields of quantum physics and complexity science. What’s more, the ubiquitous use of various network and graph theories inside of both disciplines, creates a stage for an abstracted comparison of networked systems, recovering both fields as special cases of more general mathematical entities.

Work along these lines is really only just getting started. And even with these similarities, and other bridges still being built, there seems to be an even vaster host of differences. Pinpointing these similarities and reconciling these differences in increasingly precise terms broadly defines our research commitment. An ultimate goal of our effort is to form a new theory, uniting these disciplines.

Work along these lines is really only just getting started. And even with these similarities, and other bridges still being built, there seems to be an even vaster host of differences. Pinpointing these similarities and reconciling these differences in increasingly precise terms broadly defines our research commitment. An ultimate goal of our effort is to form a new theory, uniting these disciplines.

A theory uniting disciplines

One could argue that the fields of quantum information science and complex network theory (a.k.a. complexity science) both address complexity, yet from opposite perspectives. Indeed, the former makes use of a complex system as a computational resource whereas the later generally studies (and often using computer simulations) the scaling, collective behavior and emergent properties of complex system(s).

Accordingly, how the term complexity arises in these two fields is not always interchangeable. So called, computational complexity in quantum information science considers quantifying computational resources whereas complexity science investigates how relationships between parts give rise to collective behaviors of the whole.

And then after closer inspection, these two fields indeed also share some intriguing similarities. By correctly studying information as an entity fundamentally governed by the laws of physics, our development of an emerging common language is already binding certain ideas and mapping some techniques between these a priori distinct fields. What’s more, the ubiquitous use of various network and graph theories inside of both disciplines, has allowed us to create a stage for an abstracted comparison of networked systems, recovering both fields as special cases of more general mathematical entities.

And even with these similarities, and other bridges still being built, there seems to be an even vaster host of differences. Pinpointing these similarities and reconciling these differences in increasingly precise terms broadly defines our research initiative aimed at a new theory, uniting the disciplines of quantum information science with the theory of complex and networked systems.

Why unite the fields of quantum physics and complex systems science?

The independent problems solved in each of these two fields have proven to be reminiscent of each other. And these different solutions to related problems could evidently be made to better apply across disciplines. This seems especially true for contemporary challenges. For example, multi-level (a.k.a. multiplex) networks are a special case of tensor networks – well studied in quantum theory. Additionally, modern experimental breakthroughs in controlling quantum systems have made the state-of-the-art in the size of the state-spaces considered to be roughly the same in both disciplines. As this size of accessible coherent (non-mean field) quantum systems continues to grow, the emergent properties of quantum complex systems will take center stage as a quantum generalization of complex and networked systems science emerges. Note that in particular, we are not concerned with mean-field condensates or distributed quantum communication networks but instead we are making headway towards a full first-principles account of a ‘quantum theory’ of complex and networked systems. It’s a very different challenge.

What are some promising avenues for new research?

Community detection for quantum systems is an area that seems to make a lot of sense for potential applications of complex network theory inside of quantum physics [Physical Review X 4, 041012 (2014)]. Particularly in the areas where quantum effects have been shown to be present in biological systems (here a community might be a region in which a particle might travel which behaves quantum mechanically).

Additionally, chemical reaction networks have been shown to correspond to certain wide classes of non-unitary field theories [Baez and Biamonte]. The bridges here are interesting, a version of coherent states emerged as the steady state solution to a wide class of networks, results related to conserved quantiles have been established by Baez and Fong and much much more. Yet central ideas related to network theory have yet to be mapped to this discipline. I could tell you some really exciting ideas, but then you’d know what we’re working on.

And of course, the cross over among quantum tensor networks and multiplex networks is certainly just as interesting as casting the equations of motion for multiplex network evolution into the framework defined in ‘quantum techniques for stochastic mechanics’.

What should I read first?

We’ve written a few blog articles that explain some aspects of ‘quantum network theory’.

And you should also check out the ‘network theory project’ which seeded many of the overall directions taken here.

Our papers merging quantum physics and complex systems science

Quantum Techniques for Stochastic Mechanics
John C. Baez, Jacob Biamonte
Book preprint arXiv:1209.3632 (2016) [PDF]

john-baez

Community Detection in Quantum Complex Networks
with Mauro Faccin, Piotr Migdał, Tomi Johnson and Ville Bergholm
Physical Review X 4, 041012 (2014)
abstract, popular summary and open access PDF

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.

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.

[PDF]

Degree Distribution in Quantum Walks on Complex Networks
with Mauro Faccin, Tomi Johnson, Sabre Kais and Piotr Migdał
Physical Review X 3, 041007 (2013)
abstract, popular summary and open access PDF

Abstract
In this theoretical study, we analyze quantum walks on complex networks, which model network-based processes ranging from quantum computing to biology and even sociology. Specifically, we analytically relate the average long-time probability distribution for the location of a unitary quantum walker to that of a corresponding classical walker. The distribution of the classical walker is proportional to the distribution of degrees, which measures the connectivity of the network nodes and underlies many methods for analyzing classical networks, including website ranking. The quantum distribution becomes exactly equal to the classical distribution when the walk has zero energy, and at higher energies, the difference, the so-called quantumness, is bounded by the energy of the initial state. We give an example for which the quantumness equals a Rényi entropy of the normalized weighted degrees, guiding us to regimes for which the classical degree-dependent result is recovered and others for which quantum effects dominate.

Popular Summary
Imagine a web surfer mindlessly wandering from one page to another by clicking randomly on one of the many hyperlinks on each page they encounter. Where would they end up? This question and the answer to it actually are essential to how Google’s web-search engine decides the relative importance of the world’s webpages. Algorithmically, the world’s webpages are represented by a huge network of nodes (pages) and links (hyperlinks) and the mindless internet surfer by a “random walker.” Now, what happens if the random walker is quantum mechanical instead? This may sound like a question for science fiction, but it is actually part of a recent fundamental drive toward merging the science of complex networks—relevant to many scientific disciplines, including statistical physics, biology, computer science, and social science—with quantum mechanics. In this paper, we make one of the first steps in that drive: to uncover and delineate some of the fundamental connections and differences between classical and quantum networks, by developing and investigating a revealing toy model of quantum random walks on complex networks.

It is well known that for a classical random walker on a complex network, the probability of finding the walker on a node after a long time is proportional to the probability of that node’s degree (or the number of links to other nodes), reflecting only the network’s connective topology. A quantum walker, however, brings conceptually nontrivial subtleties to the problem, including hallmark quantum effects such as quantum interference and the ability of a walker to be in a coherent superposition of states. In addition, the long-time state of a quantum walker depends on its initial state and most often does not converge to a steady state.

Here, we have constructed a model of a quantum walker on a network. The walker’s state is a multicomponent one, with the squared amplitude of the ith component representing the probability of finding the walker at node i of the network. This multicomponent state evolves in time according to a Schrödinger equation that has a correspondence with the classical walker. By investigating this model, we have succeeded in uncovering the following properties: (1) When the walker starts from its zero-energy ground state, the long-time average of probability of finding it at a node follows the classical result; (2) at higher energies, the walker’s long-time behavior deviates from the classical case, reflecting its quantumness, and this quantumness is quantitatively bounded by the initial energy of the walker and equal to Rényi entropy—a property associated with the network’s degree distribution.

Our paper thus provides the first analytical connection between classical and quantum walks on complex networks, as well as highlighting their differences. We see this work as the beginning of an exciting development that will involve quantum physics, graph and network theory, and the physics of stochastic processes.

[PDF]

Quantum Transport Enhancement by Time-Reversal Symmetry Breaking
with Zolt ́an Zimbor ́as, Mauro Faccin, Zoltan Kadar, and James Whitfield
Scientific Reports 3, 2361 (2013)
abstract and open access PDF

Models of continuous time quantum walks, which implicitly use time-reversal symmetric Hamiltonians, have been intensely used to investigate the effectiveness of transport. Here we show how breaking time-reversal symmetry of the unitary dynamics in this model can enable directional control, enhancement, and suppression of quantum transport. Examples ranging from exciton transport to complex networks are presented. This opens new prospects for more efficient methods to transport energy and information.

scientific-reports

Chiral Quantum Walks
Dawei Lu, Jacob Biamonte, Jun Li, Hang Li, Tomi Johnson, Ville Bergholm, Mauro Faccin, Zoltan Zimboras,
Raymond Laflamme, Jonathan Baugh, Seth Lloyd
Phys. Rev. A 93, 042302 (2016)
abstract and link

Abstract. Given its importance to many other areas of physics, from condensed matter physics to thermodynamics, time-reversal symmetry has had relatively little influence on quantum information science. Here we develop a network-based picture of time-reversal theory, classifying Hamiltonians and quantum circuits as time-symmetric or not in terms of the elements and geometries of their underlying networks. Many of the typical circuits of quantum information science are found to exhibit time-asymmetry. Moreover, we show that time-asymmetry in circuits can be controlled using local gates only, and can simulate time-asymmetry in Hamiltonian evolution. We experimentally implement a fundamental example in which controlled time-reversal asymmetry in a palindromic quantum circuit leads to near-perfect transport. Our results pave the way for using time-symmetry breaking to control coherent transport, and imply that time-asymmetry represents an omnipresent yet poorly understood effect in quantum information science.

quantum-walks

Related Papers by John Baez

Relevant Scientific Blog Articles

Talks

Quantum Physics and Complex Networks: chiral quantum walks (talk by Jacob Biamonte)
Workshop on critical and collective effects in graphs and networks, April 25 – April 29, Moscow, 2016
Department of Discrete Mathematics, MITP.  [PDF] video

Quantum theory meets complex networks
Russian Quantum Center (RQC) – Moscow June 10, 2016
abstract slides

A ‘complex network’ is defined only conceptually.  It’s a graph with certain topological features—deviating from networks such as lattices or random graphs and providing predictive features in a range of graphs modelling real systems.  For example, the probability distribution of a stochastic walker clicking mindlessly on links on the WWW network is proportional to the distribution of degrees, which measures the connectivity of the network nodes and underlies many methods for analyzing classical networks, including website ranking.  Various types of graph and network methods are being employed in quantum information science and at the same time, information theory and entropic measures have recently been employed to better understand features of traditional (non-quantum) complex networks.  The name of the game is to build a bridge between these two disciplines, to develop new tools and to study these types of complex networks with quantum theory.  This talk will present a broad overview of the sorts of networks used in the areas of modern quantum theory and broadly outline the areas where there seems to be the most promising overlap between these two fields.   We will then explain a quantum walker on the WWW.  The quantum probability distribution in our model becomes exactly equal to the classical distribution when the walk has zero energy, and at higher energies, the difference, the so-called quantumness, is bounded by the energy of the initial state. We give an example for which the quantumness equals a Rényi entropy of the normalized weighted degrees, guiding us to regimes for which the classical degree-dependent result is recovered and others for which quantum effects dominate.

[PDF]

Common networks in quantum theory

Quantum spins arranged on graphs – quantum random walks on graphs

Quantum circuits/networks – tool to represent operations appearing in quantum information science. This includes quantum algorithms and quantum communication protocols. `Quantum complexity science’ attempts to quantify the number of gates in such networks
papers

Categorical Quantum Circuits
Ville Bergholm and J.D. Biamonte
Journal of Physics A: Mathematical and Theoretical 44:24, 245304 (2011)

Superconducting quantum (electrical) circuits – low-temperature (superconducting circuit) electrical network built from inductors, capacitors and Josephson Junctions. These are also called, quantum electrical networks
papers

Sign and Magnitude Tunable Coupler for Superconducting Flux Qubits
with Richard Harris et al.
Physical Review Letters 98, 177001 (2007)

Tensor network states – graphical depiction of a quantum state or operations defined in terms of interacting network components (tensors) which are multi-linear maps. Used widely in the numerical simulation of quantum systems
papers

Tensor Network Methods for Invariant Theory
Jacob Biamonte, Ville Bergholm, Marco Lanzagorta
J. Phys. A: Math. Theor. 46, 475301 (2013)

Tensor Network Contractions for #SAT
Jacob Biamonte, Jacob Turner and Jason Morton
Journal of Statistical Physics 160, 1389 (2015)

Categorical Tensor Network States
J.D. Biamonte, Stephen R.Clark and Dieter Jaksch
AIP Advances 1:4, 042172 (2011)

Quantum ‘graph states’, etc. – various maps between graphs and states exist. These have allowed researchers to study properties of quantum systems by exploiting graph theory directly. Examples include (i) graph states; (ii) boolean-states; (iii) hyper-graph states; others…
papers

Categorical Tensor Network States
J.D. Biamonte, Stephen R.Clark and Dieter Jaksch
AIP Advances 1:4, 042172 (2011)

Areas to explore

Quantum versus stochastic walks on complex network topologies

Tensor networks vs multiplex networks

Quantum versions of community detection

Entropic measures on networks

Quantum communication networks

Growing networks

Ising model — as a computational resource papers

Non-perturbative k-body to two-body Commuting Conversion Hamiltonians and Embedding Problem Instances into Ising Spins
Jacob Biamonte
Physical Review A 77, 052331 (2008)

Ground State Spin Logic
James Whitfield, Mauro Faccin and Jacob Biamonte
European Physics Letters 99, 57004 (2012)

Quantum algorithms to calculate network properties papers

Quantum algorithm to find the energy gap of molecular Hamiltonians:

Simulation of Electronic Structure Hamiltonians using Quantum Computers
with James Whitfield and Alan Aspuru-Guzik
Molecular Physics 109, 735 (2011)

Leave a Reply

Your email address will not be published. Required fields are marked *