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/0410154 · Physical Review A

Scattering model for quantum random walks on a hypercube

Jozef Košík, Vladimír Bužek

Published Jan 4, 2005• 22 citations
arXivHTMLPDF

Abstract

Following a recent work by Hillery et al. [Phys. Rev. A 68, 032314 (2003)], we introduce a scattering model of a quantum random walk (SQRW) on a hybercube. We show that this type of quantum random walk can be reduced to the quantum random walk on the line and we derive the corresponding hitting amplitudes. We investigate the scattering properties of the hypercube, connected to the semi-infinite tails. We prove that the SQRW is a generalized version of the coined quantum random walk. We show how to implement the SQRW efficiently using a quantum circuit with standard gates. We discuss one possible version of a quantum search algorithm using the SQRW. Finally, we analyze symmetries that underlie the SQRW and may simplify its solution considerably.

DOI
10.1103/physreva.71.012306

Related papers

Scattering theory and quantum walks

Mark S. Hillery, Edgar Feldman

We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem

•Dec 8, 2003•0 citations

Two models of quantum random walk

Jozef Košík

Abstract 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.

Open Physics•Dec 1, 2003•11 citations

Quantum walks on graphs and quantum scattering theory

Edgar Feldman, Mark S. Hillery

We discuss a particular kind of quantum walk on a general graph. We affix two semi-infinite lines to a general finite graph, which we call tails. On the tails, the particle making the walk simply advances one unit at each time step, so that its behavior there is analogous to free propagation We are interested in how many steps it will take the particle, starting on one tail and propagating through the graph (where its propagation is not free), to emerge onto the other tail. The probability to make such a walk in n steps and the hitting time for such a walk can be expressed in terms of the transmission amplitude for the graph, which is one element of its S matrix. Demonstrating this necessitates a study of the analyticity properties of the transmission and reflection amplitudes of a graph. We show that the graph can have bound states that cannot be accessed by a particle entering the graph from one of its tails. Time-reversal invariance of a quantum walk is defined and used to show that the transmission amplitudes for the particle entering the graph from different directions are the same if the walk is time-reversal invariant.

arXiv:quant-ph/0403066•Contemporary mathematics - American Mathematical Society•Jan 1, 2005•38 citations

Hitting time for quantum walks on the hypercube

Hari Krovi, Todd A. Brun

Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. To be analogous to the hitting time for a classical walk, the quantum hitting time must involve repeated measurements as well as unitary evolution. We derive an expression for hitting time using superoperators, and numerically evaluate it for the discrete walk on the hypercube. The values found are compared to other analogs of hitting time suggested in earlier work. The dependence of hitting times on the type of unitary ``coin'' is examined, and we give an example of an initial state and coin which gives an infinite hitting time for a quantum walk. Such infinite hitting times require destructive interference, and are not observed classically. Finally, we look at distortions of the hypercube, and observe that a loss of symmetry in the hypercube increases the hitting time. Symmetry seems to play an important role in both dramatic speed-ups and slow-downs of quantum walks.

arXiv:quant-ph/0510136•Physical Review A•Mar 27, 2006•131 citations

Quantum walk search algorithm based on phase matching and circuit cmplementation

Hanwu Chen, Ke Li, Shengmei Zhao

As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.

Acta Physica Sinica•Jan 1, 2015•0 citations

Studying the robustness of quantum random walk search on Hypercube against phase errors in the traversing coin by semi-empirical methods

Hristo Tonchev, Petar Danev

In this work we obtain semi-empirical expressions for the probability to find solution of Quantum random walk search algorithm on hypercube when the traversing coin is constructed by generalized Householder reflection and an additional phase shift. Calculations are made for specific relations between coin phases (first from the reflection and second from the shift), that are obtained in our previous works. The quantum algorithm could be made more robust against phase errors, if an experimental implementation preserves those relations. The results from numerical simulations of quantum random walk search algorithm on hypercube are used to find an empirical formulas for algorithm’s probability to find solution. Those formulas, obtained by fitting data to a suitable function, are used to make prognosis about the algorithm’s robustness when dimension of the coin is too large to be simulated on classical computer. Here, we explicitly show all steps of the method used in the paper, while also discuss its advantages and limitations. The goal of this work is to help the experimental implementation of the quantum random walk search algorithm by giving evaluation of the algorithm’s robustness and the obtained probability to find a solution when our design of the walking coin is used.

International Conference of the Balkan Physical Union (BPU)•Oct 2, 2023•3 citations
Following a recent work by Hillery et al. [Phys. Rev. A 68, 032314 (2003)], we introduce a scattering model of a quantum random walk (SQRW) on a hybercube. We show that this type of quantum random walk can be reduced to the quantum random walk on the line and we derive the corresponding hitting amplitudes. We investigate the scattering properties of the hypercube, connected to the semi-infinite tails. We prove that the SQRW is a generalized version of the coined quantum random walk. We show how to implement the SQRW efficiently using a quantum circuit with standard gates. We discuss one possible version of a quantum search algorithm using the SQRW. Finally, we analyze symmetries that underlie the SQRW and may simplify its solution considerably.
We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem
Abstract 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.
We discuss a particular kind of quantum walk on a general graph. We affix two semi-infinite lines to a general finite graph, which we call tails. On the tails, the particle making the walk simply advances one unit at each time step, so that its behavior there is analogous to free propagation We are interested in how many steps it will take the particle, starting on one tail and propagating through the graph (where its propagation is not free), to emerge onto the other tail. The probability to make such a walk in n steps and the hitting time for such a walk can be expressed in terms of the transmission amplitude for the graph, which is one element of its S matrix. Demonstrating this necessitates a study of the analyticity properties of the transmission and reflection amplitudes of a graph. We show that the graph can have bound states that cannot be accessed by a particle entering the graph from one of its tails. Time-reversal invariance of a quantum walk is defined and used to show that the transmission amplitudes for the particle entering the graph from different directions are the same if the walk is time-reversal invariant.
Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. To be analogous to the hitting time for a classical walk, the quantum hitting time must involve repeated measurements as well as unitary evolution. We derive an expression for hitting time using superoperators, and numerically evaluate it for the discrete walk on the hypercube. The values found are compared to other analogs of hitting time suggested in earlier work. The dependence of hitting times on the type of unitary ``coin'' is examined, and we give an example of an initial state and coin which gives an infinite hitting time for a quantum walk. Such infinite hitting times require destructive interference, and are not observed classically. Finally, we look at distortions of the hypercube, and observe that a loss of symmetry in the hypercube increases the hitting time. Symmetry seems to play an important role in both dramatic speed-ups and slow-downs of quantum walks.
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.
In this work we obtain semi-empirical expressions for the probability to find solution of Quantum random walk search algorithm on hypercube when the traversing coin is constructed by generalized Householder reflection and an additional phase shift. Calculations are made for specific relations between coin phases (first from the reflection and second from the shift), that are obtained in our previous works. The quantum algorithm could be made more robust against phase errors, if an experimental implementation preserves those relations. The results from numerical simulations of quantum random walk search algorithm on hypercube are used to find an empirical formulas for algorithm’s probability to find solution. Those formulas, obtained by fitting data to a suitable function, are used to make prognosis about the algorithm’s robustness when dimension of the coin is too large to be simulated on classical computer. Here, we explicitly show all steps of the method used in the paper, while also discuss its advantages and limitations. The goal of this work is to help the experimental implementation of the quantum random walk search algorithm by giving evaluation of the algorithm’s robustness and the obtained probability to find a solution when our design of the walking coin is used.