Quantum-walk-based search algorithm performance on 2D lattices with bond percolation as decoherence
L. Conde Miranda Schmittgens (TU Delft - Applied Sciences)
Miriam Blaauboer – Mentor (TU Delft - QN/Blaauboer Group)
J.L.A. Dubbeldam – Mentor (TU Delft - Mathematical Physics)
S. W.H. Eijt – Graduation committee member (TU Delft - RST/Fundamental Aspects of Materials and Energy)
M. Möller – Mentor (TU Delft - Numerical Analysis)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This thesis investigates the performance of quantum walk search algorithms (QWSAs) on
two-dimensional rectangular lattices and on bond percolated two-dimensional square lat-
tices. The focus is on how structural disorder, modelled by static and dynamic percolation,
affects the success probability and optimal runtime of the algorithm. In the unpercolated
case, the principal eigenvalue technique provides asymptotic expressions for runtime and
success probability. These approximations agree well with simulations on square grids,
but underestimate the runtime for rectangular grids. This seems to be a consequence of
breaking the grid symmetry, which enhances higher-frequency spectral components and re-
sults in interference effects that delay the optimal runtime. The introduction of dynamic
percolation causes a rapid drop in success probability, especially for larger grids. This
models strong decoherence, where the short timescale of structural change disrupts coher-
ent amplitude buildup. Static percolation degrades performance more gradually, with a
sharp decline only near the percolation threshold, where global connectivity is lost. These
results show that QWSAs are adversely affected by changing graph structures over time,
highlighting the importance of sufficiently long coherence times. This study provides a
way to test how well quantum search algorithms perform in disordered environments and
future work could extend this to other types of graphs or quantum walk algorithms.