Implementation of hitting times of discrete time quantum random walks on Cubelike graphs
arXiv:2108.13769
Abstract
We demonstrate an implementation of the hitting time of a discrete time quantum random walk on cubelike graphs using IBM's Qiskit platform. Our implementation is based on efficient circuits for the Grover and Shift operators. We verify the results about the one-shot hitting time of quantum walks on a hypercube as proved in [https://link.springer.com/article/10.1007/s00440-004-0423-2]. We extend the study to another family of cubelike graphs called the augmented cubes [https://onlinelibrary.wiley.com/doi/abs/10.1002/net.10033]. Based on our numerical study, we conjecture that for all families of cubelike graphs there is a linear relationship between the degree of a cubelike graph and its hitting time which holds asymptotically. That is, for any cubelike graph of degree , the probability of finding the quantum random walk at the target node at time approaches 1 as the degree of the cubelike graph approaches infinity.
References in corpus (11)
- Quantum Computation and Decision Trees
- Universal computation by quantum walk
- Universal quantum computation using the discrete time quantum walk
- Quantum Random Walks Hit Exponentially Faster
- Quantum Networks on Cubelike Graphs
- Quantum walk on a line for a trapped ion
- Perfect state transfer in cubelike graphs
- Optical Cavity Implementations of the Quantum Walk
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- A Comparison of Quantum Walk Implementations on NISQ Computers
- Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs