Quantum Random Walks Hit Exponentially Faster

Abstract

We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum random walks. We provide the framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We then give an application to random routing.

15 pages, no Figures

References in corpus (2)

• Strengths and Weaknesses of Quantum Computing
• Quantum Computation and Decision Trees

Cited by in corpus (50)

• Quantum algorithms: an overview
• Exponential algorithmic speedup by quantum walk
• Universal quantum computation using the discrete time quantum walk
• Quantum Walks driven by many coins
• Distance-regular graphs
• Quantum random walks with decoherent coins
• Hitting time for quantum walks on the hypercube
• Quantum walks can find a marked element on any graph
• The Hidden Subgroup Problem - Review and Open Problems
• Almost uniform sampling via quantum walks
• Coined quantum walks on percolation graphs
• Asymptotic behavior of quantum walks with spatio-temporal coin fluctuations
• Analysis of Absorbing Times of Quantum Walks
• Mixing Times in Quantum Walks on the Hypercube
• Asymptotic entanglement in a two-dimensional quantum walk
• Decoherence in Discrete Quantum Walks
• Decoherence in a quantum walk on the line
• Group Velocity of Discrete-Time Quantum Walks
• Quantum walk algorithm for element distinctness
• The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
• The QWalk Simulator of Quantum Walks
• Quantum walks on embedded hypercubes
• Quantum walk transport properties on graphene structures
• Decoherence in quantum walks and quantum computers
• A note on graphs resistant to quantum uniform mixing
• An Effective Hamiltonian Approach to Quantum Random Walk
• Concentric Network Symmetry
• Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles
• One-dimensional quantum walks with absorbing boundaries
• Efficient tests for equivalence of hidden Markov processes and quantum random walks
• Improved Upper Bounds for the Hitting Times of Quantum Walks
• Quantum walks and their algorithmic applications
• Bounds for mixing time of quantum walks on finite graphs
• Mixing in Continuous Quantum Walks on Graphs
• Symmetry of distribution for the one-dimensional Hadamard walk
• Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
• Optimizing the walk coin in the quantum random walk search algorithm through machine learning
• Limit theorems and absorption problems for quantum random walks in one dimension
• Where to quantum walk
• Analytical expression for variance of homogeneous-position quantum walk with decoherent position
• Symmetry in quantum walks
• Discrete-Time Quantum Walks and Graph Structures
• Quantum walk in symmetric Cayley graph over ${\mathbb{Z}}_2^n$
• High robustness quantum walk search algorithm with qudit Householder traversing coin, machine learning study
• Implementation of hitting times of discrete time quantum random walks on Cubelike graphs
• Quantum Algorithms and Covering Spaces
• Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory
• Investigation of continuous-time quantum walks via spectral analysis and Laplace transform
• Sequential and asynchronous processes driven by stochastic or quantum grammars and their application to genomics: a survey
• Quantum Complexity Bounds for Independent Set Problems