Strong dispersion property for the quantum walk on the hypercube

We show that the discrete time quantum walk on the Boolean hypercube of dimension n has a strong dispersion property: if the walk is started in one vertex, then the probability of the walker being at any particular vertex after O ( n ) steps is of an order O ( 1.4818 − n ) . This improves over the k...

Full description

Saved in:
Bibliographic Details
Published in:Journal of physics. A, Mathematical and theoretical Mathematical and theoretical, 2022-12, Vol.55 (49), p.495301
Main Authors: Kokainis, M, Prūsis, K, Vihrovs, J, Kashcheyevs, V, Ambainis, A
Format: Article
Language:English
Subjects:
Boolean hypercube
dispersiveness
quantum walk
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the discrete time quantum walk on the Boolean hypercube of dimension n has a strong dispersion property: if the walk is started in one vertex, then the probability of the walker being at any particular vertex after O ( n ) steps is of an order O ( 1.4818 − n ) . This improves over the known mixing results for this quantum walk which show that the probability distribution after O ( n ) steps is close to uniform but do not show that the probability is small for every vertex. Our result shows that quantum walk on hypercube is interesting for algorithmic applications which require fast dispersion over the state space.
ISSN:1751-8113
1751-8121
DOI:10.1088/1751-8121/aca6b9