We develop a generic method for quantizing classical algorithms based on random walks. We show that under certain conditions, the quantum version gives rise to a quadratic speed-up. This is the case, in particular, when the Markov chain is ergodic and its transition matrix is symmetric. This generalizes the celebrated result of L. K. Grover (1996)and a number of more recent results, including the element distinctness result of Ambainis and the result of Ambainis, Kempe and Rivosh that computes properties of quantum walks on the d-dimensional torus. Among the consequences is a faster search for multiple marked items. We show that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted.
We develop a generic method for quantizing classical algorithms based on random walks. We show that under certain conditions, the quantum version gives rise to a quadratic speed-up. This is the case, in particular, when the Markov chain is ergodic and its transition matrix is symmetric. This generalizes the celebrated result of L. K. Grover (1996)and a number of more recent results, including the element distinctness result of Ambainis and the result of Ambainis, Kempe and Rivosh that computes properties of quantum walks on the d-dimensional torus. Among the consequences is a faster search for multiple marked items. We show that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted.
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.
Spectra of Quantized Walks and a δε rule
We introduce quantized bipartite walks, compute their spectra, generalize the algorithms of Grover \cite{g} and Ambainis \cite{amb03} and interpret them as quantum walks with memory. We compare the performance of walk based classical and quantum algorithms and show that the latter run much quicker in general. Let P be a symmetric Markov chain with transition probabilities P[i,j], (i,j∈[n]). Some elements of the state space are marked. We are promised that the set of marked elements has size either zero or at least εn. The goal is to find out with great certainty which of the above two cases holds. Our model is a black box that can answer certain yes/no questions and can generate random elements picked from certain distributions. More specifically, by request the black box can give us a uniformly distributed random element for the cost of ℘0. Also, when ``inserting'' an element i into the black box we can obtain a random element j, where j is distributed according to P[i,j]. The cost of the latter operation is ℘1. Finally, we can use the black box to test if an element i is marked, and this costs us ℘2. If δ is the eigenvalue gap of P, there is a simple classical algorithm with cost O(℘0+(℘1+℘2)/δε) that solves the above promise problem. (The algorithm is efficient if ℘0 is much larger than ℘1+℘2.) In contrast,we show that for the ``quantized'' version of the algorithm it costs only O(℘0+(℘1+℘2)/δε) to solve the problem. We refer to this as the δε rule. Among the technical contributions we give a formula for the spectrum of the product of two general reflections.
We propose a new method for designing quantum search algorithms for finding a “marked” element in the state space of a classical Markov chain. The algorithm is based on a quantum walk à la Szegedy [Quantum speed-up of Markov chain based algorithms, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 32–41] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis [Quantum walk algorithm for Element Distinctness, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 22–31] and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.
We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D=P∘PT its discriminant matrix (D=P if P is symmetric), we construct a quantum walk algorithm that for any quantum state ∣v⟩ and integer t returns a quantum state ε-close to the state Dt∣v⟩/∥Dt∣v⟩∥. The algorithm uses O(∥Dt∣v⟩∥−1tlog(ε∥Dt∣v⟩∥)−1) expected quantum walk steps and O(∥Dt∣v⟩∥−1) expected reflections around ∣v⟩. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = \sqrt{P\circ P^T} its discriminant matrix (D=P if P is symmetric), we construct a quantum walk algorithm that for any quantum state |v> and integer t returns a quantum state \epsilon-close to the state D^t|v>/\|D^t|v>. The algorithm uses O(|D^t|v>|^{-1}\sqrt{t\log(\epsilon\|D^t|v>})^{-1}}) expected quantum walk steps and O(\|D^t|v>|^{-1}) expected reflections around |v>. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
Quantum walks are the quantum analogues of classical random walks or Markov chains. They are universal models of quantum computing, and they underpin a variety of quantum algorithms. We prove that a continuous-time quantum walk effected by a generalized Laplacian, which can arise in spin chains, can solve a computational problem more quickly than typical quantum walks governed by the standard Laplacian or adjacency matrix. This generalized Laplacian consists of the standard Laplacian plus a real-valued multiple of the degree matrix, and we prove that as the magnitude of the multiple of the degree matrix is increased, its corresponding quantum walk can search the complete bipartite graph with multiple marked vertices in time that approaches the optimal. This raises the potential for the generalized Laplacian quantum walk to be a useful method for developing additional faster quantum algorithms.