Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases

Abstract

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.

arXiv commentpublished version, 13 pages, 8 figures

References in corpus (8)

• Quantum random walks - an introductory overview
• Exponential algorithmic speedup by quantum walk
• Hitting time for quantum walks on the hypercube
• Quantum walks with infinite hitting times
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Hitting time for the continuous quantum walk
• Quantum Walks
• Quantum walks on embedded hypercubes

Cited by in corpus (3)

• Predicting quantum advantage by quantum walk with convolutional neural networks
• Many-body quantum interference on hypercubes
• GPU-accelerated algorithms for many-particle continuous-time quantum walks