Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (π/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube.
The mixing time of a discrete-time quantum walk on the hypercube is considered. The mean probability distribution of a Markov chain on a hypercube is known to mix to a uniform distribution in time
O(n log n). We show that the mean probability distribution of a discrete-time quantum walk on a hypercube mixes to a (generally nonuniform) distribution $\ensuremath{\pi}(x)$ in time
O(n), and the stationary distribution is determined by the initial state of the walk. An explicit expression for $\ensuremath{\pi}(x)$ is derived for the particular case of a symmetric walk. These results are consistent with those obtained previously for a continuous-time quantum walk. The effect of decoherence due to randomly breaking links between connected sites in the hypercube is also considered. We find that the probability distribution mixes to the uniform distribution as expected. However, the mixing time has a minimum at a critical decoherence rate $p\ensuremath{\approx}0.1$. A similar effect was previously reported for a quantum walk on an
N-cycle with decoherence from repeated measurements of position. A controlled amount of decoherence helps in obtaining---and preserving---a uniform distribution over the
2n sites of the hypercube in the shortest possible time.
We present a study of the effects of decoherence in the operation of a discrete quantum walk on a line, cycle, and hypercube. We find high sensitivity to decoherence, increasing with the number of steps in the walk, as the particle is becoming more delocalized with each step. However, the effect of a small amount of decoherence is to enhance the properties of the quantum walk that are desirable for the development of quantum algorithms. Specifically, we observe a highly uniform distribution on the line, a very fast mixing time on the cycle, and more reliable hitting times across the hypercube.
We present a study of the effects of decoherence in the operation of a discrete quantum walk on a line, cycle and hypercube. We find high sensitivity to decoherence, increasing with the number of steps in the walk, as the particle is becoming more delocalised with each step. However, the effect of a small amount of decoherence is to enhance the properties of the quantum walk that are desirable for the development of quantum algorithms. Specifically, we observe a highly uniform distribution on the line, a very fast mixing time on the cycle, and more reliable hitting times across the hypercube.
We study the one-shot and concurrent hitting for the discrete-time Grover-coined quantum walk on cubelike graphs
G=Cay(Z2d,Ω) of degree
Δ=∣Ω∣. Starting from the vertex labeled
0, we identify
σ=⨁ω∈Ωω as a natural target vertex; for the hypercube,
σ is precisely the antipodal vertex.
For families with
Δ→∞, let
T be an integer having the same parity as
Δ and satisfying $ \left|T-\frac{πΔ}{2}\right|\leq 1. $ We show that the probability
pT(σ) of finding the walker at
σ when it is measured at time
T satisfies
pT(σ)=1−O(Δ−1/5). Thus the target is found with probability tending to one after
Θ(Δ) steps.
For the concurrently measured walk, let
HTConc(σ) denote the probability that the target is detected at or before time
T when it is tested after every step. We prove
pT(σ)≤THTConc(σ), which implies
HTConc(σ)=Ω(Δ−1) over the same time scale.
The proof uses the Walsh-Fourier decomposition, an exact two-dimensional reduction of each Fourier mode, and a universal second-moment identity for the associated character sums. Our results extend Kempe's hypercube hitting phenomenon (J. Kempe, Probab. Theory Relat. Fields 133, 215-235, 2005) to arbitrary cubelike generating sets and establish the conjectured asymptotic hitting behavior for cublelike and augmented cubes in Mulherkar, Rajdeepak and Sunitha (Int. J. Quantum Inf. 20,2250020, 2022)
In this paper, we present a quantum Bernoulli noises approach to quantum walks on hypercubes. We first obtain an alternative description of a general hypercube, and then, based on the alternative description, we find that the operators ∂k*+∂k behave actually as the shift operators, where ∂k and ∂k* are the annihilation and creation operators acting on Bernoulli functionals, respectively. With the above-mentioned operators as the shift operators on the position space, we introduce a discrete-time quantum walk model on a general hypercube and obtain an explicit formula for calculating its probability distribution at any time. We also establish two limit theorems showing that the averaged probability distribution of the walk even converges to the uniform probability distribution. Finally, we show that the walk produces the uniform measure as its stationary measure on the hypercube provided its initial state satisfies some mild conditions. Some other results are also proven.