Efficient quantum circuits for Szegedy quantum walks
arXiv:1609.00173 · doi:10.1016/j.aop.2017.04.006
Abstract
A major advantage in using Szegedy's formalism over discrete-time and continuous-time quantum walks lies in its ability to define a unitary quantum walk on directed and weighted graphs. In this paper, we present a general scheme to construct efficient quantum circuits for Szegedy quantum walks that correspond to classical Markov chains possessing transformational symmetry in the columns of the transition matrix. In particular, the transformational symmetry criteria do not necessarily depend on the sparsity of the transition matrix, so this scheme can be applied to non-sparse Markov chains. Two classes of Markov chains that are amenable to this construction are cyclic permutations and complete bipartite graphs, for which we provide explicit efficient quantum circuit implementations. We also prove that our scheme can be applied to Markov chains formed by a tensor product. We also briefly discuss the implementation of Markov chains based on weighted interdependent networks. In addition, we apply this scheme to construct efficient quantum circuits simulating the Szegedy walks used in the quantum Pagerank algorithm for some classes of non-trivial graphs, providing a necessary tool for experimental demonstration of the quantum Pagerank algorithm.
References in corpus (5)
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Creating superpositions that correspond to efficiently integrable probability distributions
- Classical approach to the graph isomorphism problem using quantum walks
- Efficient Quantum Walk on a Quantum Processor
Cited by in corpus (18)
- Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
- Quantum walk-based portfolio optimisation
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- FABLE: Fast Approximate Quantum Circuits for Block-Encodings
- Experimental parity-time symmetry quantum walks on a directed graph
- Generalized Quantum PageRank Algorithm with Arbitrary Phase Rotations
- Probability distributions for Markov chains based quantum walks
- Estimating Gibbs partition function with quantumClifford sampling
- Discrete-time Semiclassical Szegedy Quantum Walks
- SQUWALS: A Szegedy QUantum WALks Simulator
- Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs
- Implementation of Continuous-Time Quantum Walk on Sparse Graph
- Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
- Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption
- Quantum Algorithm for Testing Graph Completeness
- Complex-Phase Extensions of Szegedy Quantum Walk on Graphs
- Low Rank Approximation in Simulations of Quantum Algorithms
- Quantum Speedup for Nonreversible Markov Chains