Quantum walks with infinite hitting times
arXiv:quant-ph/0606094 · doi:10.1103/PhysRevA.74.042334
Abstract
Hitting times are the average time it takes a walk to reach a given final vertex from a given starting vertex. The hitting time for a classical random walk on a connected graph will always be finite. We show that, by contrast, quantum walks can have infinite hitting times for some initial states. We seek criteria to determine if a given walk on a graph will have infinite hitting times, and find a sufficient condition, which for discrete time quantum walks is that the degeneracy of the evolution operator be greater than the degree of the graph. The set of initial states which give an infinite hitting time form a subspace. The phenomenon of infinite hitting times is in general a consequence of the symmetry of the graph and its automorphism group. Using the irreducible representations of the automorphism group, we derive conditions such that quantum walks defined on this graph must have infinite hitting times for some initial states. In the case of the discrete walk, if this condition is satisfied the walk will have infinite hitting times for any choice of a coin operator, and we give a class of graphs with infinite hitting times for any choice of coin. Hitting times are not very well-defined for continuous time quantum walks, but we show that the idea of infinite hitting-time walks naturally extends to the continuous time case as well.
28 pages, 3 figures in EPS format
References in corpus (11)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- An example of the difference between quantum and classical random walks
- Quantum Walks driven by many coins
- The quantum to classical transition for random walks
- Connecting the discrete and continuous-time quantum walks
- Quantum random walks with decoherent coins
- Hitting time for quantum walks on the hypercube
- Quantum Algorithms for Element Distinctness
- Quantum walks on directed graphs
Cited by in corpus (62)
- Quantum walks: a comprehensive review
- Decoherence in quantum walks - a review
- Localization and its consequences for quantum walk algorithms and quantum communication
- A random walk approach to quantum algorithms
- Quantum walks: the first detected passage time problem
- 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
- Restart expedites quantum walk hitting times
- Decoherence vs entanglement in coined quantum walks
- Hitting time for the continuous quantum walk
- Coined quantum walks on percolation graphs
- Large fluctuations of the first detected quantum return time
- Recurrence of biased quantum walks on a line
- Quantum Renewal Equation for the first detection time of a quantum walk
- Directional correlations in quantum walks with two particles
- Group Velocity of Discrete-Time Quantum Walks
- Recurrences in three-state quantum walks on a plane
- Dark states of quantum search cause imperfect detection
- Quantum walks: the first detected transition time
- First detection probability in quantum resetting via random projective measurements
- Restart uncertainty relation for monitored quantum dynamics
- The first detection time of a quantum state under random probing
- Pólya number of continuous-time quantum walks
- Driving quantum systems with repeated conditional measurements
- Uncertainty and symmetry bounds for the quantum total detection probability
- Instability in the quantum restart problem
- Continuous Limit of Discrete Quantum Walks
- Optimal computation with non-unitary quantum walks
- Quantum walks on embedded hypercubes
- Quantum walk transport properties on graphene structures
- Quantum Markov chains: recurrence, Schur functions and splitting rules
- Quantum scattering theory on graphs with tails
- Non-Hermitian and Zeno limit of quantum systems under rapid measurements
- Randomly repeated measurements on quantum systems: Correlations and topological invariants of the quantum evolution
- The quantum walk search algorithm: Factors affecting efficiency
- Optimal Measurement Protocols in Quantum Zeno Effect
- Complete classification of trapping coins for quantum walks on the 2D square lattice
- Resonances of recurrence time of monitored quantum walks
- Uncertainty relation between detection probability and energy fluctuations
- Running Measurement Protocol for the Quantum First-detection problem
- Thermodynamic phases in first detected return times of quantum many-body systems
- Quest for optimal quantum resetting: protocols for a particle on a chain
- Role of symmetry in quantum search via continuous-time quantum walk
- Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases
- Where to quantum walk
- Accelerated first detection in discrete-time quantum walks using sharp restarts
- Interaction-induced transition in quantum many-body detection probability
- Mean hitting times of quantum Markov chains in terms of generalized inverses
- Quantized dynamics in closed quantum systems
- Mean hitting time formula for positive maps
- Survival probability of the Grover walk on the ladder graph
- Influence of coin symmetry on infinite hitting times in quantum walks
- Experimental measurement of quantum first-passage-time distributions
- Recurrence in discrete-time quantum stochastic walks
- Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice
- Quantum Hitting Time according to a given distribution
- Localized states in monitored quantum walks
- Key graph properties affecting transport efficiency of flip-flop Grover percolated quantum walks
- Optimal detection of quantum states via projective measurements
- Relation between quantum walks with tails and quantum walks with sinks on finite graphs
- Revisiting quantum walk advantages: A mean hitting time perspective