Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases

The expected hitting time of discrete quantum walks on a hypercube (HC) is numerically known to be exponentially shorter than that of their classical analogs in terms of the scaling with the HC dimension. Recent numerical analyses illustrated that this scaling exists not only on the bare HC, but also when the HC graph is symmetrically and locally embedded into larger graphs. The present work investigates the necessity of symmetry and locality for the speed-up by considering embeddings that are nonsymmetric or nonlocal. We provide numerical evidence that the exponential speed-up survives also in these cases. Furthermore, our numerical simulations demonstrate that removing a single edge from the HC also does not destroy the exponential speed-up. In the nonlocal embedding of the HC we encounter dark states, which we analyze. We provide a general and detailed presentation of the mapping that reduces the exponentially large Hilbert space of the quantum walk to an effective subspace of polynomial scaling. This mapping is our essential tool to numerically study quantum walks in such high-dimensional structures.
Comment: published version, 13 pages, 8 figures