## Abstracts

Poster Abstracts | Talk Abstracts

### Quantum walk search on Kronecker graphs

**Presenting Author**: Thomas Wong, Creighton University**Contributing Author(s)**: Adam Glos, Konstantin Wünscher, Joshua Lockhart, Simone Severini

In network science, graphs obtained by taking the Kronecker or tensor power of the adjacency matrix of an initiator graph are used to construct complex networks. In this paper, we analytically prove sufficient conditions under which such Kronecker graphs can be searched by a continuous-time quantum walk in optimal $\Theta(\sqrt{N})$ time. First, if the initiator is regular and its adjacency matrix has a dominant principal eigenvalue, meaning its unique largest eigenvalue asymptotically dominates the other eigenvalues in magnitude, then the Kronecker graphs generated by this initiator can be quantum searched with probability $1$ in $\pi\sqrt{N}/2$ time, asymptotically, and we give the critical jumping rate of the walk that enables this. Second, for any fixed initiator that is regular, non-bipartite, and connected, the Kronecker graphs generated by it are quantum searched in $\Theta(\sqrt{N})$ time. This greatly extends the number of Kronecker graphs on which quantum walks are known to optimally search. If the fixed, regular, connected initiator is bipartite, however, then search on its Kronecker powers is not optimal, but is still better than classical computer's $O(N)$ runtime if the initiator has more than two vertices.

Read this article online: https://arxiv.org/abs/1809.01249, https://arxiv.org/abs/1804.10560

- Home
- SQuInT
- Registration
- Program
- Instructions for Presenters
- Survey
- Lodging and Transportation
- Hotel Floor Maps (.pdf)
- Faculty Favorites at Old Town
- Past SQuInT Meetings

**SQuInT Chief Organizer**

Akimasa Miyake, Associate Professor

amiyake@unm.edu

**SQuInT Local Organizers**

Rafael Alexander, Postdoctoral Fellow

Chris Jackson, Postdoctoral Fellow

**SQuInT Administrator**

Gloria Cordova

gjcordo1@unm.edu

505 277-1850

**SQuInT Assistant**

Wendy Jay

**SQuInT Founder**

Ivan Deutsch, Regents' Professor, CQuIC Director

ideutsch@unm.edu

**Tweet About SQuInT 2019!**