DF Kvantu datorzinātnes centrā viesosies zinātniskais asistents no Polijas Zinātņu akadēmijas 21.09.2017

Ceturtdien, 21. septembrī, plkst. 13:00 Programmēšanas katedrā notiks DF Kvantu datorzinātnes centra seminārs, kurā ar referātu "You almost surely cannot hide the vertex from quantum spatial search" uzstāsies Polijas Zinātņu akadēmijas Teorētiskās un pielietojamās informātikas institūta zinātniskais asistents Adams Glos (Adam Glos).

Abstract :

The optimality of quantum spatial search means that the vertices can be found in $\Theta(\sqrt{n})$ time on a network of size $n$. In the case of deterministic graphs (e.g. full binary trees of complete graphs), it is usually well known which vertices are analysed. The situation is more complicated for graphs chosen according to some random graph model.  Recently it was shown, by Chakraborty et al., that quantum spatial search is optimal for \emph{almost all} vertices on almost all Erd\H{o}s-R\'enyi graphs. Unfortunately, the proof permits the existence of $o(n)$ nodes, which may need much more time to be found, even in the sense of complexity.

We present some result concerning the optimality of quantum spatial search for \emph{all} vertices on almost all graphs. The results include both adjacency and Laplacian matrices analysis, including both necessary and sufficient conditions for their optimality. Furthermore, we show that under some further all vertices require the same measurement time. We also provide some further research ideas.