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

arXiv:quant-ph/0109076 · Physical Review A

Implementing the quantum random walk

B. C. Travaglione, Gerard J Milburn

Published Feb 20, 2002• 295 citations
arXivHTMLPDF

Abstract

Recently, several groups have investigated quantum analogues of random walk algorithms, both on a line and on a circle. It has been found that the quantum versions have markedly different features to the classical versions. Namely, the variance on the line, and the mixing time on the circle increase quadratically faster in the quantum versions as compared to the classical versions. Here, we propose a scheme to implement the quantum random walk on a line and on a circle in an ion trap quantum computer. With current ion trap technology, the number of steps that could be experimentally implemented will be relatively small. However, we show how the enhanced features of these walks could be observed experimentally. In the limit of strong decoherence, the quantum random walk tends to the classical random walk. By measuring the degree to which the walk remains ``quantum,'' this algorithm could serve as an important benchmarking protocol for ion trap quantum computers.

DOI
10.1103/physreva.65.032310

Related papers

Implement Quantum Random Walks with Linear Optics Elements

Zhi Zhao, Jiangfeng Du, Hui Li +3 more

The quantum random walk has drawn special interests because its remarkable features to the classical counterpart could lead to new quantum algorithms. In this paper, we propose a feasible scheme to implement quantum random walks on a line using only linear optics elements. With current single-photon interference technology, the steps that could be experimentally implemented can be extended to very large numbers. We also show that, by decohering the quantum states, our scheme for quantum random walk tends to be classical.

arXiv:quant-ph/0212149•Dec 29, 2002•6 citations

Experimental implementation of a continuous-time quantum random walk on a solid-state quantum information processor*

Maimaitiyiming Tusun, Yang Wu, Wenquan Liu +2 more

There are some problems that quantum computers seem to be exponentially faster than classical computers, like factoring large numbers, machine learning, and simulation of quantum systems. Constructing an appropriate quantum algorithm becomes more important for solving these specific problems. In principle, any quantum algorithm can recast by a quantum random walk algorithm. Although quantum random walk with a few qubits has been implemented in a variety of systems, the experimental demonstration of solid-state quantum random walk remains elusive. Here we report the experimental implementation of the quantum continuous-time random walk algorithm by a two-qubit quantum processor in a nitrogen–vacancy center in diamond. We found that quantum random walk on a circle does not converge to any stationary distribution and exhibit a reversible property. Our results represent a further investigation of quantum walking dynamics in solid spin platforms, may also lead to other practical applications by the use of quantum continuous-time random walk for quantum algorithm design and quantum coherence transport.

Chinese Physics B•Sep 18, 2019•1 citation

Quantum Walk on the Line

Nayak Ashwin, Ashvin Vishwanath

Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider {\em quantum\/} walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''''. In particular, we show that after~$t$ time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval~$[-t/\sqrt{2},\;t/\sqrt{2}]$. This implies that the same walk defined on the circle mixes in {\em linear\/} time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.

•Dec 13, 2000•122 citations

A random walk approach to quantum algorithms

Viv M. Kendon

The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.

arXiv:quant-ph/0609035•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 18, 2006•116 citations

Quantum Walk on the Line

Ashwin Nayak, Ashvin Vishwanath

Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.

arXiv:quant-ph/0010117•Oct 31, 2000•14 citations

Scalable networks for discrete quantum random walks

Shingo Fujiwara, H. Osaki, I. M. Buluta +1 more

Recently, quantum random walks (QRWs) have been thoroughly studied in order to develop new quantum algorithms. In this paper we propose scalable quantum networks for discrete QRWs on circles, lines, and also in higher dimensions. In our method the information about the position of the walker is stored in a quantum register and the network consists of only one-qubit rotation and ${(\text{controlled})}^{n}\text{\ensuremath{-}}\mathrm{NOT}$ gates, therefore it is purely computational and independent of the physical implementation. As an example, we describe the experimental realization in an ion-trap system.

Physical Review A•Sep 23, 2005•14 citations
Recently, several groups have investigated quantum analogues of random walk algorithms, both on a line and on a circle. It has been found that the quantum versions have markedly different features to the classical versions. Namely, the variance on the line, and the mixing time on the circle increase quadratically faster in the quantum versions as compared to the classical versions. Here, we propose a scheme to implement the quantum random walk on a line and on a circle in an ion trap quantum computer. With current ion trap technology, the number of steps that could be experimentally implemented will be relatively small. However, we show how the enhanced features of these walks could be observed experimentally. In the limit of strong decoherence, the quantum random walk tends to the classical random walk. By measuring the degree to which the walk remains ``quantum,'' this algorithm could serve as an important benchmarking protocol for ion trap quantum computers.
The quantum random walk has drawn special interests because its remarkable features to the classical counterpart could lead to new quantum algorithms. In this paper, we propose a feasible scheme to implement quantum random walks on a line using only linear optics elements. With current single-photon interference technology, the steps that could be experimentally implemented can be extended to very large numbers. We also show that, by decohering the quantum states, our scheme for quantum random walk tends to be classical.
There are some problems that quantum computers seem to be exponentially faster than classical computers, like factoring large numbers, machine learning, and simulation of quantum systems. Constructing an appropriate quantum algorithm becomes more important for solving these specific problems. In principle, any quantum algorithm can recast by a quantum random walk algorithm. Although quantum random walk with a few qubits has been implemented in a variety of systems, the experimental demonstration of solid-state quantum random walk remains elusive. Here we report the experimental implementation of the quantum continuous-time random walk algorithm by a two-qubit quantum processor in a nitrogen–vacancy center in diamond. We found that quantum random walk on a circle does not converge to any stationary distribution and exhibit a reversible property. Our results represent a further investigation of quantum walking dynamics in solid spin platforms, may also lead to other practical applications by the use of quantum continuous-time random walk for quantum algorithm design and quantum coherence transport.
Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider {\em quantum\/} walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''''. In particular, we show that after~ttt time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval~[−t/2,  t/2][-t/\sqrt{2},\;t/\sqrt{2}][−t/2​,t/2​]. This implies that the same walk defined on the circle mixes in {\em linear\/} time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.
The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.
Recently, quantum random walks (QRWs) have been thoroughly studied in order to develop new quantum algorithms. In this paper we propose scalable quantum networks for discrete QRWs on circles, lines, and also in higher dimensions. In our method the information about the position of the walker is stored in a quantum register and the network consists of only one-qubit rotation and ${(\text{controlled})}^{n}\text{\ensuremath{-}}\mathrm{NOT}$ gates, therefore it is purely computational and independent of the physical implementation. As an example, we describe the experimental realization in an ion-trap system.