Exceptional quantum walk search on the cycle

Quantum walks are standard tools for searching graphs for marked vertices, and they often yield quadratic speedups over a classical random walk’s hitting time. In some exceptional cases, however, the system only evolves by sign flips, staying in a uniform probability distribution for all time. We prove that the one-dimensional periodic lattice or cycle with any arrangement of marked vertices is such an exceptional configuration. Using this discovery, we construct a search problem where the quantum walk’s random sampling yields an arbitrary speedup in query complexity over the classical random walk’s hitting time. In this context, however, the mixing time to prepare the initial uniform state is a more suitable comparison than the hitting time, and then, the speedup is roughly quadratic.     

Quantum random walk polynomial and quantum random walk measure

In the paper, we introduce a quantum random walk polynomial (QRWP) that can be defined as a polynomial $\{P_{n}(x)\}$ , which is orthogonal with respect to a quantum random walk measure (QRWM) on $[-1, 1]$ , such that the parameters $\alpha _{n},\omega _{n}$ are in the recurrence relations $$\begin{aligned} P_{n+1}(x)= (x - \alpha _{n})P_{n}(x) - \omega _{n}P_{n-1}(x) \end{aligned}$$ and satisfy $\alpha _{n}\in \mathfrak {R},\omega _{n}> 0$ . We firstly obtain some results of QRWP and QRWM, in which case the correspondence between measures and orthogonal polynomial sequences is one-to-one. It shows that any measure with respect to which a quantum random walk polynomial sequence is orthogonal is a quantum random walk measure. We next collect some properties of QRWM; moreover, we extend Karlin and McGregor’s representation formula for the transition probabilities of a quantum random walk (QRW) in the interacting Fock space, which is a parallel result with the CGMV method. Using these findings, we finally obtain some applications for QRWM, which are of interest in the study of quantum random walk, highlighting the role played by QRWP and QRWM.     

The discrete-time quaternionic quantum walk on a graph

Recently, the quaternionic quantum walk was formulated by the first author as a generalization of discrete-time quantum walks. We deal with the right eigenvalue problem of quaternionic matrices in order to study spectra of the transition matrix of a quaternionic quantum walk. The way to obtain all the right eigenvalues of a quaternionic matrix is given. From the unitary condition on the transition matrix of a quaternionic quantum walk, we deduce some remarkable properties of it. Our main results determine all the right eigenvalues of the quaternionic quantum walk by using those of the corresponding weighted matrix. In addition, we give some examples of quaternionic quantum walks and their right eigenvalues.     

Faster search by lackadaisical quantum walk

In the typical model, a discrete-time coined quantum walk searching the 2D grid for a marked vertex achieves a success probability of \(O(1/\log N)\) in \(O(\sqrt{N \log N})\) steps, which with amplitude amplification yields an overall runtime of \(O(\sqrt{N} \log N)\). We show that making the quantum walk lackadaisical or lazy by adding a self-loop of weight 4 / N to each vertex speeds up the search, causing the success probability to reach a constant near 1 in \(O(\sqrt{N \log N})\) steps, thus yielding an \(O(\sqrt{\log N})\) improvement over the typical, loopless algorithm. This improved runtime matches the best known quantum algorithms for this search problem. Our results are based on numerical simulations since the algorithm is not an instance of the abstract search algorithm.     

基于连续时间量子游走的链路预测方法研究*

链路预测是复杂网络研究的基础问题之一。目前研究者们已经提出了许多链路预测的方法,其中大量的链路预测方法是基于经典随机游走。量子游走是经典随机游走的量子模拟。大量研究表明,在诸如图匹配、搜索等很多领域,基于量子游走的量子算法的性能远优于其对应的经典随机游走算法。但目前关于基于量子游走的链路预测算法几乎没有研究报道。本文提出了一种基于连续时间量子游走的链路预测方法。实验结果表明,连续时间量子游走链路预测结果的AUC值和经典随机游走的结果非常接近。而在Precision和Recall指标上,远优于经典随机游走的链路预测结果。     

Claw finding algorithms using quantum walk

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f$f$ and g$g$, with domain sizes N$N$ and M$M$(N≤M)$(N\le M)$, respectively, and the same range, the goal of the problem is to find x$x$ and y$y$ such that f(x)=g(y)$f\left(x\right)=g\left(y\right)$. This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of k$k$ functions for any constant integer k>1$k>1$, where the domain sizes of the functions may be different.     

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.     

Localization of an inhomogeneous discrete-time quantum walk on the line

We investigate a space-inhomogeneous discrete-time quantum walk in one dimension. We show that the walk exhibits localization by a path counting method.     

Two-dimensional quantum walk with position-dependent phase defects

We demonstrate localization effect in a two-dimensional quantum walk architecture. With position-dependent phase defects, the symmetry of standard quantum walk is broken; the walker is trapped in a fixed position dynamically. We show how the factors such as the phase defect, initial state and coin flipping affect on the localization effect in the quantum walk architecture.     

开放量子行走的击中时分析

作为量子搜索算法研究的一个基本工具,量子行走是一个重要研究课题。同时,击中时是衡量量子行走到达某一目标顶点速度的标准,对量子算法研究具有广泛的应用。在开放量子环境下,给出开放量子行走的四种击中时定义：单次击中时、并行击中时、平均击中时和极限击中时。区分四种击中时,说明前两种用于刻画开放量子行走局部到达目标顶点,而后两种从全局和极限角度分析目标顶点到达情况。针对同质开放量子行走、异质开放量子行走和嵌套开放量子行走,分别给出四种击中时具体计算。     

Quantum walk in terms of quantum Bernoulli noises

Quantum Bernoulli noises are the family of annihilation and creation operators acting on Bernoulli functionals, which satisfy a canonical anti-commutation relation in equal time. In this paper, we first present some new results concerning quantum Bernoulli noises, which themselves are interesting. Then, based on these new results, we construct a time-dependent quantum walk with infinitely many degrees of freedom. We prove that the walk has a unitary representation and hence belongs to the category of the so-called unitary quantum walks. We examine its distribution property at the vacuum initial state and some other initial states and find that it has the same limit distribution as the classical random walk, which contrasts sharply with the case of the usual quantum walks with finite degrees of freedom.     

On probability polynomials of 1D quantum walk

We investigate a set of polynomials arising from one dimensional quantum walk with a single-parameter coin operator. In the process, explicit hypergeometric function expressions for these polynomials are presented. An explicit expression is also given for a limit probability for the special case of Hadamard walk.     

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.     

Unitary equivalent classes of one-dimensional quantum walks

This study investigates unitary equivalent classes of one-dimensional quantum walks. We prove that one-dimensional quantum walks are unitary equivalent to quantum walks of Ambainis type and that translation-invariant one-dimensional quantum walks are Szegedy walks. We also present a necessary and sufficient condition for a one-dimensional quantum walk to be a Szegedy walk.     

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.     

Spatial search using the discrete time quantum walk

We study the quantum walk search algorithm of Shenvi et al. (Phys Rev A 67:052307, 2003) on data structures of one to two spatial dimensions, on which the algorithm is thought to be less efficient than in three or more spatial dimensions. Our aim is to understand why the quantum algorithm is dimension dependent whereas the best classical algorithm is not, and to show in more detail how the efficiency of the quantum algorithm varies with spatial dimension or accessibility of the data. Our numerical results agree with the expected scaling in 2D of O(?{N logN})O(\sqrt{N \log N}), and show how the prefactors display significant dependence on both the degree and symmetry of the graph. Specifically, we see, as expected, the prefactor of the time complexity dropping as the degree (connectivity) of the structure is increased.     

Localization of a multi-dimensional quantum walk with one defect

In this paper, we introduce a multi-dimensional generalization of Kitagawa’s split-step discrete-time quantum walk, study the spectrum of its evolution operator for the case of one-defect coins, and prove localization of the walk. Using a spectral mapping theorem, we can reduce the spectral analysis of the evolution operator to that of a discrete Schrödinger operator with variable coefficients, which is analyzed using the Feshbach map.