printable pdf
比利时vs摩洛哥足彩 ,
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

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