Hitting time for quantum walks on the hypercube
arXiv:quant-ph/0510136 · doi:10.1103/PhysRevA.73.032341
Abstract
Hitting times for discrete quantum walks on graphs give an average time before the walk reaches an ending condition. To be analogous to the hitting time for a classical walk, the quantum hitting time must involve repeated measurements as well as unitary evolution. We derive an expression for hitting time using superoperators, and numerically evaluate it for the discrete walk on the hypercube. The values found are compared to other analogues of hitting time suggested in earlier work. The dependence of hitting times on the type of unitary ``coin'' is examined, and we give an example of an initial state and coin which gives an infinite hitting time for a quantum walk. Such infinite hitting times require destructive interference, and are not observed classically. Finally, we look at distortions of the hypercube, and observe that a loss of symmetry in the hypercube increases the hitting time. Symmetry seems to play an important role in both dramatic speed-ups and slow-downs of quantum walks.
8 pages in RevTeX format, four figures in EPS format
References in corpus (12)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- An example of the difference between quantum and classical random walks
- The quantum to classical transition for random walks
- Quantum Walks driven by many coins
- Quantum random walks with decoherent coins
- Quantum walks on general graphs
- Quantum Random Walks Hit Exponentially Faster
- Decoherence in Quantum Walks on the Hypercube
- Quantum Algorithms for Element Distinctness
Cited by in corpus (84)
- Quantum walks: a comprehensive review
- Quantum machine learning: a classical perspective
- Decoherence in quantum walks - a review
- Recurrence and Pólya number of quantum walks
- Quantum Machine Learning: from physics to software engineering
- Quantum Networks on Cubelike Graphs
- Quantum walks with infinite hitting times
- Quantum walks: the first detected passage time problem
- Quantum walks can find a marked element on any graph
- Quantum walks on quotient graphs
- Recurrence properties of unbiased coined quantum walks on infinite -dimensional lattices
- First detected arrival of a quantum walker on an infinite line
- Hitting time for the continuous quantum walk
- Coined quantum walks on percolation graphs
- Large fluctuations of the first detected quantum return time
- Mixing Times in Quantum Walks on the Hypercube
- Recurrence of biased quantum walks on a line
- Predicting quantum advantage by quantum walk with convolutional neural networks
- Coherent transport on Apollonian networks and continuous-time quantum walks
- Quantum Renewal Equation for the first detection time of a quantum walk
- Directional correlations in quantum walks with two particles
- Quantum transport in d-dimensional lattices
- Continuous-time quantum walks on one-dimension regular networks
- Green's function approach for quantum graphs: an overview
- Return to origin problem for particle on a one-dimensional lattice with quasi-Zeno dynamics
- Dark states of quantum search cause imperfect detection
- Group Velocity of Discrete-Time Quantum Walks
- Quantum walks: the first detected transition time
- Many-body quantum interference on hypercubes
- On the adiabatic condition and the quantum hitting time of Markov chains
- First detection probability in quantum resetting via random projective measurements
- The first detection time of a quantum state under random probing
- Driving quantum systems with repeated conditional measurements
- Coherent exciton transport and trapping on long-range interacting cycles
- Non-Markovian channel from the reduced dynamics of coin in quantum walk
- Unidirectional quantum walks: evolution and exit times
- Machine learning transfer efficiencies for noisy quantum walks
- Measurement induced quantum walks
- Uncertainty and symmetry bounds for the quantum total detection probability
- The spectral dimension controls the decay of the quantum first detection probability
- Quantum walks on embedded hypercubes
- Quantum walk transport properties on graphene structures
- Concentric Network Symmetry
- Reexamination of decoherence in quantum walks on the hypercube
- Quantum Persistence: A Random Walk Scenario
- Non-Hermitian and Zeno limit of quantum systems under rapid measurements
- Quantum scattering theory on graphs with tails
- Conditional Probability Distributions of Finite Absorbing Quantum Walks
- High-dimensional quantum state transfer in a noisy network environment
- Improved Upper Bounds for the Hitting Times of Quantum Walks
- The Lackadaisical Quantum Walker is NOT Lazy at all
- Directionally-Unbiased Unitary Optical Devices in Discrete-Time Quantum Walks
- Randomly repeated measurements on quantum systems: Correlations and topological invariants of the quantum evolution
- The quantum walk search algorithm: Factors affecting efficiency
- Symmetry and localization of quantum walk induced by extra link in cycles
- Complete classification of trapping coins for quantum walks on the 2D square lattice
- Study of Quantum Walk over a Square Lattice
- Uncertainty relation between detection probability and energy fluctuations
- Grover Walks on a Line with Absorbing Boundaries
- Coherent chemical kinetics as quantum walks II: Radical-pair reactions in Arabidopsis thaliana
- The switching effect of the side chain on quantum walks on triple graphs
- Quantum walk processes in quantum devices
- Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases
- Performance advantage of protective quantum measurements
- Where to quantum walk
- Quantized dynamics in closed quantum systems
- Hitting time for quantum walks of identical particles
- Discrete-Time Quantum Walks and Graph Structures
- Hitting statistics from quantum jumps
- Survival probability of the Grover walk on the ladder graph
- Influence of coin symmetry on infinite hitting times in quantum walks
- Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice
- Recurrence in discrete-time quantum stochastic walks
- Quantum Hitting Time according to a given distribution
- Spatial search using the discrete time quantum walk
- Absorption Probabilities of Quantum Walks
- Localized states in monitored quantum walks
- Continuous-Time Quantum Walk on Penrose Lattice
- Revisiting quantum walk advantages: A mean hitting time perspective
- Key graph properties affecting transport efficiency of flip-flop Grover percolated quantum walks
- Strong dispersion property for the quantum walk on the hypercube
- Optimal detection of quantum states via projective measurements
- Transition in Splitting Probabilities of Quantum Walks
- Relation between quantum walks with tails and quantum walks with sinks on finite graphs