Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

A systems approach to the quantum random walk

Peter J. Sherman, Ian Fuss, Lang White, Sanjeev Naguleswaran

Published Jun 7, 2007• 0 citations
Publisher

Abstract

In this paper we address the quantum random walk on the real line. Specifically, we utilize a dynamical system formulation of the walk, which leads to a momentum space expression of the probability amplitude that is a function of only the initial condition. Our focus is, for the most part, limited to the Hadamard walk. As such, this closed form expression is not as general as that given by [1]. This lack of generality is offset by the ease with which we obtain the expression, and the insight offered by it. Our closed form expression allows us to easily compute the walk pdf, hence the cdf (cumulative distribution function). It is shown that the cdf converges to its limiting form relatively quickly. We push the simple mathematics in an to attempt to obtain a closed form expression for this form. But it becomes too involved to take it to completion in this paper, without running the risk of losing appreciation for the simplicity of our approach.

DOI
10.1117/12.731359

Related papers

Quantum Random Walk via Classical Random Walk With Internal States

Robert Main Burton, Yevgeniy Kovchegov, Thinh P. Nguyen

In recent years quantum random walks have garnered much interest among quantum information researchers. Part of the reason is the prospect that many hard problems can be solved efficiently by employing algorithms based on quantum random walks, in the same way that classical random walks have played a central role in many hugely successful randomized algorithms. In this paper we introduce a new representation for the quantum random walks via the classical random walk with internal states. This new representation allows for a systematic approach to finding closed form expressions for the n-step distributions for a variety of quantum random walk models, and lends itself naturally to large deviation analysis. As an example, we show how to use the new representation to arrive at the same closed form expression for the Hadamard quantum random walk on a line, previously obtained by others. We assert the proposed method works in the most general settings.

•Apr 26, 2010•3 citations

Quantum Walks on the Line with Phase Parameters

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita +1 more

In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.

arXiv:1109.1866•IEICE Transactions on Information and Systems•Jan 1, 2012•5 citations

A path integral formula with applications to quantum random walks inZd

Wei-Shih Yang, Chaobin Liu, Kai Zhang

We consider general quantum random walks in a d -dimensional half-space. We first obtain a path integral formula for general quantum random walks in a d -dimensional space. Our path integral formula is valid for general quantum random walks on Cayley graphs as well. Then the path integral formula is applied to obtain the scaling limit of the exit distribution, the expectation of exit time and the asymptotic behaviour of the exit probabilities, for general quantum random walks in a half-space under some conditions on amplitude functions. The conditions are shown to be satisfied by both the Hadamard and Grover quantum random walks in two-dimensional half-spaces. For the two-dimensional case, we show that the critical exponent for the scaling limit of the hitting distribution is 1 as the lattice spacing tends to zero, i.e. the natural magnitude of the hitting position is of order O (1) if the lattice spacing is set to be 1/ n . We also show that the rate of convergence of the total hitting probability has lower bound n −2 and upper bound n −2+ for any > 0. For a quantum random walk with a fixed starting point, we show that the probability of hitting times at the hyperplane decays faster than that of the classical random walk. In both one and two dimensions, given the event of a hit, the conditional expectation of hitting times is finite, in contrast to being infinite for the classical case. In the one-dimensional case, we also obtain an exact order of the probability distribution of the hitting time at 0.

Journal of Physics A Mathematical and Theoretical•Jul 3, 2007•12 citations

Limiting distribution of decoherent quantum random walks

Kai Zhang

The behavior of one-dimensional quantum random walks is strikingly different from that of classical ones. However, when decoherence is involved, the limiting distributions take on many classical features over time. In this paper, we study the decoherence on both position and ``coin'' spaces of the particle. We propose an analytical approach to investigate these phenomena and obtain the generating functions which encode all the features of these walks. Specifically, from these generating functions, we find exact analytic expressions of several moments for the time and noise dependence of position. Moreover, the limiting position distributions of decoherent quantum random walks are shown to be Gaussian in an analytical manner. These results explicitly describe the relationship between the system and the level of decoherence.

arXiv:0804.4311•Physical Review A•Jun 2, 2008•22 citations

Analytic views of quantum walks

Ian Fuss, Lang White, Peter J. Sherman +1 more

The first general analytic solutions for the one-dimensional quantum walk in position and momentum space are derived. These solutions reveal new symmetry features of quantum walk probability densities and insight into the behaviour of their moments. The analytic expressions for the quantum walk probability distributions provide a means of modelling quantum phenomena that is analogous to that provided by random walks in the classical domain.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jun 7, 2007•0 citations

An analytic solution for one-dimensional quantum walks

Ian Fuss, Lang White, Peter J. Sherman +1 more

The first general analytic solutions for the one-dimensional walk in position and momentum space are derived. These solutions reveal, among other things, new symmetry features of quantum walk probability densities and further insight into the behaviour of their moments. The analytic expressions for the quantum walk probability distributions provide a means of modelling quantum phenomena that is analogous to that provided by random walks in the classical domain.

arXiv:0705.0077•May 1, 2007•3 citations
In this paper we address the quantum random walk on the real line. Specifically, we utilize a dynamical system formulation of the walk, which leads to a momentum space expression of the probability amplitude that is a function of only the initial condition. Our focus is, for the most part, limited to the Hadamard walk. As such, this closed form expression is not as general as that given by [1]. This lack of generality is offset by the ease with which we obtain the expression, and the insight offered by it. Our closed form expression allows us to easily compute the walk pdf, hence the cdf (cumulative distribution function). It is shown that the cdf converges to its limiting form relatively quickly. We push the simple mathematics in an to attempt to obtain a closed form expression for this form. But it becomes too involved to take it to completion in this paper, without running the risk of losing appreciation for the simplicity of our approach.
In recent years quantum random walks have garnered much interest among quantum information researchers. Part of the reason is the prospect that many hard problems can be solved efficiently by employing algorithms based on quantum random walks, in the same way that classical random walks have played a central role in many hugely successful randomized algorithms. In this paper we introduce a new representation for the quantum random walks via the classical random walk with internal states. This new representation allows for a systematic approach to finding closed form expressions for the n-step distributions for a variety of quantum random walk models, and lends itself naturally to large deviation analysis. As an example, we show how to use the new representation to arrive at the same closed form expression for the Hadamard quantum random walk on a line, previously obtained by others. We assert the proposed method works in the most general settings.
In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.
We consider general quantum random walks in a d -dimensional half-space. We first obtain a path integral formula for general quantum random walks in a d -dimensional space. Our path integral formula is valid for general quantum random walks on Cayley graphs as well. Then the path integral formula is applied to obtain the scaling limit of the exit distribution, the expectation of exit time and the asymptotic behaviour of the exit probabilities, for general quantum random walks in a half-space under some conditions on amplitude functions. The conditions are shown to be satisfied by both the Hadamard and Grover quantum random walks in two-dimensional half-spaces. For the two-dimensional case, we show that the critical exponent for the scaling limit of the hitting distribution is 1 as the lattice spacing tends to zero, i.e. the natural magnitude of the hitting position is of order O (1) if the lattice spacing is set to be 1/ n . We also show that the rate of convergence of the total hitting probability has lower bound n −2 and upper bound n −2+ for any > 0. For a quantum random walk with a fixed starting point, we show that the probability of hitting times at the hyperplane decays faster than that of the classical random walk. In both one and two dimensions, given the event of a hit, the conditional expectation of hitting times is finite, in contrast to being infinite for the classical case. In the one-dimensional case, we also obtain an exact order of the probability distribution of the hitting time at 0.
The behavior of one-dimensional quantum random walks is strikingly different from that of classical ones. However, when decoherence is involved, the limiting distributions take on many classical features over time. In this paper, we study the decoherence on both position and ``coin'' spaces of the particle. We propose an analytical approach to investigate these phenomena and obtain the generating functions which encode all the features of these walks. Specifically, from these generating functions, we find exact analytic expressions of several moments for the time and noise dependence of position. Moreover, the limiting position distributions of decoherent quantum random walks are shown to be Gaussian in an analytical manner. These results explicitly describe the relationship between the system and the level of decoherence.