Linear extrapolation for the graph of function of single variable based on walks

The quantum walk was introduced as a quantum counterpart of the random walk and has been intensively studied since around 2000. Its applications include topological insulators, radioactive waste reduction, and quantum search. The first author in 2019 defined a time-series model based on the measure of the ``discrete-time" and ``discrete-space" quantum walk in one dimension. Inspired by his model, this paper proposes a new model for the graph of a function of a single variable determined by the measure which comes from the weak limit measure of a ``continuous-time or discrete-time" and ``discrete-space" walk. The measure corresponds to a ``continuous-time" and ``continuous-space" walk in one dimension. Moreover, we also presents a method of a linear extrapolation for the graph by our model.The quantum walk was introduced as a quantum counterpart of the random walk and has been intensively studied since around 2000. Its applications include topological insulators, radioactive waste reduction, and quantum search. The first author in 2019 defined a time-series model based on the measure of the ``discrete-time" and ``discrete-space" quantum walk in one dimension. Inspired by his model, this paper proposes a new model for the graph of a function of a single variable determined by the measure which comes from the weak limit measure of a ``continuous-time or discrete-time" and ``discrete-space" walk. The measure corresponds to a ``continuous-time" and ``continuous-space" walk in one dimension. Moreover, we also presents a method of a linear extrapolation for the graph by our model.

arXiv:2501.13386Jan 23, 20250 citations

Continuous limit of discrete quantum walks

M N Dheeraj, Todd A. Brun

Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$ -regular, $d$ -colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$ , but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on $d$-regular, $d$-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time $O(\sqrt{N}logN)$, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the $O(\sqrt{N}logN)$ scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).

arXiv:1501.06950Physical Review AJun 5, 201517 citations

Quantum walks based on an interferometric analogy

Mark S. Hillery, János A. Bergou, Edgar Feldman

There are presently two models for quantum walks on graphs. The ``coined'' walk uses discrete-time steps, and contains, besides the particle making the walk, a second quantum system, the coin, that determines the direction in which the particle will move. The continuous walk operates with continuous time. Here a third model for quantum walks is proposed, which is based on an analogy to optical interferometers. It is a discrete-time model, and the unitary operator that advances the walk one step depends only on the local structure of the graph on which the walk is taking place. This type of walk also allows us to introduce elements, such as phase shifters, that have no counterpart in classical random walks. Several examples are discussed.There are presently two models for quantum walks on graphs. The ``coined'' walk uses discrete-time steps, and contains, besides the particle making the walk, a second quantum system, the coin, that determines the direction in which the particle will move. The continuous walk operates with continuous time. Here a third model for quantum walks is proposed, which is based on an analogy to optical interferometers. It is a discrete-time model, and the unitary operator that advances the walk one step depends only on the local structure of the graph on which the walk is taking place. This type of walk also allows us to introduce elements, such as phase shifters, that have no counterpart in classical random walks. Several examples are discussed.

arXiv:quant-ph/0302161Physical Review ASep 26, 200392 citations

Quantum Walks: Theory, Application, and Implementation

Albert T. Schmitz

The quantum walk is a method for conceptualizing and designing quantum computing algorithms and it comes in two forms: the continuous-time and discrete-time quantum walk. The thesis is organized into three parts, each of which looks to develop the concept and uses of the quantum walk. The ﬁrst part is the theory of the quantum walk. This includes deﬁnitions and considerations for the various incarnations of the discrete-time quantum walk and a discussion on the general method for connecting the continuous-time and discrete-time versions. As a result, it is shown that most versions of the discrete-time quantum walk can be put into a general form and this can be used to simulate any continuous-time quantum walk. The second part uses these results for a hypothetical application. The application presented is a search algorithm that appears to scale in the time for completion independent of the size of the search space. This behavior is then elaborated upon and shown to have general qualitative agreement with simulations to within the approximations that are made. The third part introduces a method of implementation. Given a universal quantum computer, the method is discussed and shown to simulate an arbitrary discrete-time quantum walk. Some of the beneﬁts of this method are that half the unitary evolution can be achieved without the use of any gates and there may be some possibility for error detection. The three parts combined suggest a possible experiment, given a quantum computing scheme of suﬃcient robustness.The quantum walk is a method for conceptualizing and designing quantum computing algorithms and it comes in two forms: the continuous-time and discrete-time quantum walk. The thesis is organized into three parts, each of which looks to develop the concept and uses of the quantum walk. The ﬁrst part is the theory of the quantum walk. This includes deﬁnitions and considerations for the various incarnations of the discrete-time quantum walk and a discussion on the general method for connecting the continuous-time and discrete-time versions. As a result, it is shown that most versions of the discrete-time quantum walk can be put into a general form and this can be used to simulate any continuous-time quantum walk. The second part uses these results for a hypothetical application. The application presented is a search algorithm that appears to scale in the time for completion independent of the size of the search space. This behavior is then elaborated upon and shown to have general qualitative agreement with simulations to within the approximations that are made. The third part introduces a method of implementation. Given a universal quantum computer, the method is discussed and shown to simulate an arbitrary discrete-time quantum walk. Some of the beneﬁts of this method are that half the unitary evolution can be achieved without the use of any gates and there may be some possibility for error detection. The three parts combined suggest a possible experiment, given a quantum computing scheme of suﬃcient robustness.

Jan 1, 20161 citation

QUANTUM RANDOM WALK ON FRACTALS

Kai Zhao

Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.

Jan 1, 20180 citations

Link prediction using discrete-time quantum walk

Qian, Jing, Lintao Yang, Zetai Yu +1 more

Original scientific paperLink prediction is one of the key issues of complex networks, which attracts much research interest currently.Many link prediction methods have been proposed so far.The classical random walk as an effective tool has been widely used to study the link prediction problems.Quantum walk is the quantum analogue of classical random walk.Numerous research results show that quantum algorithms using quantum walk outperform their classical counterparts in many applications, such as graph matching and searching.But there have been few studies of the link prediction based on quantum walk, especially on discrete-time quantum walk.This paper proposes a new link prediction method based on discrete-time quantum walk.Experiment results show that prediction accuracy of our method is better than the typical methods.The time complexity of our method running on classical computers, compared with the methods based on classical random walk, is slightly higher.But our method can be greatly accelerated by executing on quantum computers.Original scientific paperLink prediction is one of the key issues of complex networks, which attracts much research interest currently.Many link prediction methods have been proposed so far.The classical random walk as an effective tool has been widely used to study the link prediction problems.Quantum walk is the quantum analogue of classical random walk.Numerous research results show that quantum algorithms using quantum walk outperform their classical counterparts in many applications, such as graph matching and searching.But there have been few studies of the link prediction based on quantum walk, especially on discrete-time quantum walk.This paper proposes a new link prediction method based on discrete-time quantum walk.Experiment results show that prediction accuracy of our method is better than the typical methods.The time complexity of our method running on classical computers, compared with the methods based on classical random walk, is slightly higher.But our method can be greatly accelerated by executing on quantum computers.

Tehnicki vjesnik - Technical GazetteOct 1, 20174 citations

d

-regular,

d

-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time

O(\sqrt{N}logN)

, but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the

O(\sqrt{N}logN)

scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).