On the equivalence between quantum and random walks on finite graphs
- PDF / 4,479,436 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 183 Views
On the equivalence between quantum and random walks on finite graphs Matheus G. Andrade1 Daniel R. Figueiredo1
· Franklin de Lima Marquezino1
·
Received: 10 February 2020 / Accepted: 28 October 2020 / Published online: 13 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given vertex of the graph and the probability that the random walk is at that same vertex , for all vertices and time steps. The result is given by the construction procedure of a matrix sequence for the random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. Interestingly, these matrices allow for a different simulation approach for quantum walks where vertex samples respect neighbor locality, and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial) sampling of quantum graph trajectories (paths). Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case. Keywords Quantum walks · Random walks · Markov chains
B
Matheus G. Andrade [email protected] Franklin de Lima Marquezino [email protected] Daniel R. Figueiredo [email protected]
1
Department of Computer and System Engineering (PESC), Federal University of Rio de Janeiro (UFRJ), Rio de Janeiro, Brazil
123
417
Page 2 of 20
M. G. Andrade et al.
1 Introduction Quantum walks on graphs are a prominent area of research in quantum computing inspired to be the quantum analogue of classical random walks [1,2]. As with random walks, quantum walks have proven to be an insightful tool for designing quantum algorithms, culminating on efficient solutions for problems such as element distinctness [3], marked-vertex searching [16] and Hamiltonian simulation [4]. Among its marvelous capabilities, quantum walks were shown to perform universal quantum computation for both continuous- [6] and discrete-time [15] models. Extensive surveys covering multiple aspects of quantum walks can be found in the literature [11,20,29]. A few discrete-time models for quantum walks have shown increased community interest over the past years [1,22,28]. The coined model works on an extended Hilbert space which codifies both graph vertices and walker direction and has pioneered discrete-time models [
Data Loading...
