Quantum search by continuous-time quantum walk on t-designs

Abstract

This work examines the time complexity of quantum search algorithms on combinatorial $t$-designs with multiple marked elements using the continuous-time quantum walk. Through a detailed exploration of $t$-designs and their incidence matrices, we identify a subset of bipartite graphs that are conducive to success compared to random-walk-based search algorithms. These graphs have adjacency matrices with eigenvalues and eigenvectors that can be determined algebraically and are also suitable for analysis in the multiple-marked vertex scenario. We show that the continuous-time quantum walk on certain symmetric $t$-designs achieves an optimal running time of $O(\sqrt{n})$, where $n$ is the number of points and blocks, even when accounting for an arbitrary number of marked elements. Upon examining two primary configurations of marked elements distributions, we observe that the success probability is consistently $o(1)$, but it approaches 1 asymptotically in certain scenarios.

arXiv comment15 pages

References in corpus (15)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Scalable Noise Estimation with Random Unitary Operators
• Connectivity is a Poor Indicator of Fast Quantum Search
• Quadratic speedup for spatial search by continuous-time quantum walk
• Combinatorial optimisation via highly efficient quantum walks
• On the optimality of spatial search by continuous-time quantum walk
• Continuous-Time Quantum Search on Balanced Trees
• Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
• Quantum walk-based search algorithms with multiple marked vertices
• Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
• Walking on Vertices and Edges by Continuous-Time Quantum Walk

Cited by in corpus (1)

• Multimarked Spatial Search by Continuous-Time Quantum Walk