##### Department of Mathematics,

University of California San Diego

****************************

### Quantum Information and Computation Seminar

## Thomas Wong

#### University of Texas, Austin

## Challenges and Successes in Quantum Search on Graphs

##### Abstract:

Quantum computers are known to outperform classical computers in a variety of computational tasks. This includes search on various networks or databases, which can be encoded as graphs. The search is performed using a quantum walk--the quantum mechanical analogue of a random walk--and quantum walks often search quadratically faster than random walks. Despite this success, we show that certain graphs and arrangements of marked vertices cause difficulties for quantum walks, causing them to perform worse than classical random walks. On the other hand, some of these difficulties are successes in disguise, and we use them to construct greater-than-quadratic speedups for spatial search by quantum walk. This is joint work with Krisjanis Prusis, Jevgenijs Vihrovs, and Raqueline Santos in http://arxiv.org/abs/1608.00136 and http://arxiv.org/abs/1610.06075.

Host: David Meyer

### December 12, 2016

### 10:00 AM

### AP&M 6402

****************************