Continuous-Time Quantum Walk on Integer Lattices and Homogeneous Trees

This paper is concerned with the continuous-time quantum walk on ℤ, ℤ ^d , and infinite homogeneous trees. By using the generating function method, we compute the limit of the average probability distribution for the general isotropic walk on ℤ, and for nearest-neighbor walks on ℤ ^d and infinite homogeneous trees. In addition, we compute the asymptotic approximation for the probability of the return to zero at time t in all these cases.     

Recurrence and Pólya number of quantum walks

We analyze the recurrence probability (Pólya number) for d-dimensional unbiased quantum walks. A sufficient condition for a quantum walk to be recurrent is derived. As a by-product we find a simple criterion for localization of quantum walks. In contrast with classical walks, where the Pólya number is characteristic for the given dimension, the recurrence probability of a quantum walk depends in general on the topology of the walk, choice of the coin and the initial state. This allows us to change the character of the quantum walk from recurrent to transient by altering the initial state.     

A Limit Result for a System of Particles in Random Environment

We consider an infinite system of particles in one dimension, each particle performs independent Sinai’s random walk in random environment. Considering an instant t, large enough, we prove a result in probability showing that the particles are trapped in the neighborhood of well defined points of the lattice depending on the random environment, t and the starting points of the particles. Supported by GREFI-MEFI and Departimento di Mathematica, Universita di Roma II “Tor Vergata”, Italy.     

Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks

In the literature, there are numerous studies of one-dimensional discrete-time quantum walks (DTQWs) using a moving shift operator. However, there is no exact solution for the limiting probability distributions of DTQWs on cycles using a general coin or swapping shift operator. In this paper, we derive exact solutions for the limiting probability distribution of quantum walks using a general coin and swapping shift operator on cycles for the first time. Based on the exact solutions, we show how to generate symmetric quantum walks and determine the condition under which a symmetric quantum walk appears. Our results suggest that choosing various coin and initial state parameters can achieve a symmetric quantum walk. By defining a quantity to measure the variation of symmetry, deviation and mixing time of symmetric quantum walks are also investigated.     

One-dimensional quantum walks with a position-dependent coin

We investigate the evolution of a discrete-time one-dimensional quantum walk driven by a position-dependent coin. The rotation angle, which depends upon the position of a quantum particle, parameterizes the coin operator. For different values of the rotation angle, we observe that such a coin leads to a variety of probability distributions, e.g. localized, periodic, classicallike, semi-classical-like, and quantum-like. Further, we study the Shannon entropy associated with position and the coin space of a quantum particle, and compare them with the case of the position-independent coin. Our results show that the entropy is smaller for most values of the rotation angle as compared to the case of the position-independent coin. We also study the effect of entanglement on the behavior of probability distribution and Shannon entropy by considering a quantum walk with two identical position-dependent entangled coins. We observe that in general, a wave function becomes more localized as compared to the case of the positionindependent coin and hence the corresponding Shannon entropy is lower. Our results show that a position-dependent coin can be used as a controlling tool of quantum walks.     

Disordered quantum walks in two-dimensional lattices

The properties of the two-dimensional quantum walk with point,line,and circle disorders in phase are reported.Localization is observed in the two-dimensional quantum walk with certain phase disorder and specific initial coin states.We give an explanation of the localization behavior via the localized stationary states of the unitary operator of the walker+coin system and the overlap between the initial state of the whole system and the localized stationary states.     

Driven Tracer Particle in One Dimensional Symmetric Simple Exclusion

Consider an infinite system of particles evolving in a one dimensional lattice according to symmetric random walks with hard core interaction. We investigate the behavior of a tagged particle under the action of an external constant driving force. We prove that the diffusively rescaled position of the test particle εX(ε^-2 t), t > 0, converges in probability, as ε→ 0, to a deterministic function v(t). The function v(⋅) depends on the initial distribution of the random environment through a non-linear parabolic equation. This law of large numbers for the position of the tracer particle is deduced from the hydrodynamical limit of an inhomogeneous one dimensional symmetric zero range process with an asymmetry at the origin. An Einstein relation is satisfied asymptotically when the external force is small. Received: 5 December 1996 / Accepted: 30 June 1997     

Random Time-Dependent Quantum Walks

We consider the discrete time unitary dynamics given by a quantum walk on the lattice \mathbb Z^d{\mathbb {Z}^d} performed by a quantum particle with internal degree of freedom, called coin state, according to the following iterated rule: a unitary update of the coin state takes place, followed by a shift on the lattice, conditioned on the coin state of the particle. We study the large time behavior of the quantum mechanical probability distribution of the position observable in \mathbb Z^d{\mathbb {Z}^d} when the sequence of unitary updates is given by an i.i.d. sequence of random matrices. When averaged over the randomness, this distribution is shown to display a drift proportional to the time and its centered counterpart is shown to display a diffusive behavior with a diffusion matrix we compute. A moderate deviation principle is also proven to hold for the averaged distribution and the limit of the suitably rescaled corresponding characteristic function is shown to satisfy a diffusion equation. A generalization to unitary updates distributed according to a Markov process is also provided.     

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

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

Asymptotic properties of multistate random walks. I. Theory

A calculation is presented of the long-time behavior of various random walk properties (moments, probability of return to the origin, expected number of distinct sites visited) formultistate random walks on periodic lattices. In particular, we consider inhomogeneous periodic lattices, consisting of a periodically repeated unit cell which contains a finite number of internal states (sites). The results are identical to those for perfect lattices except for a renormalization of coefficients. For walks without drift, it is found that all the asymptotic random walk properties are determined by the diffusion coefficients for the multistate random walk. The diffusion coefficients can be obtained by a simple matrix algorithm presented here. Both discrete and continuous time random walks are considered. The results are not restricted to nearest-neighbor random walks but apply as long as the single-step probability distributions associated with each of the internal states have finite means and variances.     

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.     

Relativistic quantum coin tossing

A relativistic quantum exchange protocol enabling “coin tossing at a distance” between two participants is proposed. The exchange protocol is based on the fact that to distinguish a pair of orthogonal states with certainty in relativistic quantum mechanics requires a finite time that depends on the structure of the states themselves. Pis’ma Zh. éksp. Teor. Fiz. 70, No. 10, 684–689 (25 November 1999)     

Density and uniqueness in percolation

Two results on site percolation on thed-dimensional lattice,d1 arbitrary, are presented. In the first theorem, we show that for stationary underlying probability measures, each infinite cluster has a well-defined density with probability one. The second theorem states that if in addition, the probability measure satisfies the finite energy condition of Newman and Schulman, then there can be at most one infinite cluster with probability one. The simple arguments extend to a broad class of finite-dimensional models, including bond percolation and regular lattices.     

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.     

One-dimensional lazy quantum walks and occupancy rate

In this paper, we discuss the properties of lazy quantum walks. Our analysis shows that the lazy quantum walks have O(t n) order of the n-th moment of the corresponding probability distribution, which is the same as that for normal quantum walks. The lazy quantum walk with a discrete Fourier transform(DFT) coin operator has a similar probability distribution concentrated interval to that of the normal Hadamard quantum walk. Most importantly, we introduce the concepts of occupancy number and occupancy rate to measure the extent to which the walk has a(relatively) high probability at every position in its range. We conclude that the lazy quantum walks have a higher occupancy rate than other walks such as normal quantum walks, classical walks, and lazy classical walks.     

One-Dimensional Three-State Quantum Walk with Single-Point Phase Defects

In this paper, we study a three-state quantum walk with a phase defect at a designated position. The coin operator is a parametrization of the eigenvectors of the Grover matrix. We numerically investigate the properties of the proposed model via the position probability distribution, the position standard deviation, and the time-averaged probability at the designated position. It is shown that the localization effect can be governed by the phase defect’s position and strength, coin parameter and initial state.     

Spectral Properties of Quantum Walks on Rooted Binary Trees

We define coined quantum walks on the infinite rooted binary tree given by unitary operators $U(C)$ on an associated infinite dimensional Hilbert space, depending on a unitary coin matrix $C\in U(3)$ , and study their spectral properties. For circulant unitary coin matrices $C$ , we derive an equation for the Carathéodory function associated to the spectral measure of a cyclic vector for $U(C)$ . This allows us to show that for all circulant unitary coin matrices, the spectrum of the quantum walk has no singular continuous component. Furthermore, for coin matrices $C$ which are orthogonal circulant matrices, we show that the spectrum of the Quantum Walk is absolutely continuous, except for four coin matrices for which the spectrum of $U(C)$ is pure point.     

Calculation of the Fermi surface with complex topology from norm-conserving cluster perturbation theory for doping dependent electronic structure of the Hubbard model

The results of recently developed norm-conserving cluster perturbation theory for doping dependent electronic structure of the Hubbard model are reported. We have found that the momentum distribution of the spectral weight strongly depends on the broadening value δ. At δ = 0.1t, we reproduce the angle-resolved photoemission spectroscopy data, while at δ = 0.01t we obtain two quantum phase transitions.     

Quantum to classical transition for random walks

We look at two possible routes to classical behavior for the discrete quantum random walk on the integers: decoherence in the quantum "coin" which drives the walk, or the use of higher-dimensional (or multiple) coins to dilute the effects of interference. We use the position variance as an indicator of classical behavior and find analytical expressions for this in the long-time limit; we see that the multicoin walk retains the "quantum" quadratic growth of the variance except in the limit of a new coin for every step, while the walk with decoherence exhibits "classical" linear growth of the variance even for weak decoherence.