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.     

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.     

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

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

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

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

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.     

An improved guided random walk algorithm for quantum field theory computations

We introduce an improved guided random walk algorithm for evaluating vacuum matrix elements in hamiltonian field theories. This algorithm does not require the creation of absorption of walks, unlike related random walk techniques which have appeared in the literature. Applications to a scalar field theory in (1 + 1) dimensions and to an abelian gauge theory in (3 + 1) dimensions are described. The algorithm appears to be very fast; we have used it to generate independent abelian gauge field configurations on an 8³ spatial lattice at a rate of about one per IBM 3081 CPU second.     

Two-site quantum random walk

We study the measure theory of a two-site quantum random walk. The truncated decoherence functional defines a quantum measure μ _n on the space of n-paths, and the μ _n in turn induce a quantum measure μ on the cylinder sets within the space Ω of untruncated paths. Although μ cannot be extended to a continuous quantum measure on the full σ-algebra generated by the cylinder sets, an important question is whether it can be extended to sufficiently many physically relevant subsets of Ω in a systematic way. We begin an investigation of this problem by showing that μ can be extended to a quantum measure on a “quadratic algebra” of subsets of Ω that properly contains the cylinder sets. We also present a new characterization of the quantum integral on the n-path space.     

Scattering quantum random walk

Random processes are of interest not only from the theoretical point of view but also for practical use in algorithms for investigating large combinatorial structures. The theory of quantum computing requires implementation of classical algorithms using quantum-mechanical devices, and random walk is an obvious candidate. We present a model for quantum random walk that is based on an interferometric analogy, can be easily implemented, and is a generalization of a former model of quantum random walk proposed by Aharonov and colleagues.     

Asymptotic solutions of the continuous-time random walk model of diffusion

Asymptotic distributions of the Montroll-Weiss equation for the continuous-time random walk are investigated for long times. It is shown that, for a certain subclass of the hopping waiting time distributions belonging to the domain of attraction of stable distributions, these asymptotic distributions are of stable form. This indicates that the realm of applicability of the diffusion equation is limited. The Montroll-Weiss equation is rederived to include the influence of the initial waiting interval and the role of the stable distributions in physical problems is briefly discussed.     

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

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

Moments of the Montroll-Weiss continuous-time random walk for arbitrary starting time

The generalized version of the Montroll-Weiss formalism for continuous-time random walks is employed to show that some of the asymptotic results for large times appropriate to the ordinary walk become exact when the start of the observations is arbitrary.     

Two models of quantum random walk

We present an overview of two models of quantum random walk. In the first model, the discrete quantum random walk, we present the explicit solution for the recurring amplitude of the quantum random walk on a one-dimensional lattice. We also introduce a new method of solving the problem of random walk in the most general case and use it to derive the hitting amplitude for quantum random walk on the hypercube. The second is a special model based on a local interaction between neighboring spin-1/2 particles on a one-dimensional lattice. We present explicit results for the relevant quantities and obtain an upper bound on the speed of convergence to limiting probability distribution.     

A short walk through quantum optomechanics

This paper gives a brief review of the basic physics of quantum optomechanics and provides an overview of some of its recent developments and current areas of focus. It first outlines the basic theory of cavity optomechanical cooling and gives a brief status report of the experimental state‐of‐the‐art. It then turns to the deep quantum regime of operation of optomechanical oscillators and covers selected aspects of quantum state preparation, control and characterization, including mechanical squeezing and pulsed optomechanics. This is followed by a discussion of the “bottom‐up” approach that exploits ultracold atomic samples instead of nanoscale systems. It concludes with an outlook that concentrates largely on the functionalization of quantum optomechanical systems and their promise in metrology applications.     

Transport properties of the continuous-time random walk with a long-tailed waiting-time density

We derive asymptotic properties of the propagatorp(r,t) of a continuous-time random walk (CTRW) in which the waiting time density has the asymptotic form(t)T /t ⁺¹ whentT and 0<<1. Several cases are considered; the main ones are those that assume that the variance of the displacement in a single step of the walk is finite. Under this assumption we consider both random walks with and without a bias. The principal results of our analysis is that one needs two forms to characterizep(r,t), depending on whetherr is large or small, and that the small-r expansion cannot be characterized by a scaling form, although it is possible to find such a form for larger. Several results can be demonstrated that contrast with the case in which t= ₀ ()d is finite. One is that the asymptotic behavior ofp(0,t) is dominated by the waiting time at the origin rather than by the dimension. The second difference is that in the presence of a fieldp(r,t) no longer remains symmetric around a moving peak. Rather, it is shown that the peak of this probability always occurs atr=0, and the effect of the field is to break the symmetry that occurs when t. Finally, we calculate similar properties, although in not such great detail, for the case in which the single-step jump probabilities themselves have an infinite mean.     

Stability of continuous-time quantum filters with measurement imperfections

The fidelity between the state of a continuously observed quantum system and the state of its associated quantum filter, is shown to be always a submartingale. The observed system is assumed to be governed by a continuous-time Stochastic Master Equation (SME), driven simultaneously by Wiener and Poisson processes and that takes into account incompleteness and errors in measurements. This stability result is the continuous-time counterpart of a similar stability result already established for discrete-time quantum systems and where the measurement imperfections are modelled by a left stochastic matrix.     

Simulation of euclidean quantum field theories by a random walk process

A new Monte Carlo method for euclidean lattice field theory is introduced by writing the Boltzmann distribution e^?s as a solution of a diffusion type equation and constructing the associated random walk process. It is practically tested for a quantum mechanical model and a non-compact version of lattice QCD. It is explained where the main interest in this algorithm lies: the diffusion process coming from an action that can be generalized to include non-conservative forces. This possibility is exploited in our QCD version to implement gauge fixing without Faddeev-Popov ghosts.     

Some properties of a fractal-time continuous-time random walk in the presence of traps

The CTRW has often been applied to problems related to transport in a statistically homogeneous disordered medium, which means that there are no traps or reflecting boundaries to be found in the medium. Two physical applications, one to the migration of photons in a turbid medium and the second to the theory of diffusion-controlled reactions in a random medium, suggest that it might be useful to study properties of the CTRW, particularly as they refer to survival probability in the presence of a trap or a trapping surface. We calculate a number of these properties when the pausing-time density is asymptotically proportional to a stable law, i.e.,(t)T ⁺¹ as (t/T), where 0<<1. A forthcoming paper will establish the correspondence between properties of the CTRW and proprties of random walkers on a fractal with trapping boundaries.This paper is dedicated to Jerry Percus on the occasion of his 65th birthday. May he enjoy many more happy and productive years.     

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.     

Two-particle bosonic-fermionic quantum walk via integrated photonics

Quantum walk represents one of the most promising resources for the simulation of physical quantum systems, and has also emerged as an alternative to the standard circuit model for quantum computing. Here we investigate how the particle statistics, either bosonic or fermionic, influences a two-particle discrete quantum walk. Such an experiment has been realized by exploiting polarization entanglement to simulate the bunching-antibunching feature of noninteracting bosons and fermions. To this scope a novel three-dimensional geometry for the waveguide circuit is introduced, which allows accurate polarization independent behavior, maintaining remarkable control on both phase and balancement.     

Improving the efficiency of quantum hash function by dense coding of coin operators in discrete-time quantum walk

Li et al. first proposed a quantum hash function(QHF) in a quantum-walk architecture. In their scheme, two two-particle interactions, i.e., I interaction and π-phase interaction are introduced and the choice of I or π-phase interactions at each iteration depends on a message bit. In this paper, we propose an efficient QHF by dense coding of coin operators in discrete-time quantum walk. Compared with existing QHFs, our protocol has the following advantages: the efficiency of the QHF can be doubled and even more; only one particle is enough and two-particle interactions are unnecessary so that quantum resources are saved. It is a clue to apply the dense coding technique to quantum cryptographic protocols, especially to the applications with restricted quantum resources.