Quantum walk under coherence non-generating channels

We investigate the probability distribution of the quantum walk under coherence non-generating channels. We definea model called generalized classical walk with memory. Under certain conditions, generalized classical random walk withmemory can degrade into classical random walk and classical random walk with memory. Based on its various spreadingspeed, the model may be a useful tool for building algorithms. Furthermore, the model may be useful for measuring thequantumness of quantum walk. The probability distributions of quantum walks are generalized classical random walkswith memory under a class of coherence non-generating channels. Therefore, we can simulate classical random walkand classical random walk with memory by coherence non-generating channels. Also, we find that for another class ofcoherence non-generating channels, the probability distributions are influenced by the coherence in the initial state of thecoin. Nevertheless, the influence degrades as the number of steps increases. Our results could be helpful to explore therelationship between coherence and quantum walk.     

Stopping time of a one-dimensional bounded quantum walk

The stopping time of a one-dimensional bounded classical random walk(RW) is defined as the number of steps taken by a random walker to arrive at a fixed boundary for the first time.A quantum walk(QW) is a non-trivial generalization of RW,and has attracted a great deal of interest from researchers working in quantum physics and quantum information.In this paper,we develop a method to calculate the stopping time for a one-dimensional QW.Using our method,we further compare the properties of stopping time for QW and RW.We find that the mean value of the stopping time is the same for both of these problems.However,for short times,the probability for a walker performing a QW to arrive at the boundary is larger than that for a RW.This means that,although the mean stopping time of a quantum and classical walker are the same,the quantum walker has a greater probability of arriving at the boundary earlier than the classical walker.     

Directional quantum random walk induced by coherence

Quantum walk (QW), which is considered as the quantum counterpart of the classical random walk (CRW), is actually the quantum extension of CRW from the single-coin interpretation. The sequential unitary evolution engenders correlation between different steps in QW and leads to a non-binomial position distribution. In this paper, we propose an alternative quantum extension of CRW from the ensemble interpretation, named quantum random walk (QRW), where the walker has many unrelated coins, modeled as two-level systems, initially prepared in the same state. We calculate the walker's position distribution in QRW for different initial coin states with the coin operator chosen as Hadamard matrix. In one-dimensional case, the walker's position is the asymmetric binomial distribution. We further demonstrate that in QRW, coherence leads the walker to perform directional movement. For an initially decoherenced coin state, the walker's position distribution is exactly the same as that of CRW. Moreover, we study QRW in 2D lattice, where the coherence plays a more diversified role in the walker's position distribution.     

Irreversibility of a quantum walk induced by controllable decoherence employing random unitary operations

Quantum walk is different from random walk in reversibility and interference. Observation of the reduced re- versibility in a realistic quantum walk is of scientific interest in understanding the unique quantum behavior. We propose an idea to experimentally investigate the decoherence-induced irreversibility of quantum walks with trapped ions in phase space via the average fidelity decay. By introducing two controllable decoherence sources, i.e., the phase damping channel (i.e., dephasing) and the high temperature amplitude reservoir (i.e., dissipation), in the intervals between the steps of quantum walk, we find that the high temperature amplitude reservoir shows more detrimental effects than the phase damping channel on quantum walks. Our study also shows that the average fidelity decay works better than the position variance for characterizing the transition from quantum walks to random walk. Experimental feasibility to monitor the irreversibility is justified using currently available techniques.     

Quantum walks: Decoherence and coin-flipping games

We investigate the global chirality distribution of the quantum walk on the line when decoherence is introduced either through simultaneous measurements of the chirality and particle position, or as a result of broken links. The first mechanism drives the system towards a classical diffusive behavior. This is used to build new quantum games, similar to the spin-flip game. The second mechanism involves two different possibilities: (a) All the quantum walk links have the same probability of being broken. (b) Only the quantum walk links on a half-line are affected by random breakage. In case (a) the decoherence drives the system to a classical Markov process, whose master equation is equivalent to the dynamical equation of the quantum density matrix. This is not the case in (b) where the asymptotic global chirality distribution unexpectedly maintains some dependence with the initial condition. Explicit analytical equations are obtained for all cases.     

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

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

Finding tree symmetries using continuous-time quantum walk

Quantum walk, the quantum counterpart of random walk, is an important model and widely studied to develop new quantum algorithms. This paper studies the relationship between the continuous-time quantum walk and the symmetry of a graph, especially that of a tree. Firstly, we prove in mathematics that the symmetry of a graph is highly related to quantum walk. Secondly, we propose an algorithm based on the continuous-time quantum walk to compute the symmetry of a tree. Our algorithm has better time complexity O(N3) than the current best algorithm. Finally, through testing three types of 10024 trees, we find that the symmetry of a tree can be found with an extremely high efficiency with the help of the continuous-time quantum walk.     

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

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

Controllable simulation of topological phases and edge states with quantum walk

We simulate various topological phenomena in condense matter, such as formation of different topological phases, boundary and edge states, through two types of quantum walk with step-dependent coins. Particularly, we show that one-dimensional quantum walk with step-dependent coin simulates all types of topological phases in BDI family, as well as all types of boundary and edge states. In addition, we show that step-dependent coins provide the number of steps as a controlling factor over the simulations. In fact, with tuning number of steps, we can determine the occurrences of boundary, edge states and topological phases, their types and where they should be located. These two features make quantum walks versatile and highly controllable simulators of topological phases, boundary, edge states, and topological phase transitions. We also report on emergences of cell-like structures for simulated topological phenomena. Each cell contains all types of boundary (edge) states and topological phases of BDI family.     

Quantum Graphical Models and Belief Propagation

Belief Propagation algorithms acting on Graphical Models of classical probability distributions, such as Markov Networks, Factor Graphs and Bayesian Networks, are amongst the most powerful known methods for deriving probabilistic inferences amongst large numbers of random variables. This paper presents a generalization of these concepts and methods to the quantum case, based on the idea that quantum theory can be thought of as a noncommutative, operator-valued, generalization of classical probability theory. Some novel characterizations of quantum conditional independence are derived, and definitions of Quantum n-Bifactor Networks, Markov Networks, Factor Graphs and Bayesian Networks are proposed. The structure of Quantum Markov Networks is investigated and some partial characterization results are obtained, along the lines of the Hammersley–Clifford theorem. A Quantum Belief Propagation algorithm is presented and is shown to converge on 1-Bifactor Networks and Markov Networks when the underlying graph is a tree. The use of Quantum Belief Propagation as a heuristic algorithm in cases where it is not known to converge is discussed. Applications to decoding quantum error correcting codes and to the simulation of many-body quantum systems are described.     

Implementation of a one-dimensional quantum walk in both position and phase spaces

Quantum walks have been investigated as they have remarkably different features in contrast to classical random walks. We present a quantum walk in a one-dimensional architecture, consisting of two coins and a walker whose evolution is in both position and phase spaces alternately controlled by the two coins respectively. By analyzing the dynamics evolution of the walker in both the position and phase spaces, we observe an influence on the quantum walk in one space from that in the other space, which behaves like decoherence. We propose an implementation of the two-coin quantum walk in both position and phase spaces via cavity quantum electrodynamics(QED).     

二维量子随机行走及其物理实现

近年来量子随机行走相关课题因其非经典的特性,已经成为越来越多科研人员的研究热点。这篇文章中我们回顾了一维经典随机行走和一维量子随机行走模型,并且在分析两种二维经典随机行走模型的基础上,我们构建二维量子随机行走模型。通过对随机行走者的位置分布标准差的计算,我们可以证明基于这种二维量子随机行走模型的算法优于其他上述随机行走。除此之外,我们提出一个利用线性光学方法的实验方案,实现这种二维量子随机行走模型。     

Non-Markovian decoherent quantum walks

Quantum walks act in obviously different ways from their classical counterparts, but decoherence will lessen and close this gap between them. To understand this process, it is necessary to investigate the evolution of quantum walks under different decoherence situations. In this article, we study a non-Markovian decoherent quantum walk on a line. In a short time regime, the behavior of the walk deviates from both ideal quantum walks and classical random walks. The position variance as a measure of the quantum walk collapses and revives for a short time, and tends to have a linear relation with time. That is, the walker's behavior shows a diffusive spread over a long time limit, which is caused by non-Markovian dephasing affecting the quantum correlations between the quantum walker and his coin. We also study both quantum discord and measurement-induced disturbance as measures of the quantum correlations, and observe both collapse and revival in the short time regime, and the tendency to be zero in the long time limit. Therefore, quantum walks with non-Markovian decoherence tend to have diffusive spreading behavior over long time limits, while in the short time regime they oscillate between ballistic and diffusive spreading behavior, and the quantum correlation collapses and revives due to the memory effect.     

逾渗分立时间量子行走的传输及纠缠特性

在一维分立时间量子行走中,通过静态和动态两种方式随机地断开连接边引入无序效应,研究了静态逾渗和动态逾渗对量子行走传输特性以及位置自由度和硬币自由之间纠缠的影响.随着演化时间的增加,静态逾渗会使得量子行走从弹道传输转变为安德森局域化,而动态逾渗则会使之转变为经典扩散.理想情况下,量子纠缠在较短的时间内就达到一个常数值E_0.静态逾渗量子行走的纠缠减小,并随着时间做无规振荡,而动态逾渗量子行走的纠缠则会随着时间光滑地增加,并在某一时间超过理想情况下的常数值,表现出动态逾渗增强量子纠缠的特性.     

一维相位缺陷量子行走的共振传输

从分立时间量子行走理论出发, 分别在包含两个格点相位缺陷和一段格点相位缺陷(方相位势)的一维格点线上研究量子行走的静态共振传输. 利用系统独特的色散关系和边界点上的能量守恒条件, 获得量子行走通过缺陷区域的透射率, 讨论了相位缺陷的强度和宽度不同时透射率随入射动量的变化行为. 在相位缺陷强度π/2两侧, 透射率表现出不同的共振特性, 并给出了强缺陷强度下共振峰和缺陷宽度的关系.     

Laplace operator and random walk on one-dimensional nonhomogeneous lattice

A classical result of probability theory states that under suitable space and time renormalization, a random walk converges to Brownian motion. We prove an analogous result in the case of nonhomogeneous random walk on onedimensional lattice. Under suitable conditions on the nonhomogeneous medium, we prove convergence to Brownian motion and explicitly compute the diffusion coefficient. The proofs are based on the study of the spectrum of random matrices of increasing dimension.     

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

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

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

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

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.