A classical random walker starting on a node of a finite graph will always reach any other node since the search is ergodic, namely it fully explores space, hence the arrival probability is unity. For quantum walks, destructive interference may induce effectively non-ergodic features in such search processes. Under repeated projective local measurements, made on a target state, the final detection of the system is not guaranteed since the Hilbert space is split into a bright subspace and an orthogonal dark one. Using this we find an uncertainty relation for the deviations of the detection probability from its classical counterpart, in terms of the energy fluctuations.
A classical random walker starting on a node of a finite graph will always reach any other node since the search is ergodic, namely it fully explores space, hence the arrival probability is unity. For quantum walks, destructive interference may induce effectively non-ergodic features in such search processes. Under repeated projective local measurements, made on a target state, the final detection of the system is not guaranteed since the Hilbert space is split into a bright subspace and an orthogonal dark one. Using this we find an uncertainty relation for the deviations of the detection probability from its classical counterpart, in terms of the energy fluctuations.
We investigate a generic discrete quantum system prepared in state |ψ in under repeated detection attempts, aimed to find the particle in state |d , for example, a quantum walker on a finite graph searching for a node.For the corresponding classical random walk, the total detection probability P det is unity.Due to destructive interference, one may find initial states |ψ in with P det < 1.We first obtain an uncertainty relation which yields insight on this deviation from classical behavior, showing the relation between P det and energy fluctuations: P Var[ Ĥ ] d | d|[ Ĥ, D]|ψ in | 2 , where P = P det -| ψ in |d | 2 and D = |d d| is the measurement projector.Secondly, exploiting symmetry we show that P det 1/ν, where the integer ν is the number of states equivalent to the initial state.These bounds are compared with the exact solution for small systems, obtained from an analysis of the dark and bright subspaces, showing the usefulness of the approach.The upper bound works well even in large systems, and we show how to tighten the lower bound in this case.
We consider a quantum walk where a detector repeatedly probes the system with fixed rate 1/τ until the walker is detected.This is a quantum version of the first-passage problem.We focus on the total probability P det that the particle is eventually detected in some target state, for example, on a node r d on a graph, after an arbitrary number of detection attempts.Analyzing the dark and bright states for finite graphs and more generally for systems with a discrete spectrum, we provide an explicit formula for P det in terms of the energy eigenstates which is generically τ independent.We find that disorder in the underlying Hamiltonian renders perfect detection, P det = 1, and then expose the role of symmetry with respect to suboptimal detection.Specifically, we give a simple upper bound for P det that is controlled by the number of equivalent (with respect to the detection) states in the system.We also extend our results to infinite systems, for example, the detection probability of a quantum walk on a line, which is τ dependent and less than half, well below Polya's optimal detection for a classical random walk.
We investigate a tight-binding quantum walk on a graph. Repeated stroboscopic measurements of the position of the particle yield a measured "trajectory," and a combination of classical and quantum mechanical properties for the walk are observed. We explore the effects of the measurements on the spreading of the packet on a one-dimensional line, showing that except for the Zeno limit, the system converges to Gaussian statistics similarly to a classical random walk. A large deviation analysis and an Edgeworth expansion yield quantum corrections to this normal behavior. We then explore the first passage time to a target state using a generating function method, yielding properties like the quantization of the mean first return time. In particular, we study the effects of certain sampling rates that cause remarkable changes in the behavior in the system, such as divergence of the mean detection time in finite systems and decomposition of the phase space into mutually exclusive regions, an effect that mimics ergodicity breaking, whose origin here is the destructive interference in quantum mechanics. For a quantum walk on a line, we show that in our system the first detection probability decays classically like (time)^{-3/2}. This is dramatically different compared to local measurements, which yield a decay rate of (time)^{-3}, indicating that the exponents of the first passage time depend on the type of measurements used.
A quantum walker on a graph, prepared in the state ∣ψin⟩, e.g. initially localized at node rin, is repeatedly probed, with fixed frequency 1/τ, to test its presence at some target node rd until the first successful detection. This is a quantum version of the first-passage problem. We investigate the total detection probability Pdet, i.e. the probability to eventually detect the particle after an arbitrary number of detection attempts. It is demonstrated that this total detection probability is less than unity in symmetric systems, where it is possible to find initial states which are shielded from the detector by destructive interference, so-called dark states. The identification of physically equivalent initial states yields an upper bound for Pdet in terms of the reciprocal of the number ν of physically equivalent states. The relevant subgroup of the system's symmetry operations is found to be the stabilizer of the detection state. Using this, we prove that all bright, i.e. surely detectable, states are symmetric with respect to the stabilizer. This implies that Pdet can be obtained from a diagonalization of the "symmetrized" Hamiltonian, instead of having to find all eigenstates of the Hamiltonian.
We quantitatively differentiate between the spreads of discrete-time quantum and classical random walks on a cyclic graph. Due to the closed nature of any cyclic graph, there is additional “collision”-like interference in the quantum random walk along with the usual interference in any such walk on any graph, closed or otherwise. We find that the quantum walker exhibits inhibition of spread in comparison to the classical one, even in the absence of disorder, a phenomenon that is potentially attributable to the additional interference in the quantum case. This is to be contrasted with the situation on open graphs, where the quantum walker, being effectively denied the collision-like interference, garners a much higher spread than its classical counterpart. Inhibition of spread also occurs on open graphs, but with insertion of disorder. We use the Shannon entropy of the position probability distribution to quantify the spread of the walker in both quantum and classical cases. We find that for a given number of vertices on a cyclic graph, the entropy with respect to number of steps for the quantum walker saturates, on average, to a value lower than that for the corresponding classical one. We also analyze variations of the entropies with respect to system size, and look at the corresponding asymptotic growth rates.
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.