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

Quantum Analogs of Markov Chains

Ashwin Nayak, Peter C. Richter

Published Jan 1, 2015• 1 citation
OpenAlex

Abstract

Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:

Related papers

Spatial search on Johnson graphs by discrete-time quantum walk

Hajime Tanaka, Mohamed Sabri, Renato Portugal

Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.

arXiv:2112.03744•Journal of Physics A Mathematical and Theoretical•May 12, 2022•9 citations

Quantum Searching on Markov Chains - The Complete Graph

Min-Ho Lee, Nark Nyul Choi, Gregor Tanner

We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.

Acta Physica Polonica A•Dec 1, 2021•3 citations

Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk

Simon Apers, Shantanav Chakraborty, Leonardo Novo +1 more

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

arXiv:2112.12746•Physical Review Letters•Oct 14, 2022•65 citations

Adiabatic condition and the quantum hitting time of Markov chains

Hari Krovi, Māris Ozols, Jérémie Roland

We present an adiabatic quantum algorithm for the abstract problem of searching marked vertices in a graph, or spatial search. Given a random walk (or Markov chain) $P$ on a graph with a set of unknown marked vertices, one can define a related absorbing walk ${P}^{'}$ where outgoing transitions from marked vertices are replaced by self-loops. We build a Hamiltonian $H(s)$ from the interpolated Markov chain $P(s)=(1\ensuremath{-}s)P+{\mathit{sP}}^{'}$ and use it in an adiabatic quantum algorithm to drive an initial superposition over all vertices to a superposition over marked vertices. The adiabatic condition implies that, for any reversible Markov chain and any set of marked vertices, the running time of the adiabatic algorithm is given by the square root of the classical hitting time. This algorithm therefore demonstrates a novel connection between the adiabatic condition and the classical notion of hitting time of a random walk. It also significantly extends the scope of previous quantum algorithms for this problem, which could only obtain a full quadratic speedup for state-transitive reversible Markov chains with a unique marked vertex.

arXiv:1004.2721•Physical Review A•Aug 30, 2010•27 citations

Finding a marked node on any graph via continuous-time quantum walks

Shantanav Chakraborty, Leonardo Novo, Jérémie Roland

Spatial search by a discrete-time quantum walk can find a marked node on any ergodic, reversible Markov chain $P$ quadratically faster than its classical counterpart, i.e., in a time that is in the square root of the hitting time of $P$. However, in the framework of continuous-time quantum walks, it was previously unknown whether such general speedup is possible. In fact, in this framework, the widely used quantum algorithm by Childs and Goldstone fails to achieve such a speedup. Furthermore, it is not clear how to apply this algorithm for searching any Markov chain $P$. In this article we aim to reconcile the apparent differences between the running times of spatial search algorithms in these two frameworks. We first present a modified version of the Childs and Goldstone algorithm which can search for a marked element for any ergodic, reversible $P$ by performing a quantum walk on its edges. Although this approach improves the algorithmic running time for several instances, it cannot provide a generic quadratic speedup for any $P$. Second, using the framework of interpolated Markov chains, we provide a spatial search algorithm by a continuous-time quantum walk which can find a marked node on any $P$ in the square root of the classical hitting time. In the scenario where multiple nodes are marked, the algorithmic running time scales as the square root of a quantity known as the extended hitting time. Our results establish a connection between discrete-time and continuous-time quantum walks and can be used to develop a number of Markov chain-based quantum algorithms.

arXiv:1807.05957•Physical Review A•Aug 26, 2020•26 citations

Kvanttikävelyhakuoperaattorin tutkiminen ominaisvektorien avulla.

Niklas Keckman

Quantum walks are the quantum mechanical counterpart to classical random walks. Similarly to random walks, in quantum walks a walker moves on a graph structure from one node to another governed by some stochastic process. Unlike random walks, quantum walks exhibit quantum superposition. This allows the walker to be in multiple nodes simultaneously. Due to quantum superposition quantum walks have been applied to cryptography, optimization, graph theory and spatial search problems. The goal of a spatial search problem is to find a target node from a graph structure by moving from one node to another along the edges of the graph. On certain graph structures quantum walks are able to find the target node of the search faster than classical random walks. However, determining the speedup provided by the quantum walk can be difficult to do analytically, especially when there are multiple target nodes. Therefore, it is of importance to investigate numerical approaches for approximating the dynamics of quantum walks. This Bachelor's thesis concerns a heuristic method for analyzing the dynamics of discrete-time coined quantum walk (DTCQW) search algorithms used for finding a specific node or a set of nodes on a two-dimensional lattice graph. Instead of simulating the walk fully, the heuristic method uses the eigenvectors and eigenvalues of a unitary evolution operator that governs the walk dynamics to approximate the probability of the DTCQW search algorithm finding a node that is a target of the search. This work goes over two slightly different DTCQW search algorithms. One of these is a instance of the DTCQW search algorithm that has been investigated in previous literature (referred to as the standard DTCQW search algorithm). The other one is a slightly modified version of the standard DTCQW search algorithm (referred to as the modified DTCQW search algorithm) In this work, the method was first applied to the standard DTCQW search algorithm to compare the results to previously known analytical results. The goal of this was to showcase that by using the method one can arrive at similar results as with analytical approaches. In addition, the method was used to investigate the modified DTCQW search algorithm. This was done to give numerical showing that the modified DTCQW search algorithm is able to find certain target node formations with a higher probability than the standard DTCQW search algorithm. The results of this work show that the method can approximate the analytical results using only a couple of eigenvector-eigenvalue pairs of the unitary evolution operator. Therefore, it can be considered as a cost-efficient alternative for simulating the complete quantum walk. Using the method it can be seen that the modified search algorithm finds target nodes that are adjacent to each other in the graph structure with a high probability. Additionally, the results show that the modified search algorithm only has a small chance of finding target nodes that are not adjacent to other target nodes. This gives numerical showing that the modified search algorithm behaves differently from the standard search algorithm and could therefore be used for different applications.

•Jul 1, 2026•0 citations
Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:
Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.
We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.
We present an adiabatic quantum algorithm for the abstract problem of searching marked vertices in a graph, or spatial search. Given a random walk (or Markov chain) PPP on a graph with a set of unknown marked vertices, one can define a related absorbing walk P′{P}^{'}P′ where outgoing transitions from marked vertices are replaced by self-loops. We build a Hamiltonian H(s)H(s)H(s) from the interpolated Markov chain $P(s)=(1\ensuremath{-}s)P+{\mathit{sP}}^{'}$ and use it in an adiabatic quantum algorithm to drive an initial superposition over all vertices to a superposition over marked vertices. The adiabatic condition implies that, for any reversible Markov chain and any set of marked vertices, the running time of the adiabatic algorithm is given by the square root of the classical hitting time. This algorithm therefore demonstrates a novel connection between the adiabatic condition and the classical notion of hitting time of a random walk. It also significantly extends the scope of previous quantum algorithms for this problem, which could only obtain a full quadratic speedup for state-transitive reversible Markov chains with a unique marked vertex.
Spatial search by a discrete-time quantum walk can find a marked node on any ergodic, reversible Markov chain PPP quadratically faster than its classical counterpart, i.e., in a time that is in the square root of the hitting time of PPP. However, in the framework of continuous-time quantum walks, it was previously unknown whether such general speedup is possible. In fact, in this framework, the widely used quantum algorithm by Childs and Goldstone fails to achieve such a speedup. Furthermore, it is not clear how to apply this algorithm for searching any Markov chain PPP. In this article we aim to reconcile the apparent differences between the running times of spatial search algorithms in these two frameworks. We first present a modified version of the Childs and Goldstone algorithm which can search for a marked element for any ergodic, reversible PPP by performing a quantum walk on its edges. Although this approach improves the algorithmic running time for several instances, it cannot provide a generic quadratic speedup for any PPP. Second, using the framework of interpolated Markov chains, we provide a spatial search algorithm by a continuous-time quantum walk which can find a marked node on any PPP in the square root of the classical hitting time. In the scenario where multiple nodes are marked, the algorithmic running time scales as the square root of a quantity known as the extended hitting time. Our results establish a connection between discrete-time and continuous-time quantum walks and can be used to develop a number of Markov chain-based quantum algorithms.
Quantum walks are the quantum mechanical counterpart to classical random walks. Similarly to random walks, in quantum walks a walker moves on a graph structure from one node to another governed by some stochastic process. Unlike random walks, quantum walks exhibit quantum superposition. This allows the walker to be in multiple nodes simultaneously. Due to quantum superposition quantum walks have been applied to cryptography, optimization, graph theory and spatial search problems. The goal of a spatial search problem is to find a target node from a graph structure by moving from one node to another along the edges of the graph. On certain graph structures quantum walks are able to find the target node of the search faster than classical random walks. However, determining the speedup provided by the quantum walk can be difficult to do analytically, especially when there are multiple target nodes. Therefore, it is of importance to investigate numerical approaches for approximating the dynamics of quantum walks. This Bachelor's thesis concerns a heuristic method for analyzing the dynamics of discrete-time coined quantum walk (DTCQW) search algorithms used for finding a specific node or a set of nodes on a two-dimensional lattice graph. Instead of simulating the walk fully, the heuristic method uses the eigenvectors and eigenvalues of a unitary evolution operator that governs the walk dynamics to approximate the probability of the DTCQW search algorithm finding a node that is a target of the search. This work goes over two slightly different DTCQW search algorithms. One of these is a instance of the DTCQW search algorithm that has been investigated in previous literature (referred to as the standard DTCQW search algorithm). The other one is a slightly modified version of the standard DTCQW search algorithm (referred to as the modified DTCQW search algorithm) In this work, the method was first applied to the standard DTCQW search algorithm to compare the results to previously known analytical results. The goal of this was to showcase that by using the method one can arrive at similar results as with analytical approaches. In addition, the method was used to investigate the modified DTCQW search algorithm. This was done to give numerical showing that the modified DTCQW search algorithm is able to find certain target node formations with a higher probability than the standard DTCQW search algorithm. The results of this work show that the method can approximate the analytical results using only a couple of eigenvector-eigenvalue pairs of the unitary evolution operator. Therefore, it can be considered as a cost-efficient alternative for simulating the complete quantum walk. Using the method it can be seen that the modified search algorithm finds target nodes that are adjacent to each other in the graph structure with a high probability. Additionally, the results show that the modified search algorithm only has a small chance of finding target nodes that are not adjacent to other target nodes. This gives numerical showing that the modified search algorithm behaves differently from the standard search algorithm and could therefore be used for different applications.