Quantum walks on embedded hypercubes

Abstract

It has been proved by Kempe that discrete quantum walks on the hypercube (HC) hit exponentially faster than the classical analog. The same was also observed numerically by Krovi and Brun for a slightly different property, namely, the expected hitting time. Yet, to what extent this striking result survives in more general graphs, is to date an open question. Here we tackle this question by studying the expected hitting time for quantum walks on HCs that are embedded into larger symmetric structures. By performing numerical simulations of the discrete quantum walk and deriving a general expression for the classical hitting time, we observe an exponentially increasing gap between the expected classical and quantum hitting times, not only for walks on the bare HC, but also for a large family of embedded HCs. This suggests that the quantum speedup is stable with respect to such embeddings.

21 pages, 10 figures

References in corpus (11)

• Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
• Universal computation by quantum walk
• Quantum walks: a comprehensive review
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Universal computation by multi-particle quantum walk
• Google in a Quantum Network
• Quantum Random Walks Hit Exponentially Faster
• Quantum walks with infinite hitting times
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Quantum Walks, Quantum Gates and Quantum Computers

Cited by in corpus (9)

• Harnessing symmetry to control quantum transport
• Predicting quantum advantage by quantum walk with convolutional neural networks
• Quantum transport in d-dimensional lattices
• Many-body quantum interference on hypercubes
• Noisy quantum walks of two indistinguishable interacting particles
• Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
• The uniform measure for quantum walk on hypercube: a quantum Bernoulli noises approach
• The switching effect of the side chain on quantum walks on triple graphs
• Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases