Equivalence of Szegedy’s and coined quantum walks

Szegedy’s quantum walk is a quantization of a classical random walk or Markov chain, where the walk occurs on the edges of the bipartite double cover of the original graph. To search, one can simply quantize a Markov chain with absorbing vertices. Recently, Santos proposed two alternative search algorithms that instead utilize the sign-flip oracle in Grover’s algorithm rather than absorbing vertices. In this paper, we show that these two algorithms are exactly equivalent to two algorithms involving coined quantum walks, which are walks on the vertices of the original graph with an internal degree of freedom. The first scheme is equivalent to a coined quantum walk with one walk step per query of Grover’s oracle, and the second is equivalent to a coined quantum walk with two walk steps per query of Grover’s oracle. These equivalences lie outside the previously known equivalence of Szegedy’s quantum walk with absorbing vertices and the coined quantum walk with the negative identity operator as the coin for marked vertices, whose precise relationships we also investigate.     

Asymptotic distributions of quantum walks on the line with two entangled coins

We advance the previous studies of quantum walks on the line with two coins. Such four-state quantum walks driven by a three-direction shift operator may have nonzero limiting probabilities (localization), thereby distinguishing them from the quantum walks on the line in the basic scenario (i.e., driven by a single coin). In this work, asymptotic position distributions of the quantum walks are examined. We derive a weak limit for the quantum walks and explicit formulas for the limiting probability distribution, whose dependencies on the coin parameter and the initial state of quantum walks are presented. In particular, it is shown that the weak limit for the present quantum walks can be of the form in the basic scenario of quantum walks on the line, for certain initial states of the walk and certain values of the coin parameter. In the case where localization occurs, we show that the limiting probability decays exponentially in the absolute value of a walker??s position, independent of the parity of time.     

Establishing the equivalence between Szegedy’s and coined quantum walks using the staggered model

Coined quantum walks (QWs) are being used in many contexts with the goal of understanding quantum systems and building quantum algorithms for quantum computers. Alternative models such as Szegedy’s and continuous-time QWs were proposed taking advantage of the fact that quantum theory seems to allow different quantized versions based on the same classical model, in this case the classical random walk. In this work, we show the conditions upon which coined QWs are equivalent to Szegedy’s QWs. Those QW models have in common a large class of instances, in the sense that the evolution operators are equal when we convert the graph on which the coined QW takes place into a bipartite graph on which Szegedy’s QW takes place, and vice versa. We also show that the abstract search algorithm using the coined QW model can be cast into Szegedy’s searching framework using bipartite graphs with sinks.     

Localization of two-particle quantum walk on glued-tree and its application in generating Bell states

Studies on two-particle quantum walks show that the spatial interaction between walkers will dynamically generate complex entanglement. However, those entanglement states are usually on a large state space and their evolutions are complex. It makes the entanglement states generated by quantum walk difficult to be applied directly in many applications of quantum information, such as quantum teleportation and quantum cryptography. In this paper, we firstly analyse a localization phenomena of two-particle quantum walk and then introduce how to use it to generate a Bell state. We will show that one special superposition component of the walkers’ state is localized on the root vertex if a certain interaction exists between walkers. This localization is interesting because it is contrary to our knowledge that quantum walk spreads faster than its classical counterpart. More interestingly, the localized component is a Bell state in the coin space of two walkers. By this method, we can obtain a Bell state easily from the quantum walk with spatial interaction by a local measurement, which is required in many applications. Through simulations, we verify that this method is able to generate the Bell state \(\frac{1}{\sqrt{2}}(|A \rangle _1|A\rangle _2 \pm |B\rangle _1|B\rangle _2)\) in the coin space of two walkers with fidelity greater than \(99.99999\,\%\) in theory, and we have at least a \(50\,\%\) probability to obtain the expected Bell state after a proper local measurement.     

Generalized teleportation by quantum walks

We develop a generalized teleportation scheme based on quantum walks with two coins. For an unknown qubit state, we use two-step quantum walks on the line and quantum walks on the cycle with four vertices for teleportation. For any d-dimensional states, quantum walks on complete graphs and quantum walks on d-regular graphs can be used for implementing teleportation. Compared with existing d-dimensional states teleportation, prior entangled state is not required and the necessary maximal entanglement resource is generated by the first step of quantum walk. Moreover, two projective measurements with d elements are needed by quantum walks on the complete graph, rather than one joint measurement with \(d^2\) basis states. Quantum walks have many applications in quantum computation and quantum simulations. This is the first scheme of realizing communicating protocol with quantum walks, thus opening wider applications.     

Controllability and the theory of economic policy: a structural approach

Tinbergen's policy rule states that we must have at least as many policy instruments as the number of target variables if we wish to realize an arbitrarily fixed set of policy targets. We explore the structural characterization of the controllability of economic systems described by a set of static or dynamic equations. First, an economic system is represented as a directed graph, where the nodes stand for economic variables, while the arcs indicate the relations among these variables. Then, the main result is as follows: a static economic system is structurally controllable if and only if there exists a set of disjoint paths on the graph representation or the system which connect the set of instruments to each target. Similar graph-theoretic characterization of structural controllability is obtained for dynamic systems. Conditions for structural output controllability and structural perfect controllability are also discussed.     

Quantum walk on distinguishable non-interacting many-particles and indistinguishable two-particle

We present an investigation of many-particle quantum walks in systems of non-interacting distinguishable particles. Along with a redistribution of the many-particle density profile we show that the collective evolution of the many-particle system resembles the single-particle quantum walk evolution when the number of steps is greater than the number of particles in the system. For non-uniform initial states we show that the quantum walks can be effectively used to separate the basis states of the particle in position space and grouping like state together. We also discuss a two-particle quantum walk on a two-dimensional lattice and demonstrate an evolution leading to the localization of both particles at the center of the lattice. Finally we discuss the outcome of a quantum walk of two indistinguishable particles interacting at some point during the evolution.     

Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations

Quantum walks subject to decoherence generically suffer the loss of their genuine quantum feature, a quadratically faster spreading compared to classical random walks. This intuitive statement has been verified analytically for certain models and is also supported by numerical studies of a variety of examples. In this paper we analyze the long-time behavior of a particular class of decoherent quantum walks, which, to the best of our knowledge, was only studied at the level of numerical simulations before. We consider a local coin operation which is randomly and independently chosen for each time step and each lattice site and prove that, under rather mild conditions, this leads to classical behavior: With the same scaling as needed for a classical diffusion the position distribution converges to a Gaussian, which is independent of the initial state. Our method is based on non-degenerate perturbation theory and yields an explicit expression for the covariance matrix of the asymptotic Gaussian in terms of the randomness parameters.     

Efficiency of open quantum walk implementation of dissipative quantum computing algorithms

An open quantum walk formalism for dissipative quantum computing is presented. The approach is illustrated with the examples of the Toffoli gate and the Quantum Fourier Transform for 3 and 4 qubits. It is shown that the algorithms based on the open quantum walk formalism are more efficient than the canonical dissipative quantum computing approach. In particular, the open quantum walks can be designed to converge faster to the desired steady state and to increase the probability of detection of the outcome of the computation.     

An Example of the Difference Between Quantum and Classical Random Walks

In this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analog. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case. PACS: 03.67.Hk     

Local controllability of quantum systems

We give a criterion that is sufficient for controllability of multipartite quantum systems. We generalize the graph infection criterion to the quantum systems that cannot be described with the use of a graph theory. We introduce the notation of hypergraphs and reformulate the infection property in this setting. The introduced criterion has a topological nature and therefore it is not connected to any particular experimental realization of quantum information processing.     

A quantum Jensen–Shannon graph kernel for unattributed graphs

In this paper, we use the quantum Jensen–Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen–Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) 27 and 28 to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen–Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen–Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.     

Laplacian versus adjacency matrix in quantum walk search

A quantum particle evolving by Schrödinger’s equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace’s operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.     

Time averaged distribution of a discrete-time quantum walk on the path

The discrete time quantum walk which is a quantum counterpart of random walk plays important roles in the theory of quantum information theory. In the present paper, we focus on discrete time quantum walks viewed as quantization of random walks on the path. We obtain a weak limit theorem for the time averaged distribution of our quantum walks.     

Discrete-time quantum walk on the Cayley graph of the dihedral group

The finite dihedral group generated by one rotation and one flip is the simplest case of the non-Abelian group. Cayley graphs are diagrammatic counterparts of groups. In this paper, much attention is given to the Cayley graph of the dihedral group. Considering the characteristics of the elements in the dihedral group, we conduct the model of discrete-time quantum walk on the Cayley graph of the dihedral group by special coding mode. This construction makes Fourier transformation be used to carry out spectral analysis of the dihedral quantum walk, i.e. the non-Abelian case. Furthermore, the relation between quantum walk without memory on the Cayley graph of the dihedral group and quantum walk with memory on a cycle is discussed, so that we can explore the potential of quantum walks without and with memory. Here, the numerical simulation is carried out to verify the theoretical analysis results and other properties of the proposed model are further studied.     

Graph matching using the interference of continuous-time quantum walks

We consider how continuous-time quantum walks can be used for graph matching. We focus in detail on both exact and inexact graph matching, and consider in depth the problem of measuring graph similarity. We commence by constructing an auxiliary graph, in which the two graphs to be matched are co-joined by a layer of indicator vertices (one for each potential correspondence between a pair of vertices). We simulate a continuous-time quantum walk in parallel on the two graphs. The layer of connecting indicator vertices in the auxiliary graph allow quantum interference to take place between the two walks. The interference amplitudes on the indicator vertices are determined by differences in the two walks, and can be used to calculate probabilities for matches between pairs of vertices from the graphs. By applying the Hungarian (Kuhn-Munkres) algorithm to these probabilities, we recover a correspondence mapping between the graphs. To calculate graph similarity, we combine these probabilities with edge-consistency information to give a consistency measure. Based on the consistency measure, we define two graph similarity measures, one of which requires correspondence matches while the second does not. We analyse our approach experimentally using synthetic and real-world graphs. This reveals that our method gives results that are intermediate between the most sophisticated iterative techniques available, and simpler less complex ones.     

基于量子漫步的图形匹配算法进展与展望

图形匹配是图形研究中的重要问题,目前的经典算法受限于存储资源和计算复杂度,未能提供有效的解决方法.基于量子效应,将图形信息存储于量子比特,不仅能够极大减少存储资源的消耗,而且对量子比特进行操作可实现对存储信息的并行计算,从而为有效解决图形匹配问题提供了新的可能.量子漫步作为量子计算中的重要模型,是分析研究图形问题的有效工具.总结了量子计算的特点,介绍了量子漫步的2种模型并对二者进行了比较.然后对目前已有的基于量子漫步的图形匹配算法进行了介绍,对其算法思想、计算过程和优缺点进行了描述,同时还提出了相应的改进思路.在总结分析目前研究存在问题的基础上,探讨了今后的研究方向.     

The CGMV method for quantum walks

We review the main aspects of a recent approach to quantum walks, the CGMV method. This method proceeds by reducing the unitary evolution to canonical form, given by the so-called CMV matrices, which act as a link to the theory of orthogonal polynomials on the unit circle. This connection allows one to obtain results for quantum walks which are hard to tackle with other methods. Behind the above connections lies the discovery of a new quantum dynamical interpretation for well known mathematical tools in complex analysis. Among the standard examples which will illustrate the CGMV method are the famous Hadamard and Grover models, but we will go further showing that CGMV can deal even with non-translation invariant quantum walks. CGMV is not only a useful technique to study quantum walks, but also a method to construct quantum walks à la carte. Following this idea, a few more examples illustrate the versatility of the method. In particular, a quantum walk based on a construction of a measure on the unit circle due to F. Riesz will point out possible non-standard behaviours in quantum walks.     

On the Hitting Times of Quantum Versus Random Walks

The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of—or equivalently, to find—a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case. Then, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem (Tulsi A.: Phys. Rev. A 78:012310 2008) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains. Further, we prove that for any reversible ergodic Markov chain P, the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.     

Quantum walks on simplicial complexes

We construct a new type of quantum walks on simplicial complexes as a natural extension of the well-known Szegedy walk on graphs. One can numerically observe that our proposing quantum walks possess linear spreading and localization as in the case of the Grover walk on lattices. Moreover, our numerical simulation suggests that localization of our quantum walks reflects not only topological but also geometric structures. On the other hand, our proposing quantum walk contains an intrinsic problem concerning exhibition of non-trivial behavior, which is not seen in typical quantum walks such as Grover walks on graphs.