Quantum Walks

Chiral quantum walks offer a means to control quantum evolutions on graphs by controlling time-reversal symmetry breaking and the interplay of this effect with the global topological structure of the underlying network.  The theory is part of a larger idea to merge time-symmetry theory with quantum information science and to address the quantum challenges of control on complex networks.

For a readable introduction to quantum walks see these Azimuth Blog posts as well as the review articles on walks listed at the end of this page.

A ‘single particle quantum walker’ moves on a graph, with dynamics governed by Schrödinger’s equation.  Originally proposed by Richard Feynman, these days quantum walks have become a standard model used to study quantum transport and in fact, quantum walks can even represent a universal model of quantum computation.  Recently we developed a theory of quantum walks which exhibit time-reversal symmetry breaking in their node-to-node transition probabilities. We named these, ‘chiral quantum walks‘.

Defining 'Chiral' Quantum Walks

  • Quantum Transport Enhancement by Time-Reversal Symmetry Breaking
    by Zoltan Zimboras, Mauro Faccin, Zoltan Kadar, James Whitfield, Ben Lanyon and Jacob Biamonte
    Scientific Reports 3, 2361 (2013)

The main application we have found so far is to use this symmetry breaking as a passive means to control and direct quantum transport.  We mathematically classified time-symmetric and time-asymmetric Hamiltonians and quantum circuits in terms of their underlying network elements and geometric structures.  And we numerically studied several illustrative examples.

In a recent collaboration, we helped experimentally implemented the most fundamental time-reversal asymmetric process.  The experiments applied local gates in an otherwise time-symmetric quantum circuit to induce time-reversal asymmetry and thereby achieve (i) directional biasing in the transition probability between basis states, (ii) the controlled enhancement of and hence (iii) the controlled suppression of these transport probabilities.

Our results imply that the physical effect of time-symmetry breaking can play a role in coherent transport and offer an alternative means to control a quantum process.  We have found the effect to be omnipresent in a range of quantum information protocols and algorithms and hence provides what might turn out to be a useful yet untapped resource. We have worked towards classification of the network configurations that give rise to the effect.

Scientific Reports 3, 2361 (2013)

Quantum Transport Enhancement by Time-Reversal Symmetry Breaking
by Zoltan Zimboras, Mauro Faccin, Zoltan Kadar, James Whitfield, Ben Lanyon and Jacob Biamonte
Scientific Reports 3, 2361 (2013)
abstract and #openaccess link

Abstract. 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. [PDF]


Physical Review A 93, 042302 (2016)

Chiral Quantum Walks
DaWei Lu, Jacob Biamonte, Jun Li, Hang Li, Tomi H. Johnson, Ville Bergholm, Mauro Faccin, Zoltán Zimborás, Raymond Laflamme, Jonathan Baugh and Seth Lloyd
Physical Review A 93, 042302 (2016)
abstract and PDF

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.


Classification of Time-Reversal Symmetry Breaking in Quantum Walks
Jacob Biamonte and Jacob Turner
Draft available on request. (2016)

Review articles on [time symmetric] quantum walks

Quantum walks: a comprehensive review,S.E. Venegas-Andraca, Quantum Information Processing vol. 11(5), pp. 1015-1106 (2012) arXiv:1201.4780

Quantum random walks – an introductory overview, Julia Kempe, Contemporary Physics, Vol. 44 (4), p.307-327, 2003 arXiv:quant-ph/0303081

Decoherence in quantum walks – a review, Viv Kendon, Math. Struct. in Comp. Sci 17(6) pp 1169-1220 (2006) arXiv:quant-ph/0606016

Our other papers on quantum walks

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

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.


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

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.


Popular Media on Chiral Quantum Walks

  • First experiment to break time-reversal symmetry in quantum walks, Institute for Quantum Computing, University of Waterloo – Press Release

Experimental data and quantum circuit from Physical Review A 93, 042302 (2016).


Classification of time-symmetry breaking in quantum walks
Moscow State University – July 25, 2016
abstract slides


Quantum walks on graphs represent an established model capturing essential physics behind a host of natural and synthetic phenomena. Quantum walks have further been proven to provide a universal model of quantum computation and have been shown to capture the core underlying physics of several biological processes in which quantum effects play a central role. A ‘single particle quantum walker’ moves on a graph, with dynamics governed by Schrödinger’s equation and quantum theory predicts the probability of a walker to transition between the graphs’ nodes. Any quantum process in finite dimensions can be viewed as a single particle quantum walk.

Until recently, quantum walks implicitly modeled only probability transition rates between nodes which were symmetric under time inversion. Breaking this time-reversal symmetry provides a new arena to consider applications of this symmetry breaking and to better understand its foundations. The main application discovered so far is that this symmetry breaking can be utilized as a passive means to control and direct quantum transport.

A subtle interplay between the assignment of complex Hamiltonian edge weights and the geometry of the underlying network has emerged in a sequence of studies. This interplay has been central to several works, but in the absence of definitive statements, past work has only produced criteria for a process on a graph to be time-symmetric. Leaving the classification problem and its implications, open.

Here we provide a full classification of the Hamiltonians which enable the breaking of time-reversal symmetry in their induced transition probabilities. Our results are furthermore proven in terms of the geometry of the corresponding Hamiltonian support graph. We found that the effect can only be present if the underlying support graph is not bipartite whereas certain bipartite graphs give rise to transition probability suppression, but not broken time-reversal symmetry. These results fill an important missing gap in understanding the role this omnipresent effect has in quantum information science.


Using mathematical analysis, before solving the general case, we motivate our study be solving several toy versions of the time-symmetry classification problem. The general classification results are found using a host of techniques primarily from algebraic geometry and the theory of invariants.  In all cases, the connectivity of the network plays a central role in the presence of the effect providing an avenue to explore the effect using tools from complex network and graph theory.


We study a natural equivalence relation on quantum walks using tools from classical representation theory. We proved that a time-asymmetric quantum walk has a non-bipartite Hamiltonian support graph, and that the non-bipartite requirement is strict. Additionally, we showed that a bipartite (and hence time-symmetric) Hamiltonian can be made to break time-symmetry through the addition of non-uniform diagonal Hamiltonian terms-corresponding to self-loops in the network picture. We further proved that the addition of diagonal terms (called disorder in some areas of quantum theory) has no effect on Hamiltonians that are equivalent to real matrices. The general results of the classification rest on the proof of several core theorems, including a result which shows that if all the specific set—which we provide—of invariants of a given Hamiltonian take real values, then the induced evolution will necessarily be time-symmetric. Furthermore, we show that trees are the only graphs where there is a unique quantum walk up to equivalence.


Any quantum process in finite dimensions, including quantum circuits, algorithms, quantum gates, protocols and models of coherent and open quantum transport can be viewed as a single particle quantum walk on a graph. By changing to this framework, we have found the effect to be omnipresent—yet previously unnoticed—in a range of such quantum information protocols and algorithms. The division found in our classification not only fills a gap in the quantum walks literature which has recently began to study time reversal symmetry breaking, but has implications in the future target application areas.

[1] Classification of time-reversal symmetry breaking in quantum walks
Jacob Biamonte and Jacob Turner
Draft available on request. (2016)


Leave a Reply

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