Continuous-time quantum walks on star graphs

In this paper, we investigate continuous-time quantum walk on star graphs. It is shown that quantum central limit theorem for a continuous-time quantum walk on star graphs for N-fold star power graph, which are invariant under the quantum component of adjacency matrix, converges to continuous-time quantum walk on K₂ graphs (complete graph with two vertices) and the probability of observing walk tends to the uniform distribution.     

On the Relationship Between Continuous- and Discrete-Time Quantum Walk

Quantum walk is one of the main tools for quantum algorithms. Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. But whereas a continuous-time random walk can be obtained as the limit of a sequence of discrete-time random walks, the two types of quantum walk appear fundamentally different, owing to the need for extra degrees of freedom in the discrete-time case. In this article, I describe a precise correspondence between continuous- and discrete- time quantum walks on arbitrary graphs. Using this correspondence, I show that continuous-time quantum walk can be obtained as an appropriate limit of discrete-time quantum walks. The correspondence also leads to a new technique for simulating Hamiltonian dynamics, giving efficient simulations even in cases where the Hamiltonian is not sparse. The complexity of the simulation is linear in the total evolution time, an improvement over simulations based on high-order approximations of the Lie product formula. As applications, I describe a continuous-time quantum walk algorithm for element distinctness and show how to optimally simulate continuous-time query algorithms of a certain form in the conventional quantum query model. Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.     

State transfer on two-fold Cayley trees via quantum walks

Perfect state transfer(PST)has great significance due to its applications in quantum information processing and quantum computation.The main problem we study in this paper is to determine whether the two-fold Cayley tree,an extension of the Cayley tree,admits perfect state transfer between two roots using quantum walks.We show that PST can be achieved by means of the so-called nonrepeating quantum walk[Phys.Rev.A 89042332(2014)]within time steps that are the distance between the two roots;while both the continuous-time quantum walk and the typical discrete-time quantum walk with Grover coin approaches fail.Our results suggest that in some cases the dynamics of a discrete-time quantum walk may be much richer than that of the continuous-time quantum walk.     

基于散射量子行走的完全图上结构异常搜索算法

完全图K_N 上某个顶点连接到图G将破坏其对称性. 为加速定位这类结构异常, 基于散射量子行走模型设计搜索算法, 首先给出了算法酉算子的定义, 在此基础上利用完全图的对称性, 将算法的搜索空间限定为一个低维的坍缩图空间. 以G为一个顶点的情况为例, 利用硬币量子行走模型上的研究结论简化了坍缩图空间中酉算子的计算, 并借助矩阵扰动理论分析算法演化过程. 针对星图S_N 上结构异常的研究表明, 以星图中心节点为界将整个图分为左右两个部分, 当且仅当两部分在N→∞时具有相同的特征值, 搜索算法可以获得量子加速. 本文说明星图上的分析方法和结论可以推广至完全图的坍缩图上. 基于此, 本文证明无论完全图连接的图G结构如何, 搜索算法均可在O(√N) 时间内定位到目标顶点, 成功概率为1-O(1√N), 即量子行走搜索该类异常与经典搜索相比有二次加速.     

基于相位匹配的量子行走搜索算法及电路实现

量子行走是经典随机行走在量子力学框架下的对应, 理论上可以用来解决一类无序数据库的搜索问题. 因为携带信息的量子态的扩散速度与经典相比有二次方式的增长, 所以量子行走优于经典随机行走, 量子行走的特性值得加以利用. 量子行走作为一种新发现的物理现象的数学描述, 引发了一种新的思维方式, 孕育了一种新的理论计算模型. 最新研究表明, 量子行走本身也是一种通用计算模型, 可被视为设计量子算法的高级工具, 因此受到部分计算机理论科学领域学者的关注和研究. 对于多数问题求解方案的量子算法的设计, 理论上可以只在量子行走模型下进行考虑. 基于Grover算法的相位匹配条件, 本文提出了一个新的基于量子行走的搜索算法. 理论演算表明: 一般情况下本算法的时间复杂度与Grover算法相同, 但是当搜索的目标数目多于总数的1/3时, 本算法搜索成功的概率要大于Grover算法. 本文不但利用Grover算法中相位匹配条件构造了一个新的量子行走搜索算法, 而且在本研究室原有的量子电路设计研究成果的基础上给出了该算法的量子电路表述.     

Search algorithm on strongly regular graphs based on scattering quantum walks

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs(SRGs) with parameters(N, k, λ, μ) achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm's performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O(√N) time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.     

星图上的散射量子行走搜索算法

量子行走是一种典型的量子计算模型, 近年来开始受到量子计算理论研究者们的广泛关注. 本文首先证明了在星图上硬币量子行走与散射量子行走的酉等价关系, 之后提出了一个在星图上的散射量子行走搜索算法. 该算法的时间复杂度与Grover算法相同, 但是当搜索的目标数目多于总数的1/3时搜索成功概率大于Grover算法.     

Approximate locality for quantum systems on graphs

In this Letter we make progress on a long-standing open problem of Aaronson and Ambainis [Theory Comput. 1, 47 (2005)]: we show that if U is a sparse unitary operator with a gap Delta in its spectrum, then there exists an approximate logarithm H of U which is also sparse. The sparsity pattern of H gets more dense as 1/Delta increases. This result can be interpreted as a way to convert between local continuous-time and local discrete-time quantum processes. As an example we show that the discrete-time coined quantum walk can be realized stroboscopically from an approximately local continuous-time quantum walk.     

Investigation of continuous-time quantum walk by using Krylov subspace-Lanczos algorithm

In papers [Jafarizadehn and Salimi, Ann. Phys. 322, 1005 (2007) and J. Phys. A: Math. Gen. 39, 13295 (2006)], the amplitudes of continuous-time quantum walk (CTQW) on graphs possessing quantum decomposition (QD graphs) have been calculated by a new method based on spectral distribution associated with their adjacency matrix. Here in this paper, it is shown that the CTQW on any arbitrary graph can be investigated by spectral analysis method, simply by using Krylov subspace-Lanczos algorithm to generate orthonormal bases of Hilbert space of quantum walk isomorphic to orthogonal polynomials. Also new type of graphs possessing generalized quantum decomposition (GQD) have been introduced, where this is achieved simply by relaxing some of the constrains imposed on QD graphs and it is shown that both in QD and GQD graphs, the unit vectors of strata are identical with the orthonormal basis produced by Lanczos algorithm. Moreover, it is shown that probability amplitude of observing the walk at a given vertex is proportional to its coefficient in the corresponding unit vector of its stratum, and it can be written in terms of the amplitude of its stratum. The capability of Lanczos-based algorithm for evaluation of CTQW on graphs (GQD or non-QD types), has been tested by calculating the probability amplitudes of quantum walk on some interesting finite (infinite) graph of GQD type and finite (infinite) path graph of non-GQD type, where the asymptotic behavior of the probability amplitudes at the limit of the large number of vertices, are in agreement with those of central limit theorem of [Phys. Rev. E 72, 026113 (2005)]. At the end, some applications of the method such as implementation of quantum search algorithms, calculating the resistance between two nodes in regular networks and applications in solid state and condensed matter physics, have been discussed, where in all of them, the Lanczos algorithm, reduces the Hilbert space to some smaller subspaces and the problem is investigated in the subspace with maximal dimension.     

Transport Efficiency of Continuous-Time Quantum Walks on Graphs

Continuous-time quantum walk describes the propagation of a quantum particle (or an excitation) evolving continuously in time on a graph. As such, it provides a natural framework for modeling transport processes, e.g., in light-harvesting systems. In particular, the transport properties strongly depend on the initial state and specific features of the graph under investigation. In this paper, we address the role of graph topology, and investigate the transport properties of graphs with different regularity, symmetry, and connectivity. We neglect disorder and decoherence, and assume a single trap vertex that is accountable for the loss processes. In particular, for each graph, we analytically determine the subspace of states having maximum transport efficiency. Our results provide a set of benchmarks for environment-assisted quantum transport, and suggest that connectivity is a poor indicator for transport efficiency. Indeed, we observe some specific correlations between transport efficiency and connectivity for certain graphs, but, in general, they are uncorrelated.     

On the quantum CTRW approach

The concept of continuous-time random walk is generalized into the quantum approach using a completely positive map. This approach introduces in a phenomenological way the concept of disorder in the transport problem of a quantum open system. If the waiting-time of the continuous-time renewal approach is exponential we recover a semigroup for a dissipative quantum walk. Two models of non-Markovian evolution have been solved considering different types of waiting-time functions.     

Experimental observations of boundary conditions of continuous-time quantum walks

The continuous-time quantum walk(CTQW) is the quantum analogue of the continuous-time classical walk and is widely used in universal quantum computations. Here, taking the advantages of the waveguide arrays, we implement large-scale CTQWs on chips. We couple the single-photon source into the middle port of the waveguide arrays and measure the emergent photon number distributions by utilizing the fiber coupling platform. Subsequently, we simulate the photon number distributions of the waveguide arrays by considering the boundary conditions. The boundary conditions are quite necessary in solving the problems of quantum mazes.     

Investigation of continuous-time quantum walk via spectral distribution associated with adjacency matrix

Using the spectral distribution associated with the adjacency matrix of graphs, we introduce a new method of calculation of amplitudes of continuous-time quantum walk on some rather important graphs, such as line, cycle graph C_n, complete graph K_n, graph G_n, finite path and some other finite and infinite graphs, where all are connected with orthogonal polynomials such as Hermite, Laguerre, Tchebichef, and other orthogonal polynomials. It is shown that using the spectral distribution, one can obtain the infinite time asymptotic behavior of amplitudes simply by using the method of stationary phase approximation (WKB approximation), where as an example, the method is applied to star, two-dimensional comb lattices, infinite Hermite and Laguerre graphs. Also by using the Gauss quadrature formula one can approximate the infinite graphs with finite ones and vice versa, in order to derive large time asymptotic behavior by WKB method. Likewise, using this method, some new graphs are introduced, where their amplitudes are proportional to the product of amplitudes of some elementary graphs, even though the graphs themselves are not the same as the Cartesian product of their elementary graphs. Finally, by calculating the mean end to end distance of some infinite graphs at large enough times, it is shown that continuous-time quantum walk at different infinite graphs belong to different universality classes which are also different from those of the corresponding classical ones.     

Survival probabilities in coherent exciton transfer with trapping

In the quest for signatures of coherent transport we consider exciton trapping in the continuous-time quantum walk framework. The survival probability displays different decay domains, related to distinct regions of the spectrum of the Hamiltonian. For linear systems and at intermediate times the decay obeys a power law, in contrast with the corresponding exponential decay found in incoherent continuous-time random walk situations. To differentiate between the coherent and incoherent mechanisms, we present an experimental protocol based on a frozen Rydberg gas structured by optical dipole traps.     

初态对光波导阵列中连续量子行走影响的研究

本文使用近邻耦合模型得到的解析解,分析了周期性波导中输入态对量子行走的粒子数的概率分布函数 和二阶相干性的影响.结果表明:输入态的对称性质对量子行走过程的二阶相干度有影响, 而对粒子数的概率分布函数影响不大. 关键词： 周期性光波导阵列 量子行走 二阶相干度 纠缠态     

Skyrmion burst and multiple quantum walk in thin ferromagnetic films

We propose a new type of quantum walk in thin ferromagnetic films. A giant Skyrmion collapses to a singular point in a thin ferromagnetic film, emitting spin waves, when external magnetic field is increased beyond the critical one. After the collapse the remnant is a quantum walker carrying spin S. We determine its time evolution and show the diffusion process is a continuous-time quantum walk. We also analyze an interference of two quantum walkers after two Skyrmion bursts. The system presents a new type of quantum walk for S>1/2, where a quantum walker breaks into 2S quantum walkers.     

A Quantum Walk Model for Idea Propagation in Social Network and Group Decision Making

We propose a quantum walk model to investigate the propagation of ideas in a network and the formation of agreement in group decision making. In more detail, we consider two different graphs describing the connections of agents in the network: the line graph and the ring graph. Our main interest is to deduce the dynamics for such propagation, and to investigate the influence of compliance of the agents and graph structure on the decision time and the final decision. The methodology is based on the use of control-U gates in quantum computing. The original state of the network is used as controller and its mirrored state is used as target. The state of the quantum walk is the tensor product of the original state and the mirror state. In this way, the proposed quantum walk model is able to describe asymmetric influence between agents.     

Quantum Walks,Weyl Equation and the Lorentz Group

Quantum cellular automata and quantum walks provide a framework for the foundations of quantum field theory, since the equations of motion of free relativistic quantum fields can be derived as the small wave-vector limit of quantum automata and walks starting from very general principles. The intrinsic discreteness of this framework is reconciled with the continuous Lorentz symmetry by reformulating the notion of inertial reference frame in terms of the constants of motion of the quantum walk dynamics. In particular, among the symmetries of the quantum walk which recovers the Weyl equation—the so called Weyl walk—one finds a non linear realisation of the Poincaré group, which recovers the usual linear representation in the small wave-vector limit. In this paper we characterise the full symmetry group of the Weyl walk which is shown to be a non linear realization of a group which is the semidirect product of the Poincaré group and the group of dilations.     

High winding number of topological phase in non-unitary periodic quantum walk

Topological phases and their associated multiple edge states are studied by constructing a one-dimensional non-unitary multi-period quantum walk with parity-time symmetry. It is shown that large topological numbers can be obtained when choosing an appropriate time frame. The maximum value of the winding number can reach the number of periods in the one-step evolution operator. The validity of the bulk–edge correspondence is confirmed, while for an odd-period quantum walk and an even-period quantum walk, they have different configurations of the 0-energy edge state and π-energy edge state. On the boundary, two kinds of edge states always coexist in equal amount for the odd-period quantum walk, however three cases including equal amount, unequal amount or even only one type may occur for the even-period quantum walk.